Numerology: Fast ECC arithmetic on-chain
Optimized ECC arithmetic library for secp256k1 in Solidity
(Skip the talk, go straight to the code.)
As part of our efforts to provide better guarantees for the NuCypher protocol, we are currently exploring how to validate on-chain the work performed by NuCypher nodes. In particular, this requires using smart contracts to verify the zero-knowledge proofs that are attached to each ciphertext produced by Umbral, our proxy re-encryption library.
Since, at the moment, there is no native support for curve secp256k1 arithmetic in Solidity, we have developed Numerology, our own Solidity library of arithmetic functions for this curve. In particular, Numerology provides optimized ECC algorithms useful for verifying Schnorr-like zero-knowledge proofs. These algorithms are honed to spend as little gas as possible.
Before continuing, a warning: Don’t use it with any private input (e.g., a private key), as it’s going to be exposed in the Ethereum blockchain. Don’t ever use this to sign something! Also, this library is currently experimental — Use at your own risk!
Some implementation details
Typical ECC implementations usually have to deal with certain degree of resistance to side-channel attacks (e.g., timing attacks, power analysis, etc.), depending on the platform of execution. The main reason for that is that they need to protect leakage of secret inputs (e.g., private keys) through side-channels. In practice, this imposes certain limitations on the efficiency and performance of the ECC implementation, due to the countermeasures that have to be considered.
In our case, however, the execution platform is public (i.e., the Ethereum network). This has two major implications: on the one hand, no private input should be used with this library, ever (see the warning above!); on the other hand, our implementation can ignore most of these countermeasures.
For the moment, the focus of Numerology is to optimize the verification of equations of the form aP + bQ = R, which are common in some types of ECC-based zero knowledge proofs. In order to do so, we implement a method for simultaneous multiplication, instead of computing aP and bQ independently. We further speed up each multiplication by using an efficient curve endomorphism of secp256k1; to this regard, we implement the Gallant-Lambert-Vanstone (GLV) method, which allows trading each 256-bit multiplication, to a simultaneous multiplication with two 128-bit scalars. As a result, using Numerology to evaluate an equation of the form aP + bQ = R, takes approximately 500,000 gas.
A final note on the implementation: since a critical requirement of Numerology is to spend as little gas as possible, and due to our efforts to bypass some EVM and Solidity limitations, the code can be ugly as hell sometimes (sorry for that!).
Issues and Bugs
If you find any issues or bugs with Numerology, feel free to make an issue on Github or even a Pull Request. In case of a security issue, please email security@nucypher.com. If you would like to discuss Numerology development or ask a question, please join our development Discord server and talk with us (we’re there all the time!).
