[kimchi] absorb verifier index + recursion data

[mimoo]

• [x] adds number of proofs verifier in a recursion circuit to ConstraintSystem
• [x] adds public input size to verifier index
• [x] absorbs verifier index in proof
• [x] absorbs prev challenges in proof
• [x] specify

closes https://github.com/o1-labs/proof-systems/issues/466 https://github.com/o1-labs/proof-systems/issues/552

[mimoo]

Interestingly, I expected being able to create a proof that has prev_challenges of random length (at least as long as it's smaller than our SRS size, why would there be an issue?) But tests don't pass when I try that. From a quick glance I think the verifier's code can handle prev_challenges from a higher domain, but not from a smaller domain: https://github.com/o1-labs/proof-systems/blob/e123cf8362c57191c4ab96501eb80a069e3a8aaa/kimchi/src/verifier.rs#L66

investigating...

It looks to me like we just need to handle the case where we get a smaller domain by making this change:

-                        if index.max_poly_size == b_len {
+                        if index.max_poly_size >= b_len {
                            return vec![full];
                        }

which should be equivalent to padding the challenges with 0

it also looks like the case where the b_poly is larger only expects the b_poly to not be more than twice the size of our domain. So I added an assert to make sure we never reach that case.

[github-actions[bot]]

Stale pull request message