Folding endgame

[levs57]

Intro

UPD: I’ve added proof sketches in comments down below. I would suggest to refer to definitions there as a main source (some notation is better, and also I’ve fixed stuff here and there, the main post still has mistakes).

Hello everyone. Throughout the recent few days, I’ve discussed with different people a variety of things related to lookups, Nova, and other stuff. It seems I have now something to tell back. It will be a long post, and mostly it will consist of constructions, not security proofs. I expect this to be possible roadmap to realizing zk-proofs of very large circuits.

Logically, it is split into two independent parts (three, if we include preliminaries). I am sort of convinced that the first part works, and feel shaky but excited about the second.

First part is devoted to adding permutation argument to Nova (/ Sangria, they are not that different). This, potentially, means memory accesses between the steps, or even copy constraints between the steps. It seems to be different from Origami and Nico’s approach (communicated to me in private) - which are approaches focused on separate lookups on each step instance. The advantage of my approach is the fact that (1) it removes the need of keeping the lookup table in each instance (2) it allows us to do interesting cross-step interactions. Generally, it leads to folding of arbitrary unstructured circuits, completely superseding SuperNova. Disadvantage is the fact that it is not really incremental - the whole batch of steps needs to be known beforehand. However, I believe this should be, generally, an effective and manageable approach to very big circuits.

Second part is concerned with using Nova over integer coefficients by using Pedersen commitments in RSA group.

Acknowledgements

I would like to thank everyone who communicated with me and shared ideas through the last few days. @barryWhiteHat asked me about lookups / challenge oracle in Nova, and we have came up with ~ the approach I’m now going to tell you. Lucas Meier @cronokirby was the one who gave me the initial push. We had extensive discussion with @nico_mnbl, and some parts of what I will be telling you are influenced by him. Thanks to @aard_k_vark and @krzhang who created Origami and talked about it with me, and thanks to @kobi, @portport255 and Yar for listening to my incoherent ramblings.

Onwards.

Preliminaries

Before we start, let’s, as a short warm-up, recall how Nova works. I will consider a slightly more general case, so Sangria is also subsumed by it.

Our instance is a polynomial equation system \forall i : P^{i}(x_0, ..., x_n) = 0, with some subset of variables called “fixed” (or “instance” variables, or “public inputs”). We also assume that x_0 is fixed and equals 1. For convenience, lets split each polynomial into homogeneous parts, i.e. P^i(\bar x) = \underset{0 < k < d_i}\sum P^i_k (\bar x).

Then, the system can be rewritten into homogeneous system: P^i_{\text{new}} \overset{\text{def}}= \sum P_k^i(\bar x)x_0^{d-k}. In what follows, I will always assume w.l.o.g. that this system is homogeneous. //in Nova paper x_0 = u.

I will also denote \bar x = (\bar p, \bar q) the splitting of the vector x on instance and witness parts.

Now, let’s also create relaxed version of a system, namely \forall i: P^i(\bar x) = E^i. The vector \bar E also sort of counts as instance vector (and is called error term). We will use some linearly homomorphic vector commitment system, and commitment to a vector \bar v will be denoted [\bar v]. The committed relaxed instance is [\bar p, \bar E], and committed witness is [\bar q].

Now, given two (committed relaxed) instances of the system, the following protocol allows to prove we have solutions to both of them:

1. The prover sends to the verifier [\bar q_1], [\bar q_2] and the following cross-terms: [C_k] = [\bar P (x_1 + t x_2) |_{t^k}] \quad \forall \quad 0<k<d. Here, P|_{t^k} \overset{def}= \frac{1}{k!}(\frac{\partial}{\partial t})^k P |_{t=0}.

2. Verifier samples random \lambda, and gives it back to prover.

3. Prover now only needs to prove it knows a solution \bar q_1 + \lambda \bar q_2 to the instance [\bar p_1 + \lambda \bar p_2, \bar E_1 + \lambda^d \bar E_2 - \underset{0<k<d}\sum \lambda^k C_k] - it can do it by directly revealing all the commitments, or use the obtained relaxed committed instance to fold it again and again.

I will frequently assume that the system of equations was quadratic (because it might be simpler to write formulas this way), but actually it is not necessary. Before describing how Nova works, let’s consider the following simple protocol:

1. Prover commits to n “step instances + step witnesses”, called u_1 ... u_n. Each instance has parts of the fixed values called “input” and “output”, and we also require that \text{in}_{i+1} = \text{out}_i.

2. Prover also folds everything (i.e. shows all the commitments to the occuring cross-terms in the incremental folding process), and then reveals the witness-instance pair of the resulting folded instance (it could also publish a SNARK of it, but let’s just ignore it for a moment).

This protocol, on paper, takes O(n) verification time, but even this is already quite powerful. Imagine, for example, that it was actually a repeated computation of length N, split into batches of length n = \sqrt{N}, corresponding to each step.

Then, apparently, it takes O(\sqrt{N}) time - because we have \sqrt{N} folds, followed by reading witness of size O(\sqrt{N}).

High level idea of Nova approach is by modifying the step-predicate in such a way that it “remembers” previous steps, and so prover does not need to publish all the step commitments. Let’s recall how it works:

Denote the original step predicate F. Our new, modified step predicate F' takes all inputs as non-deterministic advice, except of 1 called h, which will be used to keep our running instance in. Denote the values obtained by applying F z_i = F^i(z_0).

Denote u_b, w_b the trivial instance-witness pair with both error term and public input being 0,

In the base case i=0 the predicate F' should just output h = H(vk, z_0, F(z_0), 1, u_b).

Now, for the step i>0:

1. Get a non-deterministic advice U_i, u_i where U_i represents the running instance and u_i the current instance, and also z_0, z_i, i.
2. Unpack the hash: H(vk, z_0, z_i, i, U_i) = u_i.h
3. Calculate F(z_i) = z_{i+1}
4. Check that u_i is well-formed, i.e. its error term is 0 and u_i.x_0 = 1
5. Fold U_i and u_i to obtain U_{i+1}
6. Set h = H(vk, z_0, z_{i+1}, i+1, U_{i+1})

Now, we are ready to attempt the same trick, but with additional challenge rounds.

Adding the second round - Origami approach ?

Interactive version was initially communicated to me by Nico, who was doing something similar independently, but it seems that these approaches do, in fact, coincide. Maybe this text will still serve as some sort of clarification for the original Origami text; as a guide of turning their argument into non-interactive IVC.

Suppose now, that our step circuit (meaning, witness) is split into two parts, which I call S_0 and S_1. There are also additional public inputs (called “challenge”), which I will denote t_1, ..., t_k, that is not present in any constraints involving S_0.

I will call an algebraic witness to such structure a solution over \mathbb{F}_p(t_1, ..., t_k), such that over S_0 it lives in \mathbb{F_p}. Good example of this is permutation or lookup arguments.

Given the challenge, it produces a normal witness with an overwhelming probability.

Now, this is my interpretation of what I’ve learned from talks with Nico and Origami team. Maybe I’m wrong / interpreting something that was not said explicitly, but for me it looks like the only reasonable way to proceed:

1. as before – but also get “partial witness commitments” W^0_i, w^0_i (they mean witnesses for the S_0). Calculate challenge using Fiat-Shamir of w^0_i (here, authors will probably insist that I need to hash the whole transcript, but I claim that in that particular case it is more than enough, but if we need we can use u_i.h, w^0_i).
2. Unpack the hash: H(vk, z_0, z_i, i, U_i, W^0_i) = u_i.h
3. Calculate F(z_i) = z_{i+1}
4. Check that u_i is well-formed, i.e. its error term is 0 and u_i.x_0 = 1
5. Fold U_i and u_i to obtain U_{i+1}, fold W^0_i and w^0_i with the same coefficient to obtain W^0_{i+1}
6. Set h = H(vk, z_0, z_{i+1}, i+1, U_{i+1}, W^0_{i+1})

The final check should also, in addition, prescribe that the witness corresponding to the first round is exactly the folded W^0. (i.e. if our final check is just “reveal the witness”, then the verifier must also extract W^0_{n+1} and check that it is, indeed, a commitment to its own part of computation of z_{n+1} using F (step 3)).

Why I think it works (totally not a security proof): assume we come up with some fake witnesses. It will, of course, mess up the computation of F^{n+1}(z_0) if we adaptively choose these witnesses, but it will still be correct folding (up to our external check). Moreover, the part of the trace of computation of F that lives over S_0 does not change. I expect it is not possible to choose w_i's adaptively in such a way that its folding would give the folding of the trace of computation of F over S_0.

Adding a second round in a different way - my approach

Now, in the paradigm above, each round has a different challenge. However, it might be reasonable to thrive for a single challenge (in a sense that a commitment to the run over S_0 is obtained, and then commitment over S_1 is produced).

I suggest doing it in a following way. Now, F' will have two running hashes, second one will be called \text{run}.

1. Get a non-deterministic advice U_i, u_i, W^0_i, w^0_i, z_0, z_i, i as before.
2. Unpack the hash: H(vk, z_0, z_i, i, U_i, W^0_i) = u_i.h
3. Guess the challenges \bar t non-deterministically.
4. Calculate F(z_i) = z_{i+1}
5. Check that u_i is well-formed, i.e. its error term is 0 and u_i.x_0 = 1
6. Fold U_i and u_i to obtain U_{i+1}, W^0_i and w^0_i to obtain W^0_{i+1}
7. Set h = H(vk, z_0, z_{i+1}, i+1, U_{i+1}, W^0_{i+1}), \text{run} = H(w^0_i, u.\text{run})

After the dust settles, the final verifier performs the check, as before, and also checks that t = \text{run}.

Errata: either we check t*U_{i+1}.x_0 = \text{run}, or we need to constrain t inbetween different steps (say incorporate it in z_i with the rule that t_{i+1} = F(t_i) = t_i). Not sure which one of these approaches is better, both seem to work.

The idea is similar: the witness vector is proposed in each step. It is both folded in, and accumulated into a running hash. The running hash then, retroactively, must be equal to the challenge used at every step, and the folded witness is then used to ensure integrity.

If this works (which I hope it does, but currently this is a mere conjecture), then we would unlock an ability to create copy constraints between different steps. This would allow to fold unstructured circuits, or emulate VM memory accesses using non-deterministic checking of memory access flow.

Integer commitments

Another very fruitful topic is potentially using Pedersen commitments in RSA groups. Nova does not exactly use the fact that it is over a field anywhere. (Here, I’m speaking specifically about groups in which RSA assumption holds. Ideal class groups do not work, because square roots are easy - which could allow rational commitments that become integer after folding, similar to a problem encountered by authors of DARK).

Provided the solution to the integer circuit is relatively tame, the folding can also be made relatively tame - say if r bits is the maximal value of a signal in a circuit, then r+256+\log_2(n) is the total maximal value in the folded circuit.

This unlocks various superpowers that, generally, feel like cheating - starting from dirt cheap range proofs, and ending with dirt cheap circuit for folding itself - expressing RSA in integer arithmetic terms should be very pleasant.

I’m not exactly sure about this part, but I think it is worth researching. Of course even if everything works, we will still need to create trusted setup ceremony, which looks very hard for RSA, but provided this is done we would be able to finally do integer arithmetic normally, which looks like it is worth a shot.

Foreword

If you see any mistakes, inaccuracies, some scheme is clearly broken or you just have valuable input / want to collab on some topic from there - please, reach me out, through twitter or telegram handle levs57. xoxo

[levs57]

A small clarification on why I think non-interactive Origami should work (possibly required, it is unclear from the post I feel).

suppose at some point during folding I chose the wrong partial witness, and now I am trying to fix it (i.e. I have poisoned W^0_i which is not the S_0 - part of my current solution to U_i).

And I’m trying to pick w^0_i in such a way that after the fold W^0_{i+1} = ( W^0_i + r w^0_i ) will become S_0-part of my full witness to U^0_{i+1}.

It should be hard to do, because the folding coeffient r is chosen from the whole computation trace, which involves the challenge, which, in turn, involves [w^0_i] (because it is hashed from it).

I hope this clarifies matters a bit.

[levs57]

Proofs

(obviously still not full, but at least sketches).
(warning: eyebleed. at some point I’ve messed up with commitments, there are definitely some lost [ ]-s in this text. as a general rule, the stuff that is happening in-circuit is about commitments unless explicitly stated otherwise, and letters U denote instances with not committed public inputs, but with commited error term U.E. if context doesn’t allow to devise the meaning of the text, I’m really sorry, this definitely needs a lot of polish)

This also involves re-assessing what is said in Origami (currently they do not explain (see Protocol 2 in the hackmd post) what is done with witness commitments to the columns (A, S, A', S'), which is exactly my W^0, but something clearly needs to be done to check their integrity; my method does it).

Definition

Enhanced relaxed R1CS.

Let’s consider R1CS structure, i.e. system of constraints, and let’s assume there is some chosen subset of a witness, called S_0. Let’s denote \pi_0 the projection of the witness vector onto the part living over this subset. For an instance-witness relaxed committed R1CS pair, let’s call “enhanced witness” the same data endowed with commitment to the vector w^0 \overset{def}= \pi_0 (w).

Let’s also assume there are some public inputs, called “challenge”, that are set up by verifier “after” these commitments are produced - this will depend on a context, in structural sense these are just separate public inputs.

Prover is said to have a game witness for an enhanced relaxed R1CS instance, if it has a polynomial time strategy that wins (except negl. probability) in a following game:

P: send [w^0]
V: set up challenges
P: present witness w to R1CS with such challenges, such that \pi_0 (w) = w^0

i.e. game witness is a strategy. I recall the notion of algebraic witness from the main post, for one particular kind of such strategy.

Protocol 1: 2-1 fold, interactive version

Prover holds two witnesses to instances u_1 and u_2 (recall that instance u is an error term u.E and the set of public inputs, of which u.x_0 is a relaxation coefficient).

He wants to convince the verifier that it has these witnesses. They engage in a following game:

P: send [w_1^0] (obtained by playing the first round of the first game)
V: send \text{chall}_1
P: send [w_1]
– repeat for 2nd instance –
P: send cross-term [C] = [A w_1 B w_2 + A w_2 B w_1 - (x_0)_1 C w_2 - (x_0)_2 C w_1]
(Step *) V: send challenge \lambda
P: open w = w_1 + \lambda w_2, open C, open w^0 = w^0_1 + \lambda w^0_2
V: check that it is a solution of R1CS instance with error term E_1 + \lambda^2 E_2 - C
INTEGRITY: check that \pi_0 (w) = w^0

This is roughly homologous to what is said in Origami, except of the things I italicized, they are, however, crucial.

Security proof sketch

Completeness is obvious, let’s discuss knowledge soundness. As typical in these situations, we will construct an Extractor: program, which, given an access to the (passing) Prover’s code, and extract witnesses for instances u_1, u_2 (so in our case it actually extracts 2 provers, which is fun to think about but makes stuff a bit weird - I will have Mini-Exractor and the real Extractor, who is Meta-Extractor).

Mini-Extractor does the following: it emulates the prover, waits until the (Step *). Here, it forks Prover 3 times, and sends to each copy a different number - \lambda_1, \lambda_2, \lambda_3. It obtains three solutions, and uses Lagrange interpolation to construct back w_{1,2}. It also obtains w^0_{1,2}. The values w_{1,2} pass due to the standard algebra (described in Nova paper), and w^0_{1,2} = \pi_0 (w_{1,2}) because the reconstruction process is linear.

Meta-Extractor is funky - it is supposed to output a pair of strategies. In fact, it outputs the code of Mini-Extractor (twice - first time adding additional instructions “\text{chall}_2 \leftarrow \text{rand}” and “return w_1, w^0_1”, and second time adding instructions \text{chall}_1 \leftarrow \text{rand} and “return w_2, w^0_2”).

Protocol 1B: 2-1 fold, synchronous challenges

assumptions are the same, but now the challenge will be the same for both instances

P: send [w^0_1], [w^0_2]
V: send \text{chall}
P: send [w_1], [w_2], [C] = [A w_1 B w_2 + A w_2 B w_1 - (x_0)_1 C w_2 - (x_0)_2 C w_1]
V: send \lambda
P: open w = w_1 + \lambda w_2, w^0 = w_1^0 + \lambda w_2^0, C
V: check w is a solution for error term E_1 + \lambda^2 E_2 - \lambda C, check \pi_0(w) = w_0

Security proof sketch

Same as before. Except, now Meta-Extractor doesn’t need to feed Mini-Extractor with random challenges, and just outputs its code, appended with either instruction “return w_1, w_1^0”, or instruction “return w_2, w_2^0”.

---

The protocols for n commitments are also proven analogously to how it is done in main Nova paper - employing the forking lemma, and final integrity check ensured by linearity.

I will write down the n-fold protocol for the reference, but refrain from writing down the forking lemma proof here. From now on I will also only discuss synchronous version, and leave Origami-style aside (they are completely similar up to the subtleties in IVC, and I believe my version has more subtle IVC)

n-fold protocol - synchronous version

Given: Circuit F with 2 non-trivial inputs, in and out, and a challenge input. We want to fold the repeated computation of such circuit. We also assume that out is “over S_0”, i.e. it can be obtained from in without asking for a challenge. Asynchronous version sidesteps this difficulty.
Further, we will use F(in) = out for any valid output (even though output might be non-unique).

P: Send z_0, z_1, ..., z_n (intermediate steps of applying circuit n times).
Send commitments [w_1^0], ..., [w_n^0].
V: Send challenge \text{chall}.
P: Send [w_1], ..., [w_n].
Initialize w_0 = 0, e_0 = 0, x_0 = 0, w_0^0 = 0 trivial solution, W_{1} = w_0.

(for i from 1 to n):
Engage into 2-1 committed fold subprotocol on [W_{i}] and [w_i] (and [U_i], [u_i]) to obtain enhanced i-w triple ([U_{i+1}], [W_{i+1}], [W^0_{i+1}]). Recall, u is a committed instance, i.e. public inputs including x_0 and committed E. Committed 2-1 = do not open, keep passing the stuff to the next stage. Check that u_i is correct (has appropriate public values u_i.\text{chall} = \text{chall, u_i.in = z_i, u_i.out = z_{i+1}} and u_i.E=0 happens here).

P: Open the resulting W_{n+1}, E_{n+1}, W^0_{n+1}. Check that relaxed R1CS is satisfied, and check that \pi_0 (W_{n+1}) = W^0_{n+1}.

This is completely analogous to normal n-fold, except we keep bringing this w^0-s everywhere. Small implementation detail: one could wonder, should we, in practice, hash [w^0]-s when folding them in. I claim that the answer is “not necessary” - they were already hashed when constructing \text{chall}, and it must be hashed by folding construction.

Proof ommitted, should be analogous to the above + use forking lemma.

IVC, synchronous version

Now, we are going to discuss the IVC. I am only going to talk about synchronous version (the one with the running hash from the main post), because I believe it is a harder and more interesting one.

One important warning is that all discussed here will inevitably be heuristic - as it is for the main Nova paper and all IVC constructions. This happens because the aforementioned protocols can be proved to be secure in non-interactive versions by using Random Oracle Model - replacing the challenges of the verifier with the random hash function to which prover and verifier have oracle access. However, IVC inevitably requires non-blackbox access to the verifier code - because it needs to turn it into a circuit. Therefore, we need to suppose that the above protocols are, in fact, secure with some concrete collision-resistant hash. In particular, our knowledge extractor for IVC will only extract us the computation trace with Assumption that there exists knowledge extractor for the underlying non-interactive 2-1 scheme. In practice, we don’t know such extractor, and it is unlikely to exist; in my defense I only want to say that this issue riddles the whole field of recursive SNARK validation.

Assumption: there exists an extractor \mathcal{E} for non-interactive 2-1 folding scheme.

Now, let’s recall IVC protocol. It constructs the circuit F', with non-trivial instance variables h, \text{run}. First represents the hash of the running instance, and the second represents the running hash of commitments [w^0_i].

The circuit F' performs the following work:

1. Guess i \geq 0 - step counter.
2. If i = 0, output h = H(vk, z_0, F(z_0), 1, u_b, 0), \text{run}=0, \text{chall} = \text{chall} (last one is non-deterministic guess). Otherwise,
3. Guess U_i, u_i, W^0_i, w^0_i, z_0, z_i
4. Constrain u_i.h = H(vk, z_0, z_i, i, U_i, W_i^0)
5. Calculate F(z_i) = z_{i+1}
6. Check that u_i is well-formed, i.e. its error term is 0 and u_i.x_0 = 1. Recall: u_i also has \text{chall} field. It is, currently, unconstrained.
7. (by guessing [w_i], [W_i] and cross-term) fold U_i and u_i to obtain U_{i+1}, W_i^0 and w_i^0 to obtain W_{i+1}^0. recall: coefficient \lambda in the fold does not depend on w^0-s.
8. Set h = H(vk, z_0, z_{i+1}, i+1, U_{i+1}, W_{i+1}^0), \text{run} = H(w_i^0, u_i.\text{run}), \text{chall}=u_i.\text{chall}.

Definition:

The IVC data on step i is (not committed, satisfying R1CS) (u_i, w_i), (U_i, W_i) and commitments to w^0_k for k>i.
Here is a subtlety: from now on, let’s assume that our commitments do not have blinding factors, i.e. construction of [X] from X is unique. I think it is manageable to avoid this, but I think it doesn’t matter too much because I do not thrive to achieve zk - and on the last step zk-snark will be applied anyways in practice.

The verification procedure is the following:

1. Check that running hash of the remaining commitments, starting from the interior hash u_i.\text{run}, in fact, equals u_i.\text{chall}.
2. Check that u_i.h = H(vk, ..., [U_i], [\pi_0 W_i]). //we could instead check that it is a commitment to U_i, but this is faster.
3. Check that u_i has error term 0 and u_i.x_0=1, u_i.\text{chall}=\text{chall}.
4. Check that w_i, W_i do satisfy respective constraint systems.

This is a bit more elaborate, let’s see why this scheme is complete, first, i.e. how to construct the solution.

Completeness

1. Commit to all the [w^0]-s of each step function (by executing first round of Prover strategy for each individual step).
2. Calculate nested hash \text{chall} = H(w^0_n, H(...H(w^0_1, H(w^0_1, 0))...)).
3. Submit it to step provers, so they can calculate full w_i's. //–snip-- this is the data which we will need to eventually extract
4. Proceed by induction. Assume we are given enhanced instance-witness triples (u_i, w_i, w_i^0) and (U_i, W_i, W_i^0) which are, in fact, solutions of the problem such that u_i has well-formed inputs u_i.\text{run} = H(w^0_{i-1}, H(w^0_{i-2}, ...)), u_i.\text{chall} = \text{chall}, and projection property holds. The base case is trivial, and inductive step looks as follows: guess the relevant data. Remember the result of folding W_{i+1}, and set w_{i+1} to be a computation trace of the circuit.

The checks pass trivially.

Knowledge soundness.

I’m writing this after few hours of staring on the page. Apparently, the worst thing one can do is attempt to prove it from 2-1 folding directly. It will break in a fascinating and painful way that I’m too ashamed to spell out here.

Instead, I will assume (in addition to plain Nova 2-1 extractor) an extractor of non-interactive n-fold protocol. This as also a heuristic assumption, with the same status: extractor exists for n-fold protocol in ROM, but then I instantiate it with some concrete hash functions and assume that it still exists.

We start by constructing first the normal Nova extractor (i.e. not care about w^0_i-s at all). This essentially repeats the argument from the Nova paper, quick recall:

Assume by induction we have extractor \mathcal{E}_{i-1} which unwraps (U_{i-1}, W_{i-1}), (u_{i-1}, w_{i-1}) into witnesses w_1, w_2, ... w_{i-1}. We will now build \mathcal{E_i}.

Starting from (U_i, W_i), (u_i, w_i), we see that the computation trace of w_i contains the 2-1 folding of [U_{i-1}], [u_{i-1}] to U_i, and W_i is a satisfying witness. Therefore, normal Nova 2-1 extractor will obtain (w_{i-1}, W_{i-1}). These do satisfy verification properties 3, 4 (and property 2 will be satisfied partially, in a sense that [W^0_{i-1}] occuring in circuit does not, anymore, need to be \pi_0(W_{i-1})). We then use \mathcal{E}_{i-1} (by induction).

This gives us, from the IVC solution, the following data: the sequence (u_i, w_i) for all i<n+1, and the corresponding accumulated instances (U_i, W_i). We also get (from the witnesses) the sequence [w^0_i], which are not yet constrained to satisfy projection property, but they satisfy the following two properties:

1. Being folded with the same coefficients as w_i's, they do give \pi_0(W_{n+1}).
2. \text{chall} = H([w^0_n], H([w^0_{n-1}], ...)) is, in fact, equal u_i.\text{chall} for all i.

Now, I claim that this is, in fact, the run for the non-interactive version of n-fold protocol (of which we assume the existence of extractor heuristically from the ROM model). \square

[barryWhiteHat]

Thanks for the post Lev.

Could you give some explicit examples to section “Adding the second round - Oragami approach” and " Adding a second round in a different way - my approach" ? I think this would help me build a toy python implmentation so i can play with it a bit. I would probbaly need an example with 4 elements in witness and constarints and 2 rounds of folding. Also comments of what is happening at each step would help me alot

For example the examples from Origami -- A Folding Scheme for Halo2 Lookups - HackMD are super helpful

Integer commitments

I am not sure how this allows you to do very cheap big int. IIUC you are still operating over a field it is just really big. I suppose you just have to range check for 64 or 256 bit numbers and then you know you are not going to overflow. Am i understanding correctly the benefits to big int ?

I am not sure i get how the circuit for folding can be very cheap. Could you give me an intuition ?

[nibnalin]

@levs57

Another very fruitful topic is potentially using Pedersen commitments in RSA groups.

I’m also curious how the rounding fraction commitments as in https://eprint.iacr.org/2021/540.pdf might interact with this idea: I don’t understand its details myself but it’s transparent and seem comparable in cost (and satisfy all the properties we care about I think?)

[levs57]

Could you give some explicit examples to section “Adding the second round - Oragami approach” and " Adding a second round in a different way - my approach" ?

I will try too cook something up, maybe even rough python implementation by myself. Examples from Origami post are fine, I just object that they do not work without my modification (or maybe they have fixed it already? I’ve asked authors to fix the problem some time ago…). Maybe I will come up with some minimal example.

I am not sure how this allows you to do very cheap big int. IIUC you are still operating over a field it is just really big. I suppose you just have to range check for 64 or 256 bit numbers and then you know you are not going to overflow. Am i understanding correctly the benefits to big int ?

I am not sure i get how the circuit for folding can be very cheap. Could you give me an intuition ?

Oh, I understood what you were saying when I’ve started implementing it my intuition was that operating with commitment is very friendly, so I do not need cycle of curves and thus do it in 1 wrapping operation instead of 2. It is correct, but I also assumed the hash will be easy, completely forgetting that Pedersen can not be used in this context because it is not pseudorandom… Still think that integer tricks should improve my life a lot, but yes, if we are using Poseidon - not much difference on this part.

[levs57]

Need to read about it.

[levs57]

A short update: I’ve also found a similar way of loading arbitrary data into the witnesses of a step-circuit. For example, loading grand product permutation there allows to unlock arbitrary copy constraints between different steps, (which I promptly announced in the main post without fully understanding the details).

This is done in a similar way - suppose there is a subset of a witness, “loading subset”, which I want to constrain to be w^1_{load}, w^2_{load} ..., w^n_{load}. Then, we can expose it (similar to how we expose w^0), and do the same trick with folding into accumulated partial witness W^{i}_{load}, and calculating running hash. The calculated running hash is then used for the integrity check, and folded partial witness for the projection check.

[CPerezz]

@levs57

It will, of course, mess up the computation of F^{n+1}(z_0) Fn+1(z0)F^{n+1}(z_0) if we adaptively choose these witnesses, but it will still be correct folding (up to our external check). Moreover, the part of the trace of computation of F FF that lives over S_0 S0S_0 does not change. I expect it is not possible to choose w_i wiw_i 's adaptively in such a way that its folding would give the folding of the trace of computation of F FF over S_0 S0S_0 .

It sounds to me that with a slightly modified forking lemma or some similar extractor proving mechanism it should be possible to proof security based on probability.

The point here is that there are many variables taking part on this. For instance, number of Error terms can vary.

@levs57

The idea is similar: the witness vector is proposed in each step. It is both folded in, and accumulated into a running hash. The running hash then, retroactively, must be equal to the challenge used at every step, and the folded witness is then used to ensure integrity.

Can’t vector commitments such as KZG or similar be helpful here? I was hoping they’ll give better performance in and out of the circuit. Also this opens some ideas like defering checks to an aggregated pairing at the end of the F_{n-1} fold.

@levs57

I’m not exactly sure about this part, but I think it is worth researching. Of course even if everything works, we will still need to create trusted setup ceremony, which looks very hard for RSA, but provided this is done we would be able to finally do integer arithmetic normally, which looks like it is worth a shot.

Is there any tooling that can already be used with unknown order groups/RSA groups?
Is there literature in regards the limitations and pros/counts of these? It sounds super interesting!!!

[levs57]

It sounds to me that with a slightly modified forking lemma or some similar extractor proving mechanism it should be possible to proof security based on probability.

Yes, indeed. I give some proofs in my comment, interactive version seems to hold in random oracle model, and non-interactive depends on the same heuristic as normal Nova IVC.

Can’t vector commitments such as KZG or similar be helpful here?

I thought about it, but thing that I particularly like about Nova is the fact that we are actually holding the same commitment. But indeed you could use generators of the form \tau^i G_j on step j, with G_j-s being picked randomly and \tau's being toxic waste. But I’m not sure it is actually worth it, overhead of running hash is pretty small. But mb you can defer all the checks, I’m not sure yet.

Is there any tooling that can already be used with unknown order groups/RSA groups?

There is a paper of a protocol called SuperSonic, which uses commitment scheme DARK, which I think actually preceeds KZG-PlonK, but it uses very different approach, they actually encode polynomials over \mathbb{F}_p inside of an integer. I think it is a bit more useful to instead use relatively small integers (because multiplication of big integers also requires FFT, just like multiplication of big polynomials), and just abuse various tricks like fast range checks, divisibility, and such.

One particular case where really big integers (hundreds of megabytes in size) can be a negotiable proposition in Nova context is RSA-accumulators (see GitHub - cambrian/accumulator: Cryptographic accumulators in Rust.) - which are updateable cryptographic accumulators, they can be used in-circuit for small-ish lookups or for discussed problem of “permanent” memory, that we’ve talked about with you.

Best theoretical result for range checks says that you can range check an integer in one quadratic constraint involving 3 additional advice values: x \in [A; B] \iff \exists m, n, k \text{ | }4(x-A)(B-x) = m^2 + n^2 + k^2, and I’m not sure what is the reference here, I’ve seen it somewhere and lost it.

There is an extensive discussion on integer commitments, keyword here is probably “Damgard-Fujisaki”, which just means “Pedersen in RSA group, but blinding is now pain in the ass”. Luckily, in what we are discussing we only care about succintness and soundness, not zk (and it probably can be added later).

Actually I hoped that I’ll get some feedback from more theoretically involved people… There are some landmines definitely - for example, DARK works in different assumptions than my scheme, because in ideal class groups you can calculate square roots - so you only get rational commitments, which could become integer after the folding with non-zero probability. They somehow cope with this, I’m just planning to use RSA group (and wonder whether there are other possible landmines, it seems no, but I need experts to look on this).