o1-labs
[kimchi] distinguish ZK_ROWS and PERM_FINAL_ACC
We currently use 2 zero-knowledge rows, but specify 3 in the code (under the constant ZK_ROWS). We use this to create enough space for three equations:
- one constraint for the final accumulator value of the permutation. In the original PLONK protocol this constraint does not exist as the constraint on the initial accumulator value takes care of that (because the accumulator wraps around). With our way of doing zero-knowledge we need to add that last constraint in a new row.
- two random values, for the zero-knowledge, as intended
It'd be nice to reflect that in the code.
Also, due to that we currently randomize the last three rows of the witness columns, which is not a big deal as they cannot be used by the circuit, but it would be good to document that :o)
random thought: intuitively, it sounds like we could use unused columns in zero gates (or other gates) to randomize the witnesses and save some rows. It doesn't save us that many rows though (2 is really negligible) and it wouldn't actually save us anything because we still need that space for the permutation. Nevermind.
![github-actions[bot] avatar](https://avatars.githubusercontent.com/in/15368?v=4 "Published by a pub.dev verified publisher"){kind=small}
Adding more color to this issue:
The relevant code is here: https://github.com/o1-labs/proof-systems/blob/master/kimchi/src/prover.rs#L109
//~ 1. Ensure we have room in the witness for the zero-knowledge rows.
//~ We currently expect the witness not to be of the same length as the domain,
//~ but instead be of the length of the (smaller) circuit.
//~ If we cannot add `ZK_ROWS` rows to the columns of the witness before reaching
//~ the size of the domain, abort.
let length_witness = witness[0].len();
let length_padding = d1_size
.checked_sub(length_witness)
.ok_or(ProofError::NoRoomForZkInWitness)?;
if length_padding < ZK_ROWS as usize {
return Err(ProofError::NoRoomForZkInWitness);
}
//~ 2. Pad the witness columns with Zero gates to make them the same length as the domain.
//~ Then, randomize the last `ZK_ROWS` of each columns.
for w in &mut witness {
if w.len() != length_witness {
return Err(ProofError::WitnessCsInconsistent);
}
// padding
w.extend(std::iter::repeat(Fr::<G>::zero()).take(length_padding));
// zk-rows
for row in w.iter_mut().rev().take(ZK_ROWS as usize) {
*row = Fr::<G>::rand(rng);
}
}
The constant ZK_ROWS is currently set to 3, but it should be set to 2 as we only need to randomize 2 rows (since we provide 2 evaluations in the protocol). That being said, we do not need to pad 3 rows here, as the permutation needs 3 clean rows at the end (1 for the final accumulator value, see the blogpost I linked, and 2 for adding zero-knowledge to the permutation argument)
there's also ZK_ROWS in lookup as well. I think it might be good to rename ZK_ROWS to EVALS or some constant that says how many evaluations we have in the protocol. (Or compute ZK_ROWS as EVALS + 1 just to be overly cautious.
@mimoo I would like to take this one! Please check the PR #974, and give me comments.
@jspada @mrmr1993 Can you review this PR? (Looks like @mimoo is busy, and this PR must be simple for you)