merkle consistency proofs

[chris-wood]

It doesn't look like the merkle crate supports consistency proofs between two different trees, but it does support (batched) inclusion proofs for leaves. Would y'all be open to adding consistency proof support?

[kevinlewi]

To clarify, is there a need for consistency proofs between two different merkle trees (where one was obtained by appending values to the other) for the purpose of enabling STARKs? Or is this more for the hopes of using the merkle tree code for another purpose?

[chris-wood]

Ah, yes, sorry, that would have been good context to add! This request is unrelated to STARKs. I found this library to be really well designed so I was interested to use it for another application, but that requires consistency proofs.

[irakliyk]

It doesn't look like the merkle crate supports consistency proofs between two different trees

Quick question: is consistency proof basically proves that two Merkle trees contain the same set of items (but maybe in different orders), or is it something else?

[kevinlewi]

@irakliyk I think what is meant here by consistency proof is the following: say you have two merkle trees T1 and T2, where T1 commits to a set of items, and T2 commits to some superset of the T1's items. In the simplest case, T2 is just obtained by adding a single entry to T1.

Do we have a way of providing a proof that T2 is derived from T1 by appending items (and not removing any existing items)?

Since I don't think we ever need to issue these kinds of proofs in winterfell, I don't think this is supported by the library. But I wanted to double-confirm :)

[irakliyk]

@kevinlewi got it! Yeah, we don't have something like this out of the box. But if we can use Rescue (or Poseidon) for these Merkle tress, AIR for this computation shouldn't be too difficult to put together.