DSL

introduces a simple DSL, originally from 0xPARC's Plonkathon, for writing circuits that can be compiled to polynomials specific to PLONK prover's algorithm.

let's take an example to compute :

x public
x2 <== x * x
out <== x2 * x + 5

Each line of DSL is a separate constraint. It's parsed and converted to corresponding WireValues, i.e. variables and coefficients for each wire. Vanilla PLONK supports fan-in 2 arithmetic (add and mul) gates, so each constraint can only support a maximum of 1 output and 2 distinct input variables with numeric constants.

Parser rules

  • supports <== for assignment and === for arithmetic equality checks
  • mark variables as public in the beginning of the program.
  • only supports quadratic constraints, i.e. don't support y <== x * x * x.
  • each token should be separated by space.

Outputs parsed output in form of WireCoeffs values and coefficients.

  • wires: represent variables corresponding to gate wires in each constraint.
  • coefficients: coefficient corresponding to each variable.
#![allow(unused)]
fn main() {
/// Values of wires with coefficients of each wire name
#[derive(Debug, PartialEq)]
pub struct WireCoeffs<'a> {
  /// variable used in each wire
  pub wires:  Vec<Option<&'a str>>,
  /// coefficients of variables in wires and [`Gate`]
  pub coeffs: HashMap<String, i32>,
}
}

Example parser outputs

  • x public => (['x', None, None], {'$public': 1, 'x': -1, '$output_coeffs': 0}
  • b <== a * c => (['a', 'c', 'b'], {'a*c': 1})
  • d <== a * c - 45 * a + 987 => (['a', 'c', 'd'], {'a*c': 1, 'a': -45, '$constant': 987})

Some default coefficients are used for certain constraints:

  • $constant: for constant variables
  • $output_coeffs: for output variables. Example: -a <== b * b has $output_coeffs as -1
  • $public: for public variable declarations

Our example wire values gets parsed as:

  • x public => ['x', None, None], {'$public': 1, 'x': -1, '$output_coeffs': 0}
  • x2 <== x * x => ['x', 'x', 'x2'], {'x*x': 1}
  • out <== x2 * x + 5 => ['x2', 'x', 'out'], {'x2*x': 1, '$constant': 5}

Gate

Gate represents the values corresponding to each wire in a gate:

flowchart BT
l[left input]-->a((x))
r[right input]-->a
a-->o[output=l*r]

l2[left input]-->b((+))
r2[right input]-->b
b-->o2[output=l+r]

#![allow(unused)]
fn main() {
/// Fan-in 2 Gate representing a constraint in the computation.
/// Each constraint satisfies PLONK's arithmetic equation: `a(X)QL(X) + b(X)QR(X) + a(X)b(X)QM(X) +
/// o(X)QO(X) + QC(X) = 0`.
pub struct Gate {
  /// left wire value
  pub l: PlutoScalarField,
  /// right wire value
  pub r: PlutoScalarField,
  /// output wire, represented as `$output_coeffs` in wire coefficients
  pub o: PlutoScalarField,
  /// multiplication wire
  pub m: PlutoScalarField,
  /// constant wire, represented as `$constant` in coefficients
  pub c: PlutoScalarField,
}
}

Taking our example:

  • x public => ['x', None, None], {'$public': 1, 'x': -1, '$output_coeffs': 0}
    • gate values are: {'l': 1, 'r': 0, 'o': 0, 'c': 0, 'm': 0}
  • x2 <== x * x => ['x', 'x', 'x2'], {'x*x': 1}
    • gate values: {'l': 0, 'r': 0, 'm': -1, 'o': 1, 'c': 0}
  • out <== x2 * x + 5 => ['x2', 'x', 'out'], {'x2*x': 1, '$constant': 5}
    • gate values: {'l': 0, 'r': 0, 'm': -1, 'o': 1, 'c': 5}

Program

Creates a program from the parsed DSL output containing required polynomials used for PLONK proving step.

Converts WireValues to required polynomials in PLONK, i.e.

  • Preprocessed polynomials:
    • selector polynomials:
    • permutation helpers:

To get selector polynomials from constraints, each constraint is parsed into fan-in 2 arithmetic gates as explained above and wire values are assigned to respective wires in lagrange form.

#![allow(unused)]
fn main() {
/// `CommonPreprocessedInput` represents circuit related input which is apriori known to `Prover`
/// and `Verifier` involved in the process.
pub struct CommonPreprocessedInput {
  /// multiplicative group order
  pub group_order: usize,
  /// Q_L(X): left wire selector polynomial
  pub ql:          Poly,
  /// Q_R(X): right wire selector polynomial
  pub qr:          Poly,
  /// Q_M(X): multiplication gate selector polynomial
  pub qm:          Poly,
  /// Q_O(X): output wire selector polynomial
  pub qo:          Poly,
  /// Q_C(X): constant selector polynomial
  pub qc:          Poly,
  /// S_σ1(X): first permutation polynomial
  pub s1:          Poly,
  /// S_σ2(X): second permutation polynomial
  pub s2:          Poly,
  /// S_σ3(X): third permutation polynomial
  pub s3:          Poly,
}
}

Permutation arguments

PLONK handles copy constraint across trace using multiset arguments, also called permutation arguments that essentially proves that set are permutation of each other in the domain, i.e. . For more info on permutation arguments, please check out resources mentioned in references.

permutation helper creates polynomials for .

  • creates a execution trace of n rows for each constraint, and 3 columns representing each wires in a gate: LEFT, RIGHT, OUTPUT
  • parses each constraint and create a map of variable usage across constraints in tuples of rows and columns.
    • In our example: 3 distinct variable exist, then map of variable usage is {'x': [(1, LEFT), (2, LEFT), (2, RIGHT), (3, RIGHT)], 'x2': [(2, OUTPUT), (3, LEFT)], 'out': [(3, OUTPUT)]}
  • to create , and , shifts each variable usage by 1 to right, i.e. variable at .
    • for example: x's usage gets shifted 1 to right, new one becomes: {'x': [(3, RIGHT), (1, LEFT), (2, LEFT), (2, RIGHT)]}.
    • This ensures that variables x is copied from to 
#![allow(unused)]
fn main() {
/// `Program` represents constraints used while defining the arithmetic on the inputs
/// and group order of primitive roots of unity in the field.
#[derive(Debug, PartialEq)]
pub struct Program<'a> {
  /// `constraints` defined during arithmetic evaluation on inputs in the circuit
  constraints: Vec<WireCoeffs<'a>>,
  /// order of multiplicative group formed by primitive roots of unity in the scalar field
  group_order: usize,
}
}

References