Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Addition

Adding an array of values and returning the sum is a common operation within circuits.

Adder

template Adder(n) {
  signal input in[n];
  signal output out;

  var lc = 0;
  for (var i = 0; i < n; i++) {
    lc += in[i];
  }
  out <== lc;
}

No matter how large is, a sum operation is just a single linear constraint! Formally, for an array with sum the following is a valid rank-1 constraint:

The variable lc within the code stands for “linear combination” and its just a variable that stores the expression on the right hand-side in equation above:

lc = in[0] + in[1] + ... + in[n-1]

Constraint Count

Adder(n) has 0 non-linear constraints, no matter how large n is. Its only constraint is linear, and linear constraints are free: the compiler simply substitutes out with the sum wherever it is used.