I used AirAssembly to create a zk-STARK which can be used to prove that verification of a Schnorr signature was executed correctly. Specifically:

Given a message m, a public key P, and a signature (R, s) a prover can generate a proof that s \cdot G = R + hash(P, R, m) \cdot P.

In the current implementation, the verifier needs to know m, P, and R (but not s) to check the proof. It should be possible (with some effort) to update the scheme so that the verifier can verify the proof with only m and hash(P), and I believe this would result in a quantum-resistant signature scheme.

### benchmarks

The STARK can be used to prove verification of one or more signatures. Proof sizes look roughly as follows:

- 1 signature: 110 KB
- 8 signatures: 140 KB
- 64 signatures: 180 KB

Extrapolating this further, it seems like a proof for 10K signatures should be somewhere around 300 KB in size. Moreover, with some optimizations, it may be possible to reduce proof sizes by 10% - 20%.

Proving time is currently rather slow: on my machine, it takes just under 2 seconds to prove a single signature verification, and a bit over 2 mins to prove 64 signature verifications. But, all is not lost:

- The field Iâ€™m using has not been optimized with WebAssembly - so, all math happens in JavaScript which is terribly slow. Moving math operations to WebAssembly should speed things up by a factor of 6x - 8x (and native code would be even faster than that).
- AirAssembly compiler hasnâ€™t been optimized yet - so, the code it outputs is pretty inefficient. Optimizing it could speed things up by a factor of 2x - 3x.
- Iâ€™m running everything in a single thread. With multithreading, things will get significantly faster.

### STARK structure

AirAssembly source code for the STARK is here and the runable example is here. Despite looking intimidating, the structure is rather simple:

- Execution trace has 14 registers:
- The first 7 are used to compute s \cdot G ,
- The other 7 are used to compute R + h \cdot P, where h is an input equal to hash(P, R, m).

- I use a simple double-and-add algorithm for elliptic curve multiplication:
- At each step the base point is doubled, and when needed, added to the accumulated result (x, y coordinates for base points and accumulated results account for 4 out of 7 registers used in each multiplication).
- I also pre-compute slopes for addition/doubling one step before the actual addition/doubling to keep constraint degree low.

- The total number of transition constraints is 18, and the highest constraint degree is 6.

The elliptic curve Iâ€™m currently using is P-224 because it is one of the standard curves defined over a â€śSTARK-friendlyâ€ť field. But swapping it out for some other curve is trivial.

If anyone sees any issues, or has any feedback - let me know!