❌ This repository is deprecated. Please refer to the crypto-lib repository to find the latest implementation of the secp256r1 curve.

secp256r1 verify

Description

secp256r1-verify is a specialized Solidity library that enables on-chain ECDSA signature verification on the secp256r1 curve with notable efficiency. This repository is a simple implementation for signature verification. It sets a vital foundation for the widespread application of FIDO2's Webauthn, serving as an authentication protocol for smart accounts. If you are looking for an alternative implementation, such as the ones based on the *codedopy opcodes, check out Renaud Dubois' FreshCryptoLib repository.

Installation

Foundry

To install the secp256r1-verify package in a Foundry project, execute the following command:

forge install https://github.com/get-smooth/secp256r1-verify

This command will install the latest version of the package in your lib directory. To install a specific version of the library, follow the instructions in the official Foundry documentation.

Hardhat or Truffle

To install the secp256r1-verify package in a Hardhat or Truffle project, use npm to run the following command:

npm install @smoo.th/secp256r1-verify

After the installation, import the package into your project and use it.

Usage

This repository provides a unique verification implementation. After you've integrated this library into your project, you can freely import the ECDSA256r1 and use it.

🚨 The implementations have not been audited. DO NOT USE IT IN PRODUCTION.

1️⃣ The traditional implementation

The traditional approach is the implementation present in this repository. You can take a look to it here: ECDSA256r1 file. This implementation is ready to use right out of the box; simply deploy the library and interact with it by calling its singular exposed function, verify, which accepts three parameters:

• bytes32 messageHash: The hash of the message to verify
• uint256[2] calldata rs: The r and s values of the ECDSA signature
• uint256[2] calldata point: The public key point of the signer

This approach computes uG + vQ using the Strauss-Shamir's trick on the secp256r1 elliptic curve on-chain, where G is the base point and Q is the public key.

Scripts

This repository includes a script directory containing a set of scripts that can be used to deploy the different implementations on-chain. Each script contains a set of instructions and an example of how to use it. The scripts are expected to be run using the forge script command.

Gas reports

These gas reports were produced using the 0.8.19 version of the Solidity compiler (with 100k optimizer runs), specifically for the 0.4.1 version of the library. The library version corresponds to commit 4d0716f.

ℹ️ If you import the library into your project, we strongly recommend you to enable the optimizer with 100k in order to have the best gas consumption.

The traditional implementation 🔗

Contributing

To contribute to the project, you must have Foundry and Node.js installed on your system. You can download them from their official websites:

• Node.js: https://nodejs.org/
• Foundry: https://book.getfoundry.sh/getting-started/installation

ℹ️ We recommend using nvm to manage your Node.js versions. Nvm is a flexible node version manager that allows you to switch between different versions of Node.js effortlessly. This repository includes a .nvmrc file at the root of the project. If you have nvm installed, you can run nvm use at the root of the project to automatically switch to the appropriate version of Node.js.

Following the installation of Foundry and Node.js, there's an additional dependency called make that needs to be addressed.

make is a build automation tool that employs a file known as a makefile to automate the construction of executable programs and libraries. The makefile details the process of deriving the target program from the source files and other dependencies. This allows developers to automate repetitive tasks and manage complex build processes efficiently. make is our primary tool in a multi-environment repository. It enables us to centralize all commands into a single file (the makefile), eliminating the need to deal with npm scripts defined in a package.json or remembering the various commands provided by the foundry cli. If you're unfamiliar with make, you can read more about it here.

make is automatically included in all modern Linux distributions. If you're using Linux, you should be able to use make without any additional steps. If not, you can likely find it in the package tool you usually use. MacOS users can install make using Homebrew with the following command:

brew install make

At this point, you should have all the required dependencies installed on your system.

💡 Running make at the root of the project will display a list of all the available commands. This can be useful to know what you can do

Installing the dependencies

To install the project dependencies, you can run the following command:

make install

This command will install the forge dependencies in the lib/ directory, the npm dependencies in the node_modules directory and the git hooks defined in the project (refer to the Git hooks sections to learn more about them). These dependencies aren't shipped in production; they're utility dependencies used to build, test, lint, format, and more, for the project.

⚠️ This package uses a dependency installed on the Github package registry, meaning you need to authenticate with GitHub Packages to install it. For more information, refer to the troubleshooting section. We're open to deploying it on the npm registry if there's a demand for it. Please open an issue if you'd like to see this package on the npm registry.

Next, let's set up the git hooks.

Git hooks

This project uses Lefthook to manage Git hooks, which are scripts that run automatically when certain Git events occur, such as committing code or pushing changes to a remote repository. Lefthook simplifies the management and execution of these scripts.

After installing the dependencies, you can configure the Git hooks by running the following command in the project directory:

make hooks-i

This command installs a Git hook that runs Lefthook before pushing code to a remote repository. If Lefthook fails, the push is aborted.

If you wish to run Lefthook manually, you can use the following command:

make hooks

This will run all the Git hooks defined in the lefthook file.

Skipping git hooks

Should you need to intentionally skip Lefthook, you can pass the --no-verify flag to the git push command. To bypass Lefthook when pushing code, use the following command:

git push origin --no-verify

Testing

Unit tests

The unit tests are stored in the test directory. They test individual functions of the package in isolation. These tests are automatically run by GitHub Actions with every push to the main branch and on every pull request targeting this branch. They are also automatically run by the git hook on every push to a remote repository if you have installed it (refer to the Git hooks section). Alternatively, you can run them locally by executing the following command in the project directory:

make test

ℹ️ By adding the sufix -v the test command will run in verbose mode, displaying valuable output for debugging.

For your information, these tests are written using forge, and some employ the property-based testing pattern (fuzzing) to generate random inputs for the functions under test.

Additionally, some test fixtures have been generated using Google's wycheproof project, which tests crypto libraries against known attacks. These fixtures are located in the fixtures directory.

The tests use two different cheatcodes you should be aware of:

• vm.readFile: This cheatcode lets us read the fixtures data from the test/fixtures directory. This means that every time you run the test suite, the fixtures are read from the disk, eliminating the need to copy/paste the fixtures into the test files. However, if you modify a fixture, you need to rerun the tests to see the changes. More information is available here.
• vm.ffi: This cheatcode allows us to execute an arbitrary command during the test suite. This cheatcode is not enabled by default when creating a new foundry project, but in our case, it's enabled in our configuration (foundry configuration) for all tests. This cheatcode is used to run the computation library that calculates 256 points on the secp256r1 elliptic curve from a public key. This is required for the variants that need these points to be deployed on-chain. Therefore, even if it's not explicit, every time you run the test suite, a Node.js script is executed multiple times. You can learn more about the library we use here.

📖 Cheatcodes are special instructions exposed by Foundry to enhance the developer experience. Learn more about them here.

💡 Run make to learn how to run the test in verbose mode, or to display the coverage or the gas consumption.

Quality

This repository uses forge-fmt, solhint and prettier to enforce code quality. These tools are automatically run by the GitHub Actions on every push to the main branch and on every pull request targeting this branch. They are also automatically run by the git hook on every push to a remote repository if you have installed it (refer to the Git hooks section). Alternatively, you can run them locally by executing the following command in the project directory:

make lint # run the linter
make format # run the formatter
make quality # run both

ℹ️ By adding the sufix -fix the linter and the formatter will try to fix the issues automatically.

Acknowledgements

Special thanks to rdubois-crypto for developing the reference implementation here and for the invaluable cryptographic guidance. The implementation, and more precisely, all the ingenious mathematical tricks you can discover in this repository, are from his mind. My role here was to clean up his work to improve the chances of accepting contributions. All credit goes to him.

If you want to learn more about the math behind this project, check out this publication written by rdubois-crypto.

Contents

• ECDSA
• nModInv
• pModInv
• secp256r1 constants

ECDSA

Git Source

Library for handling Elliptic Curve Digital Signature Algorithm (ECDSA) operations on a compatible curve

Functions

zz2Aff

Convert from XYZZ coordinates to affine coordinates Learn more about the XYZZ representation here: https://hyperelliptic.org/EFD/g1p/auto-shortw-xyzz-3.html#addition-add-2008-s*

function zz2Aff(uint256 x, uint256 y, uint256 zz, uint256 zzz) internal returns (uint256 x1, uint256 y1);

Parameters

Returns

zzAddN

Adds a point in XYZZ coordinates to a point in affine coordinates

function zzAddN(
    uint256 x1,
    uint256 y1,
    uint256 zz1,
    uint256 zzz1,
    uint256 x2,
    uint256 y2
)
    internal
    pure
    returns (uint256 P0, uint256 P1, uint256 P2, uint256 P3);

Parameters

Returns

zzDouble

Performs point doubling operation in XYZZ coordinates on an elliptic curve

This implements the "dbl-2008-s-1" doubling formulas from Sutherland's 2008 paper

function zzDouble(
    uint256 x,
    uint256 y,
    uint256 zz,
    uint256 zzz
)
    internal
    pure
    returns (uint256 P0, uint256 P1, uint256 P2, uint256 P3);

Parameters

Returns

affIsOnCurve

Check if a point in affine coordinates is on the curve

function affIsOnCurve(uint256 x, uint256 y) internal pure returns (bool);

Parameters

Returns

affAdd

Add two points on the elliptic curve in affine coordinates

function affAdd(uint256 x0, uint256 y0, uint256 x1, uint256 y1) internal returns (uint256 x2, uint256 y2);

Parameters

Returns

nModInv

Git Source

Calculate the modular inverse of a given integer, which is the inverse of this integer modulo n.

Uses the ModExp precompiled contract at address 0x05 for fast computation using little Fermat theorem

function nModInv(uint256 self) returns (uint256 result);

Parameters

Returns

pModInv

Git Source

Calculate the modular inverse of a given integer, which is the inverse of this integer modulo p.

Uses the ModExp precompiled contract at address 0x05 for fast computation using little Fermat theorem

function pModInv(uint256 self) returns (uint256 result);

Parameters

Returns

Constants

Git Source

p

uint256 constant p = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF;

a

uint256 constant a = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC;

b

uint256 constant b = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B;

gx

uint256 constant gx = 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296;

gy

uint256 constant gy = 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5;

n

uint256 constant n = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551;

MINUS_2

uint256 constant MINUS_2 = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFD;

MINUS_2MODN

uint256 constant MINUS_2MODN = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC63254F;

MINUS_1

uint256 constant MINUS_1 = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF;

MODEXP_PRECOMPILE

address constant MODEXP_PRECOMPILE = 0x0000000000000000000000000000000000000005;

ECDSA256r1

Git Source

A library to verify ECDSA signatures made on the secp256r1 curve

This is the easiest library to deal with but also the most expensive in terms of gas cost. Indeed, this library must calculate multiple points on the curve in order to verify the signature. Use it kmowingly.

Functions

isPointValid

Verifies that a point is on the secp256r1 curve

function isPointValid(uint256 x, uint256 y) internal pure returns (bool);

Parameters

Returns

mulmuladd

and Q is the public key.

function mulmuladd(uint256 Q0, uint256 Q1, uint256 scalar_u, uint256 scalar_v) internal returns (uint256 X);

Parameters

Returns

verify

Verifies an ECDSA signature on the secp256r1 curve given the message, signature, and public key. This function is the only one exposed by the library

Note the required interactions with the precompled contract can revert the transaction

function verify(bytes32 message, uint256 r, uint256 s, uint256 qx, uint256 qy) internal returns (bool);

Parameters

Returns