owned this note
owned this note
Published
Linked with GitHub
# Gate refactor [WIP]
**TODO**: Specify aim
- Configurable number of wires
- Unified internal API for gates
- Configurable number of custom gates per circuit.
The low-level design is based around `Constraint`s and `Gate`s.
## Constraints
We conceptualize 2 ways of thinking about constraints (as opposed to Gates):
1. Constraints can be thought of a single row in halo2 circuit (Within a specific Region).
2. They can also be thought of as a term in the quotient polynomial.
Sometimes the concept of gate may coincide, in the sense that we can have single-constraint gates. An example of this can be the arithmetic gate.
However this is not necessarily the case. The `LogicGate` uses many constraints, in particular for an input of `b` bytes it uses `b/4 + 1` `LogicConstraint` gates.
**Some assumptions**
::: danger
**TODO**: check if these are reasonable.
What are their implications?
We should write down the actual version of our quotient poly.
:::
::: info
- Wires are shared between all the gates. We refer to them as:
`w_1, w_2, ..., w_i`
- Wire selectors are also shared between all the gates. These are the
selectors that multiply just one wire: `q_i * w_i`
:::
### Configuration
The `Commitment` type, as well as the `Field` and the number of wires should be derived from a `Config` as explained in [this issue](https://github.com/ZK-Garage/plonk/issues/128).
``` rust
trait Configuration {
/// Total Number of Wires Accessible to the Compiler
const WIRE_COUNT: usize;
/// Scalar Field Type
///
/// This type represents the underlying coefficient field for polynomial constraints.
type Field: ark_ff::Field;
/// Polynomial Commitment Type
type Commitment;
...
```
We could have different implementations of gates/constraints for
different types of fields for example. However the most likely use case
will be having implementations that are generic over the field and PCS and
specific to a certain number of wires.
``` rust
/// These are the extra inputs needed in a gate other
/// than the wire values of the current rotation
trait ConstraintInput<C, const N: usize>
where
C: Configuration<WIRE_COUNT = N>
```
``` rust
pub trait Constraint<C, const N: usize>
where
C: Configuration<WIRE_COUNT = N>
{
/// Fixed columns of the constraint
type Fixed: ConstraintFixed<C, N>
/// Return the commitments that the constraint will add to vk.
fn commitments(...) -> Vec<C::Commitments>;
/// Return the commitments that the constraint will add to the proof.
fn eval(...) -> Vec<C::Field>;
/// prepares the data structures in the std composer for gates that use this constraint
/// TODO: Concrete how.
/// Install may be moved to the Compiler
fn install(sc: &mut StandardComposer);
fn add_constraint(&self, input: Self::Fixed,
wires: [Variable; N],
compiler: &mut Compiler);
}
```
> Not sure here which is the purpose of `install`. I don't see which modifications need
> to be done to the Composer from the `Constraint` trait.
> The only thing I can imagine would be to extend the `Vec<Wires>` or `Vec<Selectors>`.
> But this would mean that it needs to know the order on which they're installed and the order so
> that re-using wires and selectors is possible.
> [name=CPerezz]
> One idea is that `install` receives a `&mut Compiler` instance and adds the constraint installation as:
> `Box<impl FnMut(&mut Compiler, [w,i,r,e,s], [s,e,l,e,c,t,o,r,s])>`
> That means the `Compiler` holds a `Vec<Box<impl FnMut([Variable; N], [F;M])>` with `const M, N: usize`.
> On that way, the installation takes care of actually adding into the compiler the logic of how to create a specific Constraint.
>
> Assuming that, inside the Compiler we should have access to all of the Wires and Selectors identified by some string or ID.
> On that way we can re-use them cross-constraints types.
> [name=CPerezz]
> The purpose of install is simply to keep track of which constraints are used in a circuit. This allows the `Compiler` to know the actual structure
of the proof, verifier and prover keys. In addition, these installs should
provide the `Compiler` with the list of constraints whose contribution is
needed for the quotient and linearization poly.
> With regard to the wires I think the best approach is to handle them in
the `Compiler`. In the declaration of the circuit the `Configuration` establishes the number of wires, then with each constraint installation we check their compatibility (essentially that they don't need more wires than the specified number for the circuit ).
> [name=davidnevadoc]
### Example 1
This is a simple example that uses 5 wires and no rotations.
Implementation of a 5 width arithmetic gate with 2 multiplications.
``` rust
// q_arith * (
// q_mul1 * w_1 * w_2 +
// q_mul2 * w_3 * w_4 +
// q_1 * w_1 +
// q_2 * w_2 +
// q_3 * w_3 +
// q_4 * w_4 +
// q_5 * w_5 +
// q_constant +
// PI )
pub struct ArithmeticInput<C>
where
C: Configuration,
{
q_mul1: C::Field;
q_mul2: C::Field;
q_constant: C::Field;
// Assuming wire selectors (q_1, q_2,...) are common
// across all gates, and therefore added by the standard composer.
// this may change...
// Gates that use rotations also specify their values here.
};
impl ConstraintInput<C, 5>, for ArithmeticInput<C>
where
C: Configuration<WIRE_COUNT = N>
```
::: info
Consider what is the best struct to store these values.
If each constraint holds its selector values independently they
should keep track of the index (row number in the circuit) or the
compiler should.
:::
``` rust
pub struct ArithmeticConstraint<C>
where
C: Configuration,
{
type Input = ArithmeticInput<C, 5>
// Define its selectors / fixed columns
q_arith: Vec<C::Field>;
q_mul1: Vec<C::Field>;
q_mul2: Vec<C::Field>;
q_constant: Vec<C::Field>;
// Witness values (rotations included)
// are not included here (?)
};
impl Constraint<C, 5> for ArithmeticConstraint<C>{
/// Return the commitments that the constraint will add to vk.
fn commitments(commit_key: PC::CommitKey, ...)-> Vec<C::Commitments>{
let polys = vec![DensePolynomial::from(self.q_arith),
DensePolynomial::from(self.q_mul1),
DensePolynomial::from(self.q_mul2),
DensePolynomial::from(self.q_constant)]
let (comms, _) = PC::commit(commit_key, polys.iter(), None);
comms
// Assuming the wire selectors q_1, q_2,... are common and thus
// will be added by the compiler
}
/// Return the evaluations that the constraint will add to the proof.
fn eval(...) -> Vec<C::Field>{
// This polynomial in particular does not add extra evaluations.
// The reason for this is that having evals of all wires and
// wire selectors we have a linear polynomial without needing
// extra evaluations.
vec![]
}
/// This may be removed and added in the StandardComposer instead
/// prepares the data structures in the std composer for gates that use this constraint
/// Adding a reference to the struct in the StandardComposer (?)
fn install(sc: &mut StandardComposer);
... // it knows how to set up the standard composer for its contribution to quotient
}
// In this design the values for the selectros are stored in the
// constraint struct. The compiler has a reference to this struct.
fn add_constraint(&self, input: Self::Input,
wires: [Variable; N],
compiler: &mut Compiler)
{
// gate selector activated
self.q_arith.push(F::one());
// fixed columns
self.q_mul1.push(input.q_mul1);
self.q_mul2.push(input.q_mul2);
self.q_constant.push(input.q_constant);
// wire values
// The standard composer should handle the wire values
compiler.add_wires(wires)
// compiler.add_wires( input .. rotations if we have.. )
}
```
### Example 2
Variable base EC addition.
The first version shows the handling of gates with rotation.
The second version eliminates rotations at the expense of a wider circuit.
#### Version 1. - 4-width + 1 rotation-
``` rust
// P1 = (x1, y1)
// P2 = (x2, y2)
// P3 = P1 + P2 = (x3, y3)
// k = separation challenge
//
// Auxiliary cells:
// x1y2 = x1 * y2
//
// Circuit Layout:
// ---------------
//
// 1 | 2 | 3 | 4 |
// -----------------------
// x1 | y1 | x2 | y2 |
// x3 | y3 | 0 | x1y2|
//
//
// The constraint is
// q_vbca *(
// (x1 * y2 - x1y2 ) +
// ((x1y2 + y1 * x2) - x3 + (x3 *COEFF_D * x1 * y2 * y1 * x2)) * k +
// ((y1 * y2 + x1 * x2) - y3 + (y3 * COEFF_D * x1 * y2 * y1 * x2) ) * k^2
// )
//
// written with polynomial notation,
// where a, b, c, d are the wire polynomials and w is the root of unity:
// q_vbca(X) *(
// (a(X) * d(X) - d(wX) ) +
// ((d(wX) + b(X) * c(X)) - a(wX) + (a(wX) *COEFF_D * a(X) * d(X) * b(X) * c(X))) * k +
// ((b(X) * d(X) + a(X) * c(X)) - b(wX) + (b(wX) * COEFF_D * a(X) * d(X) * b(X) * c(X)) ) * k^2
// )
// Variable Base Curve Addition
pub struct VBCAInput<C>
where
C: Configuration,
{
w1_rot1: Variable,
w2_rot1: Variable,
w4_rot1: Variable,
};
impl ConstraintInput<C, 4>, for VBCAInput<C>
where
C: Configuration<WIRE_COUNT = N>
// Variable Base Curve Addition
pub struct VBCAConstraint<C>
where
C: Configuration,
{
type Input = VBCAInput<C, 4>
q_vbca: Vec<C::Field>,
};
impl Constraint<C, 5> for ArithmeticConstraint<C>{
/// Return the commitments that the constraint will add to vk.
fn commitments(commit_key: PC::CommitKey, ...)-> Vec<C::Commitments>{
let polys = vec![DensePolynomial::from(self.q_arith)];
let (comms, _) = PC::commit(commit_key, polys.iter(), None);
comms
}
/// Return the evaluations that the constraint will add to the proof.
fn eval(...) -> Vec<C::Field>{
// Double check this
// x3 and y3 evals are not needed to get a linear poly
// Only q_vbca and w4_rot1 (x1y2) are needed
vec![
DensePolynomial::from(self.q_vbca).eval(challenge),
// get evals at omega^rot_n * challenge from compiler
]
}
/// This may be removed and added in the StandardComposer instead
/// prepares the data structures in the std composer for gates that use this constraint
/// Adding a reference to the struct in the StandardComposer (?)
fn install(sc: &mut StandardComposer);
... // it knows how to set up the standard composer for its contribution to quotient
}
// In this design the values for the selectros are stored in the
// constraint struct. The compiler has a reference to this struct.
fn add_constraint(&self, input: Self::Input,
wires: [Variable; N],
compiler: &mut Compiler)
{
// gate selector activated
self.q_vbca.push(F::one());
// fixed columns
//
// wire values
// The standard composer should handle the wire values
compiler.add_wires(wires)
// compiler.add_wires( input .. rotations if we have.. )
compiler.add_wires([input.w1_rot1,
input.w2_rot1,
compiler.zerovar,
input.w4_rot1,
])
}
```
#### Version 2 - width 7 -
``` rust
// P1 = (x1, y1)
// P2 = (x2, y2)
// P3 = P1 + P2 = (x3, y3)
// k = separation challenge
//
// Auxiliary cells:
// x1y2 = x1 * y2
//
// Circuit Layout:
// ---------------
//
// 1 | 2 | 3 | 4 | 5 | 6 | 7 |
// -----------------------
// x1 | y1 | x2 | y2 | x3 | y3 | x1y2|
//
//
// The constraint is
// q_vbca *(
// (x1 * y2 - x1y2 ) +
// ((x1y2 + y1 * x2) - x3 + (x3 *COEFF_D * x1 * y2 * y1 * x2)) * k +
// ((y1 * y2 + x1 * x2) - y3 + (y3 * COEFF_D * x1 * y2 * y1 * x2) ) * k^2
// )
//
// written with polynomial notation,
// where a, b, c, d, e, f, g are the wire polynomials:
// q_vbca(X) *(
// (a(X) * d(X) - g(X) ) +
// ((g(X) + b(X) * c(X)) - e(X) + (e(X) *COEFF_D * a(X) * d(X) * b(X) * c(X))) * k +
// ((b(X) * d(X) + a(X) * c(X)) - f(X) + (f(X) * COEFF_D * a(X) * d(X) * b(X) * c(X)) ) * k^2
// )
// Variable Base Curve Addition
pub struct VBCAInput<C>
where
C: Configuration,
{
};
impl ConstraintInput<C, 7>, for VBCAInput<C>
where
C: Configuration<WIRE_COUNT = N>
// Variable Base Curve Addition
pub struct VBCAConstraint<C>
where
C: Configuration,
{
type Input = VBCAInput<C, 7>
q_vbca: Vec<C::Field>,
};
impl Constraint<C, 7> for ArithmeticConstraint<C>{
/// Return the commitments that the constraint will add to vk.
fn commitments(commit_key: PC::CommitKey, ...)-> Vec<C::Commitments>{
let polys = vec![DensePolynomial::from(self.q_vbca)];
let (comms, _) = PC::commit(commit_key, polys.iter(), None);
comms
}
/// Return the evaluations that the constraint will add to the proof.
fn eval(...) -> Vec<C::Field>{
vec![
DensePolynomial::from(self.q_vbca).eval(challenge),
]
}
/// This may be removed and added in the StandardComposer instead
/// prepares the data structures in the std composer for gates that use this constraint
/// Adding a reference to the struct in the StandardComposer (?)
fn install(sc: &mut StandardComposer);
... // it knows how to set up the standard composer for its contribution to quotient
}
// In this design the values for the selectros are stored in the
// constraint struct. The compiler has a reference to this struct.
fn add_constraint(&self, input: Self::Input,
wires: [Variable; N],
compiler: &mut Compiler)
{
// gate selector activated
self.q_vbca.push(F::one());
// fixed columns
//
// wire values
// The standard composer should handle the wire values
compiler.add_wires(wires)
// compiler.add_wires( input .. rotations if we have.. )
}
```
### MultiConstraints
There are no optimization across constraints. This means mainly no
shared selectors (fixed columns) and no maximum optimization in the
linearization polynomial.
The `MultiConstraint` trait is a way to allow several constraints to be combined into one and in this way, optimize selectors and evaluations they may share.
``` rust
pub trait MultiConstraint<C> {
where
C: Configuration
{
///
fn commitments(...) -> Vec<C::Commitments>;
///
fn evals(...) -> Vec<C::Field>;
/// install all the constraints represented by this multi-constraint
///
/// what constraints can the circuit construction use, contribution to quotient polynomial
fn install_all(c &mut StandardComposer);
}
```
> I think we will need to store the Selectors "named" as I don't really see how from one particular
> trait impl we can access the previous installed stuff.
> One idea would be to make 2 `install` rounds.
> 1. Extends the Wire and Selector vectors.
> 2. Adds the `Constraint` generator fn Boxed. See my previous comments above about this.
> [name=CPerezz]
> I think that to obtain maximum modulararity we should limit the components shared between constraints to **wires** and **wire selectors**. Trying to make automatic optimizations, such as reusing selectors in different gates will greatly increase the complexity of the design and may yield very little benefit.
> The idea of `MultiConstraint` is that if optimizations of this sort are really necessary, the user has the option of defining a combined constraint in which he can specify how these optimizations are made.
> [name=davidnevadoc]
### Example 3
Combining 2 `Constraints` allows for manual optimizations. Mainly shared
selectors and a more optimal linerization.
``` rust
///
pub struct OptimizedArithLogic;
```
## Gates
The `Gate` is the interface that a user building a circuit should use. It should hold the logic for how the rows or constraints must be added to the
standard composer to achieve the desired gate.
``` rust
pub trait Gate<C, const N: usize>
where
C: Configuration<N>,
{
/// Constraints that are required for this Gate to work
type Constraints: Constraint<C, N>;
/// ???
fn constraints() -> Self::Constraints;
/// explicit Circuit construction
/// TODO This can't handle rotations
fn add_constraints(
&self,
wire_selectors: [C::Field; N],
wires: [Variable; N],
compiler: &mut StandardComposer<C, N>,
);
}
```
> I envision this as:
> You specify the Constraint type/types. Once done, `add_constraints` contains the logic to generate an
> Array of constraints which is passed to the Composer to fill the Constraint list that it holds.
> It also takes care of computing all of the intermediate values needed to build the gate constraints.
> [name=CPerezz]
``` rust
pub struct Power;
impl Constraint for Power { }
pub struct SBox;
impl Gate for SBox {
type Constraints = (Arithmetic, Power);
}
```
``` rust
pub struct LogicConstraint;
impl Constraint for LogicConstraint {
... // it knows how to set up the standard composer for its contribution to quotient
}
pub struct LogicGate;
impl Gate<4> for LogicGate {
fn add_constraints(&self, wires: [Variable; 4], compiler: &mut Compiler) {
/// will use LogicConstraint (that has already been installed in the compiler)
...
}
}
```
``` rust
pub struct Arithmetic<const N: usize> {
mul: F,
wire_selectors: [F; N],
}
impl Gate<4> for Arithmetic<4> {
fn add_constraints(&self, wires: [Variable; 4], compiler: &mut Compiler) {
todo!()
}
}
fn booleanity_gate() -> Arithmetic<4> {
Arithmetic { mul: 1, wire_selectors: [-1, 0, 0, 0] }
}
fn circuit(compiler: &mut Compiler) {
booleanity_gate().add_constraints([x, zerovar, zerovar, zerovar], compiler);
}
```
::: danger
**TODO** Would be good to define 2 stages:
1. A first stage where the configuration + installed gates is specified
2. The actual circuit building steps
The idea would be to avoid weird behavior if a gate is installed midway
through the building of the circuit.
:::
> I discussed this with @davidnevadoc and expressed the fact that we need to be careful with
> defining installations, then adding constraints and then install more gates.
> This will result in mismatching len wire/selector vectors.
> Also, It might be better to define 2 install phases. One where the `Wire` and `Selector` Vectors are
> extended and another where they inclusion of the Constraint generation fn is added to the `Compiler`.
``` rust
fn circuit() {
/// RAW API
compiler.install(ArithmeticConstraint { ... });
compiler.install(LogicConstraint { ... });
compiler.install(EccConstraint { ... });
compiler.install(LookupConstraint { ... }); // whatever you need to do
compiler.install(CopyConstraint { ... });
/// REGULAR API
// could be automatically derived from some programming context???
// compiler.install(ArithmeticConstraint { ... });
// compiler.install(LogicConstraint { ... });
// compiler.install(EccConstraint { ... });
// if theres a way to detect which constraints have already been turned on,
// then you can inline the installation into the gate constructions?
// - O(1) membership check for constraints "map?"
/*
let gate = ArithmeticGate { ... };
compiler.register_capabilities(gate); /// internally this calls `Arithmetic::Constraints::install_all` if it hasn't already been called??
*/
}
```
> We can try to impl attribute macros or similar so that is easier for the user to just write the circuit logic and forget about
> the compilation stuff.
> [name=CPerezz]
Sign in with Wallet
