Support for cyclic recursion

[dlubarov]

Support recursion where the inner circuit is the circuit currently being built, as in IVC etc. This is nontrivial since it's circular - we don't know what circuit we're verifying since it hasn't been constructed yet.

I think @ebfull mentioned using public inputs to pass in the verification key (which, in our setting, is basically a Merkle root of preprocessed polynomials). That seems like a good approach.

However, we will need a different workaround to deal with parameters that affect the "shape" of the recursion circuit. Plonky2 has several such parameters:

• degree (determines Merkle proof lengths)
• list of custom gates
• number of public inputs
• sequence of FRI reduction arities
• degree of the quotient polynomial
• number of preprocessed polynomials, and of partial product polynomials

None of these are known until the circuit is complete. We could have the caller specify these params (and raise an error if they don't work), but that would be a bit inconvenient.

Alternatively, we could estimate these params, then add recursion circuitry assuming those params in a clone of the circuit. Then we build the cloned circuit, and if the resulting params don't match our estimates, we update our estimates and try again.

We could generalize this further, allowing the user to define a set of circuits with various (potentially cyclic) recursive dependencies, then searching for a set of parameters that works for the whole set of circuits. That seems a bit difficult though, and I don't see an immediate need for it.

Discussed a bit in Discord; cc @Sladuca.

[Sladuca]

Alternatively, we could estimate these params, then add recursion circuitry assuming those params in a clone of the circuit. Then we build the cloned circuit, and if the resulting params don't match our estimates, we update our estimates and try again.

I think this is the best approach - I'd imagine the number of use cases that need the third approach is very small, and this keeps the details inside the library so we don't end up stuck with it for backwards compatibility if a more efficient way becomes possible down the line.

[Sladuca]

Given our discussions on discord, here's an idea how this could work:

1. Add a Vec of self-verifiers to be lazily added to the circuit.
2. Add an add_recursive_self_verifier method to CircuitBuilder that just adds a new entry to the self-verifier Vec.
3. Add a build_with_self_verifier() -> Vec<ProofWithPublicInputsTarget> method to CircuitBuilder that should be called instead of build() when using add_recursive_self_verifier. This is where the the retry logic takes place. It also creates, registers, and returns a Vec of public input targets which can be set in a witness via pw.set_proof_target - these input targets have to be given after the circuit is built because we don't know their dimensions until then.
4. To prevent misuse, It might be a good idea to have build_with_self_verifier() panic if add_recursive_self_verifier was never called, and have build() panic if it was called.

[Sladuca]

Also, I'd be happy to take this on I once we decide on an API. As far as I understand, this would be somewhat straightforward since #445 has all of the methods needed to generate the inner targets given the size estimates - the one thing I'm still a bit fuzzy on is how custom gates fits into this.

[dlubarov]

That sounds like a good plan, just a couple thoughts -

• We renamed add_recursive_verifier -> verify_proof, so maybe this could be named verify_proof_circular or verify_self_verifying_proof.
• I think we may need build_with_self_verifier to return a whole Vec<ProofWithPublicInputsTarget<D>>? So that the caller has the ProofTarget data, in addition to public input targets, to later use with set_proof_target. Unless there's another approach that I'm not thinking of

[Sladuca]

think we may need build_with_self_verifier to return a whole Vec<ProofWithPublicInputsTarget<D>>?

Yes, we do need this. Otherwise the user doesn't have a way to set both the ProofTarget and public inputs with set_proof_with_pis_target once they have a ProofWithPublicInputs put in.

[Sladuca]

verify_proof uses the the inner circuit's instance digest to seed fiat-shamir when generating challenges. We don't have this either until the circuit is built.

Should we make this a public input or is there some alternative way to seed fiat-shamir here?

[dlubarov]

Hm that's a good question. Currently the instance digest is just the Merkle root of preprocessed polynomials (constants_sigmas_cap), and we were planning to make that a public input, so I think we can reuse that public input for now.

When we get around to fixing the instance digest, I think it will look something like

• constants_sigmas_cap = ...
• constraint_system_digest = ... (hash of all constraint polynomials)
• instance_digest = hash(constants_sigmas_cap, constraint_system_digest)

Then constants_sigmas_cap can be a public input as before, constraint_system_digest can be something we fix in the retry loop (so it becomes baked into the circuit), and instance_digest gets dynamically computed as their hash. But we can do that later.

[dlubarov]

Done in https://github.com/mir-protocol/plonky2/pull/782