Suppose Alice has committed to several sets of values using Merkle trees. For example, let's say there are 2 sets of values, and each set represents leaves of a separate tree like this:

  • $a_0, a_1 ... a_n$ are the leaves of tree $A$
  • $b_0, b_1, ... b_m$ are the leaves of tree $B$

Victor wants to make sure Alice didn't cheat by including a lot of invalid values into the trees. So, he queries each tree in $x$ random positions, and Alice provides Merkle proofs for the requested leaves. If all proofs check out, Victor is satisfied.

A common way to make the above scheme non-interactive is to use roots of the trees as seeds to PRNG, specifically:

  • $PRNG(root_A)$ would produce $x$ positions at which tree $A$ should be queried.
  • $PRNG(root_B)$ would produce $x$ positions at which tree $B$ should be queried.

I am wondering if a slightly different approach can be used to improve security (and thereby reduce the number of queries needed). Specifically:

  • Alice would first calculate $h=hash(root_A + root_B)$,
  • Then, she'd calculate positions for tree $A$ as $PRNG(h)$,
  • And positions for tree $B$, as $PRNG(hash(h))$,

The thinking is that this setup makes it more difficult for Alice to cheat. In the original setup, Alice could try many different permutations of $A$ until $PRNG(root_A)$ resulted in query positions that are just right. And then, she could do the same for tree $B$.

But with the new setup, any change to either of the trees changes query positions for both trees simultaneous. Thus, potentially, many more permutations would be needed.

If this scheme works, how would it affect the number of queries? In the original setup, $2x$ queries were required, how would it change in the new setup?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.