Question for cryptographers: SNARK friendly signature protocol

zk-s[nt]arks
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.

1 Like