Back in August, 2023, zkSecurity announced that it was partnering with ZPrize to organize their third prize 🏆, which was to produce the fastest proofs of valid ECDSA signatures. The results surprised us all, and we ended up choosing not one, but two winners with two very different approaches! We just announced the results last week 📣, so keep reading to learn more about who won, how they won, and how we split the $500,000 prize!
If you didn't know, ZPrize is a now-2-year-old initiative, which was started to incentivize developers to produce useful AND open-source libraries for the ZK ecosystem. The incentive is to reward the winners with cash! Every year, teams assemble to compete in coming up with the fastest implementations for different algorithms.
For prize 3 of the latest ZPrize edition, all teams started 7 months ago with the same starting point/benchmark code, and end goal: implement ZK circuits to prove 50 ECDSA signatures of different lengths on top of the Varuna proof system. We picked the same ECDSA configuration as Ethereum (keccak256 hash and secp256k1 curve) because of the kind of usecases it could unlock right out of the box.
I said that signing is often enough, and ZKPs are overkill in a number of scenarios, but verifying signatures in a ZKP is something that actually leads to interesting and useful applications. Both Coda protocol and Plumo did exactly this (verifying consensus and transaction signatures for nodes/light clients). More recently, Sui came out with zkLogin which allows you to prove that a platform (e.g. Google) signed over your username/mail without leaking that information, and Aayush and Sampriti came up with zkEmail which allows you to verify that your email provider signed on the fact that you received some email without leaking the content or your email. (cryptologie.net)
This is the first ZPrize category, ever, that focuses on an end-to-end application. Other categories from this ZPrize, as well as the previous and first one, usually focused on lower-level primitives like implementations of MSM and FFT (which are often found as building blocks of proof systems).
OK so who won and where's the code? Turns out that we had a hard time figuring out who really deserved to win. We received a number of excellent submissions, and tried to rank them according to pure speed (given the benchmarks we had released), quality of the code, quality of the write up, auditability, etc. Two solutions came up ahead in most metrics, but with very different solutions. So much so that we decided to pick two winners to share the prize evenly: Zproof and Mengling.
Both solutions took around 10 minutes on a consumer device (Macbook pro with 32GB of memory) to prove the target of 50 signatures over 100B messages. Note that the solutions had to include the circuitry to hash the messages as well! Both solutions ended up using an SRS of size $2^{22}$, taking advantage of advanced features like table lookups. The benchmarks for messages of 1kB took around the same time to prove.
What can we make out of that? We now have a new baseline to bench against: 10min for 50 ECDSA proofs of 100B to 1kB messages on a consumer device. While this might not seem like a realistic time for client-side proving, it still showcases that with tomorrow's improvements and with better hardware, this kind of applications will become much more realistic. Besides, 10 minutes is not a crazy time to wait for someone who might really care about a specific privacy usecase.
The Mengling solution took a classical and expected route: they implemented all the constraints necessary to verify 1 proof in a single Varuna circuit. They took advantage of advanced features like table lookups and proof batching, as well as clever constraint optimizations, to ship a clean solution. Varuna's batch proving also helped reduce the cost of proving multiple such proofs.
On the other hand, the Zproof team bet on a different proof system (or shall I say proof systems!) by using the starky+plonky2 combo and verifying these proofs recursively within a Varuna proof. As such, their stack was much more complex and involved many more tools (and programming languages). The different circuits addressing the different message sizes always boiled down to a single verifier circuit for plonky2 (implemented in Varuna using table lookups as well) which forced their solution to have a circuit size lower bound across all benchmarks.
While this added quite the complexity for usecases with smaller message lengths and lower number of signatures, this approach paid off on much larger messages. Benchmarks using 50kB messages took less than 1,000 seconds on a c6a.8xlarge AWS instance (32 vCPU, 64GB of memory).
While we'll have to wait a bit to have this kind of hardware in our laptops, this shows that ZK truly is about to get better and better for client-side proving.
In the meantime, 1kB is more than enough for a LOT of usecases, and we're curious to see what people will do with this code in their hands. See you at the next ZPrize!
Thanks to all the teams that participated: zproof, mengling, trapdoortech, ponos technology, storswiftlabs. Special thanks as well to Victor Sint-Nicolaas for the help assessing the solutions.
