search

snarkify / sirius

A Plonkish folding framework for Incrementally Verifiable Computation (IVC).
MIT License
105 stars 15 forks source link

feat(example): poseidon-based merkle-tree benchmark #285

Open cyphersnake opened 3 weeks ago

cyphersnake commented 3 weeks ago

Start with initial tree state. The initial tree can be fully filled with default values (e.g. hash(NULL)). Then batch update the merkle tree by a list of nodes.

Public Input [Old Root Hash, Root Hash] Private Input Vec<(leaf_index, new_leaf_value)>

chaosma commented 2 weeks ago

when tree height is large e.g. 32 levels, then it is practical to start with default tree.

In bottom level (level 1), each leaf has default value v1=hash(NULL) In next level (level 2), each node has default value v2=hash(v1,v1), ... The root of merkle tree has default value v32=hash(v31,v31)

cyphersnake commented 1 week ago

FYI

Apart from the benchmark itself, the only thing left is the correctness of the merkle-tree calculation on-circuit

Now you can rearrange the sibling in the counting of the original root and the new one - and the circuit will think that everything is correct, but it is wrong. I'll fix it tomorrow by fixing the order of hash input with index.

But except for this nuance - the circuit is ready and working and folding

https://github.com/snarkify/sirius-test-circuits

cyphersnake commented 1 week ago

I finished to implement merkle-tree-update-circuit, collect data for all the batch we are interested in, moved to the task of implementing this circuit within halo2, so far the problem is that MockProver passes, but does not work full IPA. I'm figuring it out

cyphersnake commented 6 days ago

Benchmark Update: