fix: underconstrained bug #11174
fix: underconstrained bug #11174
Conversation
This stack of pull requests is managed by Graphite. Learn more about stacking. |
benesjan
force-pushed
the
01-10-refactor_variablemerkletree_readability_improvements
branch
from
4541806 to
6c8ecfd
Compare
benesjan
force-pushed
the
01-10-fix_underconstrained_bug
branch
from
a1eec2b to
2de30bd
Compare
| @@ -50,17 +51,15 @@ fn get_prev_power_2(value: u32) -> u32 { | |||
|
|
|||
| let next_power_2 = 2 << next_power_exponent; | |||
| let prev_power_2 = next_power_2 / 2; | |||
| assert((value == 0) | (value == 1) | (value > prev_power_2)); | |||
| assert(prev_power_2 < value); | |||
There was a problem hiding this comment.
If value equals 0 or 1, the previous power of 2 is completely unconstrained and we could craft a response from get_next_power_exponent such that prev_power_2 is anything in [1, 2, 4, 8, 16, ...].
|
|
||
| // hash base layer | ||
| // If we have no num_non_empty_leaves, we return 0 | ||
| let mut stop = num_non_empty_leaves == 0; |
There was a problem hiding this comment.
Before the code changes we could do the following when hashing base layer.
For num_non_empty_leaves = 0, there is no damage because stop on the line above would be set to true.
For num_non_empty_leaves = 1, this could allow us to hash also the empty leaves getting a different root.
| nodes[i] = accumulate_sha256([leaves[2 * i], leaves[2 * i + 1]]); | ||
| } | ||
| } | ||
|
|
||
| // hash the other layers | ||
| stop = prev_power_2 == 1; |
There was a problem hiding this comment.
Here we can cause damage even for num_non_empty_leaves = 0, because we decide whether to hash just based on prev_power_2.
| let mut next_layer_size = next_layer_end; | ||
| let mut root = nodes[0]; | ||
| for i in 0..(N - 1 - N / 2) { | ||
| if !stop { | ||
| nodes[prev_power_2 + i] = accumulate_sha256([nodes[2 * i], nodes[2 * i + 1]]); |
There was a problem hiding this comment.
For num_non_empty_leaves = 0 and 1 we could cause havoc here as prev_power_2 is directly used in index here and on line 108.
| } else { | ||
| // For more than 1 leaf, we dynamically compute num of nodes in layer 1 by finding the previous power of 2 | ||
| get_prev_power_2(num_non_empty_leaves) | ||
| }; |
There was a problem hiding this comment.
These ^ ifs are the fix --> now we don't enter get_prev_power_2 for num_non_empty_leaves < 2 and instead in those situations we explicitly set the values.
| // If we have no num_non_empty_leaves, we return 0 | ||
| let mut stop = num_non_empty_leaves == 0; | ||
|
|
||
| let num_nodes_layer_1 = if (num_non_empty_leaves == 0) { |
There was a problem hiding this comment.
Renamed prev_power_2 to num_nodes_layer_1 as I found it hard to reason about prev_power_2.
benesjan
force-pushed
the
01-10-refactor_variablemerkletree_readability_improvements
branch
from
6c8ecfd to
3bcccd6
Compare
benesjan
force-pushed
the
01-10-fix_underconstrained_bug
branch
from
2de30bd to
26c5817
Compare
Changes to circuit sizes
🧾 Summary (100% most significant diffs)
Full diff report 👇
|
benesjan
changed the base branch from
01-10-refactor_variablemerkletree_readability_improvements
to
graphite-base/11174
benesjan
force-pushed
the
01-10-fix_underconstrained_bug
branch
from
26c5817 to
52422a8
Compare
* master: (329 commits) fix(avm): mac build (#11195) fix: docs rebuild patterns (#11191) chore: refactor Solidity Transcript and improve error handling in sol_honk flow (#11158) chore: move witness computation into class plus some other cleanup (#11140) fix: get_next_power_exponent off by 1 (#11169) chore(avm): vm2 followup cleanup (#11186) fix: underconstrained bug (#11174) refactor: VariableMerkleTree readability improvements (#11165) chore: removing noir bug workaround (#10535) chore(docs): Remove node pages (#11161) git subrepo push --branch=master noir-projects/aztec-nr git_subrepo.sh: Fix parent in .gitrepo file. [skip ci] chore: replace relative paths to noir-protocol-circuits git subrepo push --branch=master barretenberg feat(avm2): avm redesign init (#10906) feat: Sync from noir (#11138) feat: simulator split (#11144) chore: rpc server cleanup & misc fixes (#11145) git subrepo push --branch=master noir-projects/aztec-nr git_subrepo.sh: Fix parent in .gitrepo file. [skip ci] ...
Fixes underconstrained bug Nico spotted here.
Note on severity
The bug could not be exploited because the
VariableMerkleTreeis only used when computing anout_hashhere andout_hashis checked on L1 against a hash computed on L1. For this reason the severity of the bug is low. But it makes sense to fix because it could become an issue in case the implementation would get used somewhere else later on.The bug is explained in comments.