Benchmarking 2: Merkle Tree inclusion-proof scenario of depth n about examples HOT 7 CLOSED

@bobbinth @itzmeanjan

Can you help me with a small problem?

I have a vector [0, 1, 2, ...], which I want to use as my Merkle path. So I want to apply Rescue Prime to each element of the vector.

let merkle_path_vector_full: Vec<u64> = (0..1000).collect();

I use miden-core v0.3 and import chiplets for the chiplets::hasher::hash_elements(). Alternatively I can use chiplets::hasher::merge().

So now, hash_elements() only accepts 4 Felts.

That means I must transform every vector number into 4 Felts. So 0 as 4 Felts is unclear to me.

Is there a way to simply hash 0, 1, 2, 3, ... using Rescue Prime?

from examples.

A couple of comments:

1. I'm not sure checking Merkle paths of large length (i.e., over 256) makes much sense - this will probably never be used in practice. In fact, I would say that in practice Merkle paths of depth greater than 64 will be rarely used. I would re-define the benchmark to pick a Merkle path of some depth (e.g., something like 32) and then $n$ would be the number of Merkle paths we verify. So, for $n=10$ we verify 10 Merkle paths of depth 32, for $n=100$ we verify 100 Merkle paths of depth 32 etc.
2. A Merkle paths must consists of digests (outputs of a hash functions) - so, we can't use simple number. What you can do is convert each number to an element (via Felt::new()) and then hash this element using hash_elements()). This will give you a digest for each node in the path.
3. To compute a root of this path, you'll need to hash the elements of the path using merge() function. The order in which you do the merging will define the index of the leaf in the Merkle tree. It may actually make sense to generate a random 32-bit index, and then use it to compute the root of the path.

from examples.

Thanks a lot, that helps indeed.

1. Let me discuss that point with Tim and Delendum. Your scenario makes more sense to me.
2. I did it exactly like you described in the end. The problem is that Felt::new() gives me only 1 element, but hash_elements() consumes a Digest as you say. So my solution to create a mocked Merkle path is now, to quadruple the number that I wanted to hash and then create Felts from those four numbers and hash it using hash_elements().

[1000, 999, ...] -> [1000, 1000, 1000, 1000, 999, 999, ...] -> [Felt::new(1000), Felt::new(1000), Felt::new(1000), Felt::new(1000), 999, 999, ...]

3. I did use merge() and rphash (Assembly) and had to play around with the order a bit. But now it works.

Here is the PR for reference
delendum-xyz/zk-benchmarking#15
[It will be easy to change to your suggestion and it might be easier to discuss on the PR]

from examples.

The problem is that Felt::new() gives me only 1 element, but hash_elements() consumes a Digest

hash_elements() takes a slice of field elements (not a Digest) - so, you should be able to do something like hash_elements(&[Felt::new(x)]);

from examples.

OK, we change the scenario now and re-define the benchmark to pick a Merkle path of some depth (e.g., something like 32), and then n would be the number of Merkle paths we verify. So, for n=10, we verify 10 Merkle paths of depth 32; for n=100, we verify 100 Merkle paths of depth 32 etc. (as @bobbinth suggested)

To discuss a super simple example, for n=1 and depth=2, that means I create a SparseMerkleTree.

        let merkle_leafs_keys: Vec<u64> = (0..4).collect();
        let mut merkle_leafs: Vec<Word> = Vec::new();

        for i in 0..merkle_leafs_keys.len() {
            merkle_leafs.push([Felt::new(merkle_leafs_keys[i]), Felt::ZERO, Felt::ZERO, Felt::ZERO]);
        }

        // Now we create a Sparse Merkle Tree with the leafs we just created
        let smt = AdviceSet::new_sparse_merkle_tree(merkle_leafs_keys, merkle_leafs, 2).unwrap();

Then the scenario is about verifying that node_0 (the node with index 0) is indeed part of the tree.

I understand that in Miden assembly, we can create a simple program to verify the inclusion of a node into a Merkle Tree.

  begin
  # verify a merkle path
      mtree_get
  end

If this is correct so far, I need to create ProgramInputs for that program, hence for stack_init = [depth, index, root of the tree] and the tree must be present in the advice provider, so I can push the tree smt as advice_sets.

Is this correctly understood @bobbinth ?

from examples.

Yes, that's correct. Maybe one small comment that we also need to check the state of the stack at the end to make sure we got the expected leaf.

from examples.

Closed by delendum-xyz/zk-benchmarking#24

from examples.