Proof of Existence

Chainscript Segments can be notarized in a blockchain as a proof of existence or a proof of anteriority.

Proofs of existence are often backed by a Merkle proof and a blockchain transaction with the Merkle proof in it (eg in the case of Bitcoin, it would be using OP_RETURN).

The merkle proof can be saved in the meta.evidence of the Segment. When the meta.evidence.state is “COMPLETE”, it indicates that a transaction has been broadcasted to the blockchain network. This allows others to validate the audit trail of the Segment using methods that are publicly accessible.

Merkle trees

A Merkle tree is a data structure that is able to take n number of hashes and represent it with a single hash.

A Merkle tree proof is generated by taking the hash of one leaf of the tree and hashing it with its neighbouring hash. The parent hash then hashes with its neighbour until the root hash is calculated. Leaf hashes can be verified against the root hash by following the tree from leaf and neighbour back to the root.

Merkle tree Diagram

Image via Wikipedia. Learn More about Merkle trees on Wikipedia.

Merkle Proofs

The Merkle root represents all the hashes in the tree where if one hash is modified the entire tree is invalid. Thus, with the Merkle tree path corresponding with the Blockchain transaction, one can guarantee the proof-of-existence of the unmodified dataset.

From the Merkle proof the path can be validated by concatenating the left and right hash, and validating the result against the parent. This step is repeated until the Merkle root is found.

The transaction hash and blockchain will be included in the Objective Evidence for validating the Merkle root. As an example, for the Bitcoin Blockchain, the Merkle root is stored using the OP_RETURN opt code.

The format is the following:

{
  "merkleRoot": "855e019f67bc5ba09b7efb3a9e169bbe14e6abafa5b02d686607e25107db1b4c",
  "merklePath": [
    {
      "left": "fa871e81c469fa947eacd40f89dc5627a0cb3a96551a651c034787c752d4448e",
      "right": "aa1331b6f1155fff5865116e5adcb6e4cdf0435fc2bd68053a4d24795f47dad3",
      "parent": "39b43545134a903dd16be3d0b5391474ef82241acd33e8496b103ee8d378efea"
    },
    {
      "left": "39b43545134a903dd16be3d0b5391474ef82241acd33e8496b103ee8d378efea",
      "right": "9fb3164966231fca20c75a562d0b4c1e7adc68738ac6c179dd1ecf921845dbfd",
      "parent": "fedacd347e84d39ab3122f78d762dbbc79646704deb90fbb118b140c85f4df96"
    },
    {
      "left": "d7fa0ed22e4b58eb227a826a1d2f0ef564f5052172bd36fe612a2fa214d452c8",
      "right": "fedacd347e84d39ab3122f78d762dbbc79646704deb90fbb118b140c85f4df96",
      "parent": "7e7dec576382e948f4980e4295f6ef9b89748e4586723a7b9481ee20cfb14db5"
    },
    {
      "left": "2c0ada2bdea45977acd0a4d56fda6f970f34df32a1e507e99cd7284c0038b22a",
      "right": "7e7dec576382e948f4980e4295f6ef9b89748e4586723a7b9481ee20cfb14db5",
      "parent": "fe7214757ed9d701a2ed112d01c1b17a734094444ee067dd2ee4c14907419a24"
    },
    {
      "left": "dae80a5aa2b397285ce6ca079c78dad737099d293a8783d4b8680efff57e921e",
      "right": "fe7214757ed9d701a2ed112d01c1b17a734094444ee067dd2ee4c14907419a24",
      "parent": "5f9343488c91f22a0cfea5c9797e244c1a6d20872048e157e515a1172678ebcf"
    }
  ],
  "transactions": {
    "bitcoin:testnet": "15359dc0ef4c430d6219d07e0dd7be96442af20ffd6f79727559028a06518474"
  }
}

You can verify that a Merkle proof is valid on your own without using any proprietary tools. It uses standard cryptographic functions which are available in many programming languages.

Here is a script to do it using Node.js:

var crypto = require('crypto');

// The `canonical-json` package is required.
// You can install it with `npm install canonical-json`.
var stringify = require('canonical-json');

// Computes the canonical hash of a JSON object.
function hashJson(obj) {
  var hash = crypto.createHash('sha256');
  hash.update(stringify(obj));
  return hash.digest();
}

// Returns whether the Merkle proof of a Chainscript state is valid.
function verifyMerkleProof(segment) {
  var hash = hashJson(segment.link);
  var evidence = segment.meta.evidence;

  var merklePath = evidence.merklePath;

  // Check levels one by one
  for (var i = 0; i < merklePath.length; i++) {
    var level = merklePath[i];
    var left = new Buffer(level.left, 'hex');

    if (level.right) {
      var right = new Buffer(level.right, 'hex');
    }

    // Make sure hash is in the current level
    if (hash.compare(left) !== 0 && (!right || hash.compare(right) !== 0)) {
      return false;
    }

    // Compute parent hash
    if (right) {
      var parent = crypto
        .createHash('sha256')
        .update(Buffer.concat([left, right]))
        .digest();
    } else {
      parent = left;
    }

    // Make sure parent hash is corrent
    if (parent.compare(new Buffer(level.parent, 'hex')) !== 0) {
      return false;
    }

    hash = parent;
  }

  // Make sure root is correct
  return hash.compare(new Buffer(evidence.merkleRoot, 'hex')) === 0;
}

module.exports = verifyMerkleProof;