Soundness bug in Bytecode circuit 1 (missing state transition constraint) #1332
Comments
|
Would like to give this a try! Btw, there is a typo in Bug 2. I think you meant to say q_enable=0 on the last row. Will first change the specs! By "last row" do you mean the last row of a bytecode (header,byte,byte....,) or do you mean the last row of the whole bytecode circuit (q_last)? |
Thanks for catching the typo! I updated the first message :)
For "last row" I mean the last row of the whole bytecode circuit (where q_last = 1) |
### Description Fixes bug soundness in bytecode circuit, where an attacker can insert as many bytes after the last byte (row where `q_last`=1). ### Issue Link #1332 ### Type of change - [x] Bug fix (non-breaking change which fixes an issue) - [ ] New feature (non-breaking change which adds functionality) - [ ] Breaking change (fix or feature that would cause existing functionality to not work as expected) - [ ] This change requires a documentation update ### Contents - Bug fix 1: Add a constraint that forces the next state to be "Header" when the current state is "Byte" and `index == length - 1` - Bug fix 2: set `q_enable=1` for the row where `q_last=1` ### Rationale This would patch the possibility of an attacker inserting false bytes that extend beyond the correct bytecode. ### How Has This Been Tested? Created a test called `bytecode_soundness_bug_1` that overwrites the last rows with`tag=Byte`. `cargo test --features test --package zkevm-circuits --lib -- bytecode_circuit::circuit::tests::bytecode_soundness_bug_1 --exact --nocapture` Also ran other unit tests to check correctness was maintained. --------- Co-authored-by: Eduard S <eduardsanou@posteo.net>
|
Resolved via #1333 |
Signed-off-by: noelwei <fan@scroll.io>
The Bytecode circuit is missing the constraint that forces the a "header" state after the last "byte" state in a bytecode. This allows an attacker to insert bytes after the last real byte. If we insert a "byte" state after the last bytecode "byte", we reach a situation in which we can only have "byte" states until the end of the circuit. In theory this should not be possible because we are constraining the last state to be "header", but there's another bug here!
q_enableis used in the constraint to force the last row to be "header", andq_enable = 0in the last row.Here's an example of the attack:
For a bytecode circuit of size 6 which contains 1 bytecode of length 3 it looks like this:
But we can do this assignment and the constraints will work
We're introducing bytes 3 and 4 and we can use any value for those.
Summary
Bug 1
The transition Byte -> Header is not constrained to be true when the appropriate condition appears
Bug 2
The last row has
q_enable=0, which effectively disables all polynomial constraints applied in that row (including the one that forces the row to be a "Header" state).q_enable=1to all rows of the circuit, including the last oneDemo
This commit main...bug/bytecode_soundness1 includes a test and some helper code that overwrites the assignment to show how bytes can be added after the "real" bytecode, and all the constraints still pass.
The text was updated successfully, but these errors were encountered: