Date

October 9, 2023

Author

Nalin

TL;DR

P256Verifier is:

• a pure function, without per-account precomputation
• a best-practices codebase: no assembly, no unchecked, 100% test coverage and tested against the Wycheproof vectors
• thoroughly documented
• gas-efficient
• compatible with the proposed EIP-7212 precompile
• and, as of last week, audited by Veridise

We’ll go into more detail about each of these and talk about the internals of the verifier later in this post, but first, here’s how you can get started using it today.

Install the repository using forge install daimo-eth/p256-verifier and add p256-verifier/=lib/p256-verifier/src/ to your remappings.txt file to get started. Usage is as simple as:

import "p256-verifier/P256.sol";

bytes32 hash; // message hash
uint256 r, s; // signature
uint256 x, y; // public key

bool valid = P256.verifySignature(hash, r, s, x, y);

If you’re trying to use it on a chain where the verifier is not currently deployed, see the deploy script in the repository.

Comparison

Other teams have deployed a variety of different solutions to bring P256 signatures on-chain. There are primarily three interesting approaches: ZK-SNARK based verifiers, smart contract verifiers (with and without signing-key-specific precomputation), and native protocol precompiles.

P256Verifier uses a smart-contract based approach (with no precomputation) and makes tradeoffs that we believe make it one of the best choices for verifying P256 signatures on-chain.

SNARK-based verifiers

Using SNARK (succinctness) properties, ZK-SNARKs provide a great way to reduce gas cost for computation on Ethereum.

The specific case of verifying a single P256 signature, however, only requires a few elliptic curve operations, which are lighter even compared to the verification algorithms of ZK-SNARKs. The two most popular SNARK based verifiers, written in Halo2 and Circom, both cost more (or comparable) gas compared to our verifier.

Additionally, both these SNARK verifiers require a preprocessing step: converting a signature into a SNARK proof. This step usually requires a beefy server and takes several seconds. This provides a significantly worse UX compared to P256Verifier, which provides users the ability to instantly submit transactions to the chain.

On the security side, besides the circuits lacking audits, using SNARKs introduces extra cryptographic assumptions such as pairings, STARK/FRI, trusted setup etc that may be broken in future. In comparison, P256Verifier only relies on standard P256 ECDSA verification, and with it a more lindy set of cryptographic assumptions.

However, in the long term, one reason SNARK-based approaches may be more effective than our approach is if SNARKs are used to aggregate many signatures across users before transactions are batched and posted on-chain. In the near term, however, transactions using P256 signatures seem few and far apart for applications to actually benefit from aggregation while maintaining a good UX.

Smart contract verifiers

The other leading approach has been through writing a signature verifier directly in Solidity. The naive implementation of a verifier is unsurprisingly very expensive in gas cost. The DNSSEC-Oracle in the ENS smart contracts was one of the first such implementations and cost ~2M gas for a verification.

Many teams have since worked on optimising smart contract verifiers, and most recently, Renaud Dubois from the Ledger team published a paper presenting the currently gas-optimal smart contract verifier: https://eprint.iacr.org/2023/939.pdf. He suggests usage of some great classical ideas and particular tricks that optimize for the EVM instruction set to enable a verifier that costs only ~270k gas$^1$.

Our P256Verifier implementation builds on top of the Ledger implementation. We’ve significantly simplified it, made the code cleaner, added more thorough testing and most importantly, we’ve gotten our code audited.

Our simplifications and code improvement (in particular, removing assembly and unchecked) came at a cost: the average signature verification costs ~20% more gas. We believe this increase to be worth the advantages of simpler code and improved auditability for such an important primitive.

Native protocol precompiles

Finally, the long term approach that has slowly been gaining momentum is the idea of enshrining P256 verification as a new precompile. This is proposed in EIP-7212, and would reduce cost by about 99% to a constant 3450 gas, similar to the 3000 gas charged by ecrecover, one of the earliest Ethereum precompiles.

While there is a lot of interest from application developers to add this precompile, there is also a lot of resistance to adding this precompile from Ethereum L1 and L2 protocol developers. Vitalik recently wrote about the tradeoffs of adding new precompiles to the L1. On the L2 side, in the near term, many L2s aim to make their chains as cross-compatible and easy to use for developers. So they don’t want to add new precompiles for worry of “losing” EVM equivalence with the rest of the ecosystem.

To address this, we propose a new idea of progressive precompiles. The primary purpose of many precompiles is to reduce the gas cost of common operations. Notably, in many cases, they do not introduce an entirely new capability, so it is still possible to write the functionality of the precompile in Solidity using existing EVM opcodes, albeit for much more gas cost. P256Verifier is one such case: the proposed precompile would reduce the gas cost of a verification to ~3.4k gas from ~334k for the smart contract verifier.

This suggests a nice trick: we can create precompiles at deterministic CREATE2 deploy addresses of the same functionality written in a smart contract for a smoother precompile deployment process. Different “EVM-equivalent” L2s and L1s may ship the precompile at different times, but developer contracts keep working, calling into the same address. It just becomes more gas-efficient once the precompile lands.

This approach also enables cross-compatibility for contracts between chains where the precompile may or may not exist, and for L2s to effectively introduce precompiles for specific functionality that gains popularity on their specific chain.

We’d love to hear more community discussion around EIP-7212 and the idea of progressive precompiles with it.

Under The Hood

The P256Verifier implementation relies on a number of cute math tricks and engineering optimisations. Our implementation was inspired by Renaud Dubois/Ledger's implementation and blst, and credit for many of these tricks goes to them.

First, as a quick reminder, to verify a P256 ECDSA signature, we input the signature consisting of a tuple of scalars $(r, s)$, hash of the signed message $h$, and public key $(x, y)$ representing an elliptic curve point. The signature is considered valid iff the $x$-coordinate of $(h \cdot s^{-1}) \cdot G + (r \cdot s^{-1}) \cdot (x, y)$ == $r$ (where $G$ is the generator element of the P256 EC group).

Strauss-Shamir Trick

The first major optimisation relies on the observation that we are computing something of the form $u \cdot G + v \cdot P$ where $u$ and $v$ are scalars and $G$ and $P$ are elliptic curve points. The naive way to perform this computation would be to first perform two scalar multiplications to compute $u \cdot G$ and $v \cdot P$ and then perform a elliptic curve addition to add the resultant points.

Scalar multiplications are expensive operations. The primitive operations available in an elliptic curve are point addition and point doubling. So, to perform a scalar multiplication, we need to go over the scalar bit-by-bit and maintain an accumulator point we keep adding to. If a bit is active we add the point we’re multiplying and at each step we double the accumulator. Both elliptic curve additions and doublings are expensive primitives by themselves, so saving on these yields a large optimisation.

The Strauss-Shamir trick notices a pattern in the computation of $u \cdot G + v \cdot P$. Since we only care about the resultant value and not the intermediaries, one way we could re-arrange the computation is to go over $u$ and $v$ bit-by-bit simultaneously. We maintain an accumulator we’ll double at each step as before, but now, we notice that if a bit is active in $u$, then we add $G$ to the accumulator. If the bit is active in $v$, we add $P$ and if the bit if active in both $u$ and $v$, we add $G + P$ to the accumulator. This already halves the number of elliptic curve doublings we had to do compared to before. Notice further that $G + P$ can be precomputed and re-used during the additions where both $u$ and $v$ had active bits, so we actually save even more cycles.

Extended Jacobian Representation

Much of the underlying field arithmetic is already made cheap in the EVM by the existence of ADDMOD and MULMOD opcodes (that perform modular addition and modular multiplication, respectively). Building on top of these, however, there is a lot of optimization space to implement elliptic curve point addition and point doubling efficiently. Luckily, this is a common problem for many cryptography libraries and the Explicit Formulas Database provides guidance on the state-of-the-art for different curve types.

In particular for the P256 curve parameters, it turns out the extended Jacobian representation is the most efficient representation for implementation. This representation (and implementations of efficient EC doubling and addition using it) exist across many popular cryptography libraries such as blst and gnark. We’ve based our Solidity implementation of these functions on the blst implementation, cross-referencing the formulas database itself for correctness (as our code comments indicate).

Point at infinity

One edge case to be particularly careful about in implementation is the so-called point at infinity of the elliptic curve. This is a point $O$ such that for any point on the elliptic curve $P$, $P + O = O + P = P$. Essentially, the point at infinity that acts as the additive identity for points on the curve. Such a point does not actually exist on the curve, so the tradition is to use $(0, 0)$ as a dummy point not on the curve to represent it. This adds some edge cases that require careful handling.

Wycheproof and test vectors

Finally, our implementation is accompanied by a clean test suite using the Wycheproof test vectors. It’s implemented in two pieces: the first is a package to generate test vectors matching the input format of the P256Verifier contract and cross-checking the generated vectors using the SubtleCrypto and Noble curves libraries.

These vectors also match the specification for EIP-7212, so they double as test vectors for potential future client implementations.

The second is our foundry test-suite that parses and runs our verifier against the vectors. Funnily enough, in the process of writing and getting our verifier to pass all the vectors, we ended up discovering a footgun in foundry JSON parsing and recreating our implementation in Sage.

We hope this test suite will be useful to others building P256 verifier implementations or implementing EIP-7212 in execution clients.

If this post and our mission of making Ethereum payments real is interesting to you, check out our Open Roles page or reach out to us at blog@daimo.xyz

Thanks to Renaud Dubois, Supranational, and the Clave team whose work we depend on and mention in this blog post.