indexed-merkle-noir

Indexed Merkle Tree implementation in Javascript and Noir

• Keys can be max 64-bit uints
• Values can be any field element
• Max tree size: 2^32 items

TODO

• Multi-inserts

Installation

$ git clone https://github.com/numtel/indexed-merkle-noir
$ cd indexed-merkle-noir
$ npm install

# Test javascript implementation
$ npm test

# Test noir implementation
$ nargo test

JavaScript Usage

The IndexedMerkleTree class provides methods to create and manage an indexed Merkle tree.

import {IndexedMerkleTree} from 'indexed-merkle-noir';

// Create a new tree
const tree = new IndexedMerkleTree();

// Insert an item (key must be bigint > 0, value must be bigint >= 0)
tree.insertItem(10n, 345n);
tree.insertItem(20n, 234n);
const transitionProof = tree.insertItem(30n, 123n);

// Generate proof for a key
const proof = tree.generateProof(20n);
// Returns { leafIdx, leaf, root, siblings }

// Generate exclusion proof (proves a key does NOT exist)
const exclusionProof = tree.generateExclusionProof(13n);
// Returns proof for neighboring key that proves 13n doesn't exist

// Verify a proof
const isValid = tree.verifyProof(proof);
const isValidInsert = tree.verifyInsertionProof(transitionProof);
// Returns true if proof is valid

IndexedMerkleTree Methods

• constructor(): Creates a new indexed Merkle tree
• insertItem(key, value): Inserts a new item with the given key and value
  • key: bigint greater than 0
  • value: bigint greater than or equal to 0
  • Returns insertion proof data object
• generateProof(key): Generates a Merkle proof for the given key
  • Returns {leafIdx, leaf, root, siblings}
• generateExclusionProof(key): Generates a proof that a key doesn't exist in the tree
  • Returns proof for a neighboring key that proves the target key doesn't exist
• verifyProof(proof): Verifies a Merkle proof
  • Returns true if valid, false otherwise
• verifyInsertionProof(insertionProof): Verifies an insertion proof
  • Returns true if valid, false otherwise

Noir Library Functions

The Noir library includes functions for verifying proofs generated by the JavaScript implementation:

verifyProof

Verifies that a leaf with the given properties exists in the Merkle tree.

fn verifyProof(
    leafIdx: u32,
    leafKey: u64,
    leafNextIdx: u32,
    leafNextKey: u64,
    leafValue: Field,
    root: Field,
    siblings: [Field; 32]
)

verifyExclusionProof

Verifies that a key does NOT exist in the Merkle tree.

fn verifyExclusionProof(
    leafIdx: u32,
    leafKey: u64,
    leafNextIdx: u32,
    leafNextKey: u64,
    leafValue: Field,
    root: Field,
    siblings: [Field; 32],
    excludedKey: u64
)

This function verifies:

1. The proof is valid (calls verifyProof)
2. The excluded key is greater than the leaf key
3. The excluded key is less than the next key (if next key exists)

verifyInsertionProof

Verifies that the tree root state transition is valid for the given insertion

fn verifyInsertionProof(
    ogLeafIdx: u32,
    ogLeafKey: u64,
    ogLeafNextIdx: u32,
    ogLeafNextKey: u64,
    ogLeafValue: Field,
    newLeafIdx: u32,
    newLeafKey: u64,
    newLeafValue: Field,
    rootBefore: Field,
    rootAfter: Field,
    siblingsBefore: [Field; 32],
    siblingsAfterOg: [Field; 32],
    siblingsAfterNew: [Field; 32]
)

This function verifies:

1. All three individual proofs must be valid
2. Sibling arrays for both leaves are same length
3. The "sub-roots" of both changed leaves match

License

MIT