Internet-Draft CoMETRE December 2023
Steele, et al. Expires 13 June 2024 [Page]
Workgroup:
COSE
Internet-Draft:
draft-ietf-cose-merkle-tree-proofs-03
Published:
Intended Status:
Standards Track
Expires:
Authors:
O. Steele
Transmute
H. Birkholz
Fraunhofer SIT
A. Delignat-Lavaud
Microsoft
C. Fournet
Microsoft

Concise Encoding of Signed Merkle Tree Proofs

Abstract

This specification describes verifiable data structures and associated proof types for use with COSE. The extensibility of the approach is demonstrated by providing CBOR encodings for RFC9162.

Discussion Venues

This note is to be removed before publishing as an RFC.

Discussion of this document takes place on the CBOR Object Signing and Encryption Working Group mailing list (cose@ietf.org), which is archived at https://mailarchive.ietf.org/arch/browse/cose/.

Source for this draft and an issue tracker can be found at https://github.com/cose-wg/draft-ietf-cose-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 13 June 2024.

Table of Contents

1. Introduction

Merkle trees are one of many verifiable data structures that enable tamper evident secure information storage, through their ability to protect the integrity of batches of documents or collections of statements.

Merkle trees can be constructed from simple operations such as concatenation and digest via a cryptographic hash function, however, more advanced constructions enable proofs of different properties of the underlying verifiable data structure.

Verifiable data structure proofs can be used to prove a document is in a database (proof of inclusion), that a database is append only (proof of consistency), that a smaller set of statements are contained in a large set of statements (proof of disclosure, a special case of proof of inclusion), or proof that certain data is not yet present in a database (proofs of non inclusion).

Differences in the representation of verifiable data structures, and verifiable data structure proof types, can increase the burden for implementers, and create interoperability challenges for transparency services.

This document describes how to convey verifiable data structures, and associated proof types in COSE envelopes.

1.1. Requirements Notation

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.

2. CBOR Tags

This section will be removed before the document is completed, its purpose is to track the TBD code points references throughout the draft.

-111 is TBD_1:

A requested cose header parameter representing the verifiable data structure used.

-222 is TBD_2:

A requested cose header parameter representing the verifiable data structure parameters map (proofs map)

The other codepoints are assigned from the registries established in this draft, they are therefore not marked TBD.

3. Terminology

Verifiable Data Structure:

A data structure which supports one or more Proof Types.

Verifiable Data Structure Parameters:

Parameters to a verifiable data structure that are used to prove properties, such as authentication, inclusion, consistency, and freshness. Parameters can include multiple proofs of a given type, or multiple types of proof (inclusion and consistency).

Proof Type:

A verifiable process, that proves properties of a Verifiable Data Structure.

Proof Value:

An encoding of a Proof Type in CBOR.

4. Verifiable Data Structures in CBOR

This section describes representations of verifiable data structure proofs in CBOR.

For example, construction of a merkle tree leaf, or an inclusion proof from a leaf to a merkle root, might have several different representations, depending on the verifiable data structure used.

Differences in representations are necessary to support efficient verification, unique security or privacy properties, and for compatibility with specific implementations.

In order to improve interoperability we define two extension points for enabling verifiable data structures with COSE, and we provide concrete examples for the structures and proofs defined in [RFC9162].

4.1. Structures

Similar to COSE Key Types, different verifiable data structures support different algorithms. As EC2 keys (1: 2) support both digital signature and key agreement algorithms, RFC9162_SHA256 (TBD_1 : 1) supports both inclusion and consistency proofs.

This document establishes a registry of verifiable data structure algorithms, with the following initial contents:

  • Name: The name of the verifiable data structure

  • Value: The identifier for the verifiable data structure

  • Description: The identifier for the verifiable data structure

  • Reference: Where the verifiable data structure is defined

Table 1: COSE Verifiable Data Structures
Name Value Description Reference
N/A 0 N/A N/A
RFC9162_SHA256 1 SHA256 Binary Merkle Tree [RFC9162]

When desigining new verifiable data structures, please request the next available positive integer as your requested assignment, for example:

Table 2: How to register new structures
Name Value Description Reference
N/A 0 N/A N/A
RFC9162_SHA256 1 SHA256 Binary Merkle Tree [RFC9162]
Your name TBD (requested assignment 2) tbd Your specification

4.2. Parameters

Similar to COSE Key Type Parameters, As EC2 keys (1: 2) keys require and give meaning to specific parameters, such as -1 (crv), -2 (x), -3 (y), -4 (d), RFC9162_SHA256 (TBD_1 : 1) supports both (-1) inclusion and (-2) consistency proofs.

This document establishes a registry of verifiable data structure algorithms, with the following initial contents:

Table 3: COSE Verifiable Data Structure Parameters
Verifiable Data Structure Name Label CBOR Type Description Reference
1 inclusion proofs -1 array (of bstr) Proof of inclusion Section 5.2
1 consistency proofs -2 array (of bstr) Proof of append only property Section 5.3

Proof types are specific to their associated "verifiable data structure", for example, different Merkle trees might support different representations of "inclusion proof" or "consistency proof".

Implementers should not expect interoperability accross "verifiable data structures", but they should expect conceptually similar properties across the different registered proof types.

For example, 2 different merkle tree based verifiable data structures might both support proofs of inclusion.

Protocols requiring proof of inclusion ought to be able to preserve their functionality, while switching from one verifiable data structure to another, so long as both structures support the same proof types.

Security analysis SHOULD be conducted prior to migrating to new structures to ensure the new security and privacy assumptions are acceptable for the use case.

When designing new verifiable data structure parameters (or proof types), please start with -1, and count down for each proof type supported by your verifiable data structure:

Table 4: How to register new parameters
Verifiable Data Structure Name Label CBOR Type Description Reference
1 inclusion proofs -1 array (of bstr) Proof of inclusion Section 5.2
1 consistency proofs -2 array (of bstr) Proof of append only property Section 5.3
TBD (requested assignment 2) new proof type -1 tbd tbd Your_Specification
TBD (requested assignment 2) new proof type -2 tbd tbd Your_Specification
TBD (requested assignment 2) new proof type -3 tbd tbd Your_Specification

4.2.1. Registration Requirements

Each specification MUST define how to encode the verifiable data structure and its parameters (also called proof types) in CBOR.

Each specification MUST define how to produce and consume the supported proof types.

See Section 5 as an example.

5. RFC9162_SHA256

This section defines how the data structures described in [RFC9162] are mapped to the terminology defined in this document, using cbor and cose.

5.1. Verifiable Data Structure

The integer identifier for this Verifiable Data Structure is 1. The string identifier for this Verifiable Data Structure is "RFC9162_SHA256".

See Table 1.

See [RFC9162], 2.1.1. Definition of the Merkle Tree, for a complete description of this verifiable data structure.

5.2. Inclusion Proof

See [RFC9162], 2.1.3.1. Generating an Inclusion Proof, for a complete description of this verifiable data structure proof type.

The cbor representation of an inclusion proof for RFC9162_SHA256 is:

inclusion-proof = [
    tree-size: int
    leaf-index: int
    inclusion-path: [ + bstr ]
]

5.2.1. Inclusion Receipt

This specification sometimes refers to profiles of signed inclusion proofs as "receipts".

In a signed inclusion proof, the previous merkle tree root, maps to tree-size-1, and is a detached payload.

Profiles of proof signatures are encouraged to make additional protected header parameters mandatory, to ensure that claims are processed with their intended semantics.

One way to include this information in the COSE structure is use of the typ (type) Header Parameter, see [I-D.ietf-cose-typ-header-parameter] and the similar guidance provided in [I-D.ietf-cose-cwt-claims-in-headers].

The [I-D.ietf-scitt-architecture] describes one way in which signed inclusion proofs can be leveraged to support supply chain transparency.

The protected header for an RFC9162_SHA256 inclusion proof signature is:

protected-header-map = {
  &(alg: 1) => int
  &(verifiable-data-structure: -111) => int
  * cose-label => cose-value
}
  • alg (label: 1): REQUIRED. Signature algorithm identifier. Value type: int / tstr.

  • verifiable-data-structure (label: -111): REQUIRED. verifiable data structure algorithm identifier. Value type: int / tstr.

The unprotected header for an RFC9162_SHA256 inclusion proof signature is:

inclusion-proofs = [ + bstr .cbor inclusion-proof ]

verifiable-proofs = {
  &(inclusion-proof: -1) => inclusion-proofs
}

unprotected-header-map = {
  &(verifiable-data-proof: -222) => verifiable-proofs
  * cose-label => cose-value
}
  • verifiable-data-proof (label: -222): REQUIRED.

  • inclusion-proof (label: -1): REQUIRED.

The payload of an RFC9162_SHA256 inclusion proof signature is the previous Merkle tree hash as defined in [RFC9162].

The payload MUST be detached.

Detaching the payload forces verifiers to recompute the root from the inclusion proof signature, this protects against implementation errors where the signature is verified but the root does not match the inclusion proof.

18(                                 / COSE Sign 1                   /
    [
      h'a4012604...6d706c65',       / Protected                     /
      {                             / Unprotected                   /
        -222: {                     / Proofs                        /
          -1: [                     / Inclusion proofs (1)          /
            h'83080783...32568964', / Inclusion proof 1             /
          ]
        },
      },
      h'',                          / Detached payload              /
      h'2e34df43...8d74d55e'        / Signature                     /
    ]
)
Figure 1: Example inclusion receipt
{                                   / Protected                     /
  1: -7,                            / Algorithm                     /
  4: h'4930714e...7163316b',        / Key identifier                /
  -111: 1,                          / Verifiable Data Structure     /
}
Figure 2: Example inclusion receipt decoded protected header
[                                   / Inclusion proof 1             /
  8,                                / Tree size                     /
  7,                                / Leaf index                    /
  [                                 / Inclusion hashes (3)          /
     h'2a8d7dfc...15d10b22'         / Intermediate hash 1           /
     h'75f177fd...2e73a8ab'         / Intermediate hash 2           /
     h'0bdaaed3...32568964'         / Intermediate hash 3           /
  ]
]
Figure 3: Example inclusion receipt decoded inclusion proof

5.3. Consistency Proof

See [RFC9162], 2.1.4.1. Generating a Consistency Proof, for a complete description of this verifiable data structure proof type.

The cbor representation of a consistency proof for RFC9162_SHA256 is:

consistency-proof = [
    tree-size-1: int ; size of tree, at previous root
    tree-size-2: int ; size of tree, at latest root
    consistency-path: [ + bstr ] ; path from previous to latest root.
]

Editors note: tree-size-1, could be ommited, if an inclusion-proof is always present, since the inclusion proof contains, tree-size-1.

5.3.1. Consistency Receipt

In a signed consistency proof, the latest merkle tree root, maps to tree-size-2, and is an attached payload.

The protected header for an RFC9162_SHA256 consistency proof signature is:

protected-header-map = {
  &(alg: 1) => int
  &(verifiable-data-structure: -111) => int
  * cose-label => cose-value
}
  • alg (label: 1): REQUIRED. Signature algorithm identifier. Value type: int / tstr.

  • verifiable-data-structure (label: TBD_1): REQUIRED. verifiable data structure algorithm identifier. Value type: int / tstr.

The unprotected header for an RFC9162_SHA256 consistency proof signature is:

consistency-proofs = [ + bstr ]

verifiable-proofs = {
  &(consistency-proof: -2) => consistency-proofs
}

unprotected-header-map = {
  &(verifiable-data-proof: -222) => verifiable-proofs
  * cose-label => cose-value
}
  • verifiable-data-proof (label: -222): REQUIRED.

  • consistency-proof (label: -2): REQUIRED.

The payload of an RFC9162_SHA256 consistency proof signature is:

The latest Merkle tree hash as defined in [RFC9162].

The payload MUST be attached.

18(                                 / COSE Sign 1                   /
    [
      h'a3012604...392b6601',       / Protected                     /
      {                             / Unprotected                   /
        -222: {                     / Proofs                        /
          -2: [                     / Consistency proofs (1)        /
            h'83040682...2e73a8ab', / Consistency proof 1           /
          ]
        },
      },
      h'430b6fd7...f74c7fc4',       / Payload                       /
      h'd97befea...f30631cb'        / Signature                     /
    ]
)
Figure 4: Example consistency receipt
{                                   / Protected                     /
  1: -7,                            / Algorithm                     /
  4: h'68747470...6d706c65',        / Key identifier                /
  -111: 1,                          / Verifiable Data Structure     /
}
Figure 5: Example consistency receipt decoded protected header
[                                   / Consistency proof 1           /
  4,                                / Tree size 1                   /
  6,                                / Tree size 2                   /
  [                                 / Consistency hashes (2)        /
     h'0bdaaed3...32568964'         / Intermediate hash 1           /
     h'75f177fd...2e73a8ab'         / Intermediate hash 2           /
  ]
]
Figure 6: Example consistency receipt decoded consistency proof

6. Privacy Considerations

See the privacy considerations section of:

6.1. Log Length

Some structures and proofs leak the size of the log at the time of inclusion. In the case that a log only stores certain kinds of information, this can reveal details that could impact reputation. For example, if a transparency log only stored breach notices, a receipt for a breach notice would reveal the number of previous breaches at the time the notice was made transparent.

6.2. Header Parameters

Additional header parameters can reveal information about the transparency service or its log entries. A privacy analysis SHOULD be performed for all mandatory fields in profiles based on this specification.

7. Security Considerations

See the security considerations section of:

7.1. Choice of Signature Algorithms

A security analysis SHOULD be performed to ensure that the digitial signature algorithm alg is the appropriate strength to secure receipts.

7.2. Validity Period

In some cases, receipts SHOULD have strict validity periods, for example, activation not too far in the future, or expiration, not too far in the past. See the iat, nbf, and exp claims in [RFC8392], for one way to accomplish this. The details of expressing validity periods are out of scope for this document.

7.3. Status Updates

In some cases, receipts should be "revocable" or "suspendible", after being issued, regardless of their validity period. The details of expressing statuses are out of scope for this document.

8. Acknowledgements

We would like to thank Maik Riechert, Jon Geater, Mike Jones, Mike Prorock, Ilari Liusvaara, for their contributions (some of which substantial) to this draft and to the initial set of implementations.

9. IANA Considerations

9.1. Additions to Existing Registries

9.1.1. New Entries to the COSE Header Parameters Registry

This document requests IANA to add new values to the 'COSE Algorithms' and to the 'COSE Header Algorithm Parameters' registries in the 'Standards Action With Expert Review category.

9.1.1.1. COSE Header Algorithm Parameters
  • Name: verifiable-data-structure

  • Label: TBD_1

  • Value type: int / tstr

  • Value registry: https://www.iana.org/assignments/cose/cose.xhtml#header-parameters

  • Description: Algorithm name for verifiable data structure, used to produce verifiable data structure proofs.

  • Name: verifiable-data-structure-parameters

  • Label: TBD_2

  • Value type: int / tstr

  • Value registry: https://www.iana.org/assignments/cose/cose.xhtml#header-parameters

  • Description: Location for verifiable data structure proofs in COSE Header Parameters.

9.1.2. COSE Verifiable Data Structures

IANA will be asked to establish a registry of verifiable data structure identifiers, named "COSE Verifiable Data Structures" to be administered under a Specification Required policy [RFC8126].

Template:

  • Name: The name of the verifiable data structure

  • Value: The identifier for the verifiable data structure

  • Description: The identifier for the verifiable data structure

  • Reference: Where the verifiable data structure is defined

Initial contents: Provided in Table 1

9.1.3. COSE Verifiable Data Structure Parameters

IANA will be asked to establish a registry of verifiable data structure parameters, named "COSE Verifiable Data Structure Parameters" to be administered under a Specification Required policy [RFC8126].

Template:

  • Verifiable Data Structure: The identifier for the verifiable data structure

  • Name: The name of the proof type

  • Label: The integer of the proof type

  • CBOR Type: The cbor data type of the proof

  • Description: The description of the proof type

  • Reference: Where the proof type is defined

Initial contents: Provided in Table 3

10. References

10.1. Normative References

[BCP205]
Sheffer, Y. and A. Farrel, "Improving Awareness of Running Code: The Implementation Status Section", BCP 205, RFC 7942, DOI 10.17487/RFC7942, , <https://www.rfc-editor.org/rfc/rfc7942>.
[RFC2119]
Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, , <https://www.rfc-editor.org/rfc/rfc2119>.
[RFC6234]
Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms (SHA and SHA-based HMAC and HKDF)", RFC 6234, DOI 10.17487/RFC6234, , <https://www.rfc-editor.org/rfc/rfc6234>.
[RFC6962]
Laurie, B., Langley, A., and E. Kasper, "Certificate Transparency", RFC 6962, DOI 10.17487/RFC6962, , <https://www.rfc-editor.org/rfc/rfc6962>.
[RFC6979]
Pornin, T., "Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)", RFC 6979, DOI 10.17487/RFC6979, , <https://www.rfc-editor.org/rfc/rfc6979>.
[RFC7049]
Bormann, C. and P. Hoffman, "Concise Binary Object Representation (CBOR)", RFC 7049, DOI 10.17487/RFC7049, , <https://www.rfc-editor.org/rfc/rfc7049>.
[RFC8032]
Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital Signature Algorithm (EdDSA)", RFC 8032, DOI 10.17487/RFC8032, , <https://www.rfc-editor.org/rfc/rfc8032>.
[RFC8126]
Cotton, M., Leiba, B., and T. Narten, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 8126, DOI 10.17487/RFC8126, , <https://www.rfc-editor.org/rfc/rfc8126>.
[RFC8174]
Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, , <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, , <https://www.rfc-editor.org/rfc/rfc8949>.
[RFC9053]
Schaad, J., "CBOR Object Signing and Encryption (COSE): Initial Algorithms", RFC 9053, DOI 10.17487/RFC9053, , <https://www.rfc-editor.org/rfc/rfc9053>.
[RFC9162]
Laurie, B., Messeri, E., and R. Stradling, "Certificate Transparency Version 2.0", RFC 9162, DOI 10.17487/RFC9162, , <https://www.rfc-editor.org/rfc/rfc9162>.

10.2. Informative References

[I-D.ietf-cose-countersign]
Schaad, J., "CBOR Object Signing and Encryption (COSE): Countersignatures", Work in Progress, Internet-Draft, draft-ietf-cose-countersign-10, , <https://datatracker.ietf.org/doc/html/draft-ietf-cose-countersign-10>.
[I-D.ietf-cose-cwt-claims-in-headers]
Looker, T. and M. B. Jones, "CBOR Web Token (CWT) Claims in COSE Headers", Work in Progress, Internet-Draft, draft-ietf-cose-cwt-claims-in-headers-10, , <https://datatracker.ietf.org/doc/html/draft-ietf-cose-cwt-claims-in-headers-10>.
[I-D.ietf-cose-typ-header-parameter]
Jones, M. B. and O. Steele, "COSE "typ" (type) Header Parameter", Work in Progress, Internet-Draft, draft-ietf-cose-typ-header-parameter-02, , <https://datatracker.ietf.org/doc/html/draft-ietf-cose-typ-header-parameter-02>.
[I-D.ietf-scitt-architecture]
Birkholz, H., Delignat-Lavaud, A., Fournet, C., Deshpande, Y., and S. Lasker, "An Architecture for Trustworthy and Transparent Digital Supply Chains", Work in Progress, Internet-Draft, draft-ietf-scitt-architecture-04, , <https://datatracker.ietf.org/doc/html/draft-ietf-scitt-architecture-04>.
[RFC8392]
Jones, M., Wahlstroem, E., Erdtman, S., and H. Tschofenig, "CBOR Web Token (CWT)", RFC 8392, DOI 10.17487/RFC8392, , <https://www.rfc-editor.org/rfc/rfc8392>.

Appendix A. Implementation Status

Note to RFC Editor: Please remove this section as well as references to [BCP205] before AUTH48.

This section records the status of known implementations of the protocol defined by this specification at the time of posting of this Internet-Draft, and is based on a proposal described in [BCP205]. The description of implementations in this section is intended to assist the IETF in its decision processes in progressing drafts to RFCs. Please note that the listing of any individual implementation here does not imply endorsement by the IETF. Furthermore, no effort has been spent to verify the information presented here that was supplied by IETF contributors. This is not intended as, and must not be construed to be, a catalog of available implementations or their features. Readers are advised to note that other implementations may exist.

According to [BCP205], "this will allow reviewers and working groups to assign due consideration to documents that have the benefit of running code, which may serve as evidence of valuable experimentation and feedback that have made the implemented protocols more mature. It is up to the individual working groups to use this information as they see fit".

A.1. Implementer

An open-source implementation was initiated and is maintained by the Transmute Industries Inc. - Transmute.

A.2. Implementation Name

An application demonstrating the concepts is available at https://scitt.xyz.

A.3. Implementation URL

An open-source implementation is available at:

  • https://github.com/transmute-industries/cose

A.4. Maturity

The code's level of maturity is considered to be "prototype".

A.5. Coverage and Version Compatibility

The current version ('main') implements the verifiable data structure algorithm, inclusion proof and consistency proof concepts of this draft.

A.6. License

The project and all corresponding code and data maintained on GitHub are provided under the Apache License, version 2.

A.7. Implementation Dependencies

The implementation builds on concepts described in SCITT [I-D.ietf-scitt-architecture] (https://scitt.io/).

The implementation uses the Concise Binary Object Representation [RFC7049] (https://cbor.io/).

The implementation uses the CBOR Object Signing and Encryption [RFC9053], maintained at: - https://github.com/erdtman/cose-js

The implementation uses an implementation of [RFC9162], maintained at:

  • https://github.com/transmute-industries/rfc9162/tree/main/src/CoMETRE

A.8. Contact

Orie Steele (orie@transmute.industries)

Authors' Addresses

Orie Steele
Transmute
United States
Henk Birkholz
Fraunhofer SIT
Rheinstrasse 75
64295 Darmstadt
Germany
Antoine Delignat-Lavaud
Microsoft
United Kingdom
Cedric Fournet
Microsoft
United Kingdom