---
# System prepended metadata

title: Concise Encoding of Signed Merkle Tree Proofs

---

# Concise Encoding of Signed Merkle Tree Proofs

## Status

DRAFT

## Goals

- Define a format for a Merkle tree root signature with metadata. via COSE signature
- Define a format for an inclusion path. via COSE 
- Define a format for the disclosure of a single leaf payload, aka signed Merkle tree proof.
- All formats should be as compact as possible.

## Terminology

### Leaf Bytes

TBD

### Merkle Tree

A Merkle tree is a tree where every leaf is labelled with the cryptographic hash of a sequence of bytes and every node that is not a leaf is labeled with the cryptographic hash of the labels of its child nodes.

### Merkle Tree Root

A Merkle tree root is the root node of a tree which represents the cryptographic hash that commits to all leaves in the tree.

### Merkle Tree Algorithm

A Merkle tree algorithm specifies how nodes in the tree must be hashed to compute the root node.

### Payload and Extra Data

A payload is data bound to in a Merkle tree leaf. The Merkle tree algorithm determines how a payload together with extra data is bound to a leaf. The simplest case is that the payload is the leaf itself without extra data.

### Inclusion Path

An inclusion path confirms that a value is a leaf of a Merkle tree known only by its root hash (and tree size, possibly).

### Signed Merkle Tree Proof

A signed Merkle tree proof is the combination of signed Merkle tree root hash, inclusion path, extra data, and payload.

## Data formats

BIG TODO: where will all the types end up in practice: principles, examlpes, etc & exhaustive list of options?

### Signed Merkle Tree Root

A Merkle tree root is signed with COSE_Sign1, creating a Signed Merkle Tree Root:

```c
SMTR = THIS.COSE.profile .and COSE_Sign1_Tagged
```
Protected header parameters:

- alg (label: 1): REQUIRED. Signature algorithm. Value type: int / tstr.
- tree alg (label: TBD): REQUIRED. Merkle tree algorithm. Value type: int / tstr.
- tree size (label: TBD): OPTIONAL. Merkle tree size as the number of leaves. Value type: uint.

A COSE profile of this specification may add further header parameters, for example to identify the signer.

Payload: Merkle tree root hash bytes according to tree alg (i.e., header params tell you what the alg id is here)

Note: The payload is just a byte string representing the Merkle tree root hash (and not some wrapper structure) so that it can be detached (see defintion of payload in https://www.rfc-editor.org/rfc/rfc9052#section-4.1) and easily re-computed from an inclusion path and leaf bytes. This allows to design other structures that force re-computation and prevent faulty implementations (forgetting to match a computed root with one embedded in a signature).

### Inclusion Path

If the tree size and leaf index is known, then a compact inclusion path (see, REF NEEDED, CT RFC?) variant can be used:

```c
IndexAwareInclusionPath = #6.1234([
    leaf_index: int
    hashes: [+ bstr]
])
```

Otherwise, the direction for each path step must be included (see, REF NEEDED, ask cabo?):
(bit vector: Bitmask'ish 0 -> right, 1 -> left, so no bit lables, they are "self-explaingin" in a way?)

```c
IndexUnawareInclusionPath = #6.1235([
    hashes: [+ bstr]
    left: uint  ; bit vector
])
```

For some tree algorithms, like Quantum Ledger Data Base (QLDB) [FIXME, commercial refernce?], the direction is derived from the hashes themselves and both the index and direction can be left out in the path:

```c
; TODO: find a better name for this
UndirectionalInclusionPath = #6.1236([+ bstr])
```

```c
InclusionPath = IndexAwareInclusionPath / IndexUnawareInclusionPath / UndirectionalInclusionPath
```

Note: Including the tree size and leaf index may not be appropriate in certain privacy-focused applications as an attacker may be able to derive private information from them.

TODO: Should leaf index be part of inclusion path (IndexAwareInclusionPath) or outside?

TODO: Define root computation algorithm for each inclusion path type

TODO: [Do we need both inclusion path types? what properties does each type have?](https://github.com/ietf-scitt/cose-merkle-tree-proofs/issues/6)

TODO: Should the inclusion path be opaque (bstr) and fixed by the tree algorithm? It seems this is orthogonal and the choice of inclusion path type should be application-specific.

### Signed Merkle Tree Proof

A signed Merkle tree proof is a CBOR array containing a signed tree root, an inclusion path, extra data for the tree algorithm, and the payload.

```c
SignedMerkleTreeProof = [
  signed_tree_root: bstr .cbor SMTR  ; payload of COSE_Sign1_Tagged is detached
  inclusion_path: bstr .cbor InclusionPath
  extra_data: bstr / nil
  payload: bstr
]
```

`extra_data` is an additional input to the tree algorithm and is used together with the payload to compute the leaf hash. A use case for this field is to implement blinding.

TODO: maybe rename `extra_data`

### Signed Merkle Tree Multiproof

TODO: define a multi-leaf variant of a signed Merkle tree proof like in:

- https://github.com/transmute-industries/merkle-proof
- https://transmute-industries.github.io/merkle-disclosure-proof-2021/

TODO: consider using sparse multiproofs, see https://medium.com/@jgm.orinoco/understanding-sparse-merkle-multiproofs-9b9f049e8f08 and https://arxiv.org/pdf/2002.07648.pdf

## Merkle Tree Algorithms

This document establishes a registry of Merkle tree algorithms with the following initial contents:

FIXME: this is an explorational table, what should go into -00?

 Name           | Label | Description
----------------|-------|------------
Reserved        | 0     | (in COSA IANA zero is not registered, so we are mimicing it here)
CCF_SHA256      | 1     | CCF with SHA-256
RFC6962_SHA256  | 2     | RFC6962 with SHA-256
RFC6962_BL_SHA256  | 3     | RFC6962 with blinding and SHA-256
QLDB_SHA256     | 4     | QLDB with SHA-256
OZ_Keccak256    | 5     | Open Zeppelin with keccak256

Each tree algorithm defines how to compute the root node from a sequence of leaves each represented by payload and extra data. Extra data is algorithm-specific and should be considered opaque.

### CCF_SHA256

For n > 1 inputs, let k be the largest power of two smaller than n.

```c
MTH({d(0)}) = SHA-256(d(0))
MTH(D[n]) = SHA-256(MTH(D[0:k]) || MTH(D[k:n]))
```

where `d(0)` is computed as:

```c
d(0) = writeset_digest || SHA-256(commit_evidence) || SHA-256(payload)
```

with extra data defined as:

```c
ExtraData = bstr .cbor [
    writeset_digest: bstr .size 32
    commit_evidence: bstr
]
```

### RFC6962_SHA256

For n > 1 inputs, let k be the largest power of two smaller than n.

```c
MTH({d(0)}) = SHA-256(0x00 || d(0))
MTH(D[n]) = SHA-256(0x01 || MTH(D[0:k]) || MTH(D[k:n]))
```

where `d(0)` is the payload. This algorithm takes no extra data.

### RFC6962_BL_SHA256

For n > 1 inputs, let k be the largest power of two smaller than n.

```c
MTH({d(0)}) = SHA-256(0x00 || d(0))
MTH(D[n]) = SHA-256(0x01 || MTH(D[0:k]) || MTH(D[k:n]))
```

where `d(0)` is computed as:

```c
d(0) = nonce || payload
```

with extra data defined as:

```c
ExtraData = bstr .size 32  ; nonce
```

### QLDB_SHA256

For n > 1 inputs, let k be the largest power of two smaller than n.

```c
MTH({d(0)}) = SHA-256(d(0))
MTH(D[n]) = SHA-256(DOT(MTH(D[0:k]), MTH(D[k:n])))
DOT(H1, H2) = if H1 < H2 then H1 || H2 else H2 || H1
```

where `d(0)` is the payload. This algorithm takes no extra data.

### OZ_keccak256

For n > 1 inputs, let k be the largest power of two smaller than n.

```c
MTH({d(0)}) = keccak256(keccak256(d(0)))
MTH(D[n]) = MTH2(sorted([ MTH([d]) | d in D ]))
MTH2({h(0)}) = h(0)
MTH2(H[n]) = keccak256(DOT(MTH2(H[0:k]), MTH2(H[k:n])))
DOT(H1, H2) = if H1 < H2 then H1 || H2 else H2 || H1
```

where `d(0)` is the payload. This algorithm takes no extra data.
