Instances
Instance, public input, statement, whatever.
So far, every circuit we have defined has been specific to a statement we wanted the prover to satisfy. This would be of no use for, e.g. a zk-rollup / validium. We would need a separate circuit for every state transition: in a zk-rollup the circuit shows that a transition between commitments to two adjacent states is valid, without public inputs we would need a separate circuit for every such pair of commitments. Ouch. This in turn would require the verifier to regenerate the verification key for every such new circuit, a very expensive operation, which would defeat the purpose of zk-rollups / validiums: that verification is faster than execution.
The solution is Instance columns.
You can think of instances/public inputs as parameterizing the circuit:
for every assignment (known to the verifier) the prover can be asked to provide a witness.
In other, computer science, words:
the SNARK proves satisfiability of some NP relation \( \mathcal{R} \):
\[
\mathcal{R}(\mathsf{x}, \mathsf{w}) = 1
\]
Where \( \mathsf{x} \), the statement, is known to both parties and \( \mathsf{w} \), the witness (advice column assignments), is known only to the prover.
So far we have always had \( \mathsf{x} \) be the empty string.
Instances
An Instance column is just a regular column, like an advice column,
but the values in the instance column are provided/known to the verifier;
as opposed to the Advice column, which are only known to the prover.
Because Instance columns themselves are pretty simple,
we are going to visit some additional techniques in the examples below:
as a bit of a throwback to the very first circuit we defined,
we will define a circuit that takes an index and returns the fibonacci number at that index.
This means that the circuit must be able to accommodate a variable number of "steps" in the fibonacci sequence.
Our circuit will have 5 columns:
-
fib: anAdvicecolumn which will contain the fibonacci sequence. -
flag: anAdvicecolumn which will contain a "flag" for the gate.
More details on this later. -
index: anAdvicecolumn which will contain the index of the fibonacci number. -
q_step: this is theSelectorcolumn which turns on the sole gate: the "fibonacci" gate. -
instance:Instancecolumn which will contain the index of the fibonacci number we want.
Looks like this:
fn configure(meta: &mut ConstraintSystem<F>) -> Self::Config {
let fib = meta.advice_column();
let flag = meta.advice_column();
let index = meta.advice_column();
let q_fib = meta.complex_selector();
let instance = meta.instance_column();
meta.enable_equality(fib);
meta.enable_equality(instance);
meta.enable_equality(index);The Fibonacci Gate
There is a single gate in this circuit, the "fibonacci" gate. This gate is by far the most complex gate we have defined so far, so hold on to your hats:
meta.create_gate("fibonacci", |meta| {
// selector
let enable = meta.query_selector(q_fib);
// index in the Fibonacci sequence
let idx0 = meta.query_advice(index, Rotation(0));
let idx1 = meta.query_advice(index, Rotation(1));
// fibonacci sequence
let w0 = meta.query_advice(fib, Rotation(0));
let w1 = meta.query_advice(fib, Rotation(1));
let w2 = meta.query_advice(fib, Rotation(2));
// indicator
let bit = meta.query_advice(flag, Rotation(0));
let not_bit = Expression::Constant(F::ONE) - bit.clone();
vec![
// it's a bit (strictly speaking, this is redundant)
enable.clone() * bit.clone() * not_bit.clone(),
// apply the Fibonacci rule
enable.clone() * bit.clone() * (w0.clone() + w1.clone() - w2.clone()),
enable.clone()
* bit.clone()
* (idx1.clone() - idx0.clone() - Expression::Constant(F::ONE)),
// OR, maintain the value / index
enable.clone() * not_bit.clone() * (w1.clone() - w2.clone()),
enable.clone() * not_bit.clone() * (idx1.clone() - idx0.clone()),
]
});The layout of the gate is as follows:
This is a gate that essentially allows the prover to choose between two smaller gates:
- Force
bitto be either 0 or 1. - If
bit = 1: calculate the next fibonacci number.w2 = w0 + w1idx1 = idx0 + 1
- If
bit = 0: do nothing.w2 = w0idx1 = idx0
The motivation for this gate is that we want to be able to calculate the fibonacci number at any index:
by setting the bit to 0, the prover can choose to stop progressing the fibonacci sequence once it reaches the desired index.
An alternative way to implement this gate would be to use a dynamic lookup, but we have not covered these yet, stay tuned.
Observe that the gate has a comment about the first constraint being redundant. Why is this?
The Fibonacci Circuit
The circuit is simply turning on the "fibonacci" gate for some number of rows. We save the cells from all these assignments, finally we export the initial state and the final state as instances.
We will break it down in the next section, but here it is in all its glory:
fn synthesize(
&self,
config: Self::Config, //
mut layouter: impl Layouter<F>,
) -> Result<(), Error> {
let instances = layouter.assign_region(
|| "fibonacci-steps",
|mut region| {
// apply the "step" gate STEPS = 5 times
let mut fib_cells = Vec::new();
let mut flg_cells = Vec::new();
let mut idx_cells = Vec::new();
for i in 0..STEPS {
// turn on the gate
config.q_fib.enable(&mut region, i)?;
// assign the fibonacci value
fib_cells.push(region.assign_advice(
|| "assign-fib",
config.fib,
i,
|| self.fib_seq.as_ref().map(|v| v[i]),
)?);
// assign the flag
flg_cells.push(region.assign_advice(
|| "assign-bit",
config.flag,
i,
|| {
self.flg_seq
.as_ref()
.map(|v| if v[i] { F::ONE } else { F::ZERO })
},
)?);
// assign the index
idx_cells.push(region.assign_advice(
|| "assign-idx",
config.index,
i,
|| self.idx_seq.as_ref().map(|v| F::from_u128(v[i] as u128)),
)?);
}
// assign the last index
idx_cells.push(region.assign_advice(
|| "assign-fib",
config.index,
STEPS,
|| {
self.idx_seq
.as_ref()
.map(|v| F::from_u128(v[STEPS] as u128))
},
)?);
// assign the last two fibonacci values
fib_cells.push(region.assign_advice(
|| "assign-fib",
config.fib,
STEPS,
|| self.fib_seq.as_ref().map(|v| v[STEPS]),
)?);
fib_cells.push(region.assign_advice(
|| "assign-fib",
config.fib,
STEPS + 1,
|| self.fib_seq.as_ref().map(|v| v[STEPS + 1]),
)?);
// sanity check
assert_eq!(flg_cells.len(), STEPS);
assert_eq!(idx_cells.len(), STEPS + 1);
assert_eq!(fib_cells.len(), STEPS + 2);
// enforce instances
Ok([
fib_cells[0].cell(), // start fib0
fib_cells[1].cell(), // start fib1
idx_cells[0].cell(), // start idx0
fib_cells.last().unwrap().cell(), // end fib
idx_cells.last().unwrap().cell(), // end idx
])
},
)?;
for (i, cell) in instances.into_iter().enumerate() {
layouter.constrain_instance(cell, config.instance, i)?;
}
Ok(())
}Most of the code is very reminiscent of the circuit we explored in the "Endless Spreadsheets" section very early on.
One small difference is that we save the assigned cells,
e.g. saving the assigned cells of the fib column in the fib_cells vector:
fib_cells.push(region.assign_advice(
|| "assign-fib",
config.fib,
i,
|| self.fib_seq.as_ref().map(|v| v[i]),
)?);Then at the end return some cells from the region:
Ok([
fib_cells[0].cell(), // start fib0
fib_cells[1].cell(), // start fib1
idx_cells[0].cell(), // start idx0
fib_cells.last().unwrap().cell(), // end fib
idx_cells.last().unwrap().cell(), // end idx
])Namely:
- The first two cells of the
fibcolumn (first two fibonacci numbers). - The initial index of the first fibonacci number, i.e. 0.
- The final cell of the
fibcolumn. - The final index of the last fibonacci number.
We then enforce that the instance column is equal to these cells:
for (i, cell) in instances.into_iter().enumerate() {
layouter.constrain_instance(cell, config.instance, i)?;
}This, in a nutshell, is how we use instances.
The Witness Generation
Let's briefly look at how the prover generates the witness for this circuit:
let fib_steps = 20; // the number of Fibonacci steps we want to prove
let fib_start0 = Fr::from(1u64); // first Fibonacci number
let fib_start1 = Fr::from(1u64); // second Fibonacci number
// generate a witness
let mut flg_seq = vec![];
let mut idx_seq = vec![0];
let mut fib_seq = vec![fib_start0, fib_start1];
for idx in 1..=STEPS {
if idx <= fib_steps {
// generate the Fibonacci sequence
let f0 = fib_seq[fib_seq.len() - 2];
let f1 = fib_seq[fib_seq.len() - 1];
flg_seq.push(true);
fib_seq.push(f0 + f1);
idx_seq.push(idx);
} else {
// pad the sequences
flg_seq.push(false);
fib_seq.push(*fib_seq.last().unwrap());
idx_seq.push(*idx_seq.last().unwrap());
}
}
// create the circuit
let circuit = TestCircuit::<Fr> {
_ph: PhantomData,
fib_seq: Value::known(fib_seq.clone()),
flg_seq: Value::known(flg_seq.clone()),
idx_seq: Value::known(idx_seq.clone()),
};In other words, the prover progresses the fibonacci sequence until
idx > fib_steps at which point the prover sets the flag bit to 0
and adds padding until the end of the region.
The Verifier
The only change to the MockProver is that we need to provide the instances:
// run the MockProver
let fib_result = fib_seq.last().unwrap().clone();
let prover = MockProver::run(
10,
&circuit,
vec![vec![
fib_start0, // first Fibonacci number
fib_start1, // second Fibonacci number
Fr::from_u128(0 as u128), // start index
fib_result, // claimed result
Fr::from_u128(fib_steps as u128), // after this number of steps
]],
)
.unwrap();
prover.verify().unwrap();