specs & benchmarks for the ZPrize 3 - High Throughput Signature Verification

Overview

Zprize: High Throughput Signature Verification

How fast do you think you can verify our ECDSA signatures on Aleo?

This year's Zprize is winner-take-all. Join and compete for $500,000.

The competition will start on September 15th, 2023, and will end in February, 2024.

Read on the learn more about the High Throughput Signature Verification prize.

What is ECDSA?

ECDSA is the most widely used digital signature scheme as of today. It is based on the now depreciated DSA standard, which was already based on Schnorr signatures at the time (but different enough to avoid patents).

ECDSA is defined on elliptic curves, must often with the P-256 curve, but in the cryptocurrency world the secp256k1 curve is most often found instead.

A signature scheme is usually always accompanied with a hash function. ECDSA is commonly used with the SHA-256 hash function, but other hash functions can be used as well. For example, Ethereum uses the keccak256 hash function (which is essentially SHA-3 with custom parameters).

Why ECDSA signature verification?

Verifying ECDSA signatures allows bridging on-chain applications with either off-chain applications or other web3 platforms that make use of the signature standard (for example, Ethereum, Celestia, Bitcoin, etc.)

In addition, many of the problems that have to be optimized in order to make ECDSA signature verification more efficient in SNARKs are found in other useful use cases as well (see next section).

Why is it hard?

Verifying ECDSA signature(s) inside a SNARK is considered problematic, as it involves:

  • bitwise operations (XOR, ROT, etc.) for the hash function which is not SNARK-friendly
  • non-native arithmetic (NNA) for the elliptic curve operations that are not native to the field used by the circuit

On top of this, you need to implement elliptic curve operations (like scalar multiplication) and the ECDSA verifier algorithm itself. Due to this, every seemingly-benign operation will tend to blow up, causing the ECDSA verifier circuit to be very large.

What is the prize about?

Different projects and proof systems use different techniques, and techniques used in one project don't often easily translate to other projects as they involve a lot of ad-hoc manual work.

For this reason, it is a good idea to narrow the context of this competition to make it useful for a specific proof system and framework.

For this prize, we'll specifically target the Aleo proof system Varuna based on the Marlin proof system (see here for a nice explainer).

What am I allowed to do?

The proof system of Aleo, Varuna, is based on the R1CS arithmetization. As such, your first leverage is to optimize the R1CS circuit itself. You can do this in two ways: by using the high-level DSL Leo, Aleo instructions, or by writing R1CS directly in Rust using Aleo's embedded DSL (more on that later). Writing R1CS directly is usually preferred when one is trying to reduce the number of constraints as much as they can. But low-level R1CS gadgets can be exposed to Leo through Leo operators.

Your second line of attack is to blindly optimize the prover's implementation. We do not expect the most impressive changes to come from there, and as such we will not place a lot of emphasis on this part of the solution. Furthermore, we won't allow GPU and more generally approaches making use of hardware acceleration.

Finally, we're also doing something special: we'll allow protocol-level modifications on Varuna, as long as they're contained and realistic. That is, they should not dramatically increase the prover time and memory usage for current programs that people are writing. The proof sizes should not drastically increase as well. In general, we expect people to take advantage of lookup tables, which are specified in the latest Varuna specification.

Note: another way to tackle this problem could be to use a different proof system, as long as that other proof system is secure, and that a proof for that different proof system can be safely wrapped in a Varuna proof (that is, you can write a verifier circuit with the Varuna stack).

How should I start?

First, you should take a look at the zprize_2023 branch of the SnarkVM repository.

If you want to write in Aleo instructions, the vm/ folder contains various tests which show how to write and prove programs.

If you want to write R1CS or lookups directly in Aleo's embedded DSL, you can take a look at the tests in the circuit/ folder. The subfolders contain gadgets showing how to create R1CS or lookup constraints.

A naive solution should be the start of any solution :) you can look at xJsnark and Gnark's pure R1CS optimizations for non-native arithmetic. These solutions could be implemented using Aleo's embedded DSL.

To get a sense of how costs scale asymptotically, participants can either run a benchmark or look at the Varuna specification.

Don't hesitate to check prior work in lookups (e.g. the XOR table optimization in this paper).

Security first

Playing with constraint optimizations, or protocol-level changes can be dangerous. You should always make sure that your changes are sound and secure.

As such, security will be the first metric we'll use to judge results. As it will be hard for us to review different solutions that explore different (potentially dangerous) techniques, we will place a lot of emphasis in clarity, readability, and auditability of the code and the associated documentation.

In other words, if your solution looks like this PR, this is not going to work for us :)

What are the other metrics for the prize?

The competition will start in a free-form format, but later in September we will release a set of benchmarks that will be used to judge the different solutions.

We're expecting these to be Rust benchmarks that you'll be able to run locally with your code to measure how long it takes to verify our random ECDSA signatures. Note that messages should be hashed in-circuit, not outside.

As such, you can expect benchmarks that will attempt to verify proofs with the following public inputs: ECDSA signatures, public keys, and messages (all unrelated). The ECDSA configuration will use secp256k1 and keccak256.

Competitors will be able to split these public inputs over several proofs if needed (for example, if you need 4 proofs to verify our 3 signatures, you can do that).

Licensing

All submission code must be open-sourced at the time of submission. Code and documentation must be dual-licensed under both the MIT and Apache-2.0 licenses

Questions

If there are any questions about this prize, please contact [email protected] or ask your question on Discord.

You might also like...
A certificate verification library for rustls that uses the operating system's verifier

rustls-platform-verifier A Rust library to verify the validity of TLS certificates based on the operating system's certificate facilities. On operatin

A certificate verification library for rustls that uses the operating system's verifier

rustls-platform-verifier A Rust library to verify the validity of TLS certificates based on the operating system's certificate facilities. On operatin

RSA dependency for rust, with cert verification

About Project End to End encryption (RSA) for multiple languages (cross-platform) with double encryption and double decryption methods Icon Item 🥳 Up

Simple, reliable, open-source contract verification built for an L2 centric Ethereum ecosystem

Cove This repo contains the backend verification1 code for Cove, a simple, reliable, open-source contract verification built for an L2 centric Ethereu

A high performance blockchain kernel for enterprise users.
A high performance blockchain kernel for enterprise users.

English | 简体中文 What is CITA CITA is a fast and scalable blockchain kernel for enterprises. CITA supports both native contract and EVM contract, by whi

An extremely high performance matching engine written in Rust.

Galois Introduction Galois is an extremely high performance matching engine written in Rust, typically used for the crypto currency exchange service.

High Performance Blockchain Deserializer

bitcoin-explorer bitcoin_explorer is an efficient library for reading bitcoin-core binary blockchain file as a database (utilising multi-threading). D

Spartan: High-speed zkSNARKs without trusted setup

Spartan: High-speed zkSNARKs without trusted setup Spartan is a high-speed zero-knowledge proof system, a cryptographic primitive that enables a prove

Authenticated Encryption with Associated Data Algorithms: high-level encryption ciphers

RustCrypto: Authenticated Encryption with Associated Data (AEAD) Algorithms Collection of Authenticated Encryption with Associated Data (AEAD) algorit

Owner
null
Rust implementation of {t,n}-threshold ECDSA (elliptic curve digital signature algorithm).

Multi-party ECDSA This project is a Rust implementation of {t,n}-threshold ECDSA (elliptic curve digital signature algorithm). Threshold ECDSA include

[ZenGo X] 706 Jan 5, 2023
Cryptographic signature algorithms: ECDSA, Ed25519

RustCrypto: signatures Support for digital signatures, which provide authentication of data using public-key cryptography. All algorithms reside in th

Rust Crypto 300 Jan 8, 2023
ECDSA Signature Server

Simple REST API used for serving ECDSA signatures to prevent automation software from minting NFTs in bulk.

Jonathan 3 Nov 30, 2022
An ECDSA threshold signature algorithm implemented in Rust.

Open TSS This project is a Rust implementation of multi-party {t,n}-threshold signature scheme(TSS). The current version of this library supports ECDS

LatticeX Foundation 64 Dec 17, 2022
Fastmurmur3 - Fast non-cryptographic hash, with the benchmarks to prove it.

Fastmurmur3 Murmur3 is a fast, non-cryptographic hash function. fastmurmur3 is, in my testing, the fastest implementation of Murmur3. Usage let bytes:

Kurt Wolf 13 Dec 2, 2022
Benchmarks of most widely used web frameworks built in rust.

Rust framework benchmarks Benchmarking utility to test the performance of all the rust web frameworks. Built with rust ?? . Demo (Last updated: Thu Ju

Ishtmeet Singh 4 Oct 21, 2022
cargo-generate template for Criterion benchmarks

Criterion Benchmark Template This is a cargo-generate template for quickly creating benchmarks using the Criterion benchmarking framework. Usage $ car

Lily Mara 4 Jan 19, 2023
Fast and efficient ed25519 signing and verification in Rust.

ed25519-dalek Fast and efficient Rust implementation of ed25519 key generation, signing, and verification in Rust. Documentation Documentation is avai

dalek cryptography 563 Dec 26, 2022
deductive verification of Rust code. (semi) automatically prove your code satisfies your specifications!

Le marteau-pilon, forges et aciéries de Saint-Chamond, Joseph-Fortuné LAYRAUD, 1889 About Creusot is a tool for deductive verification of Rust code. I

Xavier Denis 609 Dec 28, 2022
An implementation of NZ COVID Pass verification written in Rust

NZCP Rust   An implementation of NZ COVID Pass verification, New Zealand's proof of COVID-19 vaccination solution, written in Rust ?? We also have a J

Vaxx.nz 7 Nov 24, 2022