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

The inclusion proof and signature are verified in order. First the verifiers applies the inclusion proof to a possible entry (set member) bytes. The result is the merkle root implied by the inclusion proof path for the candidate value. The COSE Sign1 payload MUST be set to this value. Second the verifier checks the signature of the COSE Sign1. If the resulting signature verifies, the Receipt has proved inclusion of the entry in the verifiable data structure. If the resulting signature does not verify, the signature may have been tampered with.¶

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.¶

As the proof must be processed prior to signature verification the implementation SHOULD check the lengths of the proof paths are appropriate for the provided tree sizes.¶

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.3.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_path

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

right-peaks are obtained by invoking peaks(tree-size-2 - 1), and discarding length(proofs) from the left.¶

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.¶

Perform the following for each consistency-proof in the list, verifying the signature with the output of the last.¶

1. Initialize current proof as the first consistency-proof.¶

2. Initialize accumulatorfrom to the peaks of tree-size-1 in the current proof.¶

3. Initialize ifrom to tree-size-1 - 1 from the current proof.¶

4. Initialize proofs to the consistency-paths from the current proof.¶

5. Apply the algorithm consistent_roots (Section 7.1.1)¶

6. Apply the peaks algorithm to obtain the accumulator for tree-size-2¶

7. From the peaks for tres-size-2, discard from the left the number of roots returned by consistent_roots.¶

8. Create the consistent accumulator by appending the remaining peaks to the consistent roots.¶

9. If there are no remaining proofs, use the consistent accumulator as the detached payload 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 consistency proof.¶

As the proof must be processed prior to signature verification the implementation SHOULD check the lengths of the proof paths are appropriate for the provided tree sizes.¶

  def consistent_roots(ifrom, accumulatorfrom, proofs):

    frompeaks = peaks(ifrom)

    # if length(frompeaks) != length(proofs) -> ERROR

    roots = []
    for i in range(len(accumulatorfrom)):
      root = included_root(
          frompeaks[i], accumulatorfrom[i], proofs[i])

      if roots and roots[-1] == root:
          continue
      roots.append(root)

    return 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 the Section 8.2.2 and Section 8.2.1 implementation defined storage methods.¶

And the methods:¶

• index_height (Section 9.1)¶

• Section 8.3.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 result of invoking Append(f)
    i = db.append(f)

    # If index_height(i) is greater than g (#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 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 new i, which is g + 1
      g += 1

    return i

8.2. Implementation defined storage methods

The following methods are assumed to be available to the implementation. Very minimal requirements are specified.¶

Informally, the storage must be array like and have no gaps.¶

8.3. Node values

Interior nodes in the 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.¶

Assumes MMR(i+1) is complete, implementations can check for this condition by testing the height of i+1¶

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

10.1. Detection of improper inclusion

A receipt of inclusion shows only that the element is included in the ledger. Defining whether that inclusion was legitimate, or in some way valid, is out of scope for this document.¶

10.2. Misbehaving Ledgers

A ledger can misbehave in several ways. Examples include the following: failing to incorporate a leaf entry in the MMR; presenting different, conflicting views of the MMR at different times and/or to different parties.¶

Detection of a failure to include items in the first place is out of scope for this document.¶

Having included an element, ledger implementations using this draft MUST use consistency proofs as the basis for proving entries are not moved, modified or excluded in future states of the MMR. Similarly, consistency proofs MUST be the basis for proving the unequivocal history of additions.¶

11.1. Additions to Existing Registries

Editors note: todo registry requests¶

11.2. New Registries

A.1. Informative References

• ReyzinYakoubov¶

• CrosbyWallach¶

• CrosbyWallachStorage 3.3 Storing the log on secondary storage¶

• PostOrderTlog¶

• PeterTodd¶

• KnuthTBT 2.3.1 Traversing Binary Trees¶

• BNT¶

B.1. log2floor

Returns the floor of log base 2 x¶

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

B.2. most_sig_bit

Returns the mask for the 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.¶

B.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()

B.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:
    msb = most_sig_bit(pos)
    mask = (1 << (msb + 1)) - 1
    return pos == mask

B.5. ones_count

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

B.6. trailing_zeros

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