Sparse Merkle Trees for Private DID Updates

Jun 12, 2026

Sparse Merkle Trees for Private DID Updates

Introduction

Beacon aggregation in did:btcr2 puts many DID updates into one Bitcoin transaction. This reduces the on-chain cost. Each signal of a CAS Beacon commits to a map from DIDs to update hashes. Each member of the cohort can read that map, and any party can read it if the map goes on CAS.

The SMT (Sparse Merkle Tree) Beacon shows less. Only one root goes on-chain, and no map of DIDs to updates exists. If a leaf uses the optional nonce, other parties cannot see if that DID has an update. In the spec design, this includes the Aggregation Service. Of the three beacon types in btcr2, the SMT Beacon shows the least data about updates, and it has the most complex proofs.

What a Sparse Merkle Tree Is

A Sparse Merkle Tree is a Merkle tree in which most leaves are empty. The tree has a fixed depth. In btcr2, the depth is 256 levels, one level for each bit of a SHA-256 output (did:btcr2 spec, Optimized SMT appendix). Thus, the tree has 2^256 possible leaf positions. Almost all of these positions will always be empty.

In a regular Merkle tree, you must store all leaves. In a sparse Merkle tree, an empty subtree has a known hash value for each height. A subtree in which all leaves are empty always gives the same hash at a given height. Thus, you can calculate each value one time and use it again.

The spec calls these values the cached zeros: cachedZero[0] = hash(0 + 0) and cachedZero[n] = hash(cachedZero[n-1] + cachedZero[n-1]), where 0 is 32 zero bytes. With these values, the tree is practical, although its theoretical size is very large. You store only the non-empty leaves and calculate the rest.

How the SMT Beacon Works

Leaf Position

Each DID has a fixed position in the tree. The position comes from the DID string:

position = int(SHA-256(did_string))

This formula gives each DID one 256-bit position. Two DIDs get the same position only if SHA-256 has a collision. The position does not hide the DID. The Privacy Considerations appendix of the spec says that the Aggregation Service MUST know all DIDs in the cohort (did:btcr2 spec, Privacy Considerations). The service needs the paths to build the tree and the proofs. The privacy comes from the leaf value, as the next sections show.

The spec is not consistent on this point. The Beacons section says that an SMT Beacon controller never has to show its DID to the aggregator (Beacons). The example protocol sends the index, which is the SHA-256 hash of the DID. Any party with a candidate DID can calculate that hash and compare it. This post follows the Privacy Considerations appendix.

Leaf Values

The spec defines four possible leaf values. The DID controller selects one for each index and each signal (SMT Proof Verification):

  • Nonce and update: hash(hash(nonce) + updateId). The signal announces an update, and other parties cannot see this.
  • Nonce only: hash(hash(nonce)). The signal announces no update, and other parties cannot see this.
  • Update only: updateId. The signal announces an update, and all parties can see this.
  • No nonce and no update: cachedZero[0], the value of an empty leaf. The signal announces no update, and the index is empty.

Here, updateId is the SHA-256 hash of the canonical (JCS) signed update. The nonce is an optional 256-bit value that is unique for each DID and each signal. To anchor an update in nonce mode, the controller does these steps (Aggregate Beacons):

  1. Make a new 256-bit nonce for this DID and this signal. Keep the nonce, because a verifier needs it later.
  2. Calculate the leaf value: hash(hash(nonce) + updateId)
  3. Calculate the tree index from the DID: index = int(SHA-256(did))
  4. Send the index and the leaf value to the Aggregation Service

The Aggregation Service knows the DIDs of the cohort, because it needs them to build the tree and the proof paths. In nonce mode, the leaf value does not show the content of the update. A participant with no update sends hash(hash(nonce)), and the service cannot tell this value from an update leaf. Thus, the service cannot see which positions carry an update (did:btcr2 spec, Optimized SMT appendix). Without a nonce, all parties can see if a DID has an update. If the update is on CAS, all parties can also get its content, because the leaf value is the retrieval key.

Root Computation

The Aggregation Service puts all leaf values into the SMT and calculates the Merkle root. The spec requires a leaf for each registered index (Aggregate Beacons, Step 3). This one 32-byte hash commits to the full tree state: each leaf at each position. The Beacon Signal puts the root in an OP_RETURN output, which is the last output of the transaction (Signal Bytes).

Inclusion Proofs

The Aggregation Service builds an SMT proof for each index and gives it to the controller. The controller gives the proof to verifiers (did:btcr2 spec, Optimized SMT appendix). The proof contains the sibling hashes on the path from the leaf to the root. The path has one sibling for each of the 256 levels, but the proof lists only the non-empty siblings. A 256-bit collapsed bitmap marks each level with an empty sibling, and the verifier uses the cached zero for that level. The number of listed hashes plus the number of 1 bits in collapsed must be 256 (SMT Proof).

In a tree with few leaves, most siblings are empty, so the list of hashes is short.

The verifier does these steps (SMT Proof Verification):

  1. Calculate the index from the DID. Calculate the leaf value from the nonce and updateId fields of the proof.
  2. Walk the path from the leaf to the root. At each level, use the next listed hash or the cached zero, as the collapsed bitmap shows.
  3. Make sure that the calculated root equals proof.id, and that proof.id equals the root in the Beacon Signal.
  4. Make sure that updateId equals the hash of the signed update in the sidecar data (Process SMT Beacon).

Non-Update Proofs

The SMT also lets a controller prove a non-update: the position of the DID has no update in this signal. The proof depends on the mode (SMT Proof Verification):

  • In nonce mode, the leaf value is hash(hash(nonce)). The proof gives the nonce, the collapsed bitmap, and the non-empty sibling hashes. It has no updateId.
  • In no-nonce mode, the leaf is empty, with the value cachedZero[0]. The proof has no nonce and no updateId.

In both modes, the verifier calculates the root again and compares it. Because index = int(SHA-256(did)) binds one leaf to each DID, a resolver can confirm that a signal has no update for that DID. The resolver needs a proof for each SMT signal, also for a signal with no update for the DID. If the sidecar data has no proof for a root, resolution stops with a MISSING_UPDATE_DATA error (Process SMT Beacon).

Privacy Analysis

What the Aggregation Service Learns

  • The DIDs of the cohort and their leaf positions. The service needs them to build the tree and the proofs.
  • One leaf value for each position.
  • In nonce mode, not whether a participant has an update. The per-leaf nonce makes an update leaf and a non-update leaf look the same.
  • In nonce mode, nothing about the content of an update. The controller delivers the update separately, for example as sidecar data.
  • In no-nonce mode, which DIDs have an update, and the hash of each update.

These properties describe the protocol in the spec. As of September 2026, the reference implementation (@did-btcr2/aggregation 0.7.x) works differently.

Each participant sends its full signed update to the service (aggregation docs). A participant with no update sends an explicit message that it has no update. The service then makes the nonce for each leaf (cohort.ts). Thus, in the reference implementation, the service knows which participants have an update, and it sees the content of each update. Other parties still see only the root and the proofs that they get.

What an On-Chain Observer Learns

  • One Merkle root for each beacon transaction
  • Nothing about the number of updates
  • Nothing about the positions that have leaves
  • Nothing about the DIDs or the update content
  • An observer can know a DID document that lists the beacon address. Then the observer knows that the DID can have an update in each signal. In nonce mode, the observer cannot see if it has one.

What a Verifier with a Proof Learns

  • That a specific update, or no update, is at a specific position under a specific root
  • The relation between the DID and the position. The verifier knows the DID, so it can calculate the position.
  • Which sibling subtrees on the path are empty, from the collapsed bitmap
  • In nonce mode, nothing about the content or the update status of other leaves

Comparison with the CAS Beacon

The CAS Beacon uses a Beacon Announcement Map that links each DID to its update hash. Each cohort member sees the map (Privacy Considerations). The spec expects the map on CAS, where any party with its hash can read it (CAS Announcement). A resolver can also get the map from sidecar data.

The SMT Beacon has no such map. Only the root goes on-chain. In nonce mode, the per-leaf nonce hides which cohort members have an update from the other members. In the spec design, it also hides this from the Aggregation Service, which still must know the DIDs of the cohort to build the tree. The tradeoff is more complex proof generation and verification.

Implementation Details

The reference SMT implementation of btcr2 is @did-btcr2/smt, version 0.4.1 as of September 2026. It has these parts:

  • A flat entry model: The spec-conformant beacon tree (BTCR2MerkleTree) works on a flat list of { did, nonce?, updateId? } entries, not on a hierarchy of node objects. The presence of nonce and updateId selects one of the four leaf values (leafValue). The tree puts each leaf at index = int(SHA-256(did)) (didToIndex), and it calculates the root with recursive subtree hashes (zeroHashRoot). The older BaseNode/LeafNode/ParentNode node classes belong to the superseded OptimizedSMT path. That path gives a different root that does not conform to the spec, and the package keeps it only for a transition.
  • A cache of empty-subtree hashes for each level: Empty subtrees use a precomputed CACHED_ZERO array, with one value for each tree height. The seed is 32 zero bytes (cachedZero[0] = hash(0 + 0), then cachedZero[h] = hash(cachedZero[h-1] + cachedZero[h-1])). The package also exports those 32 zero bytes as the NULL_HASH constant. A non-update leaf in nonce mode comes from the per-leaf nonce (hash(hash(nonce))), not from NULL_HASH. Proofs do not carry empty siblings: the collapsed bitmap marks the levels where the verifier uses the cached zero. A proof that lists a cached zero as a sibling hash is not valid.
  • A lifecycle with two steps: You add entries with addEntries(), and finalize() calculates the tree. reset() clears the calculated leaves and root, and keeps the entries, so you can use the structure again. There is no operation to delete one leaf.
  • Proofs: proof(did) gives a proof with the minimum set of sibling hashes that the verifier needs. For a DID that is not in the tree, it gives the proof of an empty index.

The tree depth of 256 matches the output size of SHA-256. The results are:

  • Each DID maps to one position. Two DIDs share a position only if SHA-256 has a collision.
  • The tree size does not change when new DIDs come into use.
  • The position calculation is one hash operation.

When to Use the SMT Beacon

The SMT Beacon is a good choice in these conditions:

  • The DID controller wants the Aggregation Service to learn as little as possible. In the spec design with a nonce, the service learns the DIDs of the cohort. It does not learn which controllers have an update or the update content. Make sure that the implementation that you use follows this design.
  • The controller does not want on-chain observers or other cohort members to learn about its updates.
  • The use case has sensitive identities, for example whistleblowers, dissidents, or medical credentials.

For less sensitive use cases, the CAS Beacon gives similar cost savings with simpler proofs. For single, infrequent updates, the Singleton Beacon is simpler: it needs no cohort and no Aggregation Service. For the MuSig2 signatures and the message flow of a cohort, see MuSig2 and DID Aggregation.

Conclusion

Of the did:btcr2 beacon types, the SMT Beacon shows the least update data to other parties, and it has the most complex proof system. On-chain observers see only one root. In nonce mode, the per-leaf nonce hides the update status and the update content from other parties. In the spec design, this includes the Aggregation Service.

The 256-bit tree gives each DID one position, with the collision resistance of SHA-256. The proofs let a verifier check one DID with no data about the updates of other cohort members. Use the SMT Beacon when the privacy of updates is a firm requirement, and make sure that your implementation keeps the nonce with the controller.

Jintek LLC