TypeScript icon, indicating that this package has built-in type declarations

1.0.0 • Public • Published

Sparse Merkle tree

Sparse Merkle tree implementation in TypeScript.

Github license NPM version Downloads npm bundle size (scoped) Linter eslint Code style prettier

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.


  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.


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


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


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.

    entry: [ '2b', '44', '1' ],
    matchingEntry: undefined,
    siblings: [
    root: 'c3c023c84afc0a7bab1dbebcef5f7beaf3d6af4af98e8f481620dec052be7d0d',
    membership: true

    entry: [ '16' ],
    matchingEntry: undefined,
    siblings: [
    root: 'c3c023c84afc0a7bab1dbebcef5f7beaf3d6af4af98e8f481620dec052be7d0d',
    membership: false

# verifyProof(proof: Proof): boolean

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



Package Sidebar


npm i @zk-kit/smt

Weekly Downloads






Unpacked Size

95.4 kB

Total Files


Last publish


  • njofce
  • akinovak
  • cedoor