Question for cryptographers: SNARK friendly signature protocol


#1

Now we are building plasma with SNARKs friendly state and I think that proving also the signatures inside the SNARK may be a good idea because in future it provides us transaction history compression.

Is it safe to build ECDSA on jubjub and Pedersen hash? The circuit for ECDSA is using about 10000 constraints, but I have not seen the usage of this approach anywhere.

Most of the projects are using much heavier sha256 and EdDSA.


#2

It should be safe to build ECDSA inside a snark. I think ECDSA requires a greater than check which is quire expensive in the snark. But still totally possible.

Eddsa does not require this so thats why it was a natural option. Schnorr could work quite well inside a snark.

The circuit for ECDSA is using about 10000 constraints, but I have not seen the usage of this approach anywhere.

Can you share this implmentation?

Most of the projects are using much heavier sha256 and EdDSA.

We are seeing if pedersen commitments are safe inside a signature scheme and potentially moving to use that.


#3

We have not implemented it in Bellman yet. But I can share here current draft pseudocode.

I will use notation from wiki. We get signature (r, s), public key Q_A and group element G with order n, message hash z. All integers inside the SNARK are elements of Z_p.

To verify the signature we need to check following equations::

0 < r < n \\ 0 < s < n \\ Q_A \neq O \\ Q_A \in Curve \\ n Q_A = O \\ z (s^{-1} G) + r (s^{-1} Q) = (x_1, y_1) \neq O \\ x_1 = r \mod n

For circuit simplification we can transform (r, s) signature into (r_1, s_1) signature, where r_1 = r s^{-1} \mod n, s_1 = s^{-1} \mod n.

Arbitrary conditional point addition gets 8 constraints, point addition gets 6 constraints, point doubling gets 5 constraints, so we get 13 constraints per bit arbitrary point multiplication.

Constant point multiplication is described here: 4.2 constraints per bit.

We can exclude checks for Q inside the circuit. Then the circuit will not reject wrong public keys, but plasma users are conserned to use valid public keys and consider inclusion of wrong keys as defect in plasma. So we get following system of equations:

0 < r_1 < n \\ 0 < s_1 < n \\ z (s_1 G) + r_1 Q = (x_1, y_1) \neq O \\ x_1 s_1 = r_1 \mod n

We consider r_1, s_1 as elements of Z_n and transform equation system into

z (s_1 G) + r_1 Q = (x_1, y_1) \\ x_1 (s_1 G) = (r_1 G) \neq O

We can do it, because O=(0,1) for jubjub, so, x_1,\ s_1,\ r_1 \neq 0 \mod n and (x_1, y_1) \neq O here.

Here is the SNARK in pseudocode:

def ecdsa_check(z, r_1, s_1, Q):
    split_to_bits(z) # 252 constraints
    split_to_bits(r_1) # 252 constraints
    split_to_bits(s_1) # 252 constraints
    C0 := ec_mulc(s_1, G) # 4.2 * 252 = 1058 constraints
    C1 := ec_mul(z, C0) # 13 * 252 = 3276 constraints
    C2 := ec_mul(r_1, Q) # 13 * 252 = 3276 constraints
    x1 := X(C1+C2) # 6 constraints
    split_to_bits(x1) # 254 constraints
    C3 := ec_mulc(r_1, G) # 4.2 * 252 = 1058 constraints
    C4 := ec_mul(x, C0) # 8 * 254 = 2032 constraints, using precomputed doublings of C0
    C3 == C4 # 2 constraints
    X(C3)^2+(Y(C3)-1)^2 != 0 # 255 constraints 

About 12000 constraints total.


#4

Nice. We can do eddsa for 7000 https://github.com/HarryR/ethsnarks/blob/093b660eb22b5132c2936286a1f1c940365b5561/src/jubjub/eddsa.cpp There is eddsa in belman somewhere https://github.com/matterinc/plasma_winter hope that helps you with the implmentaiton.


#5

Jubjub is a pairing-freindly curve (Edwards birationally equivalent to BLS12-381). So what about using a BLS short signature?


#6

how expensive would paring operation be to compute inside a snark?


#7

Pairing operations are implemented for Weierstrass curves in libsnark: https://github.com/scipr-lab/libsnark/tree/master/libsnark/gadgetlib1/gadgets/pairing although I’m unsure of how many constraints it requires.

However, to implement it for the BabyJubJub curve you would need to implement similar algorithms as above, described in:

Alternatively we could find new Weierstrass curve parameters as an alternative to the ones supported by the existing libsnark gadgets. The SCIPR lab already has code for this: https://github.com/scipr-lab/ecfactory - but I’m unsure about what would be necessary to tune them to find a candidate suitable for the alt-bn scalar field - doing so would be really cool as it opens opportunities for recursive SNARKs on EVM now.