Merkle Tools

Nexscript 1.0.0 introduces extended tools to interact with Merkle trees and validate item inclusion in a dataset in decentralized and permissionless fashion.

Currently the merkleRoot macro is an emulation of a proposed OP_MERKLE opcode.

Limitations

merkleRoot macro beingh emulated comes with some limitations. The main one comes from the amount of opcodes needed for emulation, the larger (and deeper) the tree gets the more VM logic needs to be applied. The base cost for this macro is 12 opcodes, with additional 5 opcodes per each tree height. Tree height is Math.floor(Math.log2(nElements - 1) + 1). So for 1000 elements in the dataset, the resulting code would require 62 opcodes. It is advised to choose the max tree capacity before deploying contracts.

Applications

Merkle Database

The idea behind the Merkle Database is to enable the contract users to propose the next state of a decentralized database in a permissionless and trustless fashion, while owners of the database can also update the elements in it knowing the exact contents of it.

// lastElement index is dataset size - 1
contract merkleDatabase(bytes20 root, int lastElementIndex) {
  function append(bytes proof, bytes20 lastLeaf, bytes20 newLeaf) {

    // VALIDATE the existence of chosen leaf.
    bytes20 generatedRoot = merkleRoot(2, proof, lastElementIndex, lastLeaf ); // Generate a merkle root from the merkle proof.
    require(generatedRoot == root); //Validate that the merkle proof is valid.

    // APPEND the chosen leaf to the new leaf.
    lastElementIndex = lastElementIndex + 1; // Increment the leaf index.
    bytes20 generatedRootNew = merkleRoot(2, proof, lastElementIndex, newLeaf ); // Generate a merkle root for the new merkle leaf.

    // Apply changes to child UTXO
    bytes20 templateHash = hash160(this.activeBytecode); // Extract the template hash from the lockingbytecode
    bytes20 constraintHash = hash160(encodeData(generatedRootNew) + encodeNumber(lastElementIndex)); // Create the new constraintScript with the new root and new lastElementIndex.
    bytes newContractLock = new LockingBytecodeP2ST(templateHash, constraintHash, bytes(0x)); // Generate new locking byte code for the child UTXO.
    require(tx.outputs[0].lockingBytecode == newContractLock); // Lock the locking script for the child UTXO.
  }

  function update(bytes proof, int leafIndex, bytes20 leaf, bytes20 newLeaf) {

    // VALIDATE the existence of chosen leaf.
    bytes20 generatedRoot = merkleRoot(2, proof, leafIndex, leaf ); // Generate a merkle root from the merkle proof.
    require(generatedRoot == root); //Validate that the merkle proof is valid.

    // UPDATE the chosen leaf to the new leaf.
    bytes20 generatedRootNew = merkleRoot(2, proof, leafIndex, newLeaf ); // Generate a merkle root for the new merkle leaf.

    // Apply changes to child UTXO
    bytes20 templateHash = hash160(this.activeBytecode); // Extract the template hash from the lockingbytecode
    bytes20 constraintHash = hash160(encodeData(generatedRootNew) + encodeNumber(lastElementIndex)); // Create the new constraintScript with the new root.
    bytes newContractLock = new LockingBytecodeP2ST(templateHash, bytes(constraintHash), bytes(0x)); // Generate new locking byte code for the child UTXO.
    require(tx.outputs[0].lockingBytecode == newContractLock); // Lock the locking script for the child UTXO.
  }
}

See nexscript/test/e2e/Merkle.test.ts:342 for sample code to validate, update and extend contents of such database.