A sparse Merkle tree is a data structure useful for storing a key/value map where every leaf node of the tree contains the cryptographic hash of a key/value pair and every non leaf node contains the concatenated hashes of its child nodes. Sparse Merkle trees provides a secure and efficient verification of large data sets and they are often used in peer-to-peer technologies. This implementation is an optimized version of the traditional sparse Merkle tree and it is based on the concepts expressed in the papers and resources below.

References

1. Rasmus Dahlberg, Tobias Pulls and Roel Peeters. Efficient Sparse Merkle Trees: Caching Strategies and Secure (Non-)Membership Proofs. Cryptology ePrint Archive: Report 2016/683, 2016. https://eprint.iacr.org/2016/683.
2. Faraz Haider. Compact sparse merkle trees. Cryptology ePrint Archive: Report 2018/955, 2018. https://eprint.iacr.org/2018/955.
3. Jordi Baylina and Marta Bellés. Sparse Merkle Trees. https://docs.iden3.io/publications/pdfs/Merkle-Tree.pdf.
4. Vitalik Buterin Fichter. Optimizing sparse Merkle trees. https://ethresear.ch/t/optimizing-sparse-merkle-trees/3751.

Install

npm or yarn

You can install @zk-kit/smt package with npm:

npm i @zk-kit/smt --save

or yarn:

yarn add @zk-kit/smt

CDN

You can also load it using a script tag using unpkg:

<script src="https://unpkg.com/@zk-kit/smt"></script>

or JSDelivr:

<script src="https://cdn.jsdelivr.net/npm/@zk-kit/smt"></script>

📜 Usage

# new SMT(hash: HashFunction, bigNumbers?: boolean): SMT

import { SMT } from "@zk-kit/smt"
import sha256 from "crypto-js/sha256"
import { poseidon } from "circomlibjs"

// Hexadecimal hashes.
const hash = (childNodes: ChildNodes) => sha256(childNodes.join("")).toString()
const tree = new SMT(hash)

// Big number hashes.
const hash2 = (childNodes: ChildNodes) => poseidon(childNodes)
const tree2 = new SMT(hash2, true)

console.log(tree.root) // 0
console.log(tree2.root) // 0n

# add(key: string | number, value: string | number): void

tree.add("2b", "44") // Hexadecimal key/value.
tree.add("16", "78")
tree.add("d", "e7")
tree.add("10", "141")
tree.add("20", "340")

console.log(tree.root) // 31ee2a59741c9c32a32d8c7fafe461cca1ccaf5986c2d592586e3e6482a48645

# get(key: string | number): undefined | string

const value = tree.get("16")

console.log(value) // 78

# update(key: string | number, value: string | number): void

tree.update("16", "79")

const value = tree.get("16")

console.log(value) // 79

# delete(key: string | number): void

tree.delete("16")

const value = tree.get("16")

console.log(value) // undefined

# createProof(key: string | number): Proof

const membershipProof = tree.createProof("2b")
const nonMembershipProof = tree.createProof("16") // This key has been deleted.

console.log(membershipProof)
/*
{
    entry: [ '2b', '44', '1' ],
    matchingEntry: undefined,
    siblings: [
        '006a0ab15a212e0e0126b81e056b11576628b1ad80792403dbb3a90be2e71d64',
        'f786ce5a843614d7da216d95c0087c1eb29244927feeeeeb658aa60cf124cd5e'
    ],
    root: 'c3c023c84afc0a7bab1dbebcef5f7beaf3d6af4af98e8f481620dec052be7d0d',
    membership: true
}
*/

console.log(nonMembershipProof)
/*
{
    entry: [ '16' ],
    matchingEntry: undefined,
    siblings: [
        '960f23d9fbb44241be53efb7c4d69ac129bb1cb9482dcb6789d3cc7e6de2de2b',
        '2a1aef839e68d1bdf43c1b3b1ed9ef16c27162e8a175898c9ac64a679b0fc825'
    ],
    root: 'c3c023c84afc0a7bab1dbebcef5f7beaf3d6af4af98e8f481620dec052be7d0d',
    membership: false
}
*/

# verifyProof(proof: Proof): boolean

console.log(tree.verifyProof(membershipProof)) // true
console.log(tree.verifyProof(nonMembershipProof)) // true

Contacts

Developers

• e-mail : [email protected]
• github : @cedoor
• website : https://cedoor.dev