How to deal with variable proofset length when verifying a merkle tree in a circuit

[beegmon]

Hi All!

I understand that input into a circuit must be defined at compile time.

So this wont work:
type Circuit struct { MerkleRoot frontend.Variable MerklePath []frontend.Variable }

And then at assignment:

assignment := &circuit { MerkleRoot frontend.Variable(merkleRootFrElement) MerklePath []frontend.Variable{merkleProofSet[:]}

This results in undefined slice which makes sense since the circuit inputs have to be defined at compile time.

For a simple program test program, I can easily set the []frontend.Variable to something like [5]frontend.Variable in the struct definition and [5]frontend.Variable(merkleProofSet[:]) in the assignment where the length of merkleProofSet is 5 at 100 entries in the merkle tree.

However, for more than a simple demo, the Merkle proof set is going to grow and shrink over time depending on the number elements.

How does one overcome this without basically building a tree that is always the largest allowed size of said tree (filling it with padded data/leaves where there is no more real data to fill the tree with)?

I have tried using a hint, but the number of outputs is still statically set when making the hint call in circuit. This means I can't feed a hint the fully padded proof set [255]frontend.Variable(paddedMerklePath[:] to the hint, and get back an set of just the valid elements in that padded set (because the number of items in return set is variable based on the statically defined number of outputs on the hint call.

The other idea I had was to pad out the merkle proof set to some really large size that will accommodate all reasonable tree sizes I might calculate in the future.

Then then feed the circuit an int value that represents the "real" proof set length. I would then in circuit loop through the padded proofset, selecting 0 thru N number of elements from the padded proof set, and use those to set my merkle Path for the proof.

This doesn't work because I don't think because I can't use a circuit variable in a for loop along the lines of for i : =0; i < circuit.validMerkleProofSetLenth; i++ .

I have also tried using a hint to return the validMerklePathSetLength, but that is also a frontend.Variable so I can't use that for a for loop either.

Any ideas on how I might accommodate the need for the merkle proof set size to change over time without padding out the tree to its max size?

[ivokub]

Hi, unfortunately it is not possible to have a variable-length input to the circuit directly. The circuit definition is compiled into a set of polynomial identities and for that the compiler needs to know the length of the inputs at compile time.

However, one possible approach is to use recursion. Lets say you have a PLONK circuit verifying MT of size 2^8 (layer 0). Then you can construct a recursive which verifies another MT and the previous PLONK proofs.

[beegmon]

Thanks for this. I was heading down this path as well but was hoping for something simpler first. I will digest this for a bit and see if it is something we can fit into our given requirements.

Thanks!

[hussein-aitlahcen]

It's possible to do what you want within a single circuit by having padding data (defining a maximum depth for the merkle tree) and providing an input that tells the current size. The downside is that the perf will always be worst case (full tree).

Example:

type C struct {
  Size frontend.Variable
  Elements [2^MaxDepth]frontend.Variable
  ...
}