This specification describes the Merkle Proof Signature Suite created in 2019 for the Linked Data Proofs specification.

This is an experimental specification and is undergoing regular revisions. It is not fit for production deployment.

Introduction

This specification describes the Merkle Proof Signature Suite created in 2019 for the Linked Data Proofs [[LD-PROOFS]] specification. It uses the RDF Dataset CANONICALIZATION Algorithm [[RDF-DATASET-CANONICALIZATION]] to transform the input document into its canonical form. It uses SHA-256 [[RFC6234]] as the message digest algorithm and ECDSA signature algorithm with a secp256k1 curve described in [[LDS-ECDSA-SECP256K1-2019]] as the proof algorithm.

Terminology

The following terms are used to describe concepts involved in the generation and verification of the Linked Data Proof 2019 proof suite.

proof suite
A specified set of cryptographic primitives typically consisting of a canonicalization algorithm, a message digest algorithm, and a proof algorithm that are bundled together by cryptographers for developers for the purposes of safety and convenience.
canonicalization algorithm
An algorithm that takes an input document that has more than one possible representation and always transforms it into a canonical form. This process is sometimes also called CANONICALIZATION.
message digest algorithm
An algorithm that takes an input message and produces a cryptographic output message that is often many orders of magnitude smaller than the input message. These algorithms are often 1) very fast, 2) non-reversible, 3) cause the output to change significantly when even one bit of the input message changes, and 4) make it infeasible to find two different inputs for the same output.
proof algorithm
An algorithm that takes an input message and produces an output value where the receiver of the message can mathematically verify that the message has not been modified in transit and came from someone possessing a particular secret.

The 2019 Merkle Proof Signature Suite

The 2019 Merkle Proof proof suite MUST be used in conjunction with the signing and verification algorithms in the Linked Data Proofs [[LD-PROOFS]] specification. The suite consists of the following algorithms:

Parameter Value Specification
canonicalizationAlgorithm https://w3id.org/security#GCA2015 [[RDF-DATASET-CANONICALIZATION]]
digestAlgorithm https://tools.ietf.org/html/rfc6234 [[RFC6234]]
signatureAlgorithm https://w3c-ccg.github.io/lds-ecdsa-secp256k1-2019 [[LDS-ECDSA-SECP256K1-2019]]

Modification to Algorithms

This signature suite uses the root hash of the Merkle Tree defined in [[RFC6962]] and [[LDS-ECDSA-SECP256K1-2019]]. The signature algorithm uses the Merkle Tree root hash, stored in the input data of a Bitcoin or Ethereum transaction with ECDSA signature.

Modifications to Signature Algorithm

The digital signature algorithm defined in Section 7.1: Signature Algorithm takes an array of tbs, a privateKey, and options as inputs and produces a proofValue as an output.

  1. Take an array of tbs, which is an array of the data to be signed, as input and generate a Merkle Tree.
  2. Include the root of the Merkle Tree ("Merkle Root") in the data field of the Blockchain (Bitcoint or Ethereum) transaction. For Bitcoin this is the OP_RETURN field. For Ethereum this is data field of the transaction.
  3. Sign the transaction with encoding of privateKey appropriate for the blockchain. For Bitcoin this is a WIF encoding. Per the signature suite definition, this is using [[LDS-ECDSA-SECP256K1-2019]].
  4. For each tbs, create the proof object, which includes:
    • The hash of the element as targetHash
    • The merkle root as merkleRoot
    • The Merkle Proof for tbs, which is the path from targetHash to merkleRoot in the Merkle Tree, as proof. The should not include the endpoints of the path (targetHash and merkleRoot)
    • The blockchain anchor(s) as anchors. This describes how to look up the blockchain transaction. Its fields include the blockchain, the network, the transaction hash and optionally the block as blink (Blockchain Links specification). The URL format of a Blockchain Link is the following: blink:::[:]
  5. Encode resulting object using Concise Binary Object Representation (CBOR) [[RFC7049]] according to the algorithm described below. Encode resulting array buffer using multi-base base58btc encoding and return the result string as proofValue.

Compressing and encoding proofValue using CBOR

The proofValue object descrined in the previous step must be encoded using CBOR before encoding the result using base58btc.

  1. Convert JSON proofValue into a map. The keys must be replaced with the corresponding numeric IDs from the keymap:
    • merkleRoot: 0
    • targetHash: 1
    • anchors: 2
      • BLOCKCHAIN: 0
      • NETWORK: 1
      • TRANSACTION: 2
      • BlOCK: 3 (optional)
    • path: 3
      • left: 0
      • right: 1
  2. Every hexadecimal string value must be encoded using CBOR Major Type 2.
  3. Constant string values, such as a blockchain name or a network must be substituted using the corresponding numeric key from the blockchain keymap below.

Blockchain keymap

  • btc: 0
    • mainnet: 1
    • testnet: 3
  • eth: 1
    • mainnet: 1
    • ropsten: 3
    • rinkeby: 4
Add more blockchains and networks.

Modifications to Signature Verification Algorithm

Prior to verifying the signature, proofValue object must be reconstructed from CBOR / multo-base encoded string.

In order to do that, a reverse algorithm to Compressing and encoding proofValue using CBOR must be applied.

The digital signature algorithm defined in Section 7.2: Signature Verification Algorithm takes the value to be verified, a tbv, the public key to the signature algorithm and returns a boolean value.

  1. Validate the values targetHash, path, and merkleRoot form a valid Merkle Path.
  2. Verify that targetHash matches the JSON-LD canonicalized, SHA256 Hash of tbv.
  3. Verify merkleRoot matches what is stored in the transaction at blink URL (Blockchain Link).
  4. If all of the above checks pass, return true, otherwise return false.

Security Considerations

The following section describes security considerations that developers implementing this specification should be aware of in order to create secure software.

TODO: We need to add a complete list of security considerations.

Examples

A simple example of a decoded proofValue: 

        "proofValue": {
          "path": [
            { "right": "51b4e22ed024ec7f38dc68b0bf78c87eda525ab0896b75d2064bdb9fc60b2698" },
            { "right": "61c56cca660b2e616d0bd62775e728f50275ae44adf12d1bfb9b9c507a14766b" }
          ],
          "merkleRoot": "3c9ee831b8705f2fbe09f8b3a92247eed88cdc90418c024924be668fdc92e781", 
          "targetHash": "c65c6184e3d5a945ddb5437e93ea312411fd33aa1def22b0746d6ecd4aa30f20",
          "anchors": [
            "blink:btc:testnet:582733d7cef8035d87cecc9ebbe13b3a2f6cc52583fbcd2b9709f20a6b8b56b3"
          ]
        }

An example of CDDL for CBOR-encoded proofValue: 

        84                                     # array(4)
          82                                   # array(2)
             03                                # unsigned(3)
             82                                # array(2)
                82                             # array(2)
                   01                          # unsigned(1)
                   58 22                       # bytes(34)
                      582051B4E22ED024EC7F38DC68B0BF78C87EDA525AB0896B75D2064BDB9FC60B2698 # "X Q\xB4\xE2.\xD0$\xEC\x7F8\xDCh\xB0\xBFx\xC8~\xDARZ\xB0\x89ku\xD2\x06K\xDB\x9F\xC6\v&\x98"
                82                             # array(2)
                   01                          # unsigned(1)
                   58 22                       # bytes(34)
                      582061C56CCA660B2E616D0BD62775E728F50275AE44ADF12D1BFB9B9C507A14766B # "X a\xC5l\xCAf\v.am\v\xD6'u\xE7(\xF5\x02u\xAED\xAD\xF1-\e\xFB\x9B\x9CPz\x14vk"
          82                                   # array(2)
             00                                # unsigned(0)
             58 22                             # bytes(34)
                58203C9EE831B8705F2FBE09F8B3A92247EED88CDC90418C024924BE668FDC92E781 # "X <\x9E\xE81\xB8p_/\xBE\t\xF8\xB3\xA9\"G\xEE\xD8\x8C\xDC\x90A\x8C\x02I$\xBEf\x8F\xDC\x92\xE7\x81"
          82                                   # array(2)
             01                                # unsigned(1)
             58 22                             # bytes(34)
                5820C65C6184E3D5A945DDB5437E93EA312411FD33AA1DEF22B0746D6ECD4AA30F20 # "X \xC6\\a\x84\xE3\xD5\xA9E\xDD\xB5C~\x93\xEA1$\x11\xFD3\xAA\x1D\xEF\"\xB0tmn\xCDJ\xA3\x0F "
          82                                   # array(2)
             02                                # unsigned(2)
             81                                # array(1)
                83                             # array(3)
                   82                          # array(2)
                      00                       # unsigned(0)
                      00                       # unsigned(0)
                   82                          # array(2)
                      01                       # unsigned(1)
                      03                       # unsigned(3)
                   82                          # array(2)
                      02                       # unsigned(2)
                      58 22                    # bytes(34)
                         5820582733D7CEF8035D87CECC9EBBE13B3A2F6CC52583FBCD2B9709F20A6B8B56B3 # "X X'3\xD7\xCE\xF8\x03]\x87\xCE\xCC\x9E\xBB\xE1;:/l\xC5%\x83\xFB\xCD+\x97\t\xF2\nk\x8BV\xB3"

A simple example of a Merkle Proof Signature Suite 2019 signature (proofValue encoded): 

      "proof": {
        "@context": ["https://w3id.org/security/v2"],
        "type": "MerkleProof2019",
        "creator": "did:example:abcdefghij0123456789",
        "created": "2019-10-16T20:21:34Z",
        "domain": "example.org",
        "nonce": "2bbgh3dgjg2302d-d2b3gi423d42",
        "proofValue": "z6nGv6rMRybRe9CuMzbQbdu7sA858v1d13JU3hoAr1x93cheinB35kDXqCvaA93WTLWGtLZMdQSvvNCxEMZPhLvDa4CbUYkm4pCwBe7kCZAsuwHZwHxgyzCbRUWFbMXHhkVSHoPYmPzfi4arfHKMgKSurZ7oqe3GHRdi78TbHGvA65edK8JBEdTUt8SpCdc7wz5qiwj3THtcNAXfgK4LmCAu4fq8CnjLcMtGoEdfXfjy3turtaTapyM3katuYKAzbJF3FiE8i8NXBsiBnEbvKk7k"
      }