This specification describes a signature option that provides the ability to cryptographically prove when a digital signature was created by anchoring the signature to a hash in a publically available merkle tree.

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

Introduction

This specification describes a signature option that provides the ability to cryptographically prove when a digital signature was created by anchoring the signature to a hash in a publically available merkle tree. This signature option is intended to be used with the signature options data structure used in the Linked Data Signatures [[!LD-SIGNATURES]] specification.

Terminology

The following terms are used to describe concepts involved in the generation and verification of the Proof of Publication signature option.

signature options
A set of options that is included in the Linked Data Signatures [[!LD-SIGNATURES]] signature data.
merkle tree
A tree in which every non-leaf node is labelled with the hash of the labels or values (in case of leaves) of its child nodes. Wikipedia has a more complete definition.
signature suite
A specified set of cryptographic primitives typically consisting of a canonicalization algorithm, a message digest algorithm, and a signature algorithm that are bundled together by cryptographers for developers for the purposes of safety and convenience.

Constructing a Proof of Publication

A merkle tree-based proof of publication is generated by adding a merkle tree root hash value into a ledger then including a proof in the digital signature. There are several values that MUST be included in order to ensure the proof is valid: a proof of publication algorithm identifier, a ledger identifier, a transaction identifier, the merkle root hash and an array of proofs where each entry in the array is a combination of the parent, the left sibling, and the right sibling.

Another alternative is to include the path from our entry back to the merkle root. We're trying to minimize the data that goes into the signature by making it extremely unlikely that the three hashes just happen to be clustered elsewhere in the same tree. We need to calculate the statistical probability of this happening (hint: it's fantastically unlikely, but we need to think through the threat model).

This algorithm is still too vague for implementers. For example: How do you know what information to include in the merkle leaf nodes when generating the hash? Do you just include all of it? Is it okay to select the same message digest algorithm as what's used in the active signature suite?

The term "proof" is not specific enough. It should either be made more specific or replaced with something like `merklePath` should it be determined that a full path is necessary for security.

To generate the proof of publication, perform the following steps:

  1. Add all desired entries to a merkle tree.
  2. Let array of entries be an empty array.
  3. For each merkle tree entry that is being included in the proof, add an entry to array of entries with the following key-value pairs:
    merkleParent
    A message digest of the parent node for the entry in the merkle tree using the same message digest algorithm as specified in the active signature suite.
    merkleLeftSibling
    A message digest of the left sibling node for the entry in the merkel tree using the same message digest algorithm as specified in the active signature suite.
    merkleRightSibling
    A message digest of the right sibling node for the entry in the merkel tree using the same message digest algorithm as specified in the active signature suite.
  4. Let merkle root hash be the hash of the root node of the merkle tree using the same message digest algorithm as specified in the active signature suite.
  5. Add the merkle root hash to the ledger recording the ledger identifier and the transaction identifier.
  6. Return the following data structure:
    type
    The value PoP2016.
    ledger
    The value of ledger identifier.
    Should this be a URL? URN? We should probably not require a registry.
    transactionId
    The value of transaction identifier.
    merkleRoot
    The value of merkle root hash.
    proof
    The value of array of entries.
The data structure returned above should then be associated with a merklePublicationProof and included in signature options before the signature is generated.

Verifying a Proof of Publication

A merkle tree-based proof of publication is verified by checking to see if a value exists in a ledger at the appropriate time. The input is a signature options document containing a merklePublicationProof entry. The output is true if the proof is valid, or false if it is not.

To verify the proof of publication, perform the following steps:

  1. Ensure that the type value is PoP2016.
  2. Extract the ledger identifier, the transaction identifier, and merkle root hash from the signature options.
  3. If the merkle root hash does not exist in the transaction identified by transaction identifier on the ledger identified by ledger identifier, return false.
    This isn't right, we need to also check a timestamp of some kind. We have a timestamp in the Linked Data Signature, but it may not be aligned w/ the timestamp in the ledger. What timing tolerances do we allow? Should we just record the ledger transaction timestamp?
  4. Extract array of entries from the signature options.
  5. For each entry in array of entries:
    1. If the parent, left sibling, and right sibling, does not exist in the merkle tree, return false.
  6. Return true.

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.

Proof of Publication Examples

{
  "@context": "https://w3id.org/identity/v1",
  "title": "Hello World!",
  "signature": {
    "type": "LinkedDataSignature2015",
    "creator": "http://example.com/i/pat/keys/5",
    "created": "2011-09-23T20:21:34Z",
    "domain": "example.org",
    "nonce": "2bbgh3dgjg2302d-d2b3gi423d42",
    "merklePublicationProof": {
      "type": "PoP2016",
      "ledger": "bitcoin",
      "transactionId": "7ea0cef6a31c65590d6c1d61abbfa02d3006da6509a018cdbc709d0a781a7c28",
      "merkleRoot": "80ab866e989432e023b51e866545c141e00d456e59fa1e253fac3a561e1a6c14",
      "proof": [{
        "merkleParent": "f51cd07057a813f92a33a05ed58a0f26600d2205f9c590f3461f94bd8451b567",
        "merkleLeftSibling": "247911c653b43a2d13010538c7eae52e500a556448f17384d636857b2b63ae45",
        "merkleRightSibling": "93ca67aea78e996fb9e10368243110c6f037143dbeec726de0b9172766427399"
      }, {
        "merkleParent": "e6a881dd07c479eaf2afdd26ae34b441af2fede85c90b5281346846a5dc81bca",
        "merkleLeftSibling": "44c66b49e4024bf1ba370c38a3655f2094cd110caf91636f749d9e0385fb9272",
        "merkleRightSibling": "93ca67aea78e996fb9e10368243110c6f037143dbeec726de0b9172766427399"
      ]
    },
    "signatureValue": "OGQzNGVkMzVm4NTIyZTkZDY...NmExMgoYzI43Q3ODIyOWM32NjI="
  }
}