@cedoor/smt v0.1.7

A sparse Merkle tree (SMT) 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. SMTs 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.

Notice: this library is still not stable and therefore it must be used with care.

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.

Table of Contents

• 🛠 Install
• 📜 API reference
• 🔬 Development
  • Rules
    • Commits
    • Branches
• 🧾 MIT License
• ☎️ Contacts
  • Developers

Install

npm or yarn

You can install utils package with npm:

npm i @cedoor/smt --save

or with yarn:

yarn add @cedoor/smt

CDN

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

<script src="https://unpkg.com/@cedoor/smt/"></script>

or JSDelivr:

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

API reference

• Creating trees
• Adding entries
• Getting values
• Updating values
• Deleting entries
• Creating proofs
• Verifying proofs

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

import { SMT, hexToDec } from "@cedoor/smt"
import { sha256 } from "js-sha256"
import { poseidon } from "circomlib"

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

// Big number hashes.
const hash2 = (childNodes: ChildNodes) => poseidon(childNodes)
const tree2 = new SMT(hash, 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,
    sidenodes: [
        '006a0ab15a212e0e0126b81e056b11576628b1ad80792403dbb3a90be2e71d64',
        'f786ce5a843614d7da216d95c0087c1eb29244927feeeeeb658aa60cf124cd5e'
    ],
    root: 'c3c023c84afc0a7bab1dbebcef5f7beaf3d6af4af98e8f481620dec052be7d0d',
    membership: true
}
*/

console.log(nonMembershipProof)
/*
{
    entry: [ '16' ],
    matchingEntry: undefined,
    sidenodes: [
        '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 : me@cedoor.dev
• github : @cedoor
• website : https://cedoor.dev