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

Field.toBits() and fromBits() are unsound #1023

Closed
mitschabaude opened this issue Jul 10, 2023 · 0 comments · Fixed by #1461
Closed

Field.toBits() and fromBits() are unsound #1023

mitschabaude opened this issue Jul 10, 2023 · 0 comments · Fixed by #1461
Assignees
Labels
breaking Issues that will lead to breaking changes v1 Prerequisite for o1js v1.0 zkDSL Issues to improve the core experience of writing circuits

Comments

@mitschabaude
Copy link
Member

mitschabaude commented Jul 10, 2023

Field.toBits() without the optional length parameter returns 255 Bools to represent a field element. However, the representation of a field element as 255 bits is not necessarily unique!

Namely, for most Pasta field elements $x$, both $x$ and $x + p$ fit within 255 bits. If the decomposition of $x$ into bits is checked like I think it is -- as $x = x_0 + 2 x_1 + ... + 2^{254} x_{254} \bmod{p}$ --, then the prover can choose between two decompositions: that of $x$ and that of $x + p$.

The same vulnerability applies to fromBits() which likely uses the same constraints

Possible fix: Make 254 the default bit length parameter and don't allow 255.

@mitschabaude mitschabaude changed the title Is Field.toBits() unsound? Are Field.toBits() and fromBits() unsound? Jul 10, 2023
@mitschabaude mitschabaude added the zkDSL Issues to improve the core experience of writing circuits label Dec 13, 2023
@mitschabaude mitschabaude added the breaking Issues that will lead to breaking changes label Jan 30, 2024
@mitschabaude mitschabaude changed the title Are Field.toBits() and fromBits() unsound? Field.toBits() and fromBits() are unsound Jan 30, 2024
@garwalsh garwalsh added the v1 Prerequisite for o1js v1.0 label Jan 30, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
breaking Issues that will lead to breaking changes v1 Prerequisite for o1js v1.0 zkDSL Issues to improve the core experience of writing circuits
Projects
None yet
Development

Successfully merging a pull request may close this issue.

4 participants