zkDataPrep
Structuring datasets into Merkle Sum Trees
This is a Typescript (backend-friendly) library used to create Merkle Sum Trees where each node entry is username -> balance
. The root of this tree contains the aggregated sum of all the node entries, thereby, representing the total assets/liabilities of a firm.
But coming to the point.
What is a Merkle Sum Tree?
A merkle sum tree is a binary Merkle Tree with the following properties:
- Each entry of the merkle tree is a struct, of username and balance
- Each leaf node of the merkle tree contains a hash and a sum. The hash is equal to
h(username, balance)
. The sum is equal to the balance itself, at the node level. - Each non-leaf node contains a hash and a sum. The hash is equal to
h(left_child.hash, left_child.sum, right_child.hash, right_child.sum)
. The sum is therefore equal to the sum of the sum of it's children. - The root node represents the executed/constructed state of the tree and contains all the users'/entry balances. The
merkleSumTree()
is a Typescript implementation of a Merkle Sum Tree and it provides all the functions to construct the above mentioned modified Merkle Tree by just ingesting data from a csv file, picking up only theusername -> balance
.
This diagram is a representation of a similar Merkle Sum Tree
Setup
Installing the package
- The package can be directly installed from the npm registry with the following command:
$ npm i @0xagnish/zk-data-prep
For Database
- Import your database to a csv file, for example this
API Guide
new MerkleSumTree (pathToCsv : string) : MerkleSumTree
import { MerkleSumTree } from '0xagnish/zk-data-prep';
const pathToCsv = 'test/entryPatterns/entry-16-valid.csv';
const tree = new MerkleSumTree(pathToCsv);
//constructs a tree using the given entries in the csv dataset
entries: [] Entry
The entries contain the username parsed as BigInt. This transformation is needed in order to make the entries hashing friendly and later on operate with zkSNARKs.
const entries = tree.entries
// [
// Entry {
// _usernameToBigInt: 7440338505707899769n,
// _balance: 7534n,
// _username: 'gAdsIaKy'
// },
// Entry {
// _usernameToBigInt: 6008493982388733799n,
// _balance: 2060n,
// _username: 'SbuqOZGg'
// },
// ...
// ]
leaves : [] 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 does not exist in the tree, it returns -1.
const index = tree.indexOf("gAdsIaKy", BigInt(7534)) // 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.
tree.verifyProof(proof)
Benchmarking
To construct a Merkle Sum Tree with 262144 (2**18 leaves) it takes:
Time taken | OS/Kernel | RAM |
---|---|---|
108s | Ubuntu 22 LTS | 8 GB |
154s | Macbook Air M1 | 8 GB |