Pyt-merkle-sum-tree NPM

pyt-merkle-sum-tree

TypeScript library to create Merkle Sum Trees starting from username -> balance entries. The root of the tree contains the sum of all the entries, representing the total liabilities of a CEX.

This package is a fork of ZK-KIT

What is a Merkle Sum Tree?

A Merkle Sum Tree is a binary Merkle Tree with the following properties:

Each entry of a Merkle Sum Tree is a pair of a username and a balance.
Each Leaf Node contains a hash and a sum. The hash is equal to H(username, balance). The sum is equal to the balance itself.
Each Middle Node contains a hash and a sum. The hash is equal to H(LeftChild.hash, LeftChild.sum, RightChild.hash, RightChild.sum). The sum is equal to the sum of the sums of its children.
The Root Node represents the committed state of the Tree and contains the sum of all the entries' balances. The MerkleSumTree class is a TypeScript implementation of a Merkle Sum tree and it provides all the functions to create a tree starting from a csv file that contains a list of entries in the format username -> balance.

Setup

npm install pyt-merkle-sum-tree
Import your database of users and their balances to a csv file, for example entry-16-valid.csv.

APIs - Merkle Sum Tree

# new MerkleSumTree(pathToCsv: string): MerkleSumTree

import { MerkleSumTree } from "pyt-merkle-sum-tree"

const pathToCsv = "test/entries/entry-16-valid.csv" 

const tree = new MerkleSumTree(pathToCsv) // Init a tree from the entries in the csv file

# entries: []Entry

The entries contains the username parsed as a BigInt. This transformation is performed here. We need the username to be express as BigInt in order to operate with zkSNARKs.

const entries = tree.entries
// [
//       Entry {
//         _usernameToBigInt: 7440338505707899769n,
//         _balance: 7534n,
//         _username: 'gAdsIaKy'
//       },
//       Entry {
//         _usernameToBigInt: 6008493982388733799n,
//         _balance: 2060n,
//         _username: 'SbuqOZGg'
//       },
//       ...
// ]

# leaves: []Node

const leaves = tree.leaves 
    // [
    //   {
    //     hash: 937608857767727606133996830760270048555279161038903523915984285975854603703n,
    //     sum: 7534n
    //   },
    //   {
    //     hash: 3405497655013061136502768874542176491465275092205995841574082657535821212714n,
    //     sum: 2060n
    //   },
    //   ...
    // ]

# root: Node

const root = tree.root 
    // {
    //   hash: 5256203632563331423195629050622063453704745190370457907459595269961493651429n,
    //   sum: 84359n
    // }

# indexOf(username: string, balance: bigint): number

Returns the index of an entry in the tree. If the entry is not in the tree, it returns -1.

const index = tree.indexOf("gAdsIaKy", BigInt(7543)) // 0

# createProof(index: number): MerkleProof

Creates a proof of membership for an entry identified by its index. The MerkleProof contains the path from the leaf to the root.

const proof = tree.createProof(0)

# verifyProof(proof: MerkleProof): boolean

Verifies a proof and returns true or false. It verifies that a leaf is included in the tree and that the sum computed from the leaf to the root is equal to the total sum of the tree.