COSE O. Steele
Internet-Draft Transmute
Intended status: Standards Track H. Birkholz
Expires: 22 April 2024 Fraunhofer SIT
A. Delignat-Lavaud
C. Fournet
Microsoft
20 October 2023
Concise Encoding of Signed Merkle Tree Proofs
draft-ietf-cose-merkle-tree-proofs-01
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.
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 22 April 2024.
Copyright Notice
Copyright (c) 2023 IETF Trust and the persons identified as the
document authors. All rights reserved.
Steele, et al. Expires 22 April 2024 [Page 1]
Internet-Draft CoMETRE October 2023
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 . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Requirements Notation . . . . . . . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Verifiable Data Structures in CBOR . . . . . . . . . . . . . 4
3.1. Algorithms Registry . . . . . . . . . . . . . . . . . . . 4
3.1.1. Registration Requirements . . . . . . . . . . . . . . 4
4. Proof Types in CBOR . . . . . . . . . . . . . . . . . . . . . 5
4.1. Proof Types Registry . . . . . . . . . . . . . . . . . . 5
4.2. Inclusion Proof . . . . . . . . . . . . . . . . . . . . . 5
4.3. Consistency Proof . . . . . . . . . . . . . . . . . . . . 6
5. RFC9162_SHA256 as a Verifiable Data Structure . . . . . . . . 6
5.1. Algorithm Definition . . . . . . . . . . . . . . . . . . 6
5.2. Inclusion Proof Definition . . . . . . . . . . . . . . . 6
5.2.1. Inclusion Proof Signature . . . . . . . . . . . . . . 7
5.3. Consistency Proof Definition . . . . . . . . . . . . . . 8
5.3.1. Consistency Proof Signature . . . . . . . . . . . . . 9
6. Privacy Considerations . . . . . . . . . . . . . . . . . . . 10
7. Security Considerations . . . . . . . . . . . . . . . . . . . 10
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10
8.1. Additions to Existing Registries . . . . . . . . . . . . 11
8.1.1. New Entries to the COSE Header Parameters Registry . 11
8.1.2. Verifiable Data Structures . . . . . . . . . . . . . 11
8.1.3. Verifiable Data Structure Proof Types . . . . . . . . 12
9. References . . . . . . . . . . . . . . . . . . . . . . . . . 12
9.1. Normative References . . . . . . . . . . . . . . . . . . 12
9.2. Informative References . . . . . . . . . . . . . . . . . 13
Appendix A. Implementation Status . . . . . . . . . . . . . . . 14
A.1. Implementer . . . . . . . . . . . . . . . . . . . . . . . 14
A.2. Implementation Name . . . . . . . . . . . . . . . . . . . 14
A.3. Implementation URL . . . . . . . . . . . . . . . . . . . 14
A.4. Maturity . . . . . . . . . . . . . . . . . . . . . . . . 14
A.5. Coverage and Version Compatibility . . . . . . . . . . . 15
A.6. License . . . . . . . . . . . . . . . . . . . . . . . . . 15
A.7. Implementation Dependencies . . . . . . . . . . . . . . . 15
A.8. Contact . . . . . . . . . . . . . . . . . . . . . . . . . 15
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 15
Steele, et al. Expires 22 April 2024 [Page 2]
Internet-Draft CoMETRE October 2023
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. Terminology
Verifiable Data Structure: A data structure which supports one or
more Proof Types.
Proof Type: A verifiable process, that proves properties of one or
more Verifiable Data Structures.
Proof Value: An encoding of a Proof Type in CBOR.
Proof Signature: A COSE Sign1 encoding of a specific Proof Type for
a specific Verifiable Data Structure.
Steele, et al. Expires 22 April 2024 [Page 3]
Internet-Draft CoMETRE October 2023
3. Verifiable Data Structures in CBOR
This section describes representations of verifiable data structure
proofs structures in CBOR.
Different verifiable data structures support the same proof types,
but the representations of the proofs varies greatly.
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.
Some differences in representations are necessary to support
efficient verification of different kinds of proofs and for
compatibility with specific implementations.
Some proof types benefit from standard envelope formats for signing
and encryption, whilst others require no further cryptographic
intervention at all.
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].
3.1. Algorithms Registry
This document establishes a registry of verifiable data structure
algorithms, with the following initial contents:
+============+================+===========+
| Identifier | Algorithm | Reference |
+============+================+===========+
| 0 | N/A | |
+------------+----------------+-----------+
| 1 | RFC9162_SHA256 | [RFC9162] |
+------------+----------------+-----------+
Table 1: Verifiable Data Structure
Alogrithms
3.1.1. Registration Requirements
Each specification MUST define how to encode the algorithm and proof
types in CBOR.
Each specification MUST define how to produce and consume the
supported proof types.
Steele, et al. Expires 22 April 2024 [Page 4]
Internet-Draft CoMETRE October 2023
See Section 5 as an example.
4. Proof Types in CBOR
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 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.
4.1. Proof Types Registry
This document establishes a registry of verifiable data structure
proof types tags, with the following initial contents:
+============+=============+===============+=============+
| Identifier | Proof Type | Proof Value | Reference |
+============+=============+===============+=============+
| 0 | N/A | N/A | N/A |
+------------+-------------+---------------+-------------+
| 1 | inclusion | array of bstr | Section 4.2 |
+------------+-------------+---------------+-------------+
| 2 | consistency | array of bstr | Section 4.3 |
+------------+-------------+---------------+-------------+
Table 2: Verifiable Data Structure Proof Types
4.2. Inclusion Proof
Inclusion proofs provide a mechanism for a verifier to validate set
membership.
The integer identifier for this Proof Type is 1. The string
identifier for this Proof Type is "inclusion". The value of this
Proof Type is array of bstr.
Section 5.2 provides a concrete example.
Steele, et al. Expires 22 April 2024 [Page 5]
Internet-Draft CoMETRE October 2023
4.3. Consistency Proof
Consistency proofs provide a mechanism for a verifier to validate the
consistency of a verifiable data structure.
The integer identifier for this Proof Type is 2. The string
identifier for this Proof Type is "consistency". The value of this
Proof Type is array of bstr.
Section 5.3 provides a concrete example.
5. RFC9162_SHA256 as a Verifiable Data Structure
This section defines how the data structures described in [RFC9162]
are mapped to the terminology defined in this document, using cbor
and cose.
RFC9162_SHA256 requires the following:
* -11111 (verifiable-data-structure): 1, the integer representing
the RFC9162_SHA256 verifiable data structure algorithm.
* -22222 (verifiable-data-proofs): a map supporting the following
proof types:
* 1 (inclusion-proof): an array of bstr representing RFC9162_SHA256
inclusion proofs
* 2 (consistency-proof): an array of bstr representing
RFC9162_SHA256 consistency proofs
5.1. Algorithm Definition
The integer identifier for this Verifiable Data Structure is 1. The
string identifier for this Verifiable Data Structure is
"RFC9162_SHA256".
See Section 3.1.
See [RFC9162], 2.1.1. Definition of the Merkle Tree, for a complete
description of this verifiable data structure.
5.2. Inclusion Proof Definition
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:
Steele, et al. Expires 22 April 2024 [Page 6]
Internet-Draft CoMETRE October 2023
inclusion-proof = [
tree-size: int
leaf-index: int
inclusion-path: [+ bstr]
]
5.2.1. Inclusion Proof Signature
In a signed inclusion proof, the previous merkle tree root, maps to
tree-size-1, and is a detached payload.
Other specifications refer to signed inclusion proofs as "receipts",
profiles of proof signatures are encouraged to make additional
protected header parameters mandatory.
TODO: reference to scitt receipts.
The protected header for an RFC9162_SHA256 inclusion proof signature
is:
* alg (label: 1): REQUIRED. Signature algorithm identifier. Value
type: int / tstr.
* verifiable-data-structure (label: -11111): REQUIRED. verifiable
data structure algorithm identifier. Value type: int / tstr.
The unprotected header for an RFC9162_SHA256 inclusion proof
signature is:
inclusion-proofs = [ + bstr ]
verifiable-proofs = {
&(inclusion-proof: 1) => inclusion-proofs
}
unprotected-header-map = {
&(verifiable-data-proof: -22222) => verifiable-proofs
* cose-label => cose-value
}
* inclusion-proof (label: 1): REQUIRED. proof type identifier.
Value type: [ + bstr ].
The payload of an RFC9162_SHA256 inclusion proof signature is the
previous Merkle tree hash as defined in [RFC9162].
The payload MUST be detached.
Steele, et al. Expires 22 April 2024 [Page 7]
Internet-Draft CoMETRE October 2023
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 Single Signer Data Object /
[
h'a3012604...392b6601', / Protected header /
{ / Unprotected header /
-22222: { / Proofs /
1: [ / Inclusion proofs (1) /
h'83040282...1f487bb1', / Inclusion proof 1 /
]
},
},
h'', / Detached payload /
h'1c0f970e...bf4bae7f' / Signature /
]
)
{ / Protected header /
1: -7, / Cryptographic algorithm to use /
4: h'68747470...6d706c65', / Key identifier /
-11111: 1 / Verifiable data structure /
}
[ / Inclusion proof 1 /
4, / Tree size /
2, / Leaf index /
[ / Inclusion hashes (2) /
h'a39655d4...d29a968a' / Intermediate hash 1 /
h'57187dff...1f487bb1' / Intermediate hash 2 /
]
]
5.3. Consistency Proof Definition
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 the tree, when the previous root was produced.
tree-size-2: int ; size of the tree, when the latest root was produced.
consistency-path: [+ bstr] ; consistency path, from previous root to latest root.
]
Steele, et al. Expires 22 April 2024 [Page 8]
Internet-Draft CoMETRE October 2023
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 Proof Signature
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:
* 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.
* kid (label: 4): OPTIONAL. Key identifier. Value type: bstr
* crit (label: 2): OPTIONAL. Criticality marker. Value type: [ +
label ]
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: -22222) => verifiable-proofs
* cose-label => cose-value
}
* consistency-proof (label: 2): REQUIRED. proof type identifier.
Value type: [ + bstr ].
The payload of an RFC9162_SHA256 consistency proof signature is:
The latest Merkle tree hash as defined in [RFC9162].
The payload MUST be attached.
Steele, et al. Expires 22 April 2024 [Page 9]
Internet-Draft CoMETRE October 2023
18( / COSE Single Signer Data Object /
[
h'a3012604...392b6601', / Protected header /
{ / Unprotected header /
-22222: { / Proofs /
2: [ / Consistency proofs (1) /
h'83040682...2e73a8ab', / Consistency proof 1 /
]
},
},
h'430b6fd7...f74c7fc4', / Payload /
h'8bcb1b79...78829bca' / Signature /
]
)
{ / Protected header /
1: -7, / Cryptographic algorithm to use /
4: h'68747470...6d706c65', / Key identifier /
-11111: 1 / Verifiable data structure /
}
[ / 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 /
]
]
6. Privacy Considerations
See the privacy considerations section of:
* [RFC9162]
* [RFC9053]
7. Security Considerations
See the security considerations section of:
* [RFC9162]
* [RFC9053]
8. IANA Considerations
Steele, et al. Expires 22 April 2024 [Page 10]
Internet-Draft CoMETRE October 2023
8.1. Additions to Existing Registries
8.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.
8.1.1.1. COSE Header Algorithm Parameters
* Name: verifiable-data-structure
* Label: -11111
* 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 proofs.
* Name: verifiable-data-proof
* Label: -222222
* Value type: int / tstr
* Value registry: https://www.iana.org/assignments/cose/
cose.xhtml#header-parameters
* Description: Location for verifiable data proofs in COSE Header
Parameters.
8.1.2. Verifiable Data Structures
IANA will be asked to establish a registry of tree algorithm
identifiers, named "Verifiable Data Structures" to be administered
under a Specification Required policy [RFC8126].
Template:
* Identifier: The two-byte identifier for the algorithm
* Algorithm: The name of the data structure
* Reference: Where the data structure is defined
Steele, et al. Expires 22 April 2024 [Page 11]
Internet-Draft CoMETRE October 2023
Initial contents: Provided in Table 1
8.1.3. Verifiable Data Structure Proof Types
IANA will be asked to establish a registry of tree algorithm
identifiers, named "Verifiable Data Structures Proof Types" to be
administered under a Specification Required policy [RFC8126].
Template:
* Identifier: The two-byte identifier for the algorithm
* Algorithm: The name of the proof type algorithm
* Reference: Where the algorithm is defined
Initial contents: Provided in Table 2
9. References
9.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, July 2016,
.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
.
[RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms
(SHA and SHA-based HMAC and HKDF)", RFC 6234,
DOI 10.17487/RFC6234, May 2011,
.
[RFC6962] Laurie, B., Langley, A., and E. Kasper, "Certificate
Transparency", RFC 6962, DOI 10.17487/RFC6962, June 2013,
.
[RFC6979] Pornin, T., "Deterministic Usage of the Digital Signature
Algorithm (DSA) and Elliptic Curve Digital Signature
Algorithm (ECDSA)", RFC 6979, DOI 10.17487/RFC6979, August
2013, .
Steele, et al. Expires 22 April 2024 [Page 12]
Internet-Draft CoMETRE October 2023
[RFC7049] Bormann, C. and P. Hoffman, "Concise Binary Object
Representation (CBOR)", RFC 7049, DOI 10.17487/RFC7049,
October 2013, .
[RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital
Signature Algorithm (EdDSA)", RFC 8032,
DOI 10.17487/RFC8032, January 2017,
.
[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, June 2017,
.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, .
[RFC8949] Bormann, C. and P. Hoffman, "Concise Binary Object
Representation (CBOR)", STD 94, RFC 8949,
DOI 10.17487/RFC8949, December 2020,
.
[RFC9053] Schaad, J., "CBOR Object Signing and Encryption (COSE):
Initial Algorithms", RFC 9053, DOI 10.17487/RFC9053,
August 2022, .
[RFC9162] Laurie, B., Messeri, E., and R. Stradling, "Certificate
Transparency Version 2.0", RFC 9162, DOI 10.17487/RFC9162,
December 2021, .
9.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, 20 September 2022,
.
[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-03, 16
October 2023, .
Steele, et al. Expires 22 April 2024 [Page 13]
Internet-Draft CoMETRE October 2023
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 (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".
Steele, et al. Expires 22 April 2024 [Page 14]
Internet-Draft CoMETRE October 2023
A.5. Coverage and Version Compatibility
The current version ('main') implements the tree 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
Email: orie@transmute.industries
Henk Birkholz
Fraunhofer SIT
Rheinstrasse 75
64295 Darmstadt
Germany
Email: henk.birkholz@sit.fraunhofer.de
Steele, et al. Expires 22 April 2024 [Page 15]
Internet-Draft CoMETRE October 2023
Antoine Delignat-Lavaud
Microsoft
United Kingdom
Email: antdl@microsoft.com
Cedric Fournet
Microsoft
United Kingdom
Email: fournet@microsoft.com
Steele, et al. Expires 22 April 2024 [Page 16]