search

privacy-scaling-explorations / halo2

https://privacy-scaling-explorations.github.io/halo2/
Other
201 stars 121 forks source link

soundness bug: enabled selector returns a zero Expression #325

Closed themighty1 closed 4 months ago

themighty1 commented 4 months ago

Update: confirming that this was fixed in main by 54a8fd8becc9096c7f13b28722b6730ef6354d37

I have a fixed lookup table with 4 items [0,1,2,3]. I'm trying to lookup the value 123, expecting the lookup to fail. However, the lookup succeeds.

Apparently the lookup selector even though it is .enable()d, returns a zero Expression. Since my lookup table has a 0, this causes the lookup to always succeed.

Here is a link to a minimal repro: https://github.com/themighty1/authdecode_lookup/tree/bug_repro You can reproduce by running:

git clone https://github.com/themighty1/authdecode_lookup -b bug_repro
cd authdecode_lookup/
cargo build --release
./target/release/authdecode_lookup

You will see "Proof verifier" when in fact it should fail.

themighty1 commented 4 months ago

Feel free to close this since it has been fixed. Maybe if you had a test which asserts that the wrong item is not present in the lookup table, you could have caught the bug earlier?

ed255 commented 4 months ago

I'm sorry you encountered this bug! As you have already seen, it was fixed via https://github.com/privacy-scaling-explorations/halo2/pull/322

Maybe if you had a test which asserts that the wrong item is not present in the lookup table, you could have caught the bug earlier?

In the PR where we fixed the bug we also added a test that checks the behavior of compression of selectors as enabled/disabled and also adds some tests that should fail. But you're right that we need to improve our unit tests to avoid facing issues like this in the future.

I'll close this issue and create a new one to improve unit testing, mentioning your suggestion of the lookup table test.