Open in app

Sign in

Write

Sign in

Fuzzing the BLS-Precompiles

Marius Van Der Wijden
Coinmonks
5 min readSep 21, 2020

--

Ethereum’s upcoming hardfork Berlin should introduce a lot of new primitives. One of those are BLS (Boneh–Lynn–Shacham) signatures. BLS signatures are interesting as they allow for signature aggregation. They are a needed for the deposit contract for ETH2. This article gives a quick rundown of our work on testing these consensus critical components.

EIP-2537 introduces 9 new precompiles into Ethereum. They implement basic curve operations for the BLS12–381 curve. Here’s a short explainer for BLS12–381. The following table gives a quick overview over the precompiles.

Overview of the 9 BLS-Precompiles

The PR that implements the curve functions in assembly and golang came with a lot of test cases. These however mostly tested the cryptographic functions not the integration into the go-ethereum code (things like gas computations). I created a differential fuzzer to test the assembly and golang version against each other as well as against another BLS library.

This basic fuzzer found an issue where the gas calculation crashed with an index out of bounds error and an carry bug in the multiplication code with adx turned off. They were quickly fixed by the PR author. We decided to merge the PR to setup YOLOv1 but disable the assembly code.

We launched an ephemeral testnet called yolov1 to allow for better testing between clients, not only between BLS libraries. There were some hiccups with yolov1, after some initial testing the signer went out of disk, was then reset to a signer that didn’t have the BLS precompiles enabled so the signer crashed when I send the next proper BLS call to it. The Ethereum Cat Herders published a nice timeline of it here.

The first fuzzer only created purely random inputs to the precompiles. Most operations however require very specific structures that are almost never hit by a random fuzzer. I started working on a new fuzzer that could generate valid inputs to the precompiles and send transactions to the testnet. Since all major clients, go-ethereum, OpenEthereum, Besu and Nethermind had implemented the testnet spec by then, I could run each of them on my local machine to see if they crash.

I found several crashes during fuzzing. OpenEthereum calculated a block differently (most likely because of a configuration issue) and crashed completely on an input which turned out to be a on-off issue in devp2p. Besu had another index out of bounds issue during gas calculation, the same we found earlier in go-ethereum.

But fuzzing on a testnet isn’t really viable. I could send ~100 transactions every 15 seconds which really limited the amount of fuzzing we could do. So we created another fuzzer that creates state tests (tests that can be executed by all clients) using goevmlab.

The third fuzzer can also generate valid pairings which the previous fuzzers couldn’t. It found several crashers in Netherminds state-test execution code. The first one was gas calculation problem in Nethermind’s implementation of G1 multiexponentiation. The second one was a crasher in MapToG1. Nethermind did not throw an error on input that was larger than expected. We also found two non-critical bugs in the tool used to run the generated state tests.

Another crasher that took us extremely long to debug was a gas difference between geth and OE. It turned out that OE had included another EIP into their Berlin config (which we used for yolov1), EIP-2046 which reduced the costs for the STATICCALL opcode, thus producing different gas results.

List of all uncovered bugs:

List of our fuzzers:

  • Basic BLS Fuzzer: creates random tests against the BLS library used in go-ethereum directly. Does differential fuzzing of this library against another BLS library.
  • Transaction Fuzzer: creates transactions that can be send to a network. Implements better generators to reach deeper states in the implementation.
  • State-Test Fuzzer: creates state tests that can be executed on most clients. It executes the state tests, collects the execution traces and compares them.

A big thanks to Martin Holst Swende for his continued work on goevmlab and all the CPU cycles he donated to keeping Ethereum save! A big thanks to Alexander Vlasov for implementing the libraries and helping us every step of the way. And a big thanks to all the client teams that acted so fast on Martin and my bug reports.

If you have any questions about our fuzzing efforts, please reach out to me! @vdWijden on Twitter or Marius van der Wijden on Linkedin.

Also, Read

Ethereum
Cryptography
Fuzzing
Bugs
Solidity

--

--

Marius Van Der Wijden
Coinmonks

Written by Marius Van Der Wijden

111 Followers
Writer for

Ethereum Developer, State Channel Researcher, Student at TU Darmstadt

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams