COSE Receipts for MMRs

4.1. inclusion_proof_path

inclusion_proof_path(i, c) is used to produce the verification paths for inclusion proofs and consistency proofs.¶

Given:¶

• c the index of the last node in any tree which contains i.¶

• i the index of the mmr node whose verification path is required.¶

And the methods:¶

• index_height (Section 9.1) which obtains the zero-based height g of any node.¶

And the constraints:¶

• i <= c¶

We define inclusion_proof_path as¶

  def inclusion_proof_path(i, c):

    path = []

    g = index_height(i)

    while True:

      # The sibling of i is at i +/- 2^(g+1)
      siblingoffset = (2 << g)

      # If the index after i is higher, it is the left parent,
      # and i is the right sibling
      if index_height(i+1) > g:

        # The witness to the right sibling is offset behind i
        isibling = i - siblingoffset + 1

        # The parent of a right sibling is stored immediately
        # after
        i += 1
      else:

        # The witness to a left sibling is offset ahead of i
        isibling = i + siblingoffset - 1

        # The parent of a left sibling is stored immediately after
        # its right sibling
        i += siblingoffset

      # When the computed sibling exceeds the range of MMR(C+1),
      # we have completed the path
      if isibling > c:
          return path

      path.append(isibling)

      # Set g to the height of the next item in the path.
      g += 1

5.1. Verifying the Receipt of inclusion

A receipt of inclusion proves that a value is a node of the tree. When the inclusion-path is not empty, the path also binds the index because each step hashes the position of the parent; when it is empty, see Tree size of a receipt of inclusion (Section 11.1).¶

Whether a node is a leaf, and what its entry commits to, are properties of the leaf commitment scheme, which this profile leaves to the application; see Leaf commitment scheme (Section 11.2).¶

Perform the following, in order. Verification fails if any step fails.¶

1. Decode the protected header. It MUST be deterministically encoded as required in COSE Receipt of Consistency (Section 7); vds MUST be TBD_1. Labels the verifier does not recognise are skipped.¶

2. Apply included_root (Section 5.2) to the index, the value and the inclusion-path. The result is the peak the path implies.¶

3. Set the COSE Sign1 payload to the bytes of that peak and verify the signature of the COSE Sign1.¶

It is recommended that implementations return a single boolean result for Receipt verification operations, to reduce the chance of accepting a valid signature over an invalid inclusion proof.¶

A verifier that holds a trusted tree size and accumulator can additionally check that the proven node is the accumulator peak for the index at that size, which fixes the length of the inclusion path and binds the index when the path is empty.¶

5.2. included_root

The algorithm included_root calculates the accumulator peak for the provided proof and node value.¶

Given:¶

• i is the index the nodeHash is to be shown at¶

• nodehash the value whose inclusion is to be shown¶

• proof is the path of sibling values committing i.¶

And the methods:¶

• index_height (Section 9.1) which obtains the zero-based height g of any node.¶

• hash_pospair64 (Section 8.2.1) which applies H to the new node position and its children.¶

We define included_root as¶

  def included_root(i, nodehash, proof):

    root = nodehash

    g = index_height(i)

    for sibling in proof:

      # If the index after i is higher, it is the left parent,
      # and i is the right sibling

      if index_height(i + 1) > g:

        # The parent of a right sibling is stored immediately after

        i = i + 1

        # Set `root` to `H(i+1 || sibling || root)`
        root = hash_pospair64(i + 1, sibling, root)
      else:

        # The parent of a left sibling is stored immediately after
        # its right sibling.

        i = i + (2 << g)

        # Set `root` to `H(i+1 || root || sibling)`
        root = hash_pospair64(i + 1, root, sibling)

      # Set g to the height of the next item in the path.
      g = g + 1

    # If the path length was zero, the original nodehash is returned
    return root

6.1. consistency_proof_paths

Produces the verification paths for inclusion of the peaks of tree-size-1 under the peaks of tree-size-2.¶

right-peaks are the node values of the peaks of tree-size-2 that no consistency path leads to, in descending height order.¶

Given:¶

• ifrom is the last index of tree-size-1¶

• ito is the last index of tree-size-2¶

And the methods:¶

• inclusion_proof_path (Section 4.1)¶

• Section 9.2¶

And the constraints:¶

• ifrom <= ito¶

We define consistency_proof_paths as¶

  def consistency_proof_paths(ifrom, ito):

    proof = []

    for i in peaks(ifrom):
      proof.append(inclusion_proof_path(i, ito))

    return proof

7.1. Verifying the Receipt of consistency

Verification accommodates verifying the result of a cumulative series of consistency proofs.¶

The verifier MUST hold, from a source it already trusts, the tree size and the accumulator of the state it is verifying consistency from; these are referred to below as the trusted tree size and the trusted accumulator. The empty tree, with tree size 0 and an empty accumulator, is a valid trusted state; see The empty tree as trusted state (Section 11.4) for what verification from it establishes.¶

Trusted state advances only forwards. Step 3 below rejects a receipt whose first consistency-proof starts from any size other than the trusted size, including a receipt that starts from the empty tree once a later state is held. A verifier MAY nevertheless choose to accept such a receipt, for example after a ledger has re-issued receipts under new credentials following a key compromise ([RFC9943], Section 9.4.2), but it MUST do so as a new verification from a trusted state at the size the receipt declares, discarding the state it previously held, and MUST NOT treat the receipt as a continuation of that state.¶

Perform the following, in order. Verification fails if any step fails.¶

1. Decode the protected header. It MUST be deterministically encoded as required in COSE Receipt of Consistency (Section 7); vds MUST be TBD_1; tree-size-2 MUST be present and MUST be an unsigned integer. Labels the verifier does not recognise are skipped.¶

2. The protected tree-size-2 MUST equal tree-size-2 of the last consistency-proof.¶

3. tree-size-1 of the first consistency-proof MUST equal the trusted tree size.¶

4. Initialize sizefrom to the trusted tree size and accumulatorfrom to the trusted accumulator.¶

5. For each consistency-proof, in order:¶

   1. tree-size-1 of the proof MUST equal sizefrom.¶

   2. Apply consistent_roots (Section 7.1.1) to sizefrom, tree-size-2 of the proof, accumulatorfrom and the consistency-paths of the proof, obtaining roots and nright.¶

   3. The length of right-peaks MUST equal nright.¶

   4. Set accumulatorfrom to roots followed by right-peaks, and sizefrom to tree-size-2 of the proof.¶

6. Use the final accumulatorfrom as the detached payload and verify the signature of the COSE Sign1.¶

consistent_roots requires the proof to have exactly the shape the two sizes imply: tree-size-2 MUST be a complete MMR size; each consistency path MUST have exactly the length that inclusion_proof_path (Section 4.1) produces for its peak; and every path leading to the same peak of tree-size-2 MUST produce the same value. The number of roots it returns and the number of right-peaks it requires are fixed by the two sizes.¶

It is recommended that implementations return a single boolean result for Receipt verification operations, to reduce the chance of accepting a valid signature over an invalid consistency proof.¶

  def consistent_roots(
      sizefrom, sizeto, accumulatorfrom, proofs):

    # if sizeto <= sizefrom -> ERROR

    leavesto = leaf_count(sizeto - 1)
    # if mmr_size_for_leaf_count(leavesto) != sizeto -> ERROR

    if sizefrom > 0:
      leavesfrom = leaf_count(sizefrom - 1)
    else:
      leavesfrom = 0

    n = ones_count(leavesfrom)
    # if length(accumulatorfrom) != n -> ERROR
    # if length(proofs) != n -> ERROR

    nto = ones_count(leavesto)
    if n == 0:
      return [], nto

    # The highest bit on which the leaf counts differ.
    split = bit_length(leavesfrom ^ leavesto) - 1

    roots = []

    # The number of nodes preceding the sub tree of the
    # current origin peak. A peak of height h is at
    # offset + 2^(h+1) - 2, and its sub tree has 2^(h+1) - 1 nodes.
    offset = 0
    i = 0

    # Origin peaks above the split are peaks of the target.
    # The path is not read; requiring it to be empty
    # rejects unused material.
    for h in range(bit_length(leavesfrom) - 1, split, -1):
      if not (leavesfrom >> h) & 1:
        continue
      # if length(proofs[i]) != 0 -> ERROR
      roots.append(accumulatorfrom[i])
      offset += (1 << (h + 1)) - 1
      i += 1

    # Origin peaks below the split are all committed by the
    # target peak of height split, so each path has length
    # split - h and every path must produce the same value.
    above = len(roots)
    root = None
    for h in range(split - 1, -1, -1):
      if not (leavesfrom >> h) & 1:
        continue
      # if length(proofs[i]) != split - h -> ERROR
      subtree = (1 << (h + 1)) - 1
      proven = included_root(
          offset + subtree - 1, accumulatorfrom[i], proofs[i])
      if i == above:
        root = proven
      # elif proven != root -> ERROR
      offset += subtree
      i += 1

    if n > above:
      roots.append(root)

    return roots, nto - len(roots)

8.1. add_leaf_hash

When a new node is appended, if its height matches the height of its immediate predecessor, then the two equal height siblings MUST be merged. Merging is defined as the append of a new node which takes the adjacent peaks as its left and right children. This process MUST proceed until there are no more completable sub trees.¶

add_leaf_hash(f) adds the leaf hash value f to the tree.¶

Given:¶

• f the leaf value resulting from H(x) for the caller defined leaf value x¶

• db an interface supporting append(entry) -> count and get(index) -> entry methods. append stores the entry and returns the number of nodes in the store after the append, which is the index at which the next node will be stored.¶

And the methods:¶

• index_height (Section 9.1)¶

• Section 8.2.1¶

We define add_leaf_hash as¶

  def add_leaf_hash(db, f: bytes):

    # Set g to 0, the height of the leaf item f
    g = 0

    # Set i to the index the next node will occupy, which is the
    # number of nodes after appending f
    i = db.append(f)

    # While the node that would be stored at i is a parent, which
    # is exactly when MMR(i) is not complete (#looptarget)
    while index_height(i) > g:

      # Set ileft to the index of the left child of i,
      # which is i - 2^(g+1)

      ileft = i - (2 << g)

      # Set iright to the index of the right child of i,
      # which is i - 1

      iright = i - 1

      # Set v to H(i + 1 || Get(ileft) || Get(iright))
      # Set i to the result of invoking Append(v)

      i = db.append(
        hash_pospair64(i+1, db.get(ileft), db.get(iright)))

      # Set g to the height of the node just appended, which is g + 1
      g += 1

    # i is the number of nodes, the MMR size after the append
    return i

add_leaf_hash returns the MMR size after the append, which is a complete MMR size. The index of the leaf itself is one less than the value of i immediately after the first append.¶

8.2. Node values

Interior nodes in the tree MUST prefix the value provided to H(x) with pos.¶

The value v for any interior node MUST be H(pos || Get(LEFT_CHILD) || Get(RIGHT_CHILD))¶

The algorithm for leaf addition is provided the result of H(x) directly.¶

  def hash_pospair64(pos, a, b):

    # Note: Hash algorithm agility is tbd, this example uses SHA-256
    h = hashlib.sha256()

    # Take the big endian representation of pos
    h.update(pos.to_bytes(8, byteorder="big", signed=False))
    h.update(a)
    h.update(b)
    return h.digest()

9.1. index_height

index_height(i) returns the zero-based height g of the node index i¶

Given:¶

• i the index of any mmr node.¶

We define index_height as¶

  def index_height(i) -> int:
    pos = i + 1
    while not all_ones(pos):
      pos = pos - most_sig_bit(pos) + 1

    return bit_length(pos) - 1

9.2. peaks

peaks(i) returns the peak indices for MMR(i+1), which is also its accumulator.¶

Requires MMR(i+1) to be complete. MMR(i+1) is complete if and only if index_height(i+1) is 0, that is, the next node to be appended would be a leaf; see Conventions and Definitions (Section 2).¶

Given:¶

• i the index of any mmr node.¶

We define peaks¶

  def peaks(i):
    peak = 0
    peaks = []
    s = i+1
    while s != 0:
      # find the highest peak size in the current MMR(s)
      highest_size = (1 << log2floor(s+1)) - 1
      peak = peak + highest_size
      peaks.append(peak-1)
      s -= highest_size

    return peaks

9.3. leaf_count

leaf_count(i) returns the number of leaves in MMR(i+1).¶

The bits of the count also form a mask with a single bit set for each peak in the accumulator, where the bit position is the height of the peak. Read from the highest bit to the lowest, the set bits give the accumulator peaks in order.¶

Given:¶

• i the index of any mmr node.¶

And the methods:¶

• bit_length (Appendix A.3)¶

We define leaf_count as¶

  def leaf_count(i):
    s = i + 1

    peaksize = (1 << bit_length(s)) - 1
    peakmap = 0
    while peaksize > 0:
      peakmap <<= 1
      if s >= peaksize:
        s -= peaksize
        peakmap |= 1
      peaksize >>= 1

    return peakmap

9.4. mmr_size_for_leaf_count

mmr_size_for_leaf_count(leaves) returns the number of nodes in the complete MMR with leaves leaves.¶

Every leaf adds itself and one interior node for each binary carry, and each peak is a carry that has not happened. Because leaf_count rounds an incomplete size down to the largest complete MMR below it, mmr_size_for_leaf_count(leaf_count(size - 1)) == size holds exactly when size is a complete MMR size.¶

Given:¶

• leaves a leaf count.¶

And the methods:¶

• ones_count (Appendix A.5)¶

We define mmr_size_for_leaf_count as¶

  def mmr_size_for_leaf_count(leaves):
    return 2 * leaves - ones_count(leaves)

11.1. Tree size of a receipt of inclusion

A receipt of inclusion carries no tree size: it verifies in every later tree size, and alone does not tie the proven node to the history a verifier has established by receipts of consistency. When the inclusion path is empty the signature is over the node value alone and the index is not bound. An application that needs the position bound in this case can include it in the entry (see Leaf commitment scheme (Section 11.2)) or check the node against a trusted accumulator for a tree size in which it is a peak.¶

11.2. Leaf commitment scheme

Leaf values are not domain separated from interior values as they are in [RFC9162]: an x equal to the pre-image pos || left || right of an interior node hashes to that node. With a non-empty inclusion path the position is bound and the height of the index shows whether the node is a leaf. With an empty path such an x verifies as an entry at any leaf index. An application should choose a form for x that no interior pre-image can take, for example a leading domain byte, and include the position in x if it needs the position bound when the path is empty.¶

11.3. Declared tree sizes

The shape of a consistency proof does not fix tree-size-2 when there are right-peaks: a right-peak carries no height, so the same consistency paths and right-peaks complete the accumulator of every tree size that adds the same number of peaks. A verifier that takes tree-size-2 from the unprotected proof, or omits the comparison with the protected tree-size-2, lets the presenter choose the size it records, and the ledger's next receipt then fails against that state although the ledger has behaved correctly.¶

11.4. The empty tree as trusted state

Every accumulator is consistent with the empty tree. A verifier that verifies from the empty tree places all of its trust in the signing key and the signed tree-size-2; the size it records is the signer's assertion, not a value derived from a state it held. The rules for accepting such a receipt once a later state is held are given in Verifying the Receipt of consistency (Section 7.1).¶

12.1. Additions to Existing Registries

12.2. New Registries

This document requests no new registries.¶

13.1. Normative References

[RFC2119]

Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/rfc/rfc2119>.

[RFC8174]

Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfc-editor.org/rfc/rfc8174>.

[RFC8949]

Bormann, C. and P. Hoffman, "Concise Binary Object Representation (CBOR)", STD 94, RFC 8949, DOI 10.17487/RFC8949, December 2020, <https://www.rfc-editor.org/rfc/rfc8949>.

[RFC9052]

Schaad, J., "CBOR Object Signing and Encryption (COSE): Structures and Process", STD 96, RFC 9052, DOI 10.17487/RFC9052, August 2022, <https://www.rfc-editor.org/rfc/rfc9052>.

[RFC9053]

Schaad, J., "CBOR Object Signing and Encryption (COSE): Initial Algorithms", RFC 9053, DOI 10.17487/RFC9053, August 2022, <https://www.rfc-editor.org/rfc/rfc9053>.

[RFC9942]

Steele, O., Birkholz, H., Delignat-Lavaud, A., and C. Fournet, "CBOR Object Signing and Encryption (COSE) Receipts", RFC 9942, DOI 10.17487/RFC9942, June 2026, <https://www.rfc-editor.org/rfc/rfc9942>.

13.2. Informative References

[CrosbyWallach]

Crosby, S. A. and D. S. Wallach, "Efficient Data Structures for Tamper-Evident Logging", 2009, <https://static.usenix.org/event/sec09/tech/full_papers/crosby.pdf>.

[KnuthTBT]

Knuth, D. E., "The Art of Computer Programming, Volume 1: Fundamental Algorithms, Section 2.3.1 Traversing Binary Trees", n.d., <https://www-cs-faculty.stanford.edu/~knuth/taocp.html>.

[PeterTodd]

Todd, P., "Merkle Mountain Ranges (bitcoin-dev mailing list)", 2016, <https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-May/012715.html>.

[PostOrderTlog]

Cox, R., "Transparent Logs for Skeptical Clients (Appendix A: Storing the Log)", 2019, <https://research.swtch.com/tlog#appendix_a>.

[ReyzinYakoubov]

Reyzin, L. and S. Yakoubov, "Efficient Asynchronous Accumulators for Distributed PKI", 2015, <https://eprint.iacr.org/2015/718.pdf>.

[RFC9162]

Laurie, B., Messeri, E., and R. Stradling, "Certificate Transparency Version 2.0", RFC 9162, DOI 10.17487/RFC9162, December 2021, <https://www.rfc-editor.org/rfc/rfc9162>.

[RFC9943]

Birkholz, H., Delignat-Lavaud, A., Fournet, C., Deshpande, Y., and S. Lasker, "An Architecture for Trustworthy and Transparent Digital Supply Chains", RFC 9943, DOI 10.17487/RFC9943, June 2026, <https://www.rfc-editor.org/rfc/rfc9943>.

A.1. log2floor

Returns the floor of log base 2 x¶

  def log2floor(x):
    return x.bit_length() - 1

A.2. most_sig_bit

Returns the mask for the most significant bit in pos¶

  def most_sig_bit(pos) -> int:
    return 1 << (pos.bit_length() - 1)

The following primitives are assumed for working with bits as they commonly have library or hardware support.¶

A.3. bit_length

The minimum number of bits to represent pos. b011 would be 2, b010 would be 2, and b001 would be 1.¶

  def bit_length(pos):
    return pos.bit_length()

A.4. all_ones

Tests if all bits, from the most significant that is set, are 1, b0111 would be true, b0101 would be false.¶

  def all_ones(pos) -> bool:
    # most_sig_bit returns a mask, so shifting it left by one
    # and subtracting one sets every bit below and including it
    mask = (most_sig_bit(pos) << 1) - 1
    return pos == mask

A.5. ones_count

Count of set bits. For example ones_count(b101) is 2¶

A.6. trailing_zeros

  (v & -v).bit_length() - 1