Skip to content
This repository has been archived by the owner on Oct 28, 2024. It is now read-only.

Reduce constraints for jubjub::PointAdder #103

Open
HarryR opened this issue Dec 19, 2018 · 0 comments
Open

Reduce constraints for jubjub::PointAdder #103

HarryR opened this issue Dec 19, 2018 · 0 comments

Comments

@HarryR
Copy link
Owner

HarryR commented Dec 19, 2018

in general, you can shave 1 constraints from the ethsnarks implementation here: https://github.com/HarryR/ethsnarks/blob/master/src/jubjub/adder.cpp
it does:

beta = x1*y2
gamma = y1*x2
delta = y1*y2
epsilon = x1*x2
tau = beta*gamma ( = x1*x2*y1*y2)
x3 * (1+d*tau) == (beta+gamma) ( => x3 = (x1*y2+y1*x2)/(1+d*x1*x2*y1*y2) )
y3 * (1-d*tau) == (delta-a*epsilon) ( => y3 = (y1*y2-a*x1*x2)/(1-d*x1*x2*y1*y2) )

if a = -1, you can do the following optimization:

beta = x1*y2
gamma = y1*x2
delta =  (x1+y1)*(x2+y2) ( = x1*x2+x1*y2+y1*x2+y1*y2)
tau = beta*gamma ( = x1*x2*y1*y2)
x3 * (1+d*tau) == (beta+gamma) ( => x3 = (x1*y2+y1*x2)/(1+d*x1*x2*y1*y2) )
y3 * (1-d*tau) == (delta - beta - gamma) ( => y3 = (y1*y2+x1*x2)/(1-d*x1*x2*y1*y2) )

maybe you can do it anyway, for a != -1?

delta = (-a*x1+y1)*(x2+y2) = -a*x1*x2 - a*x1*y2 + y1*x2 + y1*y2

and then use "delta + a*beta - gamma" in the denominator

https://ibb.co/JBhbfRt

So, it's not worthy to find a curve with a=-1 at least for the number of constraints.

Here is the new circuit:: https://github.com/iden3/circomlib/blob/master/circuits/babyjub.circom#L19

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant