Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Circuit soundness bug: unchecked program counter #94

Closed
Tracked by #90
adr1anh opened this issue Nov 3, 2023 · 1 comment · Fixed by #97
Closed
Tracked by #90

Circuit soundness bug: unchecked program counter #94

adr1anh opened this issue Nov 3, 2023 · 1 comment · Fixed by #97
Assignees
Labels
bug Something isn't working

Comments

@adr1anh
Copy link
Contributor

adr1anh commented Nov 3, 2023

The function get_from_vec_alloc_relaxed_r1cs does not check that program_counter is valid (i.e. in the range { $0,1,\ldots, \ell-1 $}. If program_counter is outside this range, the function returns the first RelaxedR1CSInstance by default.

This can be fixed by enforcing that the sum of all equal_bits (including one for the first instance) is 1. This ensures that exactly one of the equal_bits is set, and therefore program_counter is in the correct range.
Another possibility would be to ensure the returned index is equal to the input target_index.

Since the returned index is the same as the input target_index, it is not necessary for the function to return it. Instead, the function could return a vector of the equal_bits, which are already recomputed during the computation of U_next.

@adr1anh adr1anh added the bug Something isn't working label Nov 3, 2023
@huitseeker huitseeker mentioned this issue Nov 3, 2023
8 tasks
@adr1anh
Copy link
Contributor Author

adr1anh commented Nov 3, 2023

The comment in /src/supernova/circuit.rs#L420-L437 explains that ignoring the range constraint on last_augmented_circuit_index is fine, since this would make the first running instance unsatisfiable with high probability. It is not clear that this always holds for every combination of circuits.

In the fix, this comment should probably be removed.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants