search

dalek-cryptography / bulletproofs

A pure-Rust implementation of Bulletproofs using Ristretto.
MIT License
1.05k stars 219 forks source link

Enforce that circuit `n` parameter is zero or a power of two #107

Closed cathieyun closed 6 years ago

cathieyun commented 6 years ago

Currently, the inner product proof only works for vectors with lengths that are powers of two. This was fine for the range proof code, where this was a valid assumption. However, for circuits, the vectors will not always be powers of 2. After some discussion, we decided that the best solution in that case is to pad the circuits such that circuit.n is a power of 2, so that the vectors being input to the IPP are also lengths of powers of 2.

Initial discussion here: https://github.com/dalek-cryptography/bulletproofs/pull/102

TODO: double check that empty IPP outputs are okay

hdevalence commented 6 years ago

Since the IPP uses variable-time operations, padding with zeros shouldn't cost too much (it only affects the first loop iteration anyways). I think it would be good for the IPP code to check that its inputs are powers of two, and have the callees do the padding if necessary.

cathieyun commented 6 years ago

~Work here: https://github.com/dalek-cryptography/bulletproofs/pull/115~ ^ PR closed, because it was deemed not a good approach

cathieyun commented 6 years ago

Updated thoughts: I think that it does not make sense to do the circuit padding within the circuit prover module - it is better for the circuit module to only accept circuits where circuit.n is already a power of two. Then, it is up to whoever is creating a circuit (e.g. by hand, or from r1cs format) to make sure that the circuit's circuit.n is a power of two.

This makes more sense than doing the check and conversion within the circuit module itself, because doing the latter causes a strange mismatch of expectations - circuits can have circuit.n as not a power of two, but the circuit creator still needs to pass in a Generator that has a length that is a power of two. (This is necessary for doing the inner product proof). So, the user of the API still needs to convert some of their inputs (but not all!) to be a power of two. This is confusing - they should either not have to worry about power-of-two properties at all, or have them strictly enforced for all inputs.

Also, the r1cs to bulletproofs converter is already creating the matrices for the circuit, so it is very natural to do the padding during the creation process.

So, the proposed plan is to enforce that any circuits being created in the circuit module have to have circuit.n and Generators.len() be a power of two - all other inputs will be rejected. Then, in the r1cs module, the circuit creator will pad circuits until they are the right size.

hdevalence commented 6 years ago

I think that going forward we're going to want to subsume the circuit module entirely into the r1cs module -- we should pass directly from the R1CS to the proof, without any intermediate matrices, and we should do the padding as necessary just before creating the proof.

Eliminating the circuit code entirely means we don't have to worry about the expectations around it, since we just have to expose the ConstraintSystem and it can synthesize the proof directly.

cathieyun commented 6 years ago

Work:

cathieyun commented 6 years ago

All done!