Proof of knowledge of ECDSA signature

[srinathsetty]

Background on SNARKs and Spartan

Spartan is a zkSNARK, so it consists of three algorithms:

• Setup() --> pp
• Prove(pp, ckt, witness, io) --> \pi
• Verify(pp, ckt, io) --> {0, 1}

Here, pp refers to some public parameters, ckt is the description of a circuit whose satisfiability is being proved, witness is a vector of secret inputs to the circuit, and io is a vector of public inputs to the circuit. In Spartan, the circuit is specified with R1CS.

In general, the circuit (or R1CS) is defined over a prime field with a certain modulus p (i.e., the set of numbers {0, 1, ..., p-1}). Spartan can work over a "sufficiently large" prime modulus. The Spartan implementation currently uses a particular p, which is the scalar field of curve25519.

Proving the knowledge of an ECDSA signature

To prove the knowledge of an ECDSA signature, we must write a circuit with the following characteristics:

Secret inputs:

• Message M
• Signature S

Public inputs:

• The public key of the signer PK

The circuit itself must implement ECDSA's verify method to check if S is a valid signature on M using PK.

There are three options to build the circuit:

1. ECDSA signatures are defined over P-256 curve and Spartan uses curve25519. In this case, the circuit will non-natively emulate arithmetic needed to verify P-256 signatures in the scalar field of curve25519.

2. ECDSA signatures are defined over secp256k1 curve and Spartan uses secq256k1. In this case, the circuit will natively execute the necessary arithmetic over secp256k1 since the base field of secp256k1 equals the scalar field of secq256k1

3. ECDSA signatures are defined over P-256 curve and Spartan uses curve (call it Q-256). Like in case (2), the circuit will natively execute the necessary arithmetic.

The primary advantage of (2) and (3) is the size of an ECDSA signature verify circuit will be ~10K gates (an order of magnitude or more smaller than with case (1)). The downside is that Spartan implementation must be updated to support these additional curves.

[quartzjer]

For (1.) using non-native arithmetic that you believe will be over 100K gates, would you have a rough guess of the performance on a modern CPU? 10s of seconds? Similar for both the Prove and Verify?

The downside is that Spartan implementation must be updated to support these additional curves.

How much is involved in such an addition? Could you point to the relevant place(s) in the current codebase?

[csuwildcat]

I'd prefer option 2

[dwaite]

I've heard the goal stated by some that the idea of using this gadget would be for privacy while using NIST-approved curves. secp256k1 and ed25519 are not (yet) NIST approved curves. So I'd be for option 3, or option 1 if it met some ambiguous performance requirements.

The latest drafts of SP 800-186 and FIPS 186-5 add edwards25519, edwards448, and EdDSA - while not adding secp256k1. For that reason I'd prioritize a proof of knowledge of EdDSA signature (e.g 25519 curve on 25519-based spartan) over option 2.

I know that DIF already filed comments asking for the inclusion of secp256k1 in SP 800-186/FIPS 186-5, but do not know if there has been any dialogue there.

Also, is Q-256 an existing thing? It made me think of the ZKAttest work and their Tom curves.

[christianpaquin]

I'm not familiar with the Spartan Q-256 curve, but is there any reason why you couldn't instantiate the scheme with the NIST P-256 (secp256r1) curve instead? That would offer a very interesting parameters set for deployers operating in NIST land.

[srinathsetty]

For (1.) using non-native arithmetic that you believe will be over 100K gates, would you have a rough guess of the performance on a modern CPU? 10s of seconds? Similar for both the Prove and Verify?

Yes, the prover performance could be ~10 seconds (one CPU core). Verify should be less expensive (~100ms)

The downside is that Spartan implementation must be updated to support these additional curves.

How much is involved in such an addition? Could you point to the relevant place(s) in the current codebase?

For supporting other curves, we essentially would need to replace the underlying library that implements curve arithmetic (Spartan currently uses curve25519-dalek).

[srinathsetty]

I've heard the goal stated by some that the idea of using this gadget would be for privacy while using NIST-approved curves. secp256k1 and ed25519 are not (yet) NIST approved curves. So I'd be for option 3, or option 1 if it met some ambiguous performance requirements.

The latest drafts of SP 800-186 and FIPS 186-5 add edwards25519, edwards448, and EdDSA - while not adding secp256k1. For that reason I'd prioritize a proof of knowledge of EdDSA signature (e.g 25519 curve on 25519-based spartan) over option 2.

I know that DIF already filed comments asking for the inclusion of secp256k1 in SP 800-186/FIPS 186-5, but do not know if there has been any dialogue there.

Also, is Q-256 an existing thing? It made me think of the ZKAttest work and their Tom curves.

Yes, Q-256 can essentially be the same curve used in zkAttest.

[quartzjer]

For that reason I'd prioritize a proof of knowledge of EdDSA signature (e.g 25519 curve on 25519-based spartan)

I agree, let's discuss today and set the first milestone being constructing a PoK of an EdDSA signature.