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

[cyphersnake]

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]

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]

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]

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]

Benchmark Update:

• Code and scripts for data collection are ready
• halo2-kzg - given by keygen/prove are collecting
  • Verify is broken, although the code is taken directly from halo2 library. I plan to still try to figure out what could be the issue.
  • BatchSize=10 take 3141s, expected very long run for BatchSize=60,80,100
  • Also the brach with kzg support can't go to master yet, because it broke all tests, postpone this
• memory-usage - will be collect after halo2-kzg, it will take a long time to build because dhat slows down the program several times.

[cyphersnake]

Added to kzg-halo2curves branch

• cache for keygen
• Parameterization by env variable (cache clean & repeat_count)

BATCH_UPDATE_SIZE=1 cargo merkle-halo2-kzg
where 1 is size of batch update

For refresh keygen:
REFRESH_KEYGEN=true BATCH_UPDATE_SIZE=1 cargo merkle-halo2-kzg