search

HarryR / ethsnarks

A toolkit for viable zk-SNARKS on Ethereum, Web, Mobile and Desktop
GNU Lesser General Public License v3.0
240 stars 57 forks source link

Reduce number of constraints for JubJub IsOnCurve test #71

Closed HarryR closed 5 years ago

HarryR commented 5 years ago

As per @swasilyev insight on https://github.com/HarryR/ethsnarks/pull/70#issuecomment-436347492

a*x*x + y*y = 1 + d*x*x*y*y

This can be simplified to:

// axx + yy = 1 + dxxy*y
(x, x, xx)
(y, y, yy)
(d * xx, yy, a * xx + yy - 1)
swasilyev commented 5 years ago

It's not my insight. Section A.3.3 of Zcash Protocol Specification describes circuits for original (Zcash) jubjub arithmetic. Their design is highly optimized and, what can be more important, reviewed.

HarryR commented 5 years ago

Non-normative note: The last two constraints can be combined into d*uu*vv = a*uu + vv − 1. The Sapling circuit does not use this.

However, there is lots that I can implement from the Zcash specification.

I feel that this project is lacking documentation, and has lots to be desired in comparison to the Zcash specification.

HarryR commented 5 years ago

This has been implemented in #74

I am reviewing the Zcash Sapling specification for further improvements. I think some of the improvements can't be used because of the parameters of the Baby JubJub curve (e.g. the optimisation where a=-1)