zkevm-circuits icon indicating copy to clipboard operation
zkevm-circuits copied to clipboard

LtChip is missing byte range checks

Open ed255 opened this issue 2 years ago • 0 comments

The LtChip defined in gadgets/src/less_than.rs uses this constrain: lhs - rhs = diff - lt * 2.pow(8*N) where diff = from_bytes(diff_bytes) and diff_bytes: [Column<Advice>; N],

This constrain is only useful if diff is constrained to be between 0 and 2^{8*N}. This can be achieved by constraining each element in diff_bytes to be between 0 and 2^8. Nevertheless this is not constrained. There's a note in the struct field documentation saying this: https://github.com/privacy-scaling-explorations/zkevm-circuits/blob/4cfccfa6c3b251284ff61eeb907d548d59206753/gadgets/src/less_than.rs#L33-L35 But I believe this is quite dangerous, because it's very easy to forget!

I've searched for usages of LtChip and I found it's used only in the CopyCircuit: https://github.com/privacy-scaling-explorations/zkevm-circuits/blob/4cfccfa6c3b251284ff61eeb907d548d59206753/zkevm-circuits/src/copy_circuit.rs#L69 And I didn't see any byte range constraint on the elements in addr_lt_addr_end.diff, which is a bug.

I think we must avoid leaving gadgets with missing constraints and expecting the chip that uses the gadgets to add them (unless we had a way to automatically check that we didn't miss these constraints)

ed255 avatar Nov 18 '22 15:11 ed255