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

Fix/reduce constraints eddsa #129

Merged
merged 5 commits into from Aug 30, 2021
Merged

Fix/reduce constraints eddsa #129

merged 5 commits into from Aug 30, 2021

Conversation

ThomasPiellard
Copy link
Collaborator

@ThomasPiellard ThomasPiellard commented Aug 27, 2021

This PR removes the splitting of S in S1+2^bS2 in the EDDSA snark circuit.

  • Breaking changes:
type Signature struct {
	R twistededwards.Point
	S1, S2 frontend.Variable // S1+2^b S2 = S
}

-->

type Signature struct {
	R twistededwards.Point
	S frontend.Variable
}

The splitting was due to an earlier version of gnark-crypto where S was reduced modulo the number of points of the twisted Edwards instead of the group order of the base point.

A twisted Edwards on Z/rZ has at most N=r+2*sqrt(r)+3 points because there are 2 points of multiplicity 2. The group that is used for eddsa contains at most N/2 points because there is a point of order 2 on the twisted Edwards. Therefore l<r.

@gbotrel gbotrel merged commit 1875817 into develop Aug 30, 2021
@gbotrel gbotrel deleted the fix/reduce_constraints_eddsa branch August 30, 2021 13:08
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

2 participants