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

feat: add automatic non-native witness element limb constraining #446

Merged
merged 8 commits into from
Jan 24, 2023

Conversation

ivokub
Copy link
Collaborator

@ivokub ivokub commented Jan 24, 2023

Resolves #348.

High-level idea for automatic constraining of the elements. We add a flag internal for the Element type where internal=true indicates that this Element came as an output of Field methods (which we set in the methods). We ensure in the methods that we always set the flag.
If the Element comes from elsewhere (usually using NewElement), then potentially the limbs of that value are not constrained to be nbBits bits wide. However, the value may already be constrained elsewhere (but we do not want to keep the state in Element itself, as it could be modifying the witness).

We add a table of constrained limbs in Field type, indexed by limb variables (using HashCode on LinearExpression/Term). If we constrain an element, then for every limb we store its key in the map to prevent constraining the Element constraining the limb later again.
We also add a pre-condition to every Field method which performs this conditional bit-width enforcing.

Seems to be working with minimal overhead as we ever store only witness element hashes in the table and there are usually only a small number. Will have to check if makes sense to add some probabilistic filter in front of the map, but subjectively there wasn't a noticeable performance diff for large circuits (nonnative ECDSA).

Still WIP:

  • there is mess of different possible ways of instantiating Element. Have to unify and give more descriptive names. For example, want to leave NewElement only for witness creation (with input types which make sense i.e. integer-like) and for everywhere else want to have private methods (to prevent users accidentally creating internal elements).
  • now some methods become redundant (e.g. public EnforceWidth is not necessary anymore because is done automatically)
  • need to consider different paths where Elements are created so that internal flag is consistent.
  • need to consider which methods should have the pre-condition for conditionally checking width enforcement. It seems that almost all methods reduce to add/mul/sub so may be sufficient. But calling several times is no-op, so better be safe.
  • update documentation and remove unnecessary checks in tests and depending gadgets.

@ivokub ivokub added this to the v0.8.0 milestone Jan 24, 2023
@ivokub ivokub self-assigned this Jan 24, 2023
@ivokub ivokub force-pushed the feat/nonnative-enforcewidth branch from de2b65e to 216ff67 Compare January 24, 2023 15:16
@ivokub
Copy link
Collaborator Author

ivokub commented Jan 24, 2023

I checked between this branch and develop. There is no performance difference and neglibible memory diff (3MB)

@ivokub ivokub requested a review from gbotrel January 24, 2023 15:18
Copy link
Collaborator

@gbotrel gbotrel left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

seems a bit hacky but will do for now :)

@gbotrel gbotrel merged commit 8a39609 into develop Jan 24, 2023
@ivokub ivokub deleted the feat/nonnative-enforcewidth branch March 3, 2023 23:33
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants