Wallet Data and Merkle Tree

This page explains how Secubit manages a Merkle tree of wallet metadata, how it hashes and serializes wallet data, and why the tree is kept balanced.

At a high level, the server maintains the full Merkle tree for fast queries and auditing, while the HSM stores only the Merkle root (to minimize secure storage usage) and verifies updates/proofs against that root. Every change to wallet metadata updates exactly one leaf and recomputes hashes only along its path to the root.

Merkle Node

Wallet data includes the following fields:

#![allow(unused)]
fn main() {
pub struct WalletData {
    /// Version of the wallet data format
    pub version: u8,
    /// Wallet ID
    pub id: u64,
    /// Threshold of approvers required to sign a transaction
    pub threshold: u8,
    /// Whether the wallet is custodial or non-custodial
    pub custodial: bool,
    /// List of approvers' public keys
    pub approvers: Vec<String>,
}
}

Wallet data is serialized in a canonical format (stable field order, unambiguous encoding, domain‑separated) before hashing. Each leaf Merkle node contains a wallet hash where:

wallet_hash = SHA-256( serialize(wallet_data) )

And, each parent node contains the hash of its two children concatenated as left–right:

parent_hash = SHA-256( left_child_hash || right_child_hash )

Empty leaves are represented by a fixed constant ZERO (a 32‑byte all‑zero value). In the diagrams, "0000000000" labels the zero for empty leaves.

Why only the root in the HSM? The HSM stores the Merkle root to commit to all wallets without storing the entire dataset. The server proves changes by supplying the updated leaf and its Merkle path.

Algorithm

The goal is keeping the tree balanced which means a complete binary tree that fills left‑to‑right, level‑by‑level. This yields predictable paths, minimal height, and efficient proofs.

New wallets are inserted at the leftmost available leaf position (BFS order). Conceptually:

1. Start from the current node pointer.
2. If the current node has a right sibling, move to the right sibling and try to descend left.
3. If the current node has no right sibling, move up to the parent and repeat unless the parent is root which makes root current.
4. When descending, always take the left child while it exists; when you find a node with no left child, that’s the insertion point

This ensures efficient addition (O(log N) nodes updated) while maintaining tree balance and the integrity of all remaining wallet data.

The following is the flowchart of finding the next current node (next position to add a new node).

flowchart TD
    S(("start"))
    S --> GetCurrent
    GetCurrent("get current node")
    GetCurrent --> HasFather
    HasFather{"has parent?"}

    HasFather -- no --> HasLeftChild
    
    HasFather -- yes --> HasRight
    HasRight{has right </br> sibling?}
    HasRight -- yes --> SetRightToCurrent
    SetRightToCurrent("current node := </br> right node")
    SetRightToCurrent --> HasLeftChild

    HasRight -- no --> SetParentToCurrent
    SetParentToCurrent("current node := </br> parent node")
    SetParentToCurrent --> HasFather

    HasLeftChild{has left </br> child?}
    HasLeftChild -- no --> E
    HasLeftChild -- yes --> SetLeftChildToCurrent
    SetLeftChildToCurrent("current node := </br> left child node")
    SetLeftChildToCurrent --> HasLeftChild

    E(("end"))

Initializing Merkle Tree

The diagrams show which node changes (red border) and which ancestors are recomputed (orange border).

At initialization, the tree contains only one empty leaf which is root too; therefore the root is set to zero, and the current node is set to root.

flowchart TD
    R("root hash = 0000000000 </br> (current)")
    style R stroke:red,stroke-width:2px

Adding Wallet

Adding a wallet causes growing the Merkle tree. The algorithm keeps it balanced which makes it efficient with shortest update path in parents.

Adding 1st wallet

flowchart TD
    R("root hash")
    R -- L --- Z
    R -- R --- W1

    Z("0000000000 </br> (current)")
    W1("wallet hash 1")

    style W1 stroke:red,stroke-width:2px
    style R stroke:orange,stroke-width:2px

Adding 2nd wallet

flowchart TD
    R("root hash")
    R -- L --- PL
    R -- R --- W1
    W1("wallet hash 1 </br> (current)")

    PL("parent hash - L")
    PL -- L --- Z
    PL -- R --- W2
    Z("0000000000")
    W2("wallet hash 2")

    style W2 stroke:red,stroke-width:2px
    style PL stroke:orange,stroke-width:2px
    style R stroke:orange,stroke-width:2px

Adding 5th wallet

flowchart TD
    R("root hash")
    R -- L --- PL
    R -- R --- PR

    PL("parent hash - L")
    PL -- L --- PLL
    PL -- R --- PLR

    PLL("parent hash - LL")
    PLL -- L --- Z
    PLL -- R --- W4
    Z("0000000000")
    W4("wallet hash 4")

    PLR("parent hash - LR")
    PLR -- L --- W2
    PLR -- R --- W5
    W2("wallet hash 2")
    W5("wallet hash 5")

    PR("parent hash - R")
    PR -- L --- W1
    PR -- R --- W3
    W1("wallet hash 1 </br> (current)")
    W3("wallet hash 3")

    style W5 stroke:red,stroke-width:2px
    style PLR stroke:orange,stroke-width:2px
    style PL stroke:orange,stroke-width:2px
    style R stroke:orange,stroke-width:2px

Updating Wallet

When a wallet’s metadata changes (for example, new approvers or a threshold adjustment), its leaf hash must be updated and all ancestors on the Merkle path recomputed up to the root.

For example, updating wallet 2 follows this Merkle path from root: L/R/L

To verify and update this path, the HSM needs:

• the new wallet hash computed from wallet_data_2,
• the sibling hashes along the path (here, wallet hash 5 - sibling of wallet hash 2, parent LL - sibling of LR, and parent R - sibling of L),
• and the current root hash for verification.

The HSM recomputes hashes along the path using the formula parent = SHA-256(left || right). If the recomputed root matches the stored root, the update is accepted and the new root replaces the old one.

flowchart TD
    R("root hash")
    R -- L --- PL
    R -- R --- PR

    PL("parent hash - L")
    PL -- L --- PLL
    PL -- R --- PLR

    PLL("parent hash - LL")
    PLL -- L --- Z
    PLL -- R --- W4
    Z("0000000000")
    W4("wallet hash 4")

    PLR("parent hash - LR")
    PLR -- L --- W2
    PLR -- R --- W5
    W2("wallet hash 2")
    W5("wallet hash 5")

    PR("parent hash - R")
    PR -- L --- W1
    PR -- R --- W3
    W1("wallet hash 1 </br> (current)")
    W3("wallet hash 3")

    style W2 stroke:red,stroke-width:2px
    style PLR stroke:orange,stroke-width:2px
    style PL stroke:orange,stroke-width:2px
    style R stroke:orange,stroke-width:2px

Removing Wallet

When a wallet is deleted, its leaf in the Merkle tree is replaced with a ZERO value to preserve the tree’s balanced structure. Ancestors along the path must then be recomputed up to the root. This approach avoids reshuffling other wallets and keeps indices and paths stable.

For example, removing wallet 2 follows this Merkle path from root: L/R/L

To perform the removal, the HSM needs:

• the ZERO leaf value to replace wallet_data_2,
• the sibling hashes along the path (here, wallet hash 5 - sibling of wallet hash 2, parent LL - sibling of LR, and parent R - sibling of L),
• and the current root hash for verification.

The HSM recomputes the path using parent = SHA-256(left || right). If the recomputed root matches the stored root, the update is accepted and the new root is committed.

flowchart TD
    R("root hash")
    R -- L --- PL
    R -- R --- PR

    PL("parent hash - L")
    PL -- L --- PLL
    PL -- R --- PLR

    PLL("parent hash - LL")
    PLL -- L --- Z
    PLL -- R --- W4
    Z("0000000000")
    W4("wallet hash 4")

    PLR("parent hash - LR")
    PLR -- L --- W2
    PLR -- R --- W5
    W2("0000000000")
    W5("wallet hash 5")

    PR("parent hash - R")
    PR -- L --- W1
    PR -- R --- W3
    W1("wallet hash 1 </br> (current)")
    W3("wallet hash 3")

    style W2 stroke:red,stroke-width:2px
    style PLR stroke:orange,stroke-width:2px
    style PL stroke:orange,stroke-width:2px
    style R stroke:orange,stroke-width:2px