1
$\begingroup$

When I use the merkle proof example of libsnark, I find that it takes more time to calculate the merkle tree than to calculate the proof. As shown in the log below, it takes 0.04s to calculate a SHA256. When the depth of the tree is 20, it takes at least 3 hours to exac SHA256, but only 14s to exac proof. I notice that it seems like to have generated a r1cs witness when exacing SHA256, but is it necessary to generate r1cd for the whole tree?

And maybe it's because I'm not good at C++, I can't find where the hash function pass the R1CS back.

23/23 Test #23: test_sha256_gadget ............................... Passed 0.04 sec

$\endgroup$
1

1 Answer 1

3
$\begingroup$

Creating a depth 20 tree will require $2^{20}-2^{21}$ hash function evaluations and this will certainly take on the order of processor-hours of resources. Validating a claimed value for a single node of the tree will take 20 hash evaluations and so is considerably quicker, even if several nodes are required to validate the R1CS.

Because the prover must not know the nodes that will be chosen as witnesses before the creation of the tree, they have to create a tree where all nodes satisfy the R1CS and can be shown to do so if selected as a witness. If the prover had some advantage in knowing which nodes are likely to be selected as witnesses, they could construct an invalid tree where the R1CS held for the witnesses but not the other nodes. In other words there would be no guarantee of validity of values associated with non-witness nodes which would mean that invalid trace values could be used in the proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.