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 constraints for jubjub::PointAdder #103

Open HarryR opened 5 years ago

HarryR commented 5 years ago

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