How Sacred Boxes work

To keep track of deposits anonymously, Sacred Boxes take advantage of a Merkle tree. 

Specifically, the Sacred Box keeps track of the latest “former” roots as well as some nodes used to generate the next root for the next added leaf. The leaf nodes are the submitted claims, however, are not actually stored in the Sacred Box; nor does a person who withdraws ever reference a specifically submitted leaf (this would break anonymity). Instead, a person withdrawing funds provides cryptographic proof that the leaf simply exists somewhere in the tree, and that you can get to it from one of the roots that the Sacred Box stores.
Here is a diagram to illustrate a sample 5-layer tree:
​
​
In the diagram above, an arrow represents a hash function (from input to output). Actually, this particular function (Poseidon function) takes in two inputs to produce one output; where it appears that there is only one input, the second input is the appropriate hash of 0,0; let P(x,y) be the Poseidon function with inputs x and y, then a node that is shown to only have one child c at level n is actually the hash of c and the hash of the hash of … the hash of (0,0), such that there are n recursive levels of hashing (or n+1 total hash operations). This can be represented as P(P(P(P(...P(0, 0)...), 0), 0), c) or P(P^n(0,0), c) where the “exponent” represents recursion.
All the shapes represent nodes. Red nodes are nodes currently stored by the Sacred Box contract, blue nodes are the stored roots, light-blue nodes are those that had been stored at some point, and grey nodes are those that have never been stored (you will notice that the grey nodes are only ever children to one parent node). Parallelograms are the leaf nodes that contain the Sacred Claims themselves (the hash of the concatenated k and r).
Since the Poseidon function takes in two inputs, each root is actually the root of its own “virtual” binary tree; if there are n levels to the entire structure, then each root could be the root of a tree with 2^n leaves, which is a huge amount! However, this tree is never actually generated in its entirety (only the one branch leading to the current leaf) which serves to obfuscate the leaves. Since hashing only works in one direction, there is no way to compute the leaves from a given root; but it is possible to generate a path from a known leaf to a given root, and this path cannot be faked (only by computationally infeasible brute force).
When a user deposits tokens into a Sacred Box, it was mentioned that the user generates and adds a new leaf value. It is truer to say that the user generates two values, that we can call k and r, and a new Merkle root is computed from a leaf value of the hash of the concatenation of k and r.
To withdraw a deposit, a user must have generated a claim. This is a zk-SNARK of the path from the leaf to a given root (represented in dark blue) that is currently stored in the smart contract. However, this does NOT contain any information on the actual path taken, nor on the leaf involved. Purely, the user’s claim proves that there exists such a leaf and appropriate nodes; revealing this path would de-anonymize the withdrawal. This SNARK is sent to the Sacred Box, along with the nullifier h. By the nature of the functions, it is impossible to tamper with h (the SNARK will not work for a different value of h, because h is the hash of k); the contract will add the value h to a “list” of used nullifiers and check all subsequently submitted proofs to ensure that the h is not reused. Thus, it is impossible to claim the same deposit twice.
New leaves and their roots are added on the right, and the formula by which the tree is generated (it may seem chaotic in the diagram) is specifically designed such that you can get to any leaf from any later-generated root. The n-level structure is designed to support up to 2^n leaves (that’s a lot of leaves!). During implementation, the Sacred Box will store several of the latest roots (constantly cycling the oldest ones out for newer ones) to allow for the case where someone deposits just as someone else is calculating a SNARK.
The core smart contracts involving the Sacred Box and the money mixing itself were forked directly from Tornado cash, with minimal changes (apart from proving and verifying keys, see “trusted setup ceremony” below). The original Tornado Cash contracts are widely trusted, tested and audited; and we hope to take advantage of some of that credibility by keeping the core functionality pristine.

Technical Details - Previous

Relayer

Next - Technical Details

Sacred Ceremony

Last modified 3mo ago

Copy link