Concise Encoding of Signed Merkle Tree Proofs

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶

This Internet-Draft will expire on 15 September 2023.¶

Copyright Notice

Copyright (c) 2023 IETF Trust and the persons identified as the document authors. All rights reserved.¶

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License.¶

Table of Contents

1. Introduction

Merkle proofs are verifiable data structures that support secure data storage, through their ability to protect the integrity of batches of documents or collections of statements.¶

Merkle proofs can be used to prove a document is in a database (proof of existence), or that a smaller set of statements are contained in a large set of statements (proof of disclosure).¶

A merkle proof is a path from a leaf to a root in a merkle tree.¶

Merkle trees are constructed from simple operations such as concatenation and digest via a cryptographic hash function.¶

The simple design and valuable cryptographic properties of merkle trees have been leveraged in many network and database applications.¶

Differences in the representation of a merkle tree, merkle leaf and merkle inclusion proof can increase the burden for implementers, and create interoperability challenges.¶

This document describes the three data structures necessary to use merkle proofs with COSE envelopes.¶

2. Terminology

Leaf Bytes:

A merkle tree leaf is labelled with the cryptographic hash of a sequence of bytes. These bytes may be structured as a combination of Payload and Extra Data.¶

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

3. CBOR Merkle Structures

This section describes representations of merkle tree structures in CBOR.¶

Some of the structures such as the construction of a merkle tree leaf, or an inclusion proof from a leaf to a merkle root, might have several different representations.¶

Some differences in representations are necessary to support efficient verification of proofs and compatibility with deployed tree algorithms used in specific implementations.¶

SMTR = THIS.COSE.profile .and COSE_Sign1_Tagged

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

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

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

InclusionPath = IndexAwareInclusionPath / IndexUnawareInclusionPath / UndirectionalInclusionPath

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
]

4. Merkle Tree Algorithms

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

[FIXME] exploration table, what should go into -00?¶

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

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

5. Privacy Considerations

TBD¶

6. Security Considerations

TBD¶

7. IANA Considerations

Authors' Addresses