Two-phase circuit construction with intermediate commitments

[oleganza]

Problem

Our current R1CS interface allows constructing constraints using challenges bound to the external variables (V). This, however, may be risky for complex circuits. For example, a shuffle gadget is only binding if inputs on both sides are committed. However, if one side remains uncommitted (e.g. when there is a circuit in between two shuffles and only "outer" sides are ultimately committed), then the low-level variables on that side can be forged based on the knowledge of the challenge.

Disclaimer

This is an over-the-napkin draft of a maybe-solution. Little attempt was made to analyze the alternatives or soundness of this proposal.

Goal

Make gadgets locally sound by giving an opportunity to commit to input low-level variables, regardless of whether they are indirectly committed via high-level variables.

Proposal

We split the circuit construction in two phases: wireframing phase and completion phase.

Wireframing phase

Gadgets can allocate low-level variables, add constraints, but cannot use challenges. This phase produces first pair of vector commitments A_I1 and A_O1 to these variables. The constraint system trait is called WireframeCS.

This allow allocating all the gadgets and all variables between them, assigning required values to these variables. But not all gadgets can implement their internal constraints yet because they need challenge values.

The phase ends with two points A_I1 and A_O1 computed and sent to the transcript, committing to all the low-level variables allocated so far.

Completion phase

Gadgets can allocate more low-level variables, add more constraints and can use challenges. This phase produces second pair of vector commitments A_I2 and A_O2 to these additional low-level variables. The constraint system trait is called CompleteCS.

This allows implementing gadgets, such as shuffle or merge using challenges, making them locally sound because all input variables for any given gadget are already committed via A_I1/A_O1.

After the Completion Phase is complete, full commitments to the low level variables are computed and sent to the transcript:

transcript.commit_point(A_I2);
transcript.commit_point(A_O2);
let e = transcript.challenge_scalar();
let A_I = A_I1 + e*A_I2;
let A_O = A_O1 + e*A_O2;

The verifier's logic is:

1. The proof now contains 2 more points (A_I1,A_I2,A_O1,A_O2 instead of A_I,A_O).
2. The verifier starts by making the wireframe of the circuit: allocating variables and adding constraints that do not use challenge values.
3. Then, the verifier sends A_I1, A_O1 to the transcript.
4. The verifier then completes the circuit by allocating more variables, adding more constraints and using challenges to compute weights for these constraints.
5. The verifier sends A_I2, A_O2 to the transcript and gets a challenge e that prevents cancelling of one part of commitment by another.
6. Finally, vector commitments are summed up to A_I and A_O which are used in the rest of the protocol: A_I = A_I1 + e*A_I2, A_O = A_O1 + e*A_O2. Note: we do not need to commit the resulting sum A_I as in current BP protocol because we've already committed both components individually (A_I1 and A_I2).
7. The protocol proceeds as usual, only with challenge e applied to second subset of generators.

Alternative: committing via additional high-level variables

Committing to required low-level variables via additional high-level variables. This works using the current architecture almost w/o changes, but the proof size grows linearly with the size of the circuit.

Alternative: multi-phase protocol

The scheme above can be generalized to have arbitrary number of phases with A_I1,A_I2,A_I3,... etc. intermediate commitments. With use cases at hand, it seems that two phases might be enough. Also, the two-phase protocol guarantees a constant (64-byte) overhead in the proof size, while more flexible API could allow the proof to grow unbounded and harder to reason about its size.

[oleganza]

EDIT: after talking to @cathieyun, I realized that we need an extra challenge to add up two "halves" of vector commitments securely (so one does not cancel out the other). Updated the proposal accordingly.

[oleganza]

Update after discussing the problem:

Option A: to patch up CA protocol with additional high-level commitments for internal wires and use Mixes w/o challenges and keep BP design as is.

Option B: implement something like the above with closure/future-based API to have clear way for gadgets to show which wires need to be computed early and committed to, and which are computed later, when they can use challenges w.r.t. committed wires.

The plan is:

1. Finish up all other outstanding tasks
2. Get back to the problem and estimate how time-consuming / unclear the solution would be (option B).
3. If the solution is straightforward and quick, just do it.
4. If it's fuzzy and complicated, switch to option A to patch up CA, and get back to proper solution later.

[oleganza]

Just dumping some thoughts.

(1) Let's assume we will end up having a verification equation with something like A1 + e*A2 where e is sampled after A1 is committed (otherwise, A2 can cancel out A1 and commit to different values in the first-phase variables after e is known). I'm trying to find a right place where such e would get introduced. Our challenges y,z are introduced after all variables are assigned, in no particular order.

We want to enforce that second-phase variables are only computable after the first-phase variables are computed. I wonder what's the cleanest algebraic way to represent this ordering requirement? Challenges y,z,w,r do not serve this purpose: they instead allow combining several independent statements in one. Challenge x is slightly different, but mostly the same idea, we just focus on the structure of one term, ignoring others (instead of verifying that all terms have a specific value).

(2) In the above, I assumed we only have two phases. That is good for a constant proof overhead, but we need to figure if it's flexible enough for different uses. One concerning use-case is combination of the shuffle gadget and the tuple compressor gadgets: the shuffle wants its wires to be committed (or at least "binding" in some sense), but its wires are actually compressed tuples. In principle, if someone guarantees to the tuple compressor that the tuple itself is "committed", then the tuple can transitively guarantee that its output is "binding" for the next gadget (the shuffle). Then, the shuffle can just assume that these input wires are non-malleable and use challenges to produce internal structure with a peace of mind. If the API allows representing these guarantees and prevents circular dependencies, that might be a good thing to have.

[oleganza]

After a very insightful conversation with @cathieyun, we had these ideas laid out:

1. The BP framework only enforces the constraints, but not the order in which variables are assigned. That explains why things like shuffles can be broken: they need to force a specific order.
2. The right starting point in the writeup is the 2d equation <l,G>+<r,H>=... where commitments are introduced.
3. We can split that equation in two parts, for the first slice of multipliers and first slice of constraints, and for the second slices respectively. In each equation we'd use corresponding commitments. If both are true, then commitments are correctly formed and committed assignments satisfy all constraints.
4. The ordering of the commitments is enforced by sending the first one to the transcript before we allow gadgets to squeeze the internal challenges.
5. Finally, we can merge two checks <l,G>+<r,H>=... (w.r.t. to each commitment) in one statement by using a challenge e. It curiously propagates to H' which means we'll send these adjustment scalars to IPP: {e * y_i^-n}.

[oleganza]

The only remaining question is what's the right way to slice the linear constraints? Because the second subset of the linear constraints touches all variables, not just the new ones.

[oleganza]

A few observations from the CA:

1. The tx gadget produces internal variables w/o any requirement on whether the external variables are committed (because it does not directly use the challenges). Notably, tx gadget chooses assignments more-or-less freely, based on secret values, in order to satisfy downstream gadgets, and not fully deterministically in response to the constraints at its level.
2. The value shuffle gadget compresses the input values using a challenge, so it requires them to be determined (committed?), and it allocates the internal variables with assignments based on these input values to pass into the scalar shuffle gadget.
3. The scalar shuffle gadget builds a polynomial equality check sample at a challenge, so the inputs must be determined. But the inputs cannot be committed: they are themselves are challenge-based, but in the case of value_shuffle ⚬ scalar_shuffle) composition, the inputs are determined via the linear combination over committed values.

[oleganza]

Our goal is to make use of challenges safe. This means, we should make static guarantees that challenges are not available until the available variables are either committed or determined in some way.

Specifically, in the example above, what if (hypothetically, this is not how CA works) the tx gadget receives challenge-based variables? Then, the internal variables are chosen freely based on the secret values and must be committed before passed into shuffle/mix gadgets. But in a 2-phase setting they cannot be committed again: they are already in the second phase. On the other hand, free choice based on challenges does not make a lot of sense, as those are randomized by definition and so the choice depends on a chance and (probably) can only be used as an exploit, not as a feature.

So there are two ways to address this:

1. Expand commitment phases to arbitrary number of phases. So CS keeps track at which phase a variable is determined, and when a gadget needs to wait till commitment of a set of variables, it will wait till the latest one is committed. Unfortunately, it makes reasoning about the size of the proof and "depth" of the circuit harder, and probably does not match the semantics anyway (why allow free choice of lower-level variables for challenge-based input variables?)
2. Encapsulate challenge-based variables in a different type, possibly with restriction on access to the underlying value, to make it impossible to misuse them in the gadgets that need to inspect the values.

[oleganza]

Actually, there's a clearer explanation why we should not expose the challenge value. Because the gadgets like "mix" and "shuffle" use statements like "these statements are true iff this polynomial over x is equal to 0 over all values of x", where the fact that we actually sample a specific x is an implementation detail. The statements should be true for all x. This means, if we have a variable which is a linear combination of powers of x (<a,b,c), (x^0, x^1, x^2)>), then the gadget cannot rely on knowing the exact value. So we are free to isolate it (even if we actually compute it right away for efficiency).

[oleganza]

Since tx gadget needs to inspect the assignments, it can only use the "inspectable" variables. These could be the high-level vars, or first-phase vars.

Since scalar_shuffle can be used with both second-phase and first-phase variables, and does not need to inspect the actual values, it must take in more restricted "non-inspectable" variables. But it can be called with first-phase CS, and inspectable variables, so we need a way to upcast the inspectable to an non-inspectable one.

[oleganza]

Idea:

1. Rename Variable to VariableIndex
2. Introduce struct OpenVariable(Variable)
3. Introduce struct Variable(VariableIndex, Assignment)
4. OpenVariable allows access to the assignment, and can be "upcast" to the Variable.
5. Two traits for constraint systems: StaticConstraintSystem and DynamicConstraintSystem.
6. StaticCS has method .after_commitment<T:DynamicCS>(FnOnce(T) -> ()) which allows a gadget to perform necessary work in the second-phase where challenges can be used.
7. Challenges are wrapped in OpaqueScalar type that can be used indirectly to compute variable assignments and constraints, but not to read the actual value out.
8. DynamicCS impls StaticCS by calling after_commitment closure right away.
9. Assignments and constraints can be constructed both using direct scalars, but also using linear combinations in terms of OpaqueScalars, and closed Variables.
10. Additional convenience API allows allocating a variable together with a constraint using a single expression to avoid code duplication and minimize error.

[hdevalence]

One idea @cathieyun and I discussed in August with the ZCash folks was to express the phasing using futures, which allows the actual computation of the assignment to be deferred to a later phase, and might make it possible for the API to handle the phasing on its own. For instance if there are two functions, one for allocating a variable with an assignment, and another for allocating a variable with a future assignment, then the first "half" corresponds to calls to the first function and the second "half" corresponds to calls to the second one, and maybe we don't really need to change the protocol so much.

[oleganza]

Expanding the idea about futures:

1. CS.challenge_scalar returns a future scalar with an embedded index. The index is set to the current challenge counter that's incremented at each call.
2. The futures can be combined and lazily allocated multipliers and constraints can be added to the CS.
3. When CS is fully built, all non-lazy assignments are committed and sent to the transcript, then the challenges are produced in order and are assigned to the outstanding futures.
4. We can either have explicit combinators using .then() to propagate computation from challenges bottom-up into the results, or allocate the array of challenges and evaluate variables and constraints top-down. In either case, we'd need to make combinators out of Add/Sub/Mul operators and box the resulting random types so they can be stored in the arrays of variables and constraints.
5. Once the CS evaluated lazy variables and constraints, it finishes the second-phase commitment and proceeds as usual.

[oleganza]

Seems like, in order to accumulate future variables and constraints, we cannot use zero-cost iterator-style AST representation of our lazy evaluations (regardless of whether they are closure-based or based on structs like Addition, Multiplication etc).

Instead, a simpler option is to have async method CS.challange_scalar(label, closure) that's called after the CS is committed. Inside, we can compute remaining variables and constraints. We should still probably keep the OpaqueScalar to prevent accidental use of gadgets that expect non-opaque variables (like tx gadget) after the challenges are generated.

[oleganza]

Update: the async challenge API and 2-phase protocol is now fully implemented & documented in this PR: https://github.com/dalek-cryptography/bulletproofs/pull/196

[oleganza]

Continuing here: #222.