go-ethereum Documentation

Technical Documentation: ethereum/go-ethereum

ℹ️ Provenance: Multi-Tier Ingestion · CodeWiki Reference

Overview (`README.md`)

Go Ethereum

Golang execution layer implementation of the Ethereum protocol.

Automated builds are available for stable releases and the unstable master branch. Binary
archives are published at https://geth.ethereum.org/downloads/.

Building the source

For prerequisites and detailed build instructions please read the Installation Instructions.

Building geth requires both a Go (version 1.25 or later) and a C compiler. You can install
them using your favourite package manager. Once the dependencies are installed, run

shell

make geth

or, to build the full suite of utilities:

shell

make all

Executables

The go-ethereum project comes with several wrappers/executables found in the cmd
directory.

Command	Description
`geth`	Our main Ethereum CLI client. It is the entry point into the Ethereum network (main-, test- or private net), capable of running as a full node (default) or archive node (retaining all historical state). It can be used by other processes as a gateway into the Ethereum network via JSON RPC endpoints exposed on top of HTTP, WebSocket and/or IPC transports. `geth --help` and the CLI page for command line options.
`devp2p`	Utilities to interact with nodes on the networking layer, without running a full blockchain.
`abigen`	Source code generator to convert Ethereum contract definitions into easy-to-use, compile-time type-safe Go packages. It operates on plain Ethereum contract ABIs with expanded functionality if the contract bytecode is also available. It accepts contract ABIs via `--abi` (optionally with bytecode) or compiler `--combined-json` output. Please see our Native DApps page for details.
`evm`	Developer utility version of the EVM (Ethereum Virtual Machine) that is capable of running bytecode snippets within a configurable environment and execution mode. Its purpose is to allow isolated, fine-grained debugging of EVM opcodes (e.g. `evm run --trace 60ff60ff`).
`rlpdump`	Developer utility tool to convert binary RLP (Recursive Length Prefix) dumps (data encoding used by the Ethereum protocol both network as well as consensus wise) to user-friendlier hierarchical representation (e.g. `rlpdump --hex CE0183FFFFFFC4C304050583616263`).

Running `geth`

Going through all the possible command line flags is out of scope here (please consult our
CLI Wiki page),
but we've enumerated a few common parameter combos to get you up to speed quickly
on how you can run your own geth instance.

Hardware Requirements

Minimum:

CPU with 4+ cores
8GB RAM
High-performance SSD with at least 2TB of free space
8 MBit/sec download Internet service

Recommended:

Fast CPU with 8+ cores
16GB+ RAM
High-performance NVMe SSD with 2TB-4TB of space for long term growth and maintenance headroom
25+ MBit/sec download Internet service

Full node on the main Ethereum network

By far the most common scenario is people wanting to simply interact with the Ethereum
network: create accounts; transfer funds; deploy and interact with contracts. For this
particular use case, the user doesn't care about years-old historical data, so we can
sync quickly to the current state of the network. To do so:

shell

$ geth console

This command will:

Start geth in snap sync mode (default, can be changed with the --syncmode flag),
causing it to download more data in exchange for avoiding processing the entire history
of the Ethereum network, which is very CPU intensive.
Start the built-in interactive JavaScript console,
(via the trailing console subcommand) through which you can interact using web3 methods
(note: the web3 version bundled within geth is very old, and not up to date with official docs),
as well as geth's own management APIs.
This tool is optional and if you leave it out you can always attach it to an already running
geth instance with geth attach.

A Full node on the Sepolia test network

Transitioning towards developers, if you'd like to play around with creating Ethereum
contracts, you almost certainly would like to do that without any real money involved until
you get the hang of the entire system. In other words, instead of attaching to the main
network, you want to join the test network with your node, which is fully equivalent to
the main network, but with play-Ether only.

shell

$ geth --sepolia console

The console subcommand has the same meaning as above and is equally
useful on the testnet too.

Specifying the --sepolia flag, however, will reconfigure your geth instance a bit:

Instead of connecting to the main Ethereum network, the client will connect to the Sepolia
test network, which uses different P2P bootnodes, different network IDs and genesis
states.
Instead of using the default data directory (~/.ethereum on Linux for example), geth
will nest itself one level deeper into a sepolia subfolder (~/.ethereum/sepolia on
Linux). Note, on OSX and Linux this also means that attaching to a running testnet node
requires the use of a custom endpoint since geth attach will try to attach to a
production node endpoint by default, e.g.,
geth attach <datadir>/sepolia/geth.ipc. Windows users are not affected by
this.

Note: Although some internal protective measures prevent transactions from
crossing over between the main network and test network, you should always
use separate accounts for play and real money. Unless you manually move
accounts, geth will by default correctly separate the two networks and will not make any
accounts available between them.

Configuration

As an alternative to passing the numerous flags to the geth binary, you can also pass a
configuration file via:

shell

$ geth --config /path/to/your_config.toml

To get an idea of how the file should look like you can use the dumpconfig subcommand to
export your existing configuration:

shell

$ geth --your-favourite-flags dumpconfig

Docker quick start

One of the quickest ways to get Ethereum up and running on your machine is by using
Docker:

shell

docker run -d --name ethereum-node -v /Users/alice/ethereum:/root \
           -p 8545:8545 -p 30303:30303 \
           ethereum/client-go

This will start geth in snap-sync mode with a DB memory allowance of 1GB, as the
above command does. It will also create a persistent volume in your home directory for
saving your blockchain as well as map the default ports. There is also an alpine tag
available for a slim version of the image.

Do not forget --http.addr 0.0.0.0, if you want to access RPC from other containers
and/or hosts. By default, geth binds to the local interface and RPC endpoints are not
accessible from the outside.

Programmatically interfacing `geth` nodes

As a developer, sooner rather than later you'll want to start interacting with geth and the
Ethereum network via your own programs and not manually through the console. To aid
this, geth has built-in support for a JSON-RPC based APIs (standard APIs
and geth specific APIs).
These can be exposed via HTTP, WebSockets and IPC (UNIX sockets on UNIX based
platforms, and named pipes on Windows).

The IPC interface is enabled by default and exposes all the APIs supported by geth,
whereas the HTTP and WS interfaces need to manually be enabled and only expose a
subset of APIs due to security reasons. These can be turned on/off and configured as
you'd expect.

HTTP based JSON-RPC API options:

--http Enable the HTTP-RPC server
--http.addr HTTP-RPC server listening interface (default: localhost)
--http.port HTTP-RPC server listening port (default: 8545)
--http.api API's offered over the HTTP-RPC interface (default: eth,net,web3)
--http.corsdomain Comma separated list of domains from which to accept cross-origin requests (browser enforced)
--ws Enable the WS-RPC server
--ws.addr WS-RPC server listening interface (default: localhost)
--ws.port WS-RPC server listening port (default: 8546)
--ws.api API's offered over the WS-RPC interface (default: eth,net,web3)
--ws.origins Origins from which to accept WebSocket requests
--ipcdisable Disable the IPC-RPC server
--ipcpath Filename for IPC socket/pipe within the datadir (explicit paths escape it)

You'll need to use your own programming environments' capabilities (libraries, tools, etc) to
connect via HTTP, WS or IPC to a geth node configured with the above flags and you'll
need to speak JSON-RPC on all transports. You
can reuse the same connection for multiple requests!

Note: Please understand the security implications of opening up an HTTP/WS based
transport before doing so! Hackers on the internet are actively trying to subvert
Ethereum nodes with exposed APIs! Further, all browser tabs can access locally
running web servers, so malicious web pages could try to subvert locally available
APIs!

Operating a private network

Maintaining your own private network is more involved as a lot of configurations taken for
granted in the official networks need to be manually set up.

Unfortunately since the Merge it is no longer possible
to easily set up a network of geth nodes without also setting up a corresponding beacon chain.

There are three different solutions depending on your use case:

If you are looking for a simple way to test smart contracts from go in your CI, you can use the Simulated Backend.
If you want a convenient single node environment for testing, you can use our Dev Mode.
If you are looking for a multiple node test network, you can set one up quite easily with Kurtosis.

Contribution

Thank you for considering helping out with the source code! We welcome contributions
from anyone on the internet, and are grateful for even the smallest of fixes!

If you'd like to contribute to go-ethereum, please fork, fix, commit and send a pull request
for the maintainers to review and merge into the main code base. If you wish to submit
more complex changes though, please check up with the core devs first on our Discord Server
to ensure those changes are in line with the general philosophy of the project and/or get
some early feedback which can make both your efforts much lighter as well as our review
and merge procedures quick and simple.

Please make sure your contributions adhere to our coding guidelines:

Code must adhere to the official Go formatting
guidelines (i.e. uses gofmt).
Code must be documented adhering to the official Go commentary
guidelines.
Pull requests need to be based on and opened against the master branch.
Commit messages should be prefixed with the package(s) they modify.
- E.g. "eth, rpc: make trace configs optional"

Please see the Developers' Guide
for more details on configuring your environment, managing project dependencies, and
testing procedures.

Contributing to geth.ethereum.org

For contributions to the go-ethereum website, please checkout and raise pull requests against the website branch.
For more detailed instructions please see the website branch README or the
contributing page of the website.

License

The go-ethereum library (i.e. all code outside of the cmd directory) is licensed under the
GNU Lesser General Public License v3.0,
also included in our repository in the COPYING.LESSER file.

The go-ethereum binaries (i.e. all code inside of the cmd directory) are licensed under the
GNU General Public License v3.0, also
included in our repository in the COPYING file.

Overview (`metrics/README.md`)

go-metrics

Go port of Coda Hale's Metrics library: https://github.com/dropwizard/metrics.

Documentation: https://godoc.org/github.com/rcrowley/go-metrics.

Usage

Create and update metrics:

c := metrics.NewCounter()
metrics.Register("foo", c)
c.Inc(47)

g := metrics.NewGauge()
metrics.Register("bar", g)
g.Update(47)

r := NewRegistry()
g := metrics.NewRegisteredFunctionalGauge("cache-evictions", r, func() int64 { return cache.getEvictionsCount() })

s := metrics.NewExpDecaySample(1028, 0.015) // or metrics.NewUniformSample(1028)
h := metrics.NewHistogram(s)
metrics.Register("baz", h)
h.Update(47)

m := metrics.NewMeter()
metrics.Register("quux", m)
m.Mark(47)

t := metrics.NewTimer()
metrics.Register("bang", t)
t.Time(func() {})
t.Update(47)

t := metrics.GetOrRegisterTimer("account.create.latency", nil)
t.Time(func() {})
t.Update(47)

NOTE: Be sure to unregister short-lived meters and timers otherwise they will
leak memory:

// Will call Stop() on the Meter to allow for garbage collection
metrics.Unregister("quux")
// Or similarly for a Timer that embeds a Meter
metrics.Unregister("bang")

Periodically log every metric in human-readable form to standard error:

go metrics.Log(metrics.DefaultRegistry, 5 * time.Second, log.New(os.Stderr, "metrics: ", log.Lmicroseconds))

Periodically log every metric in slightly-more-parseable form to syslog:

w, _ := syslog.Dial("unixgram", "/dev/log", syslog.LOG_INFO, "metrics")
go metrics.Syslog(metrics.DefaultRegistry, 60e9, w)

Periodically emit every metric to Graphite using the Graphite client:

import "github.com/cyberdelia/go-metrics-graphite"

addr, _ := net.ResolveTCPAddr("tcp", "127.0.0.1:2003")
go graphite.Graphite(metrics.DefaultRegistry, 10e9, "metrics", addr)

Periodically emit every metric into InfluxDB:

NOTE: this has been pulled out of the library due to constant fluctuations
in the InfluxDB API. In fact, all client libraries are on their way out. see
issues #121 and
#124 for progress and details.

import "github.com/vrischmann/go-metrics-influxdb"

go influxdb.InfluxDB(metrics.DefaultRegistry,
  10e9, 
  "127.0.0.1:8086", 
  "database-name", 
  "username", 
  "password"
)

Periodically emit every metric to StatHat:

import "github.com/rcrowley/go-metrics/stathat"

go stathat.Stathat(metrics.DefaultRegistry, 10e9, "[email protected]")

Maintain all metrics along with expvars at /debug/metrics:

This uses the same mechanism as the official expvar
but exposed under /debug/metrics, which shows a json representation of all your usual expvars
as well as all your go-metrics.

import "github.com/rcrowley/go-metrics/exp"

exp.Exp(metrics.DefaultRegistry)

Installation

go get github.com/rcrowley/go-metrics

StatHat support additionally requires their Go client:

go get github.com/stathat/go

Publishing Metrics

Clients are available for the following destinations:

Graphite - https://github.com/cyberdelia/go-metrics-graphite
InfluxDB - https://github.com/vrischmann/go-metrics-influxdb
Ganglia - https://github.com/appscode/metlia
Prometheus - https://github.com/deathowl/go-metrics-prometheus
DataDog - https://github.com/syntaqx/go-metrics-datadog
SignalFX - https://github.com/pascallouisperez/go-metrics-signalfx

Overview (`accounts/scwallet/README.md`)

Using the smartcard wallet

Requirements

A USB smartcard reader
A keycard that supports the status app
PCSCD version 4.3 running on your system Only version 4.3 is currently supported

Preparing the smartcard

WARNING: FOLLOWING THESE INSTRUCTIONS WILL DESTROY THE MASTER KEY ON YOUR CARD. ONLY PROCEED IF NO FUNDS ARE ASSOCIATED WITH THESE ACCOUNTS

You can use status' keycard-cli and you should get at least version 2.1.1 of their smartcard application

You also need to make sure that the PCSC daemon is running on your system.

Then, you can install the application to the card by typing:

text

keycard install -a keycard_v2.2.1.cap && keycard init

At the end of this process, you will be provided with a PIN, a PUK and a pairing password. Write them down, you'll need them shortly.

Start geth with the console command. You will notice the following warning:

text

WARN [04-09|16:58:38.898] Failed to open wallet                    url=keycard://044def09                          err="smartcard: pairing password needed"

Write down the URL (keycard://044def09 in this example). Then ask geth to open the wallet:

text

> personal.openWallet("keycard://044def09", "pairing password")

The pairing password has been generated during the card initialization process.

The process needs to be repeated once more with the PIN:

text

> personal.openWallet("keycard://044def09", "PIN number")

If everything goes well, you should see your new account when typing personal on the console:

text

> personal
WARN [04-09|17:02:07.330] Smartcard wallet account derivation failed url=keycard://044def09 err="Unexpected response status Cla=0x80, Ins=0xd1, Sw=0x6985"
{
  listAccounts: [],
  listWallets: [{
      status: "Empty, waiting for initialization",
      url: "keycard://044def09"
  }],
  ...
}

So the communication with the card is working, but there is no key associated with this wallet. Let's create it:

text

> personal.initializeWallet("keycard://044def09")
"tilt ... impact"

You should get a list of words, this is your seed so write them down. Your wallet should now be initialized:

text

> personal.listWallets
[{
  accounts: [{
      address: "0x678b7cd55c61917defb23546a41803c5bfefbc7a",
      url: "keycard://044d/m/44'/60'/0'/0/0"
  }],
  status: "Online",
  url: "keycard://044def09"
}]

You're all set!

Usage

Start geth with the console command
Check the card's URL by checking personal.listWallets:

text

listWallets: [{
      status: "Online, can derive public keys",
      url: "keycard://a4d73015"
  }]

Open the wallet, you will be prompted for your pairing password, then PIN:

text

personal.openWallet("keycard://a4d73015")

Check that creation was successful by typing e.g. personal. Then use it like a regular wallet.

Known issues

Starting geth with a valid card seems to make firefox crash.
PCSC version 4.4 should work, but is currently untested

Overview (`cmd/devp2p/README.md`)

The devp2p command

The devp2p command line tool is a utility for low-level peer-to-peer debugging and
protocol development purposes. It can do many things.

ENR Decoding

Use devp2p enrdump to verify and display an Ethereum Node Record.

Node Key Management

The devp2p key ... command family deals with node key files.

Run devp2p key generate mynode.key to create a new node key in the mynode.key file.

Run devp2p key to-enode mynode.key -ip 127.0.0.1 -tcp 30303 to create an enode:// URL
corresponding to the given node key and address information.

Maintaining DNS Discovery Node Lists

The devp2p command can create and publish DNS discovery node lists.

Run devp2p dns sign <directory> to update the signature of a DNS discovery tree.

Run devp2p dns sync <enrtree-URL> to download a complete DNS discovery tree.

Run devp2p dns to-cloudflare <directory> to publish a tree to CloudFlare DNS.

Run devp2p dns to-route53 <directory> to publish a tree to Amazon Route53.

You can find more information about these commands in the DNS Discovery Setup Guide.

Node Set Utilities

There are several commands for working with JSON node set files. These files are generated
by the discovery crawlers and DNS client commands. Node sets also used as the input of the
DNS deployer commands.

Run devp2p nodeset info <nodes.json> to display statistics of a node set.

Run devp2p nodeset filter <nodes.json> <filter flags...> to write a new, filtered node
set to standard output. The following filters are supported:

-limit <N> limits the output set to N entries, taking the top N nodes by score
-ip <CIDR> filters nodes by IP subnet
-min-age <duration> filters nodes by 'first seen' time
-eth-network <mainnet/sepolia/hoodi> filters nodes by "eth" ENR entry
-les-server filters nodes by LES server support
-snap filters nodes by snap protocol support

For example, given a node set in nodes.json, you could create a filtered set containing
up to 20 eth mainnet nodes which also support snap sync using this command:

text

devp2p nodeset filter nodes.json -eth-network mainnet -snap -limit 20

Discovery v4 Utilities

The devp2p discv4 ... command family deals with the Node Discovery v4
protocol.

Run devp2p discv4 ping <enode/ENR> to ping a node.

Run devp2p discv4 resolve <enode/ENR> to find the most recent node record of a node in
the DHT.

Run devp2p discv4 crawl <nodes.json path> to create or update a JSON node set.

Discovery v5 Utilities

The devp2p discv5 ... command family deals with the Node Discovery v5
protocol. This protocol is currently under active development.

Run devp2p discv5 ping <ENR> to ping a node.

Run devp2p discv5 resolve <ENR> to find the most recent node record of a node in
the discv5 DHT.

Run devp2p discv5 listen to run a Discovery v5 node.

Run devp2p discv5 crawl <nodes.json path> to create or update a JSON node set containing
discv5 nodes.

Combined Discovery

Run devp2p discovery listen to run a node speaking all supported discovery protocol
versions (currently discv4 and discv5) on a single UDP port. For a single-protocol node, use
devp2p discv4 listen or devp2p discv5 listen. Add --rpc <addr> to expose the
per-protocol HTTP API (discv4_*, discv5_*).

Add the global --metrics flag to any listen command to collect metrics. They are served
at /debug/metrics/prometheus (and /debug/metrics as expvar JSON) on
--metrics.addr:--metrics.port, default 127.0.0.1:6060. The discover/* series
report table size per bucket, bytes in and out, received packets per message type, and
dropped packets per protocol version. The --metrics.influxdb* flags also work and push the
same series to InfluxDB, under the geth. prefix.

Discovery Test Suites

The devp2p command also contains interactive test suites for Discovery v4 and Discovery
v5.

To run these tests against your implementation, you need to set up a networking
environment where two separate UDP listening addresses are available on the same machine.
The two listening addresses must also be routed such that they are able to reach the node
you want to test.

For example, if you want to run the test on your local host, and the node under test is
also on the local host, you need to assign two IP addresses (or a larger range) to your
loopback interface. On macOS, this can be done by executing the following command:

text

sudo ifconfig lo0 add 127.0.0.2

You can now run either test suite as follows: Start the node under test first, ensuring
that it won't talk to the Internet (i.e. disable bootstrapping). An easy way to prevent
unintended connections to the global DHT is listening on 127.0.0.1.

Now get the ENR of your node and store it in the NODE environment variable.

Start the test by running devp2p discv5 test -listen1 127.0.0.1 -listen2 127.0.0.2 $NODE.

Eth Protocol Test Suite

The Eth Protocol test suite is a conformance test suite for the eth protocol.

To run the eth protocol test suite against your implementation, the node needs to be initialized
with our test chain. The chain files are located in ./cmd/devp2p/internal/ethtest/testdata.

initialize the geth node with the genesis.json file
import blocks from chain.rlp
run the client using the resulting database. For geth, use a command like the one below:

geth
--datadir
--nodiscover
--nat=none
--networkid 3503995874084926
--verbosity 5
--authrpc.jwtsecret jwt.secret

Note that the tests also require access to the engine API.
The test suite can now be executed using the devp2p tool.

text

devp2p rlpx eth-test \
    --chain internal/ethtest/testdata   \
    --node enode://....                 \
    --engineapi http://127.0.0.1:8551   \
    --jwtsecret $(cat jwt.secret)

Repeat the above process (re-initialising the node) in order to run the Eth Protocol test suite again.

Overview (`cmd/ethkey/README.md`)

ethkey

ethkey is a simple command-line tool for working with Ethereum keyfiles.

Usage

`ethkey generate`

Generate a new keyfile.
If you want to use an existing private key to use in the keyfile, it can be
specified by setting --privatekey with the location of the file containing the
private key.

`ethkey inspect `

Print various information about the keyfile.
Private key information can be printed by using the --private flag;
make sure to use this feature with great caution!

`ethkey signmessage `

Sign the message with a keyfile.
It is possible to refer to a file containing the message.
To sign a message contained in a file, use the --msgfile flag.

`ethkey verifymessage
`

Verify the signature of the message.
It is possible to refer to a file containing the message.
To sign a message contained in a file, use the --msgfile flag.

`ethkey changepassword `

Change the password of a keyfile.
use the --newpasswordfile to point to the new password file.

Passwords

For every command that uses a keyfile, you will be prompted to provide the
password for decrypting the keyfile. To avoid this message, it is possible
to pass the password by using the --passwordfile flag pointing to a file that
contains the password.

JSON

In case you need to output the result in a JSON format, you shall use the --json flag.

Overview (`cmd/evm/README.md`)

EVM tool

The EVM tool provides a few useful subcommands to facilitate testing at the EVM
layer.

transition tool (t8n) : a stateless state transition utility
transaction tool (t9n) : a transaction validation utility
block builder tool (b11r): a block assembler utility

State transition tool (`t8n`)

The evm t8n tool is a stateless state transition utility. It is a utility
which can

Take a prestate, including
- Accounts,
- Block context information,
- Previous block hashes (*optional)
Apply a set of transactions,
Apply a mining-reward (*optional),
And generate a post-state, including
- State root, transaction root, receipt root,
- Information about rejected transactions,
- Optionally: a full or partial post-state dump

Specification

The idea is to specify the behaviour of this binary very strict, so that other
node implementors can build replicas based on their own state-machines, and the
state generators can swap between a `geth`-based implementation and a `parityvm`-based
implementation.

Command line params

Command line params that need to be supported are

text

--input.alloc value            (default: "alloc.json")
    --input.env value              (default: "env.json")
    --input.txs value              (default: "txs.json")
    --output.alloc value           (default: "alloc.json")
    --output.basedir value        
    --output.body value           
    --output.result value          (default: "result.json")
    --state.chainid value          (default: 1)
    --state.fork value             (default: "GrayGlacier")
    --state.reward value           (default: 0)
    --trace.memory                 (default: false)
    --trace.nomemory               (default: true)
    --trace.noreturndata           (default: true)
    --trace.nostack                (default: false)
    --trace.returndata             (default: false)

Objects

The transition tool uses JSON objects to read and write data related to the transition operation. The
following object definitions are required.

`alloc`

The alloc object defines the prestate that transition will begin with.

// Map of address to account definition.
type Alloc map[common.Address]Account
// Genesis account. Each field is optional.
type Account struct {
    Code       []byte                           `json:"code"`
    Storage    map[common.Hash]common.Hash      `json:"storage"`
    Balance    *big.Int                         `json:"balance"`
    Nonce      uint64                           `json:"nonce"`
    SecretKey  []byte                            `json:"secretKey"`
}

`env`

The env object defines the environmental context in which the transition will
take place.

type Env struct {
    // required
    CurrentCoinbase  common.Address      `json:"currentCoinbase"`
    CurrentGasLimit  uint64              `json:"currentGasLimit"`
    CurrentNumber    uint64              `json:"currentNumber"`
    CurrentTimestamp uint64              `json:"currentTimestamp"`
    Withdrawals      []*Withdrawal       `json:"withdrawals"`
    // optional
    CurrentDifficulty *big.Int           `json:"currentDifficulty"`
    CurrentRandom     *big.Int           `json:"currentRandom"`
    CurrentBaseFee    *big.Int           `json:"currentBaseFee"`
    ParentDifficulty  *big.Int           `json:"parentDifficulty"`
    ParentGasUsed     uint64             `json:"parentGasUsed"`
    ParentGasLimit    uint64             `json:"parentGasLimit"`
    ParentTimestamp   uint64             `json:"parentTimestamp"`
    BlockHashes       map[uint64]common.Hash `json:"blockHashes"`
    ParentUncleHash   common.Hash        `json:"parentUncleHash"`
    Ommers            []Ommer            `json:"ommers"`
}
type Ommer struct {
    Delta   uint64         `json:"delta"`
    Address common.Address `json:"address"`
}
type Withdrawal struct {
    Index          uint64         `json:"index"`
    ValidatorIndex uint64         `json:"validatorIndex"`
    Recipient      common.Address `json:"recipient"`
    Amount         *big.Int       `json:"amount"`
}

`txs`

The txs object is an array of any of the transaction types: LegacyTx,
AccessListTx, or DynamicFeeTx.

text

/* Detailed source-code truncated for AI context efficiency. */

`result`

The result object is output after a transition is executed. It includes
information about the post-transition environment.

type ExecutionResult struct {
    StateRoot   common.Hash    `json:"stateRoot"`
    TxRoot      common.Hash    `json:"txRoot"`
    ReceiptRoot common.Hash    `json:"receiptsRoot"`
    LogsHash    common.Hash    `json:"logsHash"`
    Bloom       types.Bloom    `json:"logsBloom"`
    Receipts    types.Receipts `json:"receipts"`
    Rejected    []*rejectedTx  `json:"rejected,omitempty"`
    Difficulty  *big.Int       `json:"currentDifficulty"`
    GasUsed     uint64         `json:"gasUsed"`
    BaseFee     *big.Int       `json:"currentBaseFee,omitempty"`
}

Error codes and output

All logging should happen against the stderr.
There are a few (not many) errors that can occur, those are defined below.

EVM-based errors (`2` to `9`)

Other EVM error. Exit code 2
Failed configuration: when a non-supported or invalid fork was specified. Exit code 3.
Block history is not supplied, but needed for a BLOCKHASH operation. If BLOCKHASH
is invoked targeting a block which history has not been provided for, the program will
exit with code 4.

IO errors (`10`-`20`)

Invalid input json: the supplied data could not be marshalled.
The program will exit with code 10
IO problems: failure to load or save files, the program will exit with code 11

text

# This should exit with 3
./evm t8n --input.alloc=./testdata/1/alloc.json --input.txs=./testdata/1/txs.json --input.env=./testdata/1/env.json --state.fork=Frontier+1346 2>/dev/null
exitcode:3 OK

Forks

Basic usage

The chain configuration to be used for a transition is specified via the
--state.fork CLI flag. A list of possible values and configurations can be
found in tests/init.go.

Examples

Basic usage

Invoking it with the provided example files

text

./evm t8n --input.alloc=./testdata/1/alloc.json --input.txs=./testdata/1/txs.json --input.env=./testdata/1/env.json --state.fork=Berlin

Two resulting files:

alloc.json:

json

{
 "0x8a8eafb1cf62bfbeb1741769dae1a9dd47996192": {
  "balance": "0xfeed1a9d",
  "nonce": "0x1"
 },
 "0xa94f5374fce5edbc8e2a8697c15331677e6ebf0b": {
  "balance": "0x5ffd4878be161d74",
  "nonce": "0xac"
 },
 "0xc94f5374fce5edbc8e2a8697c15331677e6ebf0b": {
  "balance": "0xa410"
 }
}

result.json:

text

/* Detailed source-code truncated for AI context efficiency. */

We can make them spit out the data to e.g. stdout like this:

text

./evm t8n --input.alloc=./testdata/1/alloc.json --input.txs=./testdata/1/txs.json --input.env=./testdata/1/env.json --output.result=stdout --output.alloc=stdout --state.fork=Berlin

Output:

text

/* Detailed source-code truncated for AI context efficiency. */

About Ommers

Mining rewards and ommer rewards might need to be added. This is how those are applied:

block_reward is the block mining reward for the miner (0xaa), of a block at height N.
For each ommer (mined by 0xbb), with blocknumber N-delta
- (where delta is the difference between the current block and the ommer)
- The account 0xbb (ommer miner) is awarded (8-delta)/ 8 * block_reward
- The account 0xaa (block miner) is awarded block_reward / 32

To make t8n apply these, the following inputs are required:

--state.reward
- For ethash, it is 5000000000000000000 wei,
- If this is not defined, mining rewards are not applied,
- A value of 0 is valid, and causes accounts to be 'touched'.
For each ommer, the tool needs to be given an address\ and a delta. This
is done via the ommers field in env.

Note: the tool does not verify that e.g. the normal uncle rules apply,
and allows e.g two uncles at the same height, or the uncle-distance. This means that
the tool allows for negative uncle reward (distance > 8)

Example:
./testdata/5/env.json:

json

{
  "currentCoinbase": "0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  "currentDifficulty": "0x20000",
  "currentGasLimit": "0x750a163df65e8a",
  "currentNumber": "1",
  "currentTimestamp": "1000",
  "ommers": [
    {"delta":  1, "address": "0xbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb" },
    {"delta":  2, "address": "0xcccccccccccccccccccccccccccccccccccccccc" }
  ]
}

When applying this, using a reward of 0x08
Output:

json

{
  "alloc": {
    "0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa": {
      "balance": "0x88"
    },
    "0xbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb": {
      "balance": "0x70"
    },
    "0xcccccccccccccccccccccccccccccccccccccccc": {
      "balance": "0x60"
    }
  }
}

Future EIPS

It is also possible to experiment with future eips that are not yet defined in a hard fork.
Example, putting EIP-1344 into Frontier:

text

./evm t8n --state.fork=Frontier+1344 --input.pre=./testdata/1/pre.json --input.txs=./testdata/1/txs.json --input.env=/testdata/1/env.json

Block history

The BLOCKHASH opcode requires blockhashes to be provided by the caller, inside the env.
If a required blockhash is not provided, the exit code should be 4:
Example where blockhashes are provided:

text

./evm t8n --input.alloc=./testdata/3/alloc.json --input.txs=./testdata/3/txs.json --input.env=./testdata/3/env.json  --trace --state.fork=Berlin

text

cat trace-0-0x72fadbef39cd251a437eea619cfeda752271a5faaaa2147df012e112159ffb81.jsonl | grep BLOCKHASH -C2

text

{"pc":0,"op":96,"gas":"0x5f58ef8","gasCost":"0x3","memSize":0,"stack":[],"depth":1,"refund":0,"opName":"PUSH1"}
{"pc":2,"op":64,"gas":"0x5f58ef5","gasCost":"0x14","memSize":0,"stack":["0x1"],"depth":1,"refund":0,"opName":"BLOCKHASH"}
{"pc":3,"op":0,"gas":"0x5f58ee1","gasCost":"0x0","memSize":0,"stack":["0xdac58aa524e50956d0c0bae7f3f8bb9d35381365d07804dd5b48a5a297c06af4"],"depth":1,"refund":0,"opName":"STOP"}
{"output":"","gasUsed":"0x17"}

In this example, the caller has not provided the required blockhash:

text

./evm t8n --input.alloc=./testdata/4/alloc.json --input.txs=./testdata/4/txs.json --input.env=./testdata/4/env.json --trace --state.fork=Berlin
ERROR(4): getHash(3) invoked, blockhash for that block not provided

Error code: 4

Chaining

Another thing that can be done, is to chain invocations:

text

./evm t8n --input.alloc=./testdata/1/alloc.json --input.txs=./testdata/1/txs.json --input.env=./testdata/1/env.json --state.fork=Berlin --output.alloc=stdout | ./evm t8n --input.alloc=stdin --input.env=./testdata/1/env.json --input.txs=./testdata/1/txs.json --state.fork=Berlin

What happened here, is that we first applied two identical transactions, so the second one was rejected.
Then, taking the poststate alloc as the input for the next state, we tried again to include
the same two transactions: this time, both failed due to too low nonce.

In order to meaningfully chain invocations, one would need to provide meaningful new env, otherwise the
actual blocknumber (exposed to the EVM) would not increase.

Transactions in RLP form

It is possible to provide already-signed transactions as input to, using an input.txs which ends with the rlp suffix.
The input format for RLP-form transactions is identical to the output format for block bodies. Therefore, it's fully possible
to use the evm to go from json input to rlp input.

The following command takes json the transactions in ./testdata/13/txs.json and signs them. After execution, they are output to signed_txs.rlp.:

text

./evm t8n --state.fork=London --input.alloc=./testdata/13/alloc.json --input.txs=./testdata/13/txs.json --input.env=./testdata/13/env.json --output.result=alloc_jsontx.json --output.body=signed_txs.rlp
INFO [12-27|09:25:11.102] Trie dumping started                     root=e4b924..6aef61
INFO [12-27|09:25:11.102] Trie dumping complete                    accounts=3 elapsed="275.66µs"
INFO [12-27|09:25:11.102] Wrote file                               file=alloc.json
INFO [12-27|09:25:11.103] Wrote file                               file=alloc_jsontx.json
INFO [12-27|09:25:11.103] Wrote file                               file=signed_txs.rlp

The output.body is the rlp-list of transactions, encoded in hex and placed in a string a'la json encoding rules:

text

cat signed_txs.rlp
"0xf8d2b86702f864010180820fa08284d09411111111111111111111111111111111111111118080c001a0b7dfab36232379bb3d1497a4f91c1966b1f932eae3ade107bf5d723b9cb474e0a06261c359a10f2132f126d250485b90cf20f30340801244a08ef6142ab33d1904b86702f864010280820fa08284d09411111111111111111111111111111111111111118080c080a0d4ec563b6568cd42d998fc4134b36933c6568d01533b5adf08769270243c6c7fa072bf7c21eac6bbeae5143371eef26d5e279637f3bd73482b55979d76d935b1e9"

We can use rlpdump to check what the contents are:

text

rlpdump -hex $(cat signed_txs.rlp | jq -r )
[
  02f864010180820fa08284d09411111111111111111111111111111111111111118080c001a0b7dfab36232379bb3d1497a4f91c1966b1f932eae3ade107bf5d723b9cb474e0a06261c359a10f2132f126d250485b90cf20f30340801244a08ef6142ab33d1904,
  02f864010280820fa08284d09411111111111111111111111111111111111111118080c080a0d4ec563b6568cd42d998fc4134b36933c6568d01533b5adf08769270243c6c7fa072bf7c21eac6bbeae5143371eef26d5e279637f3bd73482b55979d76d935b1e9,
]

Now, we can now use those (or any other already signed transactions), as input, like so:

text

./evm t8n --state.fork=London --input.alloc=./testdata/13/alloc.json --input.txs=./signed_txs.rlp --input.env=./testdata/13/env.json --output.result=alloc_rlptx.json
INFO [12-27|09:25:11.187] Trie dumping started                     root=e4b924..6aef61
INFO [12-27|09:25:11.187] Trie dumping complete                    accounts=3 elapsed="123.676µs"
INFO [12-27|09:25:11.187] Wrote file                               file=alloc.json
INFO [12-27|09:25:11.187] Wrote file                               file=alloc_rlptx.json

You might have noticed that the results from these two invocations were stored in two separate files.
And we can now finally check that they match.

text

cat alloc_jsontx.json | jq .stateRoot && cat alloc_rlptx.json | jq .stateRoot
"0xe4b924a6adb5959fccf769d5b7bb2f6359e26d1e76a2443c5a91a36d826aef61"
"0xe4b924a6adb5959fccf769d5b7bb2f6359e26d1e76a2443c5a91a36d826aef61"

Transaction tool

The transaction tool is used to perform static validity checks on transactions such as:

intrinsic gas calculation
max values on integers
fee semantics, such as maxFeePerGas < maxPriorityFeePerGas
newer tx types on old forks

Examples

text

./evm t9n --state.fork Homestead --input.txs testdata/15/signed_txs.rlp
[
  {
    "error": "transaction type not supported",
    "hash": "0xa98a24882ea90916c6a86da650fbc6b14238e46f0af04a131ce92be897507476"
  },
  {
    "error": "transaction type not supported",
    "hash": "0x36bad80acce7040c45fd32764b5c2b2d2e6f778669fb41791f73f546d56e739a"
  }
]

text

./evm t9n --state.fork London --input.txs testdata/15/signed_txs.rlp
[
  {
    "address": "0xd02d72e067e77158444ef2020ff2d325f929b363",
    "hash": "0xa98a24882ea90916c6a86da650fbc6b14238e46f0af04a131ce92be897507476",
    "intrinsicGas": "0x5208"
  },
  {
    "address": "0xd02d72e067e77158444ef2020ff2d325f929b363",
    "hash": "0x36bad80acce7040c45fd32764b5c2b2d2e6f778669fb41791f73f546d56e739a",
    "intrinsicGas": "0x5208"
  }
]

Block builder tool (b11r)

The evm b11r tool is used to assemble and seal full block rlps.

Specification

Command line params

Command line params that need to be supported are:

text

--input.header value        `stdin` or file name of where to find the block header to use. (default: "header.json")
    --input.ommers value        `stdin` or file name of where to find the list of ommer header RLPs to use.
    --input.txs value           `stdin` or file name of where to find the transactions list in RLP form. (default: "txs.rlp")
    --output.basedir value      Specifies where output files are placed. Will be created if it does not exist.
    --output.block value        Determines where to put the alloc of the post-state. (default: "block.json")
                                <file> - into the file <file>
                                `stdout` - into the stdout output
                                `stderr` - into the stderr output
    --seal.clique value         Seal block with Clique. `stdin` or file name of where to find the Clique sealing data.
    --seal.ethash               Seal block with ethash. (default: false)
    --seal.ethash.dir value     Path to ethash DAG. If none exists, a new DAG will be generated.
    --seal.ethash.mode value    Defines the type and amount of PoW verification an ethash engine makes. (default: "normal")
    --verbosity value           Sets the verbosity level. (default: 3)

Objects

The header object is a consensus header.

go=

type Header struct {
        ParentHash  common.Hash       `json:"parentHash"`
        OmmerHash   *common.Hash      `json:"sha3Uncles"`
        Coinbase    *common.Address   `json:"miner"`
        Root        common.Hash       `json:"stateRoot"         gencodec:"required"`
        TxHash      *common.Hash      `json:"transactionsRoot"`
        ReceiptHash *common.Hash      `json:"receiptsRoot"`
        Bloom       types.Bloom       `json:"logsBloom"`
        Difficulty  *big.Int          `json:"difficulty"`
        Number      *big.Int          `json:"number"            gencodec:"required"`
        GasLimit    uint64            `json:"gasLimit"          gencodec:"required"`
        GasUsed     uint64            `json:"gasUsed"`
        Time        uint64            `json:"timestamp"         gencodec:"required"`
        Extra       []byte            `json:"extraData"`
        MixDigest   common.Hash       `json:"mixHash"`
        Nonce       *types.BlockNonce `json:"nonce"`
        BaseFee     *big.Int          `json:"baseFeePerGas"`
}

`ommers`

The ommers object is a list of RLP-encoded ommer blocks in hex
representation.

go=

type Ommers []string

`txs`

The txs object is a list of RLP-encoded transactions in hex representation.

go=

type Txs []string

`clique`

The clique object provides the necessary information to complete a clique
seal of the block.

go=

var CliqueInfo struct {
        Key       *common.Hash    `json:"secretKey"`
        Voted     *common.Address `json:"voted"`
        Authorize *bool           `json:"authorize"`
        Vanity    common.Hash     `json:"vanity"`
}

`output`

The output object contains two values, the block RLP and the block hash.

go=

type BlockInfo struct {
    Rlp  []byte      `json:"rlp"`
    Hash common.Hash `json:"hash"`
}

A Note on Encoding

The encoding of values for evm utility attempts to be relatively flexible. It
generally supports hex-encoded or decimal-encoded numeric values, and
hex-encoded byte values (like common.Address, common.Hash, etc). When in
doubt, the execution-apis way
of encoding should always be accepted.

Testing

There are many test cases in the cmd/evm/testdata directory.
These fixtures are used to power the t8n tests in
t8n_test.go. The best way to verify correctness of new evm
implementations is to execute these and verify the output and error codes match
the expected values.

Overview (`cmd/keeper/README.md`)

Keeper - geth as a zkvm guest

Keeper command is a specialized tool for validating stateless execution of Ethereum blocks. It's designed to run as a zkvm guest.

Overview

The keeper reads an RLP-encoded payload containing:

A block to execute
A witness with the necessary state data
A chainID

It then executes the block statelessly and validates that the computed state root and receipt root match the values in the block header.

Building Keeper

The keeper uses build tags to compile platform-specific input methods and chain configurations:

Example Implementation

See getpayload_example.go for a complete example with embedded Hoodi block data:

bash

# Build example with different chain configurations
go build -tags "example" ./cmd/keeper

Ziren zkVM Implementation

Build for the Ziren zkVM platform, which is a MIPS ISA-based zkvm:

bash

GOOS=linux GOARCH=mipsle GOMIPS=softfloat go build -tags "ziren" ./cmd/keeper

As an example runner, refer to https://gist.github.com/gballet/7b669a99eb3ab2b593324e3a76abd23d

Creating a Custom Platform Implementation

To add support for a new platform (e.g., "myplatform"), create a new file with the appropriate build tag:

1. Create `getinput_myplatform.go`

//go:build myplatform

package main

import (
    "github.com/ethereum/go-ethereum/params"
    // ... other imports as needed
)

// getInput returns the RLP-encoded payload
func getInput() []byte {
    // Your platform-specific code to retrieve the RLP-encoded payload
    // This might read from:
    // - Memory-mapped I/O
    // - Hardware registers
    // - Serial port
    // - Network interface
    // - File system

    // The payload must be RLP-encoded and contain:
    // - Block with transactions
    // - Witness with parent headers and state data

    return encodedPayload
}

Overview (`cmd/workload/README.md`)

Workload Testing Tool

This tool performs RPC calls against a live node. It has tests for the Sepolia testnet and
Mainnet. Note the tests require a fully synced node.

To run the tests against a Sepolia node, use:

shell

> ./workload test --sepolia http://host:8545

To run a specific test, use the --run flag to filter the test cases. Filtering works
similar to the go test command. For example, to run only tests for eth_getBlockByHash
and eth_getBlockByNumber, use this command:

text

> ./workload test --sepolia --run History/getBlockBy http://host:8545

Notably, trace tests require archive which keeps all the historical states for tracing.
The additional flag is required to activate the trace tests.

text

> ./workload test --sepolia --archive --run Trace/Block http://host:8545

Regenerating tests

There is a facility for updating the tests from the chain. This can also be used to
generate the tests for a new network. As an example, to recreate tests for mainnet, run
the following commands (in this directory) against a synced mainnet node:

shell

> go run . filtergen --queries queries/filter_queries_mainnet.json http://host:8545
> go run . historygen --history-tests queries/history_mainnet.json http://host:8545
> go run . tracegen --trace-tests queries/trace_mainnet.json --trace-start 4000000 --trace-end 4000100 http://host:8545
> go run . proofgen --proof-tests queries/proof_mainnet.json --proof-states 3000 http://host:8545

Overview (`crypto/keccak/README.md`)

This is a vendored and modified copy of golang.org/x/crypto/sha3, with an assembly
implementation of keccak256. We wish to retain the assembly implementation,
which was removed in v0.44.0.

Ethereum uses a 'legacy' variant of Keccak, which was defined before it became SHA3. As
such, we cannot use the standard library crypto/sha3 package.

Overview (`metrics/influxdb/README.md`)

go-metrics-influxdb

This is a reporter for the go-metrics library which will post the metrics to InfluxDB.

Note

This is only compatible with InfluxDB 0.9+.

Usage

import "github.com/vrischmann/go-metrics-influxdb"

go influxdb.InfluxDB(
    metrics.DefaultRegistry, // metrics registry
    time.Second * 10,        // interval
    "http://localhost:8086", // the InfluxDB url
    "mydb",                  // your InfluxDB database
    "myuser",                // your InfluxDB user
    "mypassword",            // your InfluxDB password
)

License

go-metrics-influxdb is licensed under the MIT license. See the LICENSE file for details.

Overview (`tests/fuzzers/README.md`)

Fuzzers

To run a fuzzer locally, you need go-fuzz installed.

First build a fuzzing-binary out of the selected package:

text

(cd ./rlp && CGO_ENABLED=0 go-fuzz-build .)

That command should generate a rlp-fuzz.zip in the rlp/ directory. If you are already in that directory, you can do

text

[user@work rlp]$ go-fuzz
2019/11/26 13:36:54 workers: 6, corpus: 3 (3s ago), crashers: 0, restarts: 1/0, execs: 0 (0/sec), cover: 0, uptime: 3s
2019/11/26 13:36:57 workers: 6, corpus: 3 (6s ago), crashers: 0, restarts: 1/0, execs: 0 (0/sec), cover: 1054, uptime: 6s
2019/11/26 13:37:00 workers: 6, corpus: 3 (9s ago), crashers: 0, restarts: 1/8358, execs: 25074 (2786/sec), cover: 1054, uptime: 9s
2019/11/26 13:37:03 workers: 6, corpus: 3 (12s ago), crashers: 0, restarts: 1/8497, execs: 50986 (4249/sec), cover: 1054, uptime: 12s
2019/11/26 13:37:06 workers: 6, corpus: 3 (15s ago), crashers: 0, restarts: 1/9330, execs: 74640 (4976/sec), cover: 1054, uptime: 15s
2019/11/26 13:37:09 workers: 6, corpus: 3 (18s ago), crashers: 0, restarts: 1/9948, execs: 99482 (5527/sec), cover: 1054, uptime: 18s
2019/11/26 13:37:12 workers: 6, corpus: 3 (21s ago), crashers: 0, restarts: 1/9428, execs: 122568 (5836/sec), cover: 1054, uptime: 21s
2019/11/26 13:37:15 workers: 6, corpus: 3 (24s ago), crashers: 0, restarts: 1/9676, execs: 145152 (6048/sec), cover: 1054, uptime: 24s
2019/11/26 13:37:18 workers: 6, corpus: 3 (27s ago), crashers: 0, restarts: 1/9855, execs: 167538 (6205/sec), cover: 1054, uptime: 27s
2019/11/26 13:37:21 workers: 6, corpus: 3 (30s ago), crashers: 0, restarts: 1/9645, execs: 192901 (6430/sec), cover: 1054, uptime: 30s
2019/11/26 13:37:24 workers: 6, corpus: 3 (33s ago), crashers: 0, restarts: 1/9967, execs: 219294 (6645/sec), cover: 1054, uptime: 33s

Otherwise:

text

go-fuzz -bin ./rlp/rlp-fuzz.zip

Notes

Once a 'crasher' is found, the fuzzer tries to avoid reporting the same vector twice, so stores the fault in the suppressions folder. Thus, if you
e.g. make changes to fix a bug, you should remove all data from the suppressions-folder, to verify that the issue is indeed resolved.

Also, if you have only one and the same exit-point for multiple different types of test, the suppression can make the fuzzer hide different types of errors. So make
sure that each type of failure is unique (for an example, see the rlp fuzzer, where a counter i is used to differentiate between failures:

golang

if !bytes.Equal(input, output) {
			panic(fmt.Sprintf("case %d: encode-decode is not equal, \ninput : %x\noutput: %x", i, input, output))
		}

Overview (`core/vm/program/readme.md`)

What is this

In many cases, we have a need to create somewhat nontrivial bytecode, for testing various
quirks related to state transition or evm execution.

For example, we want to have a CREATE2- op create a contract, which is then invoked, and when invoked does a selfdestruct-to-self.

It is overkill to go full solidity, but it is also a bit tricky do assemble this by concatenating bytes.

This utility takes an approach from goevmlab where it has been used for several years,
a go-lang utility to assemble evm bytecode.

Using this utility, the case above can be expressed as:

golang

// Some runtime code
	runtime := program.New().Ops(vm.ADDRESS, vm.SELFDESTRUCT).Bytecode()
	// A constructor returning the runtime code
	initcode := program.New().ReturnData(runtime).Bytecode()
	// A factory invoking the constructor
	outer := program.New().Create2AndCall(initcode, nil).Bytecode()

Warning

This package is a utility for testing, not for production. As such:

There are not package guarantees. We might iterate heavily on this package, and do backwards-incompatible changes without warning
There are no quality-guarantees. These utilities may produce evm-code that is non-functional. YMMV.
There are no stability-guarantees. The utility will panic if the inputs do not align / make sense.

Overview (`crypto/secp256k1/libsecp256k1/README.md`)

libsecp256k1

High-performance high-assurance C library for digital signatures and other cryptographic primitives on the secp256k1 elliptic curve.

This library is intended to be the highest quality publicly available library for cryptography on the secp256k1 curve. However, the primary focus of its development has been for usage in the Bitcoin system and usage unlike Bitcoin's may be less well tested, verified, or suffer from a less well thought out interface. Correct usage requires some care and consideration that the library is fit for your application's purpose.

Features:

secp256k1 ECDSA signing/verification and key generation.
Additive and multiplicative tweaking of secret/public keys.
Serialization/parsing of secret keys, public keys, signatures.
Constant time, constant memory access signing and public key generation.
Derandomized ECDSA (via RFC6979 or with a caller provided function.)
Very efficient implementation.
Suitable for embedded systems.
No runtime dependencies.
Optional module for public key recovery.
Optional module for ECDH key exchange.
Optional module for Schnorr signatures according to BIP-340.
Optional module for ElligatorSwift key exchange according to BIP-324.
Optional module for MuSig2 Schnorr multi-signatures according to BIP-327.

Implementation details

General
- No runtime heap allocation.
- Extensive testing infrastructure.
- Structured to facilitate review and analysis.
- Intended to be portable to any system with a C89 compiler and uint64_t support.
- No use of floating types.
- Expose only higher level interfaces to minimize the API surface and improve application security. ("Be difficult to use insecurely.")
Field operations
- Optimized implementation of arithmetic modulo the curve's field size (2^256 - 0x1000003D1).
  - Using 5 52-bit limbs
  - Using 10 26-bit limbs (including hand-optimized assembly for 32-bit ARM, by Wladimir J. van der Laan).
    - This is an experimental feature that has not received enough scrutiny to satisfy the standard of quality of this library but is made available for testing and review by the community.
Scalar operations
- Optimized implementation without data-dependent branches of arithmetic modulo the curve's order.
  - Using 4 64-bit limbs (relying on __int128 support in the compiler).
  - Using 8 32-bit limbs.
Modular inverses (both field elements and scalars) based on safegcd with some modifications, and a variable-time variant (by Peter Dettman).
Group operations
- Point addition formula specifically simplified for the curve equation (y^2 = x^3 + 7).
- Use addition between points in Jacobian and affine coordinates where possible.
- Use a unified addition/doubling formula where necessary to avoid data-dependent branches.
- Point/x comparison without a field inversion by comparison in the Jacobian coordinate space.
Point multiplication for verification (aP + bG).
- Use wNAF notation for point multiplicands.
- Use a much larger window for multiples of G, using precomputed multiples.
- Use Shamir's trick to do the multiplication with the public key and the generator simultaneously.
- Use secp256k1's efficiently-computable endomorphism to split the P multiplicand into 2 half-sized ones.
Point multiplication for signing
- Use a precomputed table of multiples of powers of 16 multiplied with the generator, so general multiplication becomes a series of additions.
- Intended to be completely free of timing sidechannels for secret-key operations (on reasonable hardware/toolchains)
  - Access the table with branch-free conditional moves so memory access is uniform.
  - No data-dependent branches
- Optional runtime blinding which attempts to frustrate differential power analysis.
- The precomputed tables add and eventually subtract points for which no known scalar (secret key) is known, preventing even an attacker with control over the secret key used to control the data internally.

Obtaining and verifying

The git tag for each release (e.g. v0.6.0) is GPG-signed by one of the maintainers.
For a fully verified build of this project, it is recommended to obtain this repository
via git, obtain the GPG keys of the signing maintainer(s), and then verify the release
tag's signature using git.

This can be done with the following steps:

Obtain the GPG keys listed in SECURITY.md.
If possible, cross-reference these key IDs with another source controlled by its owner (e.g.
social media, personal website). This is to mitigate the unlikely case that incorrect
content is being presented by this repository.

Clone the repository:

text

git clone https://github.com/bitcoin-core/secp256k1

Check out the latest release tag, e.g.
text
```
git checkout v0.6.0
```

Use git to verify the GPG signature:

text

% git tag -v v0.6.0 | grep -C 3 'Good signature'

gpg: Signature made Mon 04 Nov 2024 12:14:44 PM EST
gpg:                using RSA key 4BBB845A6F5A65A69DFAEC234861DBF262123605
gpg: Good signature from "Jonas Nick <[email protected]>" [unknown]
gpg:                 aka "Jonas Nick <[email protected]>" [unknown]
gpg: WARNING: This key is not certified with a trusted signature!
gpg:          There is no indication that the signature belongs to the owner.
Primary key fingerprint: 36C7 1A37 C9D9 88BD E825  08D9 B1A7 0E4F 8DCD 0366
     Subkey fingerprint: 4BBB 845A 6F5A 65A6 9DFA  EC23 4861 DBF2 6212 3605

Building with Autotools

text

$ ./autogen.sh       # Generate a ./configure script
$ ./configure        # Generate a build system
$ make               # Run the actual build process
$ make check         # Run the test suite
$ sudo make install  # Install the library into the system (optional)

To compile optional modules (such as Schnorr signatures), you need to run ./configure with additional flags (such as --enable-module-schnorrsig). Run ./configure --help to see the full list of available flags.

Building with CMake (experimental)

To maintain a pristine source tree, CMake encourages to perform an out-of-source build by using a separate dedicated build tree.

Building on POSIX systems

text

$ cmake -B build              # Generate a build system in subdirectory "build"
$ cmake --build build         # Run the actual build process
$ ctest --test-dir build      # Run the test suite
$ sudo cmake --install build  # Install the library into the system (optional)

To compile optional modules (such as Schnorr signatures), you need to run cmake with additional flags (such as -DSECP256K1_ENABLE_MODULE_SCHNORRSIG=ON). Run cmake -B build -LH or ccmake -B build to see the full list of available flags.

Cross compiling

To alleviate issues with cross compiling, preconfigured toolchain files are available in the cmake directory.
For example, to cross compile for Windows:

text

$ cmake -B build -DCMAKE_TOOLCHAIN_FILE=cmake/x86_64-w64-mingw32.toolchain.cmake

To cross compile for Android with NDK (using NDK's toolchain file, and assuming the ANDROID_NDK_ROOT environment variable has been set):

text

$ cmake -B build -DCMAKE_TOOLCHAIN_FILE="${ANDROID_NDK_ROOT}/build/cmake/android.toolchain.cmake" -DANDROID_ABI=arm64-v8a -DANDROID_PLATFORM=28

Building on Windows

To build on Windows with Visual Studio, a proper generator must be specified for a new build tree.

The following example assumes using of Visual Studio 2022 and CMake v3.21+.

In "Developer Command Prompt for VS 2022":

text

>cmake -G "Visual Studio 17 2022" -A x64 -B build
>cmake --build build --config RelWithDebInfo

Usage examples

Usage examples can be found in the examples directory. To compile them you need to configure with --enable-examples.

To compile the Schnorr signature and ECDH examples, you also need to configure with --enable-module-schnorrsig and --enable-module-ecdh.

Benchmark

If configured with --enable-benchmark (which is the default), binaries for benchmarking the libsecp256k1 functions will be present in the root directory after the build.

To print the benchmark result to the command line:

text

$ ./bench_name

To create a CSV file for the benchmark result :

text

$ ./bench_name | sed '2d;s/ \{1,\}//g' > bench_name.csv

Reporting a vulnerability

See SECURITY.md

Contributing to libsecp256k1

See CONTRIBUTING.md

Overview (`cmd/evm/testdata/10/readme.md`)

EIP-1559 testing

This test contains testcases for EIP-1559, which were reported by Ori as misbehaving.

text

[user@work evm]$ dir=./testdata/10 && ./evm t8n --state.fork=London --input.alloc=$dir/alloc.json --input.txs=$dir/txs.json --input.env=$dir/env.json --output.alloc=stdout --output.result=stdout 2>&1
INFO [05-09|22:11:59.436] rejected tx                              index=3 hash=db07bf..ede1e8 from=0xd02d72E067e77158444ef2020Ff2d325f929B363 error="gas limit reached"

Output:

text

/* Detailed source-code truncated for AI context efficiency. */

Overview (`cmd/evm/testdata/11/readme.md`)

Test missing basefee

In this test, the currentBaseFee is missing from the env portion.
On a live blockchain, the basefee is present in the header, and verified as part of header validation.

In evm t8n, we don't have blocks, so it needs to be added in the envinstead.

When it's missing, an error is expected.

text

dir=./testdata/11 && ./evm t8n --state.fork=London --input.alloc=$dir/alloc.json --input.txs=$dir/txs.json --input.env=$dir/env.json --output.alloc=stdout --output.result=stdout 2>&1>/dev/null
ERROR(3): EIP-1559 config but missing 'currentBaseFee' in env section

Overview (`cmd/evm/testdata/12/readme.md`)

Test 1559 balance + gasCap

This test contains an EIP-1559 consensus issue which happened on Ropsten, where
geth did not properly account for the value transfer while doing the check on max_fee_per_gas * gas_limit.

Before the issue was fixed, this invocation allowed the transaction to pass into a block:

text

dir=./testdata/12 && ./evm t8n --state.fork=London --input.alloc=$dir/alloc.json --input.txs=$dir/txs.json --input.env=$dir/env.json --output.alloc=stdout --output.result=stdout

With the fix applied, the result is:

text

/* Detailed source-code truncated for AI context efficiency. */

The transaction is rejected.

Overview (`cmd/evm/testdata/13/readme.md`)

Input transactions in RLP form

This testdata folder is used to exemplify how transaction input can be provided in rlp form.
Please see the README in evm folder for how this is performed.

Overview (`cmd/evm/testdata/14/readme.md`)

Difficulty calculation

This test shows how the evm t8n can be used to calculate the (ethash) difficulty, if none is provided by the caller.

Calculating it (with an empty set of txs) using London rules (and no provided unclehash for the parent block):

text

[user@work evm]$ ./evm t8n --input.alloc=./testdata/14/alloc.json --input.txs=./testdata/14/txs.json --input.env=./testdata/14/env.json --output.result=stdout --state.fork=London
INFO [03-09|10:43:57.070] Trie dumping started                     root=6f0588..7f4bdc
INFO [03-09|10:43:57.070] Trie dumping complete                    accounts=2 elapsed="214.663µs"
INFO [03-09|10:43:57.071] Wrote file                               file=alloc.json
{
  "result": {
    "stateRoot": "0x6f058887ca01549716789c380ede95aecc510e6d1fdc4dbf67d053c7c07f4bdc",
    "txRoot": "0x56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421",
    "receiptsRoot": "0x56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421",
    "logsHash": "0x1dcc4de8dec75d7aab85b567b6ccd41ad312451b948a7413f0a142fd40d49347",
    "logsBloom": "0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000",
    "receipts": [],
    "currentDifficulty": "0x2000020000000",
    "gasUsed": "0x0",
    "currentBaseFee": "0x500"
  }
}

Same thing, but this time providing a non-empty (and non-emptyKeccak) unclehash, which leads to a slightly different result:

text

[user@work evm]$ ./evm t8n --input.alloc=./testdata/14/alloc.json --input.txs=./testdata/14/txs.json --input.env=./testdata/14/env.uncles.json --output.result=stdout --state.fork=London
INFO [03-09|10:44:20.511] Trie dumping started                     root=6f0588..7f4bdc
INFO [03-09|10:44:20.511] Trie dumping complete                    accounts=2 elapsed="184.319µs"
INFO [03-09|10:44:20.512] Wrote file                               file=alloc.json
{
  "result": {
    "stateRoot": "0x6f058887ca01549716789c380ede95aecc510e6d1fdc4dbf67d053c7c07f4bdc",
    "txRoot": "0x56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421",
    "receiptsRoot": "0x56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421",
    "logsHash": "0x1dcc4de8dec75d7aab85b567b6ccd41ad312451b948a7413f0a142fd40d49347",
    "logsBloom": "0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000",
    "receipts": [],
    "currentDifficulty": "0x1ff8020000000",
    "gasUsed": "0x0",
    "currentBaseFee": "0x500"
  }
}

Overview (`cmd/evm/testdata/18/README.md`)

Invalid rlp

This folder contains a sample of invalid RLP, and it's expected
that the t9n handles this properly:

text

$ go run . t9n --input.txs=./testdata/18/invalid.rlp --state.fork=London 
ERROR(11): rlp: value size exceeds available input length

Overview (`cmd/evm/testdata/19/readme.md`)

Difficulty calculation

This test shows how the evm t8n can be used to calculate the (ethash) difficulty, if none is provided by the caller,
this time on GrayGlacier (Eip 5133).

Calculating it (with an empty set of txs) using GrayGlacier rules (and no provided unclehash for the parent block):

text

[user@work evm]$ ./evm t8n --input.alloc=./testdata/19/alloc.json --input.txs=./testdata/19/txs.json --input.env=./testdata/19/env.json --output.result=stdout --state.fork=GrayGlacier
INFO [03-09|10:45:26.777] Trie dumping started                     root=6f0588..7f4bdc
INFO [03-09|10:45:26.777] Trie dumping complete                    accounts=2 elapsed="176.471µs"
INFO [03-09|10:45:26.777] Wrote file                               file=alloc.json
{
  "result": {
    "stateRoot": "0x6f058887ca01549716789c380ede95aecc510e6d1fdc4dbf67d053c7c07f4bdc",
    "txRoot": "0x56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421",
    "receiptsRoot": "0x56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421",
    "logsHash": "0x1dcc4de8dec75d7aab85b567b6ccd41ad312451b948a7413f0a142fd40d49347",
    "logsBloom": "0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000",
    "receipts": [],
    "currentDifficulty": "0x2000000004000",
    "gasUsed": "0x0",
    "currentBaseFee": "0x500"
  }
}

Overview (`cmd/evm/testdata/2/readme.md`)

These files exemplify a selfdestruct to the 0-address.

Overview (`cmd/evm/testdata/20/readme.md`)

Block building

This test shows how b11r can be used to assemble an unsealed block.

console

$ go run . b11r --input.header=testdata/20/header.json --input.txs=testdata/20/txs.rlp --input.ommers=testdata/20/ommers.json --output.block=stdout
{
  "rlp": "0xf90216f90211a0d6d785d33cbecf30f30d07e00e226af58f72efdf385d46bc3e6326c23b11e34ea01dcc4de8dec75d7aab85b567b6ccd41ad312451b948a7413f0a142fd40d4934794e997a23b159e2e2a5ce72333262972374b15425ca0325aea6db48e9d737cddf59034843e99f05bec269453be83c9b9a981a232cc2ea056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421b901000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000082100082c3be83050785808455c5277e99476574682f76312e302e312f6c696e75782f676f312e342e32a05865e417635a26db6d1d39ac70d1abf373e5398b3c6fd506acd038fa1334eedf8897435673d874f7c8c0c0",
  "hash": "0xaba9a3b6a4e96e9ecffcadaa5a2ae0589359455617535cd86589fe1dd26fe899"
}

Overview (`cmd/evm/testdata/21/readme.md`)

Sealed block building

This test shows how b11r can be used to assemble a sealed block.

Ethash

console

$ go run . b11r --input.header=testdata/21/header.json --input.txs=testdata/21/txs.rlp --input.ommers=testdata/21/ommers.json --seal.ethash --seal.ethash.mode=test --output.block=stdout
{
  "rlp": "0xf901fdf901f8a0d6d785d33cbecf30f30d07e00e226af58f72efdf385d46bc3e6326c23b11e34ea01dcc4de8dec75d7aab85b567b6ccd41ad312451b948a7413f0a142fd40d49347940000000000000000000000000000000000000000a0325aea6db48e9d737cddf59034843e99f05bec269453be83c9b9a981a232cc2ea056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421b901000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000082100082c3be83050785808455c5277e80a05865e417635a26db6d1d39ac70d1abf373e5398b3c6fd506acd038fa1334eedf880000000000000000c0c0",
  "hash": "0x801411e9f6609a659825690d13e4f75a3cfe9143952fa2d9573f3b0a5eb9ebbb"
}

Clique

text

/* Detailed source-code truncated for AI context efficiency. */

Overview (`cmd/evm/testdata/22/readme.md`)

Building blocks with ommers

This test shows how b11r can chain together ommer assembles into a canonical block.

text

/* Detailed source-code truncated for AI context efficiency. */

Overview (`cmd/evm/testdata/23/readme.md`)

These files exemplify how to sign a transaction using the pre-EIP155 scheme.

Overview (`cmd/evm/testdata/29/readme.md`)

EIP 4788

This test contains testcases for EIP-4788. The 4788-contract is
located at address 0x000F3df6D732807Ef1319fB7B8bB8522d0Beac02, and this test executes a simple transaction. It also
implicitly invokes the system tx, which sets calls the contract and sets the
storage values

text

$ dir=./testdata/29/ && go run . t8n --state.fork=Cancun  --input.alloc=$dir/alloc.json --input.txs=$dir/txs.json --input.env=$dir/env.json --output.alloc=stdout
INFO [09-27|15:34:53.049] Trie dumping started                     root=19a4f8..01573c
INFO [09-27|15:34:53.049] Trie dumping complete                    accounts=2 elapsed="192.759µs"
INFO [09-27|15:34:53.050] Wrote file                               file=result.json
{
  "alloc": {
    "0x000f3df6d732807ef1319fb7b8bb8522d0beac02": {
      "code": "0x3373fffffffffffffffffffffffffffffffffffffffe14604457602036146024575f5ffd5b620180005f350680545f35146037575f5ffd5b6201800001545f5260205ff35b6201800042064281555f359062018000015500",
      "storage": {
        "0x000000000000000000000000000000000000000000000000000000000000079e": "0x000000000000000000000000000000000000000000000000000000000000079e",
        "0x000000000000000000000000000000000000000000000000000000000001879e": "0x0000beac00beac00beac00beac00beac00beac00beac00beac00beac00beac00"
      },
      "balance": "0x1"
    },
    "0xa94f5374fce5edbc8e2a8697c15331677e6ebf0b": {
      "balance": "0x16345785d871db8",
      "nonce": "0x1"
    }
  }
}

Overview (`cmd/evm/testdata/3/readme.md`)

These files exemplify a transition where a transaction (executed on block 5) requests
the blockhash for block 1.

Overview (`cmd/evm/testdata/31/README.md`)

This test does some EVM execution, and can be used to test the tracers and trace-outputs.
This test should yield three output-traces, in separate files

For example:

text

[user@work evm]$ go  run . t8n --input.alloc ./testdata/31/alloc.json --input.txs ./testdata/31/txs.json --input.env ./testdata/31/env.json --state.fork Cancun --output.basedir /tmp --trace
INFO [12-06|09:53:32.123] Created tracing-file                     path=/tmp/trace-0-0x88f5fbd1524731a81e49f637aa847543268a5aaf2a6b32a69d2c6d978c45dcfb.jsonl
INFO [12-06|09:53:32.124] Created tracing-file                     path=/tmp/trace-1-0x03a7b0a91e61a170d64ea94b8263641ef5a8bbdb10ac69f466083a6789c77fb8.jsonl
INFO [12-06|09:53:32.125] Created tracing-file                     path=/tmp/trace-2-0xd96e0ce6418ee3360e11d3c7b6886f5a9a08f7ef183da72c23bb3b2374530128.jsonl

Overview (`cmd/evm/testdata/32/README.md`)

This test does some EVM execution, and can be used to test callframes emitted by the tracer when they are enabled.

Overview (`cmd/evm/testdata/33/README.md`)

This test sets some EIP-7702 delegations and calls them.

Overview (`cmd/evm/testdata/34/README.md`)

This test verifies that Osaka fork blob gas calculation works correctly when
parentBaseFee is provided. It tests the EIP-7918 reserve price calculation
which requires parent.BaseFee to be properly set.

Regression test for: nil pointer dereference when parent.BaseFee was not
included in the parent header during Osaka fork blob gas calculations.

Overview (`cmd/evm/testdata/4/readme.md`)

These files exemplify a transition where a transaction (executed on block 5) requests
the blockhash for block 4, but where the hash for that block is missing.
It's expected that executing these should cause exit with errorcode 4.

Overview (`cmd/evm/testdata/5/readme.md`)

These files exemplify a transition where there are no transactions, two ommers, at block N-1 (delta 1) and N-2 (delta 2).

Overview (`cmd/evm/testdata/7/readme.md`)

This is a test for HomesteadToDao, checking if the
DAO-transition works

Example:

text

/* Detailed source-code truncated for AI context efficiency. */

Overview (`cmd/evm/testdata/8/readme.md`)

EIP-2930 testing

This test contains testcases for EIP-2930, which uses transactions with access lists.

Prestate

The alloc portion contains one contract (0x000000000000000000000000000000000000aaaa), containing the
following code: 0x5854505854: PC ;SLOAD; POP; PC; SLOAD.

Essentially, this contract does SLOAD(0) and SLOAD(3).

The alloc also contains some funds on 0xa94f5374fce5edbc8e2a8697c15331677e6ebf0b.

Transactions

There are three transactions, each invokes the contract above.

ACL-transaction, which contains some non-used slots
Regular transaction
ACL-transaction, which contains the slots 1 and 3 in 0x000000000000000000000000000000000000aaaa

Execution

Running it yields:

text

dir=./testdata/8 && ./evm t8n --state.fork=Berlin --input.alloc=$dir/alloc.json --input.txs=$dir/txs.json --input.env=$dir/env.json --trace 2>/dev/null && cat trace-* | grep SLOAD
{"pc":1,"op":84,"gas":"0x484be","gasCost":"0x834","memSize":0,"stack":["0x0"],"depth":1,"refund":0,"opName":"SLOAD"}
{"pc":4,"op":84,"gas":"0x47c86","gasCost":"0x834","memSize":0,"stack":["0x3"],"depth":1,"refund":0,"opName":"SLOAD"}
{"pc":1,"op":84,"gas":"0x49cf6","gasCost":"0x834","memSize":0,"stack":["0x0"],"depth":1,"refund":0,"opName":"SLOAD"}
{"pc":4,"op":84,"gas":"0x494be","gasCost":"0x834","memSize":0,"stack":["0x3"],"depth":1,"refund":0,"opName":"SLOAD"}
{"pc":1,"op":84,"gas":"0x484be","gasCost":"0x64","memSize":0,"stack":["0x0"],"depth":1,"refund":0,"opName":"SLOAD"}
{"pc":4,"op":84,"gas":"0x48456","gasCost":"0x64","memSize":0,"stack":["0x3"],"depth":1,"refund":0,"opName":"SLOAD"}

Similarly, we can provide the input transactions via stdin instead of as file:

text

$ dir=./testdata/8 \
  && cat $dir/txs.json | jq "{txs: .}" \
  | ./evm t8n --state.fork=Berlin \
     --input.alloc=$dir/alloc.json \
     --input.txs=stdin \
     --input.env=$dir/env.json \
     --trace  \
     2>/dev/null \
  && cat trace-* | grep SLOAD
{"pc":1,"op":84,"gas":"0x484be","gasCost":"0x834","memSize":0,"stack":["0x0"],"depth":1,"refund":0,"opName":"SLOAD"}
{"pc":4,"op":84,"gas":"0x47c86","gasCost":"0x834","memSize":0,"stack":["0x3"],"depth":1,"refund":0,"opName":"SLOAD"}
{"pc":1,"op":84,"gas":"0x49cf6","gasCost":"0x834","memSize":0,"stack":["0x0"],"depth":1,"refund":0,"opName":"SLOAD"}
{"pc":4,"op":84,"gas":"0x494be","gasCost":"0x834","memSize":0,"stack":["0x3"],"depth":1,"refund":0,"opName":"SLOAD"}
{"pc":1,"op":84,"gas":"0x484be","gasCost":"0x64","memSize":0,"stack":["0x0"],"depth":1,"refund":0,"opName":"SLOAD"}
{"pc":4,"op":84,"gas":"0x48456","gasCost":"0x64","memSize":0,"stack":["0x3"],"depth":1,"refund":0,"opName":"SLOAD"}

If we try to execute it on older rules:

text

$ dir=./testdata/8 && ./evm t8n --state.fork=Istanbul --input.alloc=$dir/alloc.json --input.txs=$dir/txs.json --input.env=$dir/env.json 
ERROR(10): failed signing transactions: ERROR(10): tx 0: failed to sign tx: transaction type not supported

Overview (`cmd/evm/testdata/9/readme.md`)

EIP-1559 testing

This test contains testcases for EIP-1559, which uses a new transaction type and has a new block parameter.

Prestate

The alloc portion contains one contract (0x000000000000000000000000000000000000aaaa), containing the
following code: 0x58585454: PC; PC; SLOAD; SLOAD.

Essentially, this contract does SLOAD(0) and SLOAD(1).

The alloc also contains some funds on 0xa94f5374fce5edbc8e2a8697c15331677e6ebf0b.

Transactions

There are two transactions, each invokes the contract above.

EIP-1559 ACL-transaction, which contains the 0x0 slot for 0xaaaa
Legacy transaction

Execution

Running it yields:

text

$ dir=./testdata/9 && ./evm t8n --state.fork=London --input.alloc=$dir/alloc.json --input.txs=$dir/txs.json --input.env=$dir/env.json --trace 2>/dev/null  && cat trace-*  | grep SLOAD
{"pc":1,"op":84,"gas":"0x484be","gasCost":"0x834","memSize":0,"stack":["0x0"],"depth":1,"refund":0,"opName":"SLOAD"}
{"pc":4,"op":84,"gas":"0x47c86","gasCost":"0x834","memSize":0,"stack":["0x3"],"depth":1,"refund":0,"opName":"SLOAD"}
{"pc":2,"op":84,"gas":"0x48c28","gasCost":"0x834","memSize":0,"stack":["0x0","0x1"],"depth":1,"refund":0,"opName":"SLOAD"}
{"pc":3,"op":84,"gas":"0x483f4","gasCost":"0x64","memSize":0,"stack":["0x0","0x0"],"depth":1,"refund":0,"opName":"SLOAD"}
{"pc":1,"op":84,"gas":"0x49cf6","gasCost":"0x834","memSize":0,"stack":["0x0"],"depth":1,"refund":0,"opName":"SLOAD"}
{"pc":4,"op":84,"gas":"0x494be","gasCost":"0x834","memSize":0,"stack":["0x3"],"depth":1,"refund":0,"opName":"SLOAD"}
{"pc":2,"op":84,"gas":"0x49cf4","gasCost":"0x834","memSize":0,"stack":["0x0","0x1"],"depth":1,"refund":0,"opName":"SLOAD"}
{"pc":3,"op":84,"gas":"0x494c0","gasCost":"0x834","memSize":0,"stack":["0x0","0x0"],"depth":1,"refund":0,"opName":"SLOAD"}
{"pc":1,"op":84,"gas":"0x484be","gasCost":"0x64","memSize":0,"stack":["0x0"],"depth":1,"refund":0,"opName":"SLOAD"}
{"pc":4,"op":84,"gas":"0x48456","gasCost":"0x64","memSize":0,"stack":["0x3"],"depth":1,"refund":0,"opName":"SLOAD"}

We can also get the post-alloc:

text

$ dir=./testdata/9 && ./evm t8n --state.fork=London --input.alloc=$dir/alloc.json --input.txs=$dir/txs.json --input.env=$dir/env.json --output.alloc=stdout 2>/dev/null
{
  "alloc": {
    "0x000000000000000000000000000000000000aaaa": {
      "code": "0x58585454",
      "balance": "0x3",
      "nonce": "0x1"
    },
    "0x2adc25665018aa1fe0e6bc666dac8fc2697ff9ba": {
      "balance": "0x5bb10ddef6e0"
    },
    "0xa94f5374fce5edbc8e2a8697c15331677e6ebf0b": {
      "balance": "0xff745ee8832120",
      "nonce": "0x2"
    }
  }
}

If we try to execute it on older rules:

text

dir=./testdata/9 && ./evm t8n --state.fork=Berlin --input.alloc=$dir/alloc.json --input.txs=$dir/txs.json --input.env=$dir/env.json --output.alloc=stdout
ERROR(10): Failed signing transactions: ERROR(10): Tx 0: failed to sign tx: transaction type not supported

It fails, due to the evm t8n cannot sign them in with the given signer. We can bypass that, however,
by feeding it presigned transactions, located in txs_signed.json.

text

dir=./testdata/9 && ./evm t8n --state.fork=Berlin --input.alloc=$dir/alloc.json --input.txs=$dir/txs_signed.json --input.env=$dir/env.json 
WARN [03-09|11:06:22.065] rejected tx                              index=0 hash=334e09..f8dce5 error="transaction type not supported"
INFO [03-09|11:06:22.066] rejected tx                              index=1 hash=a9c6c6..fa4036 from=0xa94f5374Fce5edBC8E2a8697C15331677e6EbF0B error="nonce too high: address 0xa94f5374Fce5edBC8E2a8697C15331677e6EbF0B, tx: 1 state: 0"
INFO [03-09|11:06:22.066] Trie dumping started                     root=6eebe9..a0fda5
INFO [03-09|11:06:22.066] Trie dumping complete                    accounts=2 elapsed="55.844µs"
INFO [03-09|11:06:22.066] Wrote file                               file=alloc.json
INFO [03-09|11:06:22.066] Wrote file                               file=result.json

Number 0 is not applicable, and therefore number 1 has wrong nonce, and both are rejected.

Overview (`eth/tracers/internal/tracetest/README.md`)

Filling test cases

To fill test cases for the built-in tracers, the makeTest.js script can be used. Given a transaction on a dev/test network, makeTest.js will fetch its prestate and then traces with the given configuration.
In the Geth console do:

terminal

let tx = '0x...'
loadScript('makeTest.js')
makeTest(tx, { tracer: 'callTracer' })

Postmortems 2021 08 22 Split Postmortem (`docs/postmortems/2021-08-22-split-postmortem.md`)

Minority split 2021-08-27 post mortem

This is a post-mortem concerning the minority split that occurred on Ethereum mainnet on block 13107518, at which a minority chain split occurred.

Timeline

2021-08-17: Guido Vranken submitted a bounty report. Investigation started, root cause identified, patch variations discussed.
2021-08-18: Made public announcement over twitter about upcoming security release upcoming Tuesday. Downstream projects were also notified about the upcoming patch-release.
2021-08-24: Released v1.10.8 containing the fix on Tuesday morning (CET). Erigon released v2021.08.04.
2021-08-27: At 12:50:07 UTC, issue exploited. Analysis started roughly 30m later,

Bounty report

2021-08-17 RETURNDATA corruption via datacopy

On 2021-08-17, Guido Vranken submitted a report to [email protected]. This coincided with a geth-meetup in Berlin, so the geth team could fairly quickly analyse the issue.

He submitted a proof of concept which called the dataCopy precompile, where the input slice and output slice were overlapping but shifted. Doing a copy where the src and dest overlaps is not a problem in itself, however, the returnDataslice was also using the same memory as a backing-array.

Technical details

During CALL-variants, geth does not copy the input. This was changed at one point, to avoid a DoS attack reported by Hubert Ritzdorf, to avoid copying data a lot on repeated CALLs -- essentially combating a DoS via malloc. Further, the datacopy precompile also does not copy the data, but just returns the same slice. This is fine so far.

After the execution of dataCopy, we copy the ret into the designated memory area, and this is what causes a problem. Because we're copying a slice of memory over a slice of memory, and this operation modifies (shifts) the data in the source -- the ret. So this means we wind up with corrupted returndata.

text

1. Calling datacopy

  memory: [0, 1, 2, 3, 4]
  in (mem[0:4]) : [0,1,2,3]
  out (mem[1:5]): [1,2,3,4]

2. dataCopy returns

  returndata (==in, mem[0:4]): [0,1,2,3]
 
3. Copy in -> out

  => memory: [0,0,1,2,3]
  => returndata: [0,0,1,2]

Summary

A memory-corruption bug within the EVM can cause a consensus error, where vulnerable nodes obtain a different stateRoot when processing a maliciously crafted transaction. This, in turn, would lead to the chain being split: mainnet splitting in two forks.

Handling

On the evening of 17th, we discussed options on how to handle it. We made a state test to reproduce the issue, and verified that neither openethereum, nethermind nor besu were affected by the same vulnerability, and started a full-sync with a patched version of geth.

It was decided that in this specific instance, it would be possible to make a public announcement and a patch release:

The fix can be made pretty 'generically', e.g. always copying data on input to precompiles.
The flaw is pretty difficult to find, given a generic fix in the call. The attacker needs to figure out that it concerns the precompiles, specifically the datacopy, and that it concerns the RETURNDATA buffer rather than the regular memory, and lastly the special circumstances to trigger it (overlapping but shifted input/output).

Since we had merged the removal of ETH65, if the entire network were to upgrade, then nodes which have not yet implemented ETH66 would be cut off from the network. After further discussions, we decided to:

Announce an upcoming security release on Tuesday (August 24th), via Twitter and official channels, plus reach out to downstream projects.
Temporarily revert the ETH65-removal.
Place the fix into the PR optimizing the jumpdest analysis 23381.
After 4-8 weeks, release details about the vulnerability.

Exploit

At block 13107518, mined at Aug-27-2021 12:50:07 PM +UTC, a minority chain split occurred. The discord user @AlexSSD7 notified the allcoredevs-channel on the Eth R&D discord, on Aug 27 13:09 UTC.

At 14:09 UTC, it was confirmed that the transaction 0x1cb6fb36633d270edefc04d048145b4298e67b8aa82a9e5ec4aa1435dd770ce4 had triggered the bug, leading to a minority-split of the chain. The term 'minority split' means that the majority of miners continued to mine on the correct chain.

At 14:17 UTC, @mhswende tweeted out about the issue [2].

The attack was sent from an account funded from Tornado cash.

It was also found that the same attack had been carried out on the BSC chain at roughly the same time -- at a block mined 12 minutes earlier, at Aug-27-2021 12:38:30 PM +UTC.

The blocks on the 'bad' chain were investigated, and Tim Beiko reached out to those mining operators on the minority chain who could be identified via block extradata.

Lessons learned

Disclosure decision

The geth-team have an official policy regarding vulnerability disclosure.

The primary goal for the Geth team is the health of the Ethereum network as a whole, and the decision whether or not to publish details about a serious vulnerability boils down to minimizing the risk and/or impact of discovery and exploitation.

In this case, it was decided that public pre-announce + patch would likely lead to sufficient update-window for a critical mass of nodes/miners to upgrade in time before it could be exploited. In hindsight, this was a dangerous decision, and it's unlikely that the same decision would be reached were a similar incident to happen again.

Disclosure path

Several subprojects were informed about the upcoming security patch:

Polygon/Matic
MEV
Avalanche
Erigon
BSC
EWF
Quorum
ETC
xDAI

However, some were 'lost', and only notified later

Optimism
Summa
Harmony

Action point: create a low-volume [email protected] email list where dependent projects/operators can receive public announcements.

This has been done. If you wish to receive release- and security announcements, sign up here

Fork monitoring

The fork monitor behaved 'ok' during the incident, but had to be restarted during the evening.

Action point: improve the resiliency of the forkmon, which is currently not performing great when many nodes are connected.

Action point: enable push-based alerts to be sent from the forkmon, to speed up the fork detection.

Appendix

Subprojects

The projects were sent variations of the following text:

text

We have identified a security issue with go-ethereum, and will issue a
new release (v1.10.8) on Tuesday next week.

At this point, we will not disclose details about the issue, but
recommend downstream/dependent projects to be ready to take actions to
upgrade to the latest go-ethereum codebase. More information about the
issue will be disclosed at a later date.

https://twitter.com/go_ethereum/status/1428051458763763721

Patch

text

/* Detailed source-code truncated for AI context efficiency. */

Statetest to test for the issue

text

/* Detailed source-code truncated for AI context efficiency. */

Crypto Secp256k1 Libsecp256k1 Doc Ellswift (`crypto/secp256k1/libsecp256k1/doc/ellswift.md`)

ElligatorSwift for secp256k1 explained

In this document we explain how the ellswift module implementation is related to the
construction in the
"SwiftEC: Shallue–van de Woestijne Indifferentiable Function To Elliptic Curves"
paper by Jorge Chávez-Saab, Francisco Rodríguez-Henríquez, and Mehdi Tibouchi.

1. Introduction
2. The decoding function
- 2.1 Decoding for secp256k1
3. The encoding function
4. Encoding and decoding full (x, y) coordinates
- 4.1 Full (x, y) coordinates for secp256k1

1. Introduction

The ellswift module effectively introduces a new 64-byte public key format, with the property
that (uniformly random) public keys can be encoded as 64-byte arrays which are computationally
indistinguishable from uniform byte arrays. The module provides functions to convert public keys
from and to this format, as well as convenience functions for key generation and ECDH that operate
directly on ellswift-encoded keys.

The encoding consists of the concatenation of two (32-byte big endian) encoded field elements $u$
and $t.$ Together they encode an x-coordinate on the curve $x$, or (see further) a full point $(x, y)$ on
the curve.

Decoding consists of decoding the field elements $u$ and $t$ (values above the field size $p$
are taken modulo $p$), and then evaluating $F_u(t)$, which for every $u$ and $t$ results in a valid
x-coordinate on the curve. The functions $F_u$ will be defined in Section 2.

Encoding a given $x$ coordinate is conceptually done as follows:

Loop:
- Pick a uniformly random field element $u.$
- Compute the set $L = F_u^{-1}(x)$ of $t$ values for which $F_u(t) = x$, which may have up to 8 elements.
- With probability $1 - \dfrac{\#L}{8}$, restart the loop.
- Select a uniformly random $t \in L$ and return $(u, t).$

This is the ElligatorSwift algorithm, here given for just x-coordinates. An extension to full
$(x, y)$ points will be given in Section 4.
The algorithm finds a uniformly random $(u, t)$ among (almost all) those
for which $F_u(t) = x.$ Section 3.2 in the paper proves that the number of such encodings for
almost all x-coordinates on the curve (all but at most 39) is close to two times the field size
(specifically, it lies in the range $2q \pm (22\sqrt{q} + O(1))$, where $q$ is the size of the field).

2. The decoding function

First some definitions:

$\mathbb{F}$ is the finite field of size $q$, of characteristic 5 or more, and $q \equiv 1 \mod 3.$
- For secp256k1, $q = 2^{256} - 2^{32} - 977$, which satisfies that requirement.
Let $E$ be the elliptic curve of points $(x, y) \in \mathbb{F}^2$ for which $y^2 = x^3 + ax + b$, with $a$ and $b$
public constants, for which $\Delta_E = -16(4a^3 + 27b^2)$ is a square, and at least one of $(-b \pm \sqrt{-3 \Delta_E} / 36)/2$ is a square.
This implies that the order of $E$ is either odd, or a multiple of 4.
If $a=0$, this condition is always fulfilled.
- For secp256k1, $a=0$ and $b=7.$
Let the function $g(x) = x^3 + ax + b$, so the $E$ curve equation is also $y^2 = g(x).$
Let the function $h(x) = 3x^3 + 4a.$
Define $V$ as the set of solutions $(x_1, x_2, x_3, z)$ to $z^2 = g(x_1)g(x_2)g(x_3).$
Define $S_u$ as the set of solutions $(X, Y)$ to $X^2 + h(u)Y^2 = -g(u)$ and $Y \neq 0.$
$P_u$ is a function from $\mathbb{F}$ to $S_u$ that will be defined below.
$\psi_u$ is a function from $S_u$ to $V$ that will be defined below.

Note: In the paper:

$F_u$ corresponds to $F_{0,u}$ there.
$P_u(t)$ is called $P$ there.
All $S_u$ sets together correspond to $S$ there.
All $\psi_u$ functions together (operating on elements of $S$) correspond to $\psi$ there.

Note that for $V$, the left hand side of the equation $z^2$ is square, and thus the right
hand must also be square. As multiplying non-squares results in a square in $\mathbb{F}$,
out of the three right-hand side factors an even number must be non-squares.
This implies that exactly 1 or exactly 3 out of
$\{g(x_1), g(x_2), g(x_3)\}$ must be square, and thus that for any $(x_1,x_2,x_3,z) \in V$,
at least one of $\{x_1, x_2, x_3\}$ must be a valid x-coordinate on $E.$ There is one exception
to this, namely when $z=0$, but even then one of the three values is a valid x-coordinate.

Define the decoding function $F_u(t)$ as:

Let $(x_1, x_2, x_3, z) = \psi_u(P_u(t)).$
Return the first element $x$ of $(x_3, x_2, x_1)$ which is a valid x-coordinate on $E$ (i.e., $g(x)$ is square).

$P_u(t) = (X(u, t), Y(u, t))$, where:

$$
\begin{array}{lcl}
X(u, t) & = & \left\{\begin{array}{ll}
\dfrac{g(u) - t^2}{2t} & a = 0 \
\dfrac{g(u) + h(u)(Y_0(u) - X_0(u)t)^2}{X_0(u)(1 + h(u)t^2)} & a \neq 0
\end{array}\right. \
Y(u, t) & = & \left\{\begin{array}{ll}
\dfrac{X(u, t) + t}{u \sqrt{-3}} = \dfrac{g(u) + t^2}{2tu\sqrt{-3}} & a = 0 \
Y_0(u) + t(X(u, t) - X_0(u)) & a \neq 0
\end{array}\right.
\end{array}
$$

$P_u(t)$ is defined:

For $a=0$, unless:
- $u = 0$ or $t = 0$ (division by zero)
- $g(u) = -t^2$ (would give $Y=0$).
For $a \neq 0$, unless:
- $X_0(u) = 0$ or $h(u)t^2 = -1$ (division by zero)
- $Y_0(u) (1 - h(u)t^2) = 2X_0(u)t$ (would give $Y=0$).

The functions $X_0(u)$ and $Y_0(u)$ are defined in Appendix A of the paper, and depend on various properties of $E.$

The function $\psi_u$ is the same for all curves: $\psi_u(X, Y) = (x_1, x_2, x_3, z)$, where:

$$
\begin{array}{lcl}
x_1 & = & \dfrac{X}{2Y} - \dfrac{u}{2} && \
x_2 & = & -\dfrac{X}{2Y} - \dfrac{u}{2} && \
x_3 & = & u + 4Y^2 && \
z & = & \dfrac{g(x_3)}{2Y}(u^2 + ux_1 + x_1^2 + a) = \dfrac{-g(u)g(x_3)}{8Y^3}
\end{array}
$$

2.1 Decoding for `secp256k1`

Put together and specialized for $a=0$ curves, decoding $(u, t)$ to an x-coordinate is:

Define $F_u(t)$ as:

Let $X = \dfrac{u^3 + b - t^2}{2t}.$
Let $Y = \dfrac{X + t}{u\sqrt{-3}}.$
Return the first $x$ in $(u + 4Y^2, \dfrac{-X}{2Y} - \dfrac{u}{2}, \dfrac{X}{2Y} - \dfrac{u}{2})$ for which $g(x)$ is square.

To make sure that every input decodes to a valid x-coordinate, we remap the inputs in case
$P_u$ is not defined (when $u=0$, $t=0$, or $g(u) = -t^2$):

Define $F_u(t)$ as:

Let $u'=u$ if $u \neq 0$; $1$ otherwise (guaranteeing $u' \neq 0$).
Let $t'=t$ if $t \neq 0$; $1$ otherwise (guaranteeing $t' \neq 0$).
Let $t''=t'$ if $g(u') \neq -t'^2$; $2t'$ otherwise (guaranteeing $t'' \neq 0$ and $g(u') \neq -t''^2$).
Let $X = \dfrac{u'^3 + b - t''^2}{2t''}.$
Let $Y = \dfrac{X + t''}{u'\sqrt{-3}}.$
Return the first $x$ in $(u' + 4Y^2, \dfrac{-X}{2Y} - \dfrac{u'}{2}, \dfrac{X}{2Y} - \dfrac{u'}{2})$ for which $x^3 + b$ is square.

The choices here are not strictly necessary. Just returning a fixed constant in any of the undefined cases would suffice,
but the approach here is simple enough and gives fairly uniform output even in these cases.

Note: in the paper these conditions result in $\infty$ as output, due to the use of projective coordinates there.
We wish to avoid the need for callers to deal with this special case.

This is implemented in secp256k1_ellswift_xswiftec_frac_var (which decodes to an x-coordinate represented as a fraction), and
in secp256k1_ellswift_xswiftec_var (which outputs the actual x-coordinate).

3. The encoding function

To implement $F_u^{-1}(x)$, the function to find the set of inverses $t$ for which $F_u(t) = x$, we have to reverse the process:

Find all the $(X, Y) \in S_u$ that could have given rise to $x$, through the $x_1$, $x_2$, or $x_3$ formulas in $\psi_u.$
Map those $(X, Y)$ solutions to $t$ values using $P_u^{-1}(X, Y).$
For each of the found $t$ values, verify that $F_u(t) = x.$
Return the remaining $t$ values.

The function $P_u^{-1}$, which finds $t$ given $(X, Y) \in S_u$, is significantly simpler than $P_u:$

$$
P_u^{-1}(X, Y) = \left\{\begin{array}{ll}
Yu\sqrt{-3} - X & a = 0 \
\dfrac{Y-Y_0(u)}{X-X_0(u)} & a \neq 0 \land X \neq X_0(u) \
\dfrac{-X_0(u)}{h(u)Y_0(u)} & a \neq 0 \land X = X_0(u) \land Y = Y_0(u)
\end{array}\right.
$$

The third step above, verifying that $F_u(t) = x$, is necessary because for the $(X, Y)$ values found through the $x_1$ and $x_2$ expressions,
it is possible that decoding through $\psi_u(X, Y)$ yields a valid $x_3$ on the curve, which would take precedence over the
$x_1$ or $x_2$ decoding. These $(X, Y)$ solutions must be rejected.

Since we know that exactly one or exactly three out of $\{x_1, x_2, x_3\}$ are valid x-coordinates for any $t$,
the case where either $x_1$ or $x_2$ is valid and in addition also $x_3$ is valid must mean that all three are valid.
This means that instead of checking whether $x_3$ is on the curve, it is also possible to check whether the other one out of
$x_1$ and $x_2$ is on the curve. This is significantly simpler, as it turns out.

Observe that $\psi_u$ guarantees that $x_1 + x_2 = -u.$ So given either $x = x_1$ or $x = x_2$, the other one of the two can be computed as
$-u - x.$ Thus, when encoding $x$ through the $x_1$ or $x_2$ expressions, one can simply check whether $g(-u-x)$ is a square,
and if so, not include the corresponding $t$ values in the returned set. As this does not need $X$, $Y$, or $t$, this condition can be determined
before those values are computed.

It is not possible that an encoding found through the $x_1$ expression decodes to a different valid x-coordinate using $x_2$ (which would
take precedence), for the same reason: if both $x_1$ and $x_2$ decodings were valid, $x_3$ would be valid as well, and thus take
precedence over both. Because of this, the $g(-u-x)$ being square test for $x_1$ and $x_2$ is the only test necessary to guarantee the found $t$
values round-trip back to the input $x$ correctly. This is the reason for choosing the $(x_3, x_2, x_1)$ precedence order in the decoder;
any order which does not place $x_3$ first requires more complicated round-trip checks in the encoder.

3.1 Switching to v, w coordinates

Before working out the formulas for all this, we switch to different variables for $S_u.$ Let $v = (X/Y - u)/2$, and
$w = 2Y.$ Or in the other direction, $X = w(u/2 + v)$ and $Y = w/2:$

$S_u'$ becomes the set of $(v, w)$ for which $w^2 (u^2 + uv + v^2 + a) = -g(u)$ and $w \neq 0.$
For $a=0$ curves, $P_u^{-1}$ can be stated for $(v,w)$ as $P_u^{'-1}(v, w) = w\left(\frac{\sqrt{-3}-1}{2}u - v\right).$
$\psi_u$ can be stated for $(v, w)$ as $\psi_u'(v, w) = (x_1, x_2, x_3, z)$, where

$$
\begin{array}{lcl}
x_1 & = & v \
x_2 & = & -u - v \
x_3 & = & u + w^2 \
z & = & \dfrac{g(x_3)}{w}(u^2 + uv + v^2 + a) = \dfrac{-g(u)g(x_3)}{w^3}
\end{array}
$$

We can now write the expressions for finding $(v, w)$ given $x$ explicitly, by solving each of the $\{x_1, x_2, x_3\}$
expressions for $v$ or $w$, and using the $S_u'$ equation to find the other variable:

Assuming $x = x_1$, we find $v = x$ and $w = \pm\sqrt{-g(u)/(u^2 + uv + v^2 + a)}$ (two solutions).
Assuming $x = x_2$, we find $v = -u-x$ and $w = \pm\sqrt{-g(u)/(u^2 + uv + v^2 + a)}$ (two solutions).
Assuming $x = x_3$, we find $w = \pm\sqrt{x-u}$ and $v = -u/2 \pm \sqrt{-w^2(4g(u) + w^2h(u))}/(2w^2)$ (four solutions).

3.2 Avoiding computing all inverses

The ElligatorSwift algorithm as stated in Section 1 requires the computation of $L = F_u^{-1}(x)$ (the
set of all $t$ such that $(u, t)$ decode to $x$) in full. This is unnecessary.

Observe that the procedure of restarting with probability $(1 - \frac{\#L}{8})$ and otherwise returning a
uniformly random element from $L$ is actually equivalent to always padding $L$ with $\bot$ values up to length 8,
picking a uniformly random element from that, restarting whenever $\bot$ is picked:

Define ElligatorSwift(x) as:

Loop:
- Pick a uniformly random field element $u.$
- Compute the set $L = F_u^{-1}(x).$
- Let $T$ be the 8-element vector consisting of the elements of $L$, plus $8 - \#L$ times $\{\bot\}.$
- Select a uniformly random $t \in T.$
- If $t \neq \bot$, return $(u, t)$; restart loop otherwise.

Now notice that the order of elements in $T$ does not matter, as all we do is pick a uniformly
random element in it, so we do not need to have all $\bot$ values at the end.
As we have 8 distinct formulas for finding $(v, w)$ (taking the variants due to $\pm$ into account),
we can associate every index in $T$ with exactly one of those formulas, making sure that:

Formulas that yield no solutions (due to division by zero or non-existing square roots) or invalid solutions are made to return $\bot.$
For the $x_1$ and $x_2$ cases, if $g(-u-x)$ is a square, $\bot$ is returned instead (the round-trip check).
In case multiple formulas would return the same non- $\bot$ result, all but one of those must be turned into $\bot$ to avoid biasing those.

The last condition above only occurs with negligible probability for cryptographically-sized curves, but is interesting
to take into account as it allows exhaustive testing in small groups. See Section 3.4
for an analysis of all the negligible cases.

If we define $T = (G_{0,u}(x), G_{1,u}(x), \ldots, G_{7,u}(x))$, with each $G_{i,u}$ matching one of the formulas,
the loop can be simplified to only compute one of the inverses instead of all of them:

Define ElligatorSwift(x) as:

Loop:
- Pick a uniformly random field element $u.$
- Pick a uniformly random integer $c$ in $[0,8).$
- Let $t = G_{c,u}(x).$
- If $t \neq \bot$, return $(u, t)$; restart loop otherwise.

This is implemented in secp256k1_ellswift_xelligatorswift_var.

3.3 Finding the inverse

To implement $G_{c,u}$, we map $c=0$ to the $x_1$ formula, $c=1$ to the $x_2$ formula, and $c=2$ and $c=3$ to the $x_3$ formula.
Those are then repeated as $c=4$ through $c=7$ for the other sign of $w$ (noting that in each formula, $w$ is a square root of some expression).
Ignoring the negligible cases, we get:

Define $G_{c,u}(x)$ as:

If $c \in \{0, 1, 4, 5\}$ (for $x_1$ and $x_2$ formulas):
- If $g(-u-x)$ is square, return $\bot$ (as $x_3$ would be valid and take precedence).
- If $c \in \{0, 4\}$ (the $x_1$ formula) let $v = x$, otherwise let $v = -u-x$ (the $x_2$ formula)
- Let $s = -g(u)/(u^2 + uv + v^2 + a)$ (using $s = w^2$ in what follows).
Otherwise, when $c \in \{2, 3, 6, 7\}$ (for $x_3$ formulas):
- Let $s = x-u.$
- Let $r = \sqrt{-s(4g(u) + sh(u))}.$
- Let $v = (r/s - u)/2$ if $c \in \{3, 7\}$; $(-r/s - u)/2$ otherwise.
Let $w = \sqrt{s}.$
Depending on $c:$
- If $c \in \{0, 1, 2, 3\}:$ return $P_u^{'-1}(v, w).$
- If $c \in \{4, 5, 6, 7\}:$ return $P_u^{'-1}(v, -w).$

Whenever a square root of a non-square is taken, $\bot$ is returned; for both square roots this happens with roughly
50% on random inputs. Similarly, when a division by 0 would occur, $\bot$ is returned as well; this will only happen
with negligible probability. A division by 0 in the first branch in fact cannot occur at all, because $u^2 + uv + v^2 + a = 0$
implies $g(-u-x) = g(x)$ which would mean the $g(-u-x)$ is square condition has triggered
and $\bot$ would have been returned already.

Note: In the paper, the $case$ variable corresponds roughly to the $c$ above, but only takes on 4 possible values (1 to 4).
The conditional negation of $w$ at the end is done randomly, which is equivalent, but makes testing harder. We choose to
have the $G_{c,u}$ be deterministic, and capture all choices in $c.$

Now observe that the $c \in \{1, 5\}$ and $c \in \{3, 7\}$ conditions effectively perform the same $v \rightarrow -u-v$
transformation. Furthermore, that transformation has no effect on $s$ in the first branch
as $u^2 + ux + x^2 + a = u^2 + u(-u-x) + (-u-x)^2 + a.$ Thus we can extract it out and move it down:

Define $G_{c,u}(x)$ as:

If $c \in \{0, 1, 4, 5\}:$
- If $g(-u-x)$ is square, return $\bot.$
- Let $s = -g(u)/(u^2 + ux + x^2 + a).$
- Let $v = x.$
Otherwise, when $c \in \{2, 3, 6, 7\}:$
- Let $s = x-u.$
- Let $r = \sqrt{-s(4g(u) + sh(u))}.$
- Let $v = (r/s - u)/2.$
Let $w = \sqrt{s}.$
Depending on $c:$
- If $c \in \{0, 2\}:$ return $P_u^{'-1}(v, w).$
- If $c \in \{1, 3\}:$ return $P_u^{'-1}(-u-v, w).$
- If $c \in \{4, 6\}:$ return $P_u^{'-1}(v, -w).$
- If $c \in \{5, 7\}:$ return $P_u^{'-1}(-u-v, -w).$

This shows there will always be exactly 0, 4, or 8 $t$ values for a given $(u, x)$ input.
There can be 0, 1, or 2 $(v, w)$ pairs before invoking $P_u^{'-1}$, and each results in 4 distinct $t$ values.

3.4 Dealing with special cases

As mentioned before there are a few cases to deal with which only happen in a negligibly small subset of inputs.
For cryptographically sized fields, if only random inputs are going to be considered, it is unnecessary to deal with these. Still, for completeness
we analyse them here. They generally fall into two categories: cases in which the encoder would produce $t$ values that
do not decode back to $x$ (or at least cannot guarantee that they do), and cases in which the encoder might produce the same
$t$ value for multiple $c$ inputs (thereby biasing that encoding):

In the branch for $x_1$ and $x_2$ (where $c \in \{0, 1, 4, 5\}$):
- When $g(u) = 0$, we would have $s=w=Y=0$, which is not on $S_u.$ This is only possible on even-ordered curves.
  Excluding this also removes the one condition under which the simplified check for $x_3$ on the curve
  fails (namely when $g(x_1)=g(x_2)=0$ but $g(x_3)$ is not square).
  This does exclude some valid encodings: when both $g(u)=0$ and $u^2+ux+x^2+a=0$ (also implying $g(x)=0$),
  the $S_u'$ equation degenerates to $0 = 0$, and many valid $t$ values may exist. Yet, these cannot be targeted uniformly by the
  encoder anyway as there will generally be more than 8.
- When $g(x) = 0$, the same $t$ would be produced as in the $x_3$ branch (where $c \in \{2, 3, 6, 7\}$) which we give precedence
  as it can deal with $g(u)=0$.
  This is again only possible on even-ordered curves.
In the branch for $x_3$ (where $c \in \{2, 3, 6, 7\}$):
- When $s=0$, a division by zero would occur.
- When $v = -u-v$ and $c \in \{3, 7\}$, the same $t$ would be returned as in the $c \in \{2, 6\}$ cases.
  It is equivalent to checking whether $r=0$.
  This cannot occur in the $x_1$ or $x_2$ branches, as it would trigger the $g(-u-x)$ is square condition.
  A similar concern for $w = -w$ does not exist, as $w=0$ is already impossible in both branches: in the first
  it requires $g(u)=0$ which is already outlawed on even-ordered curves and impossible on others; in the second it would trigger division by zero.
Curve-specific special cases also exist that need to be rejected, because they result in $(u,t)$ which is invalid to the decoder, or because of division by zero in the encoder:
- For $a=0$ curves, when $u=0$ or when $t=0$. The latter can only be reached by the encoder when $g(u)=0$, which requires an even-ordered curve.
- For $a \neq 0$ curves, when $X_0(u)=0$, when $h(u)t^2 = -1$, or when $w(u + 2v) = 2X_0(u)$ while also either $w \neq 2Y_0(u)$ or $h(u)=0$.

Define a version of $G_{c,u}(x)$ which deals with all these cases:

If $a=0$ and $u=0$, return $\bot.$
If $a \neq 0$ and $X_0(u)=0$, return $\bot.$
If $c \in \{0, 1, 4, 5\}:$
- If $g(u) = 0$ or $g(x) = 0$, return $\bot$ (even curves only).
- If $g(-u-x)$ is square, return $\bot.$
- Let $s = -g(u)/(u^2 + ux + x^2 + a)$ (cannot cause division by zero).
- Let $v = x.$
Otherwise, when $c \in \{2, 3, 6, 7\}:$
- Let $s = x-u.$
- Let $r = \sqrt{-s(4g(u) + sh(u))}$; return $\bot$ if not square.
- If $c \in \{3, 7\}$ and $r=0$, return $\bot.$
- If $s = 0$, return $\bot.$
- Let $v = (r/s - u)/2.$
Let $w = \sqrt{s}$; return $\bot$ if not square.
If $a \neq 0$ and $w(u+2v) = 2X_0(u)$ and either $w \neq 2Y_0(u)$ or $h(u) = 0$, return $\bot.$
Depending on $c:$
- If $c \in \{0, 2\}$, let $t = P_u^{'-1}(v, w).$
- If $c \in \{1, 3\}$, let $t = P_u^{'-1}(-u-v, w).$
- If $c \in \{4, 6\}$, let $t = P_u^{'-1}(v, -w).$
- If $c \in \{5, 7\}$, let $t = P_u^{'-1}(-u-v, -w).$
If $a=0$ and $t=0$, return $\bot$ (even curves only).
If $a \neq 0$ and $h(u)t^2 = -1$, return $\bot.$
Return $t.$

Given any $u$, using this algorithm over all $x$ and $c$ values, every $t$ value will be reached exactly once,
for an $x$ for which $F_u(t) = x$ holds, except for these cases that will not be reached:

All cases where $P_u(t)$ is not defined:
- For $a=0$ curves, when $u=0$, $t=0$, or $g(u) = -t^2.$
- For $a \neq 0$ curves, when $h(u)t^2 = -1$, $X_0(u) = 0$, or $Y_0(u) (1 - h(u) t^2) = 2X_0(u)t.$
When $g(u)=0$, the potentially many $t$ values that decode to an $x$ satisfying $g(x)=0$ using the $x_2$ formula. These were excluded by the $g(u)=0$ condition in the $c \in \{0, 1, 4, 5\}$ branch.

These cases form a negligible subset of all $(u, t)$ for cryptographically sized curves.

3.5 Encoding for `secp256k1`

Specialized for odd-ordered $a=0$ curves:

Define $G_{c,u}(x)$ as:

If $u=0$, return $\bot.$
If $c \in \{0, 1, 4, 5\}:$
- If $(-u-x)^3 + b$ is square, return $\bot$
- Let $s = -(u^3 + b)/(u^2 + ux + x^2)$ (cannot cause division by 0).
- Let $v = x.$
Otherwise, when $c \in \{2, 3, 6, 7\}:$
- Let $s = x-u.$
- Let $r = \sqrt{-s(4(u^3 + b) + 3su^2)}$; return $\bot$ if not square.
- If $c \in \{3, 7\}$ and $r=0$, return $\bot.$
- If $s = 0$, return $\bot.$
- Let $v = (r/s - u)/2.$
Let $w = \sqrt{s}$; return $\bot$ if not square.
Depending on $c:$
- If $c \in \{0, 2\}:$ return $w(\frac{\sqrt{-3}-1}{2}u - v).$
- If $c \in \{1, 3\}:$ return $w(\frac{\sqrt{-3}+1}{2}u + v).$
- If $c \in \{4, 6\}:$ return $w(\frac{-\sqrt{-3}+1}{2}u + v).$
- If $c \in \{5, 7\}:$ return $w(\frac{-\sqrt{-3}-1}{2}u - v).$

This is implemented in secp256k1_ellswift_xswiftec_inv_var.

And the x-only ElligatorSwift encoding algorithm is still:

Define ElligatorSwift(x) as:

Loop:
- Pick a uniformly random field element $u.$
- Pick a uniformly random integer $c$ in $[0,8).$
- Let $t = G_{c,u}(x).$
- If $t \neq \bot$, return $(u, t)$; restart loop otherwise.

Note that this logic does not take the remapped $u=0$, $t=0$, and $g(u) = -t^2$ cases into account; it just avoids them.
While it is not impossible to make the encoder target them, this would increase the maximum number of $t$ values for a given $(u, x)$
combination beyond 8, and thereby slow down the ElligatorSwift loop proportionally, for a negligible gain in uniformity.

4. Encoding and decoding full (x, y) coordinates

So far we have only addressed encoding and decoding x-coordinates, but in some cases an encoding
for full points with $(x, y)$ coordinates is desirable. It is possible to encode this information
in $t$ as well.

Note that for any $(X, Y) \in S_u$, $(\pm X, \pm Y)$ are all on $S_u.$ Moreover, all of these are
mapped to the same x-coordinate. Negating $X$ or negating $Y$ just results in $x_1$ and $x_2$
being swapped, and does not affect $x_3.$ This will not change the outcome x-coordinate as the order
of $x_1$ and $x_2$ only matters if both were to be valid, and in that case $x_3$ would be used instead.

Still, these four $(X, Y)$ combinations all correspond to distinct $t$ values, so we can encode
the sign of the y-coordinate in the sign of $X$ or the sign of $Y.$ They correspond to the
four distinct $P_u^{'-1}$ calls in the definition of $G_{u,c}.$

Note: In the paper, the sign of the y coordinate is encoded in a separately-coded bit.

To encode the sign of $y$ in the sign of $Y:$

Define Decode(u, t) for full $(x, y)$ as:

Let $(X, Y) = P_u(t).$
Let $x$ be the first value in $(u + 4Y^2, \frac{-X}{2Y} - \frac{u}{2}, \frac{X}{2Y} - \frac{u}{2})$ for which $g(x)$ is square.
Let $y = \sqrt{g(x)}.$
If $sign(y) = sign(Y)$, return $(x, y)$; otherwise return $(x, -y).$

And encoding would be done using a $G_{c,u}(x, y)$ function defined as:

Define $G_{c,u}(x, y)$ as:

If $c \in \{0, 1\}:$
- If $g(u) = 0$ or $g(x) = 0$, return $\bot$ (even curves only).
- If $g(-u-x)$ is square, return $\bot.$
- Let $s = -g(u)/(u^2 + ux + x^2 + a)$ (cannot cause division by zero).
- Let $v = x.$
Otherwise, when $c \in \{2, 3\}:$
- Let $s = x-u.$
- Let $r = \sqrt{-s(4g(u) + sh(u))}$; return $\bot$ if not square.
- If $c = 3$ and $r = 0$, return $\bot.$
- Let $v = (r/s - u)/2.$
Let $w = \sqrt{s}$; return $\bot$ if not square.
Let $w' = w$ if $sign(w/2) = sign(y)$; $-w$ otherwise.
Depending on $c:$
- If $c \in \{0, 2\}:$ return $P_u^{'-1}(v, w').$
- If $c \in \{1, 3\}:$ return $P_u^{'-1}(-u-v, w').$

Note that $c$ now only ranges $[0,4)$, as the sign of $w'$ is decided based on that of $y$, rather than on $c.$
This change makes some valid encodings unreachable: when $y = 0$ and $sign(Y) \neq sign(0)$.

In the above logic, $sign$ can be implemented in several ways, such as parity of the integer representation
of the input field element (for prime-sized fields) or the quadratic residuosity (for fields where
$-1$ is not square). The choice does not matter, as long as it only takes on two possible values, and for $x \neq 0$ it holds that $sign(x) \neq sign(-x)$.

4.1 Full (x, y) coordinates for `secp256k1`

For $a=0$ curves, there is another option. Note that for those,
the $P_u(t)$ function translates negations of $t$ to negations of (both) $X$ and $Y.$ Thus, we can use $sign(t)$ to
encode the y-coordinate directly. Combined with the earlier remapping to guarantee all inputs land on the curve, we get
as decoder:

Define Decode(u, t) as:

Let $u'=u$ if $u \neq 0$; $1$ otherwise.
Let $t'=t$ if $t \neq 0$; $1$ otherwise.
Let $t''=t'$ if $u'^3 + b + t'^2 \neq 0$; $2t'$ otherwise.
Let $X = \dfrac{u'^3 + b - t''^2}{2t''}.$
Let $Y = \dfrac{X + t''}{u'\sqrt{-3}}.$
Let $x$ be the first element of $(u' + 4Y^2, \frac{-X}{2Y} - \frac{u'}{2}, \frac{X}{2Y} - \frac{u'}{2})$ for which $g(x)$ is square.
Let $y = \sqrt{g(x)}.$
Return $(x, y)$ if $sign(y) = sign(t)$; $(x, -y)$ otherwise.

This is implemented in secp256k1_ellswift_swiftec_var. The used $sign(x)$ function is the parity of $x$ when represented as in integer in $[0,q).$

The corresponding encoder would invoke the x-only one, but negating the output $t$ if $sign(t) \neq sign(y).$

This is implemented in secp256k1_ellswift_elligatorswift_var.

Note that this is only intended for encoding points where both the x-coordinate and y-coordinate are unpredictable. When encoding x-only points
where the y-coordinate is implicitly even (or implicitly square, or implicitly in $[0,q/2]$), the encoder in
Section 3.5 must be used, or a bias is reintroduced that undoes all the benefit of using ElligatorSwift
in the first place.

Crypto Secp256k1 Libsecp256k1 Doc Musig (`crypto/secp256k1/libsecp256k1/doc/musig.md`)

Notes on the musig module API

The following sections contain additional notes on the API of the musig module (include/secp256k1_musig.h).
A usage example can be found in examples/musig.c.

API misuse

The musig API is designed with a focus on misuse resistance.
However, due to the interactive nature of the MuSig protocol, there are additional failure modes that are not present in regular (single-party) Schnorr signature creation.
While the results can be catastrophic (e.g. leaking of the secret key), it is unfortunately not possible for the musig implementation to prevent all such failure modes.

Therefore, users of the musig module must take great care to make sure of the following:

A unique nonce per signing session is generated in secp256k1_musig_nonce_gen.
See the corresponding comment in include/secp256k1_musig.h for how to ensure that.
The secp256k1_musig_secnonce structure is never copied or serialized.
See also the comment on secp256k1_musig_secnonce in include/secp256k1_musig.h.
Opaque data structures are never written to or read from directly.
Instead, only the provided accessor functions are used.

Key Aggregation and (Taproot) Tweaking

Given a set of public keys, the aggregate public key is computed with secp256k1_musig_pubkey_agg.
A plain tweak can be added to the resulting public key with secp256k1_ec_pubkey_tweak_add by setting the tweak32 argument to the hash defined in BIP 32. Similarly, a Taproot tweak can be added with secp256k1_xonly_pubkey_tweak_add by setting the tweak32 argument to the TapTweak hash defined in BIP 341.
Both types of tweaking can be combined and invoked multiple times if the specific application requires it.

Signing

This is covered by examples/musig.c.
Essentially, the protocol proceeds in the following steps:

Generate a keypair with secp256k1_keypair_create and obtain the public key with secp256k1_keypair_pub.
Call secp256k1_musig_pubkey_agg with the pubkeys of all participants.
Optionally add a (Taproot) tweak with secp256k1_musig_pubkey_xonly_tweak_add and a plain tweak with secp256k1_musig_pubkey_ec_tweak_add.
Generate a pair of secret and public nonce with secp256k1_musig_nonce_gen and send the public nonce to the other signers.
Someone (not necessarily the signer) aggregates the public nonces with secp256k1_musig_nonce_agg and sends it to the signers.
Process the aggregate nonce with secp256k1_musig_nonce_process.
Create a partial signature with secp256k1_musig_partial_sign.
Verify the partial signatures (optional in some scenarios) with secp256k1_musig_partial_sig_verify.
Someone (not necessarily the signer) obtains all partial signatures and aggregates them into the final Schnorr signature using secp256k1_musig_partial_sig_agg.

The aggregate signature can be verified with secp256k1_schnorrsig_verify.

Steps 1 through 5 above can occur before or after the signers are aware of the message to be signed.
Whenever possible, it is recommended to generate the nonces only after the message is known.
This provides enhanced defense-in-depth measures, protecting against potential API misuse in certain scenarios.
However, it does require two rounds of communication during the signing process.
The alternative, generating the nonces in a pre-processing step before the message is known, eliminates these additional protective measures but allows for non-interactive signing.
Similarly, the API supports an alternative protocol flow where generating the aggregate key (steps 1 to 3) is allowed to happen after exchanging nonces (steps 4 to 5).

Verification

A participant who wants to verify the partial signatures, but does not sign itself may do so using the above instructions except that the verifier skips steps 1, 4 and 7.

Crypto Secp256k1 Libsecp256k1 Doc Release Process (`crypto/secp256k1/libsecp256k1/doc/release-process.md`)

Release process

This document outlines the process for releasing versions of the form $MAJOR.$MINOR.$PATCH.

We distinguish between two types of releases: regular and maintenance releases.
Regular releases are releases of a new major or minor version as well as patches of the most recent release.
Maintenance releases, on the other hand, are required for patches of older releases.

You should coordinate with the other maintainers on the release date, if possible.
This date will be part of the release entry in CHANGELOG.md and it should match the dates of the remaining steps in the release process (including the date of the tag and the GitHub release).
It is best if the maintainers are present during the release, so they can help ensure that the process is followed correctly and, in the case of a regular release, they are aware that they should not modify the master branch between merging the PR in step 1 and the PR in step 3.

This process also assumes that there will be no minor releases for old major releases.

We aim to cut a regular release every 3-4 months, approximately twice as frequent as major Bitcoin Core releases. Every second release should be published one month before the feature freeze of the next major Bitcoin Core release, allowing sufficient time to update the library in Core.

Sanity checks

Perform these checks when reviewing the release PR (see below):

Ensure make distcheck doesn't fail.

shell

./autogen.sh && ./configure --enable-dev-mode && make distcheck

Check installation with autotools:

shell

dir=$(mktemp -d)
./autogen.sh && ./configure --prefix=$dir && make clean && make install && ls -RlAh $dir
gcc -o ecdsa examples/ecdsa.c $(PKG_CONFIG_PATH=$dir/lib/pkgconfig pkg-config --cflags --libs libsecp256k1) -Wl,-rpath,"$dir/lib" && ./ecdsa

Check installation with CMake:

shell

dir=$(mktemp -d)
build=$(mktemp -d)
cmake -B $build -DCMAKE_INSTALL_PREFIX=$dir && cmake --build $build && cmake --install $build && ls -RlAh $dir
gcc -o ecdsa examples/ecdsa.c -I $dir/include -L $dir/lib*/ -l secp256k1 -Wl,-rpath,"$dir/lib",-rpath,"$dir/lib64" && ./ecdsa

Use the check-abi.sh tool to verify that there are no unexpected ABI incompatibilities and that the version number and the release notes accurately reflect all potential ABI changes. To run this tool, the abi-dumper and abi-compliance-checker packages are required.
shell
```
tools/check-abi.sh
```

Regular release

Open a PR to the master branch with a commit (using message "release: prepare for $MAJOR.$MINOR.$PATCH", for example) that
- finalizes the release notes in CHANGELOG.md by
  - adding a section for the release (make sure that the version number is a link to a diff between the previous and new version),
  - removing the [Unreleased] section header,
  - ensuring that the release notes are not missing entries (check the needs-changelog label on github), and
  - including an entry for ### ABI Compatibility if it doesn't exist,
- sets _PKG_VERSION_IS_RELEASE to true in configure.ac, and,
- if this is not a patch release,
  - updates _PKG_VERSION_* and _LIB_VERSION_* in configure.ac, and
  - updates project(libsecp256k1 VERSION ...) and ${PROJECT_NAME}_LIB_VERSION_* in CMakeLists.txt.
Perform the sanity checks on the PR branch.

After the PR is merged, tag the commit, and push the tag:

text

RELEASE_COMMIT=<merge commit of step 1>
git tag -s v$MAJOR.$MINOR.$PATCH -m "libsecp256k1 $MAJOR.$MINOR.$PATCH" $RELEASE_COMMIT
git push [email protected]:bitcoin-core/secp256k1.git v$MAJOR.$MINOR.$PATCH

Open a PR to the master branch with a commit (using message "release cleanup: bump version after $MAJOR.$MINOR.$PATCH", for example) that
- sets _PKG_VERSION_IS_RELEASE to false and increments _PKG_VERSION_PATCH and _LIB_VERSION_REVISION in configure.ac,
- increments the $PATCH component of project(libsecp256k1 VERSION ...) and ${PROJECT_NAME}_LIB_VERSION_REVISION in CMakeLists.txt, and
- adds an [Unreleased] section header to the CHANGELOG.md.
If other maintainers are not present to approve the PR, it can be merged without ACKs.
Create a new GitHub release with a link to the corresponding entry in CHANGELOG.md.
Send an announcement email to the bitcoin-dev mailing list.

Maintenance release

Note that bug fixes need to be backported only to releases for which no compatible release without the bug exists.

If there's no maintenance branch $MAJOR.$MINOR, create one:

text

git checkout -b $MAJOR.$MINOR v$MAJOR.$MINOR.$((PATCH - 1))
git push [email protected]:bitcoin-core/secp256k1.git $MAJOR.$MINOR

Open a pull request to the $MAJOR.$MINOR branch that
- includes the bug fixes,
- finalizes the release notes similar to a regular release,
- increments _PKG_VERSION_PATCH and _LIB_VERSION_REVISION in configure.ac
  and the $PATCH component of project(libsecp256k1 VERSION ...) and ${PROJECT_NAME}_LIB_VERSION_REVISION in CMakeLists.txt
  (with commit message "release: bump versions for $MAJOR.$MINOR.$PATCH", for example).
Perform the sanity checks on the PR branch.

After the PRs are merged, update the release branch, tag the commit, and push the tag:

text

git checkout $MAJOR.$MINOR && git pull
git tag -s v$MAJOR.$MINOR.$PATCH -m "libsecp256k1 $MAJOR.$MINOR.$PATCH"
git push [email protected]:bitcoin-core/secp256k1.git v$MAJOR.$MINOR.$PATCH

Create a new GitHub release with a link to the corresponding entry in CHANGELOG.md.
Send an announcement email to the bitcoin-dev mailing list.
Open PR to the master branch that includes a commit (with commit message "release notes: add $MAJOR.$MINOR.$PATCH", for example) that adds release notes to CHANGELOG.md.

Crypto Secp256k1 Libsecp256k1 Doc Safegcd Implementation (`crypto/secp256k1/libsecp256k1/doc/safegcd_implementation.md`)

The safegcd implementation in libsecp256k1 explained

This document explains the modular inverse and Jacobi symbol implementations in the src/modinv*.h files.
It is based on the paper
"Fast constant-time gcd computation and modular inversion"
by Daniel J. Bernstein and Bo-Yin Yang. The references below are for the Date: 2019.04.13 version.

The actual implementation is in C of course, but for demonstration purposes Python3 is used here.
Most implementation aspects and optimizations are explained, except those that depend on the specific
number representation used in the C code.

1. Computing the Greatest Common Divisor (GCD) using divsteps

The algorithm from the paper (section 11), at a very high level, is this:

python

def gcd(f, g):
    """Compute the GCD of an odd integer f and another integer g."""
    assert f & 1  # require f to be odd
    delta = 1     # additional state variable
    while g != 0:
        assert f & 1  # f will be odd in every iteration
        if delta > 0 and g & 1:
            delta, f, g = 1 - delta, g, (g - f) // 2
        elif g & 1:
            delta, f, g = 1 + delta, f, (g + f) // 2
        else:
            delta, f, g = 1 + delta, f, (g    ) // 2
    return abs(f)

It computes the greatest common divisor of an odd integer f and any integer g. Its inner loop
keeps rewriting the variables f and g alongside a state variable δ that starts at 1, until
g=0 is reached. At that point, |f| gives the GCD. Each of the transitions in the loop is called a
"division step" (referred to as divstep in what follows).

For example, gcd(21, 14) would be computed as:

Start with δ=1 f=21 g=14
Take the third branch: δ=2 f=21 g=7
Take the first branch: δ=-1 f=7 g=-7
Take the second branch: δ=0 f=7 g=0
The answer |f| = 7.

Why it works:

Divsteps can be decomposed into two steps (see paragraph 8.2 in the paper):
- (a) If g is odd, replace (f,g) with (g,g-f) or (f,g+f), resulting in an even g.
- (b) Replace (f,g) with (f,g/2) (where g is guaranteed to be even).
Neither of those two operations change the GCD:
- For (a), assume gcd(f,g)=c, then it must be the case that f=a c and g=b c for some integers a
  and b. As (g,g-f)=(b c,(b-a)c) and (f,f+g)=(a c,(a+b)c), the result clearly still has
  common factor c. Reasoning in the other direction shows that no common factor can be added by
  doing so either.
- For (b), we know that f is odd, so gcd(f,g) clearly has no factor 2, and we can remove
  it from g.
The algorithm will eventually converge to g=0. This is proven in the paper (see theorem G.3).
It follows that eventually we find a final value f' for which gcd(f,g) = gcd(f',0). As the
gcd of f' and 0 is |f'| by definition, that is our answer.

Compared to more traditional GCD algorithms, this one has the property of only ever looking at
the low-order bits of the variables to decide the next steps, and being easy to make
constant-time (in more low-level languages than Python). The δ parameter is necessary to
guide the algorithm towards shrinking the numbers' magnitudes without explicitly needing to look
at high order bits.

Properties that will become important later:

Performing more divsteps than needed is not a problem, as f does not change anymore after g=0.
Only even numbers are divided by 2. This means that when reasoning about it algebraically we
do not need to worry about rounding.
At every point during the algorithm's execution the next N steps only depend on the bottom N
bits of f and g, and on δ.

2. From GCDs to modular inverses

We want an algorithm to compute the inverse a of x modulo M, i.e. the number a such that a x=1
mod M. This inverse only exists if the GCD of x and M is 1, but that is always the case if M is
prime and 0 < x < M. In what follows, assume that the modular inverse exists.
It turns out this inverse can be computed as a side effect of computing the GCD by keeping track
of how the internal variables can be written as linear combinations of the inputs at every step
(see the extended Euclidean algorithm).
Since the GCD is 1, such an algorithm will compute numbers a and b such that a x + b M = 1*.
Taking that expression mod M gives a x mod M = 1, and we see that a is the modular inverse of x
mod M.

A similar approach can be used to calculate modular inverses using the divsteps-based GCD
algorithm shown above, if the modulus M is odd. To do so, compute gcd(f=M,g=x), while keeping
track of extra variables d and e, for which at every step d = f/x (mod M) and e = g/x (mod M).
f/x here means the number which multiplied with x gives f mod M. As f and g are initialized to M
and x respectively, d and e just start off being 0 (M/x mod M = 0/x mod M = 0) and 1 (x/x mod M
= 1).

python

def div2(M, x):
    """Helper routine to compute x/2 mod M (where M is odd)."""
    assert M & 1
    if x & 1: # If x is odd, make it even by adding M.
        x += M
    # x must be even now, so a clean division by 2 is possible.
    return x // 2

def modinv(M, x):
    """Compute the inverse of x mod M (given that it exists, and M is odd)."""
    assert M & 1
    delta, f, g, d, e = 1, M, x, 0, 1
    while g != 0:
        # Note that while division by two for f and g is only ever done on even inputs, this is
        # not true for d and e, so we need the div2 helper function.
        if delta > 0 and g & 1:
            delta, f, g, d, e = 1 - delta, g, (g - f) // 2, e, div2(M, e - d)
        elif g & 1:
            delta, f, g, d, e = 1 + delta, f, (g + f) // 2, d, div2(M, e + d)
        else:
            delta, f, g, d, e = 1 + delta, f, (g    ) // 2, d, div2(M, e    )
        # Verify that the invariants d=f/x mod M, e=g/x mod M are maintained.
        assert f % M == (d * x) % M
        assert g % M == (e * x) % M
    assert f == 1 or f == -1  # |f| is the GCD, it must be 1
    # Because of invariant d = f/x (mod M), 1/x = d/f (mod M). As |f|=1, d/f = d*f.
    return (d * f) % M

Also note that this approach to track d and e throughout the computation to determine the inverse
is different from the paper. There (see paragraph 12.1 in the paper) a transition matrix for the
entire computation is determined (see section 3 below) and the inverse is computed from that.
The approach here avoids the need for 2x2 matrix multiplications of various sizes, and appears to
be faster at the level of optimization we're able to do in C.

3. Batching multiple divsteps

Every divstep can be expressed as a matrix multiplication, applying a transition matrix (1/2 t)
to both vectors [f, g] and [d, e] (see paragraph 8.1 in the paper):

text

t = [ u,  v ]
      [ q,  r ]

  [ out_f ] = (1/2 * t) * [ in_f ]
  [ out_g ] =             [ in_g ]

  [ out_d ] = (1/2 * t) * [ in_d ]  (mod M)
  [ out_e ]               [ in_e ]

where (u, v, q, r) is (0, 2, -1, 1), (2, 0, 1, 1), or (2, 0, 0, 1), depending on which branch is
taken. As above, the resulting f and g are always integers.

Performing multiple divsteps corresponds to a multiplication with the product of all the
individual divsteps' transition matrices. As each transition matrix consists of integers
divided by 2, the product of these matrices will consist of integers divided by 2^N (see also
theorem 9.2 in the paper). These divisions are expensive when updating d and e, so we delay
them: we compute the integer coefficients of the combined transition matrix scaled by 2^N, and
do one division by 2^N as a final step:

python

def divsteps_n_matrix(delta, f, g):
    """Compute delta and transition matrix t after N divsteps (multiplied by 2^N)."""
    u, v, q, r = 1, 0, 0, 1 # start with identity matrix
    for _ in range(N):
        if delta > 0 and g & 1:
            delta, f, g, u, v, q, r = 1 - delta, g, (g - f) // 2, 2*q, 2*r, q-u, r-v
        elif g & 1:
            delta, f, g, u, v, q, r = 1 + delta, f, (g + f) // 2, 2*u, 2*v, q+u, r+v
        else:
            delta, f, g, u, v, q, r = 1 + delta, f, (g    ) // 2, 2*u, 2*v, q  , r
    return delta, (u, v, q, r)

As the branches in the divsteps are completely determined by the bottom N bits of f and g, this
function to compute the transition matrix only needs to see those bottom bits. Furthermore all
intermediate results and outputs fit in (N+1)-bit numbers (unsigned for f and g; signed for u, v,
q, and r) (see also paragraph 8.3 in the paper). This means that an implementation using 64-bit
integers could set N=62 and compute the full transition matrix for 62 steps at once without any
big integer arithmetic at all. This is the reason why this algorithm is efficient: it only needs
to update the full-size f, g, d, and e numbers once every N steps.

We still need functions to compute:

text

[ out_f ] = (1/2^N * [ u,  v ]) * [ in_f ]
  [ out_g ]   (        [ q,  r ])   [ in_g ]

  [ out_d ] = (1/2^N * [ u,  v ]) * [ in_d ]  (mod M)
  [ out_e ]   (        [ q,  r ])   [ in_e ]

Because the divsteps transformation only ever divides even numbers by two, the result of t [f,g] is always even. When t is a composition of N divsteps, it follows that the resulting f
and g will be multiple of 2^N, and division by 2^N is simply shifting them down:

python

def update_fg(f, g, t):
    """Multiply matrix t/2^N with [f, g]."""
    u, v, q, r = t
    cf, cg = u*f + v*g, q*f + r*g
    # (t / 2^N) should cleanly apply to [f,g] so the result of t*[f,g] should have N zero
    # bottom bits.
    assert cf % 2**N == 0
    assert cg % 2**N == 0
    return cf >> N, cg >> N

The same is not true for d and e, and we need an equivalent of the div2 function for division by 2^N mod M.
This is easy if we have precomputed 1/M mod 2^N (which always exists for odd M):

python

def div2n(M, Mi, x):
    """Compute x/2^N mod M, given Mi = 1/M mod 2^N."""
    assert (M * Mi) % 2**N == 1
    # Find a factor m such that m*M has the same bottom N bits as x. We want:
    #     (m * M) mod 2^N = x mod 2^N
    # <=> m mod 2^N = (x / M) mod 2^N
    # <=> m mod 2^N = (x * Mi) mod 2^N
    m = (Mi * x) % 2**N
    # Subtract that multiple from x, cancelling its bottom N bits.
    x -= m * M
    # Now a clean division by 2^N is possible.
    assert x % 2**N == 0
    return (x >> N) % M

def update_de(d, e, t, M, Mi):
    """Multiply matrix t/2^N with [d, e], modulo M."""
    u, v, q, r = t
    cd, ce = u*d + v*e, q*d + r*e
    return div2n(M, Mi, cd), div2n(M, Mi, ce)

With all of those, we can write a version of modinv that performs N divsteps at once:

python3

def modinv(M, Mi, x):
    """Compute the modular inverse of x mod M, given Mi=1/M mod 2^N."""
    assert M & 1
    delta, f, g, d, e = 1, M, x, 0, 1
    while g != 0:
        # Compute the delta and transition matrix t for the next N divsteps (this only needs
        # (N+1)-bit signed integer arithmetic).
        delta, t = divsteps_n_matrix(delta, f % 2**N, g % 2**N)
        # Apply the transition matrix t to [f, g]:
        f, g = update_fg(f, g, t)
        # Apply the transition matrix t to [d, e]:
        d, e = update_de(d, e, t, M, Mi)
    return (d * f) % M

This means that in practice we'll always perform a multiple of N divsteps. This is not a problem
because once g=0, further divsteps do not affect f, g, d, or e anymore (only δ keeps
increasing). For variable time code such excess iterations will be mostly optimized away in later
sections.

4. Avoiding modulus operations

So far, there are two places where we compute a remainder of big numbers modulo M: at the end of
div2n in every update_de, and at the very end of modinv after potentially negating d due to the
sign of f. These are relatively expensive operations when done generically.

To deal with the modulus operation in div2n, we simply stop requiring d and e to be in range
[0,M) all the time. Let's start by inlining div2n into update_de, and dropping the modulus
operation at the end:

python

def update_de(d, e, t, M, Mi):
    """Multiply matrix t/2^N with [d, e] mod M, given Mi=1/M mod 2^N."""
    u, v, q, r = t
    cd, ce = u*d + v*e, q*d + r*e
    # Cancel out bottom N bits of cd and ce.
    md = -((Mi * cd) % 2**N)
    me = -((Mi * ce) % 2**N)
    cd += md * M
    ce += me * M
    # And cleanly divide by 2**N.
    return cd >> N, ce >> N

Let's look at bounds on the ranges of these numbers. It can be shown that |u|+|v| and |q|+|r|
never exceed 2^N (see paragraph 8.3 in the paper), and thus a multiplication with t will have
outputs whose absolute values are at most 2^N times the maximum absolute input value. In case the
inputs d and e are in (-M,M), which is certainly true for the initial values d=0 and e=1 assuming
M > 1, the multiplication results in numbers in range (-2^NM,2^NM). Subtracting less than 2^N
times M to cancel out N bits brings that up to (-2^N+1M,2^NM), and
dividing by 2^N at the end takes it to (-2M,M). Another application of update_de would take that
to (-3M,2M), and so forth. This progressive expansion of the variables' ranges can be
counteracted by incrementing d and e by M whenever they're negative:

python

...
    if d < 0:
        d += M
    if e < 0:
        e += M
    cd, ce = u*d + v*e, q*d + r*e
    # Cancel out bottom N bits of cd and ce.
    ...

With inputs in (-2M,M), they will first be shifted into range (-M,M), which means that the
output will again be in (-2M,M), and this remains the case regardless of how many update_de
invocations there are. In what follows, we will try to make this more efficient.

Note that increasing d by M is equal to incrementing cd by u M and ce by q M. Similarly,
increasing e by M is equal to incrementing cd by v M and ce by r M. So we could instead write:

python

...
    cd, ce = u*d + v*e, q*d + r*e
    # Perform the equivalent of incrementing d, e by M when they're negative.
    if d < 0:
        cd += u*M
        ce += q*M
    if e < 0:
        cd += v*M
        ce += r*M
    # Cancel out bottom N bits of cd and ce.
    md = -((Mi * cd) % 2**N)
    me = -((Mi * ce) % 2**N)
    cd += md * M
    ce += me * M
    ...

Now note that we have two steps of corrections to cd and ce that add multiples of M: this
increment, and the decrement that cancels out bottom bits. The second one depends on the first
one, but they can still be efficiently combined by only computing the bottom bits of cd and ce
at first, and using that to compute the final md, me values:

python

def update_de(d, e, t, M, Mi):
    """Multiply matrix t/2^N with [d, e], modulo M."""
    u, v, q, r = t
    md, me = 0, 0
    # Compute what multiples of M to add to cd and ce.
    if d < 0:
        md += u
        me += q
    if e < 0:
        md += v
        me += r
    # Compute bottom N bits of t*[d,e] + M*[md,me].
    cd, ce = (u*d + v*e + md*M) % 2**N, (q*d + r*e + me*M) % 2**N
    # Correct md and me such that the bottom N bits of t*[d,e] + M*[md,me] are zero.
    md -= (Mi * cd) % 2**N
    me -= (Mi * ce) % 2**N
    # Do the full computation.
    cd, ce = u*d + v*e + md*M, q*d + r*e + me*M
    # And cleanly divide by 2**N.
    return cd >> N, ce >> N

One last optimization: we can avoid the md M and me M multiplications in the bottom bits of cd
and ce by moving them to the md and me correction:

python

...
    # Compute bottom N bits of t*[d,e].
    cd, ce = (u*d + v*e) % 2**N, (q*d + r*e) % 2**N
    # Correct md and me such that the bottom N bits of t*[d,e]+M*[md,me] are zero.
    # Note that this is not the same as {md = (-Mi * cd) % 2**N} etc. That would also result in N
    # zero bottom bits, but isn't guaranteed to be a reduction of [0,2^N) compared to the
    # previous md and me values, and thus would violate our bounds analysis.
    md -= (Mi*cd + md) % 2**N
    me -= (Mi*ce + me) % 2**N
    ...

The resulting function takes d and e in range (-2M,M) as inputs, and outputs values in the same
range. That also means that the d value at the end of modinv will be in that range, while we want
a result in [0,M). To do that, we need a normalization function. It's easy to integrate the
conditional negation of d (based on the sign of f) into it as well:

python

def normalize(sign, v, M):
    """Compute sign*v mod M, where v is in range (-2*M,M); output in [0,M)."""
    assert sign == 1 or sign == -1
    # v in (-2*M,M)
    if v < 0:
        v += M
    # v in (-M,M). Now multiply v with sign (which can only be 1 or -1).
    if sign == -1:
        v = -v
    # v in (-M,M)
    if v < 0:
        v += M
    # v in [0,M)
    return v

And calling it in modinv is simply:

python

...
   return normalize(f, d, M)

5. Constant-time operation

The primary selling point of the algorithm is fast constant-time operation. What code flow still
depends on the input data so far?

the number of iterations of the while g ≠ 0 loop in modinv
the branches inside divsteps_n_matrix
the sign checks in update_de
the sign checks in normalize

To make the while loop in modinv constant time it can be replaced with a constant number of
iterations. The paper proves (Theorem 11.2) that 741 divsteps are sufficient for any 256-bit
inputs, and safegcd-bounds shows that the slightly better bound 724 is
sufficient even. Given that every loop iteration performs N divsteps, it will run a total of
⌈724/N⌉ times.

To deal with the branches in divsteps_n_matrix we will replace them with constant-time bitwise
operations (and hope the C compiler isn't smart enough to turn them back into branches; see
ctime_tests.c for automated tests that this isn't the case). To do so, observe that a
divstep can be written instead as (compare to the inner loop of gcd in section 1).

python

x = -f if delta > 0 else f         # set x equal to (input) -f or f
    if g & 1:
        g += x                         # set g to (input) g-f or g+f
        if delta > 0:
            delta = -delta
            f += g                     # set f to (input) g (note that g was set to g-f before)
    delta += 1
    g >>= 1

To convert the above to bitwise operations, we rely on a trick to negate conditionally: per the
definition of negative numbers in two's complement, (-v == ~v + 1) holds for every number v. As
-1 in two's complement is all 1 bits, bitflipping can be expressed as xor with -1. It follows
that -v == (v ^ -1) - (-1). Thus, if we have a variable c that takes on values 0 or -1, then
(v ^ c) - c is v if c=0 and -v if c=-1.

Using this we can write:

python

x = -f if delta > 0 else f

in constant-time form as:

python

c1 = (-delta) >> 63
    # Conditionally negate f based on c1:
    x = (f ^ c1) - c1

To use that trick, we need a helper mask variable c1 that resolves the condition δ>0 to -1
(if true) or 0 (if false). We compute c1 using right shifting, which is equivalent to dividing by
the specified power of 2 and rounding down (in Python, and also in C under the assumption of a typical two's complement system; see
assumptions.h for tests that this is the case). Right shifting by 63 thus maps all
numbers in range [-2⁶³,0) to -1, and numbers in range [0,2⁶³) to 0.

Using the facts that x&0=0 and x&(-1)=x (on two's complement systems again), we can write:

python

if g & 1:
        g += x

as:

python

# Compute c2=0 if g is even and c2=-1 if g is odd.
    c2 = -(g & 1)
    # This masks out x if g is even, and leaves x be if g is odd.
    g += x & c2

Using the conditional negation trick again we can write:

python

if g & 1:
        if delta > 0:
            delta = -delta

as:

python

# Compute c3=-1 if g is odd and delta>0, and 0 otherwise.
    c3 = c1 & c2
    # Conditionally negate delta based on c3:
    delta = (delta ^ c3) - c3

Finally:

python

if g & 1:
        if delta > 0:
            f += g

becomes:

python

f += g & c3

It turns out that this can be implemented more efficiently by applying the substitution
η=-δ. In this representation, negating δ corresponds to negating η, and incrementing
δ corresponds to decrementing η. This allows us to remove the negation in the c1
computation:

python

# Compute a mask c1 for eta < 0, and compute the conditional negation x of f:
    c1 = eta >> 63
    x = (f ^ c1) - c1
    # Compute a mask c2 for odd g, and conditionally add x to g:
    c2 = -(g & 1)
    g += x & c2
    # Compute a mask c for (eta < 0) and odd (input) g, and use it to conditionally negate eta,
    # and add g to f:
    c3 = c1 & c2
    eta = (eta ^ c3) - c3
    f += g & c3
    # Incrementing delta corresponds to decrementing eta.
    eta -= 1
    g >>= 1

A variant of divsteps with better worst-case performance can be used instead: starting δ at
1/2 instead of 1. This reduces the worst case number of iterations to 590 for 256-bit inputs
(which can be shown using convex hull analysis). In this case, the substitution ζ=-(δ+1/2)
is used instead to keep the variable integral. Incrementing δ by 1 still translates to
decrementing ζ by 1, but negating δ now corresponds to going from ζ to -(ζ+1), or
~ζ. Doing that conditionally based on c3 is simply:

python

...
    c3 = c1 & c2
    zeta ^= c3
    ...

By replacing the loop in divsteps_n_matrix with a variant of the divstep code above (extended to
also apply all f operations to u, v and all g operations to q, r), a constant-time version of
divsteps_n_matrix is obtained. The full code will be in section 7.

These bit fiddling tricks can also be used to make the conditional negations and additions in
update_de and normalize constant-time.

6. Variable-time optimizations

In section 5, we modified the divsteps_n_matrix function (and a few others) to be constant time.
Constant time operations are only necessary when computing modular inverses of secret data. In
other cases, it slows down calculations unnecessarily. In this section, we will construct a
faster non-constant time divsteps_n_matrix function.

To do so, first consider yet another way of writing the inner loop of divstep operations in
gcd from section 1. This decomposition is also explained in the paper in section 8.2. We use
the original version with initial δ=1 and η=-δ here.

python

for _ in range(N):
    if g & 1 and eta < 0:
        eta, f, g = -eta, g, -f
    if g & 1:
        g += f
    eta -= 1
    g >>= 1

Whenever g is even, the loop only shifts g down and decreases η. When g ends in multiple zero
bits, these iterations can be consolidated into one step. This requires counting the bottom zero
bits efficiently, which is possible on most platforms; it is abstracted here as the function
count_trailing_zeros.

python

def count_trailing_zeros(v):
    """
    When v is zero, consider all N zero bits as "trailing".
    For a non-zero value v, find z such that v=(d<<z) for some odd d.
    """
    if v == 0:
        return N
    else:
        return (v & -v).bit_length() - 1

i = N # divsteps left to do
while True:
    # Get rid of all bottom zeros at once. In the first iteration, g may be odd and the following
    # lines have no effect (until "if eta < 0").
    zeros = min(i, count_trailing_zeros(g))
    eta -= zeros
    g >>= zeros
    i -= zeros
    if i == 0:
        break
    # We know g is odd now
    if eta < 0:
        eta, f, g = -eta, g, -f
    g += f
    # g is even now, and the eta decrement and g shift will happen in the next loop.

We can now remove multiple bottom 0 bits from g at once, but still need a full iteration whenever
there is a bottom 1 bit. In what follows, we will get rid of multiple 1 bits simultaneously as
well.

Observe that as long as η ≥ 0, the loop does not modify f. Instead, it cancels out bottom
bits of g and shifts them out, and decreases η and i accordingly - interrupting only when η
becomes negative, or when i reaches 0. Combined, this is equivalent to adding a multiple of f to
g to cancel out multiple bottom bits, and then shifting them out.

It is easy to find what that multiple is: we want a number w such that g+w f has a few bottom
zero bits. If that number of bits is L, we want g+w f mod 2^L = 0, or w = -g/f mod 2^L. Since f
is odd, such a w exists for any L. L cannot be more than i steps (as we'd finish the loop before
doing more) or more than η+1 steps (as we'd run eta, f, g = -eta, g, -f at that point), but
apart from that, we're only limited by the complexity of computing w.

This code demonstrates how to cancel up to 4 bits per step:

python

NEGINV16 = [15, 5, 3, 9, 7, 13, 11, 1] # NEGINV16[n//2] = (-n)^-1 mod 16, for odd n
i = N
while True:
    zeros = min(i, count_trailing_zeros(g))
    eta -= zeros
    g >>= zeros
    i -= zeros
    if i == 0:
        break
    # We know g is odd now
    if eta < 0:
        eta, f, g = -eta, g, -f
    # Compute limit on number of bits to cancel
    limit = min(min(eta + 1, i), 4)
    # Compute w = -g/f mod 2**limit, using the table value for -1/f mod 2**4. Note that f is
    # always odd, so its inverse modulo a power of two always exists.
    w = (g * NEGINV16[(f & 15) // 2]) % (2**limit)
    # As w = -g/f mod (2**limit), g+w*f mod 2**limit = 0 mod 2**limit.
    g += w * f
    assert g % (2**limit) == 0
    # The next iteration will now shift out at least limit bottom zero bits from g.

By using a bigger table more bits can be cancelled at once. The table can also be implemented
as a formula. Several formulas are known for computing modular inverses modulo powers of two;
some can be found in Hacker's Delight second edition by Henry S. Warren, Jr. pages 245-247.
Here we need the negated modular inverse, which is a simple transformation of those:

Instead of a 3-bit table:
- -f or f ^ 6
Instead of a 4-bit table:
- 1 - f(f + 1)
- -(f + (((f + 1) & 4) << 1))
For larger tables the following technique can be used: if w=-1/f mod 2^L, then w(w f+2) is
-1/f mod 2^2L. This allows extending the previous formulas (or tables). In particular we
have this 6-bit function (based on the 3-bit function above):
- f(f² - 2)

This loop, again extended to also handle u, v, q, and r alongside f and g, placed in
divsteps_n_matrix, gives a significantly faster, but non-constant time version.

7. Final Python version

All together we need the following functions:

A way to compute the transition matrix in constant time, using the divsteps_n_matrix function
from section 2, but with its loop replaced by a variant of the constant-time divstep from
section 5, extended to handle u, v, q, r:

python

def divsteps_n_matrix(zeta, f, g):
    """Compute zeta and transition matrix t after N divsteps (multiplied by 2^N)."""
    u, v, q, r = 1, 0, 0, 1 # start with identity matrix
    for _ in range(N):
        c1 = zeta >> 63
        # Compute x, y, z as conditionally-negated versions of f, u, v.
        x, y, z = (f ^ c1) - c1, (u ^ c1) - c1, (v ^ c1) - c1
        c2 = -(g & 1)
        # Conditionally add x, y, z to g, q, r.
        g, q, r = g + (x & c2), q + (y & c2), r + (z & c2)
        c1 &= c2                     # reusing c1 here for the earlier c3 variable
        zeta = (zeta ^ c1) - 1       # inlining the unconditional zeta decrement here
        # Conditionally add g, q, r to f, u, v.
        f, u, v = f + (g & c1), u + (q & c1), v + (r & c1)
        # When shifting g down, don't shift q, r, as we construct a transition matrix multiplied
        # by 2^N. Instead, shift f's coefficients u and v up.
        g, u, v = g >> 1, u << 1, v << 1
    return zeta, (u, v, q, r)

The functions to update f and g, and d and e, from section 2 and section 4, with the constant-time
changes to update_de from section 5:

python

def update_fg(f, g, t):
    """Multiply matrix t/2^N with [f, g]."""
    u, v, q, r = t
    cf, cg = u*f + v*g, q*f + r*g
    return cf >> N, cg >> N

def update_de(d, e, t, M, Mi):
    """Multiply matrix t/2^N with [d, e], modulo M."""
    u, v, q, r = t
    d_sign, e_sign = d >> 257, e >> 257
    md, me = (u & d_sign) + (v & e_sign), (q & d_sign) + (r & e_sign)
    cd, ce = (u*d + v*e) % 2**N, (q*d + r*e) % 2**N
    md -= (Mi*cd + md) % 2**N
    me -= (Mi*ce + me) % 2**N
    cd, ce = u*d + v*e + M*md, q*d + r*e + M*me
    return cd >> N, ce >> N

The normalize function from section 4, made constant time as well:

python

def normalize(sign, v, M):
    """Compute sign*v mod M, where v in (-2*M,M); output in [0,M)."""
    v_sign = v >> 257
    # Conditionally add M to v.
    v += M & v_sign
    c = (sign - 1) >> 1
    # Conditionally negate v.
    v = (v ^ c) - c
    v_sign = v >> 257
    # Conditionally add M to v again.
    v += M & v_sign
    return v

And finally the modinv function too, adapted to use ζ instead of δ, and using the fixed
iteration count from section 5:

python

def modinv(M, Mi, x):
    """Compute the modular inverse of x mod M, given Mi=1/M mod 2^N."""
    zeta, f, g, d, e = -1, M, x, 0, 1
    for _ in range((590 + N - 1) // N):
        zeta, t = divsteps_n_matrix(zeta, f % 2**N, g % 2**N)
        f, g = update_fg(f, g, t)
        d, e = update_de(d, e, t, M, Mi)
    return normalize(f, d, M)

To get a variable time version, replace the divsteps_n_matrix function with one that uses the
divsteps loop from section 5, and a modinv version that calls it without the fixed iteration
count:

python

NEGINV16 = [15, 5, 3, 9, 7, 13, 11, 1] # NEGINV16[n//2] = (-n)^-1 mod 16, for odd n
def divsteps_n_matrix_var(eta, f, g):
    """Compute eta and transition matrix t after N divsteps (multiplied by 2^N)."""
    u, v, q, r = 1, 0, 0, 1
    i = N
    while True:
        zeros = min(i, count_trailing_zeros(g))
        eta, i = eta - zeros, i - zeros
        g, u, v = g >> zeros, u << zeros, v << zeros
        if i == 0:
            break
        if eta < 0:
            eta, f, u, v, g, q, r = -eta, g, q, r, -f, -u, -v
        limit = min(min(eta + 1, i), 4)
        w = (g * NEGINV16[(f & 15) // 2]) % (2**limit)
        g, q, r = g + w*f, q + w*u, r + w*v
    return eta, (u, v, q, r)

def modinv_var(M, Mi, x):
    """Compute the modular inverse of x mod M, given Mi = 1/M mod 2^N."""
    eta, f, g, d, e = -1, M, x, 0, 1
    while g != 0:
        eta, t = divsteps_n_matrix_var(eta, f % 2**N, g % 2**N)
        f, g = update_fg(f, g, t)
        d, e = update_de(d, e, t, M, Mi)
    return normalize(f, d, Mi)

8. From GCDs to Jacobi symbol

We can also use a similar approach to calculate Jacobi symbol (x | M) by keeping track of an
extra variable j, for which at every step (x | M) = j (g | f). As we update f and g, we
make corresponding updates to j using
properties of the Jacobi symbol:

((g/2) | f) is either (g | f) or -(g | f), depending on the value of f mod 8 (negating if it's 3 or 5).
(f | g) is either (g | f) or -(g | f), depending on f mod 4 and g mod 4 (negating if both are 3).

These updates depend only on the values of f and g modulo 4 or 8, and can thus be applied
very quickly, as long as we keep track of a few additional bits of f and g. Overall, this
calculation is slightly simpler than the one for the modular inverse because we no longer need to
keep track of d and e.

However, one difficulty of this approach is that the Jacobi symbol (a | n) is only defined for
positive odd integers n, whereas in the original safegcd algorithm, f, g can take negative
values. We resolve this by using the following modified steps:

python

# Before
        if delta > 0 and g & 1:
            delta, f, g = 1 - delta, g, (g - f) // 2

        # After
        if delta > 0 and g & 1:
            delta, f, g = 1 - delta, g, (g + f) // 2

The algorithm is still correct, since the changed divstep, called a "posdivstep" (see section 8.4
and E.5 in the paper) preserves gcd(f, g). However, there's no proof that the modified algorithm
will converge. The justification for posdivsteps is completely empirical: in practice, it appears
that the vast majority of nonzero inputs converge to f=g=gcd(f₀, g₀) in a
number of steps proportional to their logarithm.

Note that:

We require inputs to satisfy gcd(x, M) = 1, as otherwise f=1 is not reached.
We require inputs x &neq; 0, because applying posdivstep with g=0 has no effect.
We need to update the termination condition from g=0 to f=1.

We account for the possibility of nonconvergence by only performing a bounded number of
posdivsteps, and then falling back to square-root based Jacobi calculation if a solution has not
yet been found.

The optimizations in sections 3-7 above are described in the context of the original divsteps, but
in the C implementation we also adapt most of them (not including "avoiding modulus operations",
since it's not necessary to track d, e, and "constant-time operation", since we never calculate
Jacobi symbols for secret data) to the posdivsteps version.

--- METRICS ---

Files Extracted: 42
Estimated Token Budget: ~42801 tokens
Canonical Reference: https://codewiki.google/github.com/ethereum/go-ethereum

Docker & Self-Hosted Deployment Verified OCI

Technical Documentation: ethereum/go-ethereum

Overview (`README.md`) Copy Section

Go Ethereum Copy Chapter

Building the source Copy Chapter

Executables Copy Chapter

Running `geth` Copy Chapter

Hardware Requirements Copy Section

Full node on the main Ethereum network Copy Section

A Full node on the Sepolia test network Copy Section

Configuration Copy Section

Docker quick start

Programmatically interfacing `geth` nodes Copy Section

Operating a private network Copy Section

Contribution Copy Chapter

Contributing to geth.ethereum.org Copy Section

License Copy Chapter

Overview (`metrics/README.md`) Copy Section

go-metrics

Usage Copy Chapter

Installation Copy Chapter

Publishing Metrics Copy Chapter

Overview (`accounts/scwallet/README.md`) Copy Section

Using the smartcard wallet

Requirements Copy Chapter

Preparing the smartcard Copy Chapter

Usage Copy Chapter

Known issues Copy Chapter

Overview (`cmd/devp2p/README.md`) Copy Section

The devp2p command

ENR Decoding Copy Section

Node Key Management Copy Section

Maintaining DNS Discovery Node Lists Copy Section

Node Set Utilities Copy Section

Discovery v4 Utilities Copy Section

Discovery v5 Utilities Copy Section

Combined Discovery Copy Section

Discovery Test Suites Copy Section

Eth Protocol Test Suite Copy Section

Overview (`cmd/ethkey/README.md`) Copy Section

ethkey

Usage

`ethkey generate` Copy Section

`ethkey inspect ` Copy Section

`ethkey signmessage ` Copy Section

`ethkey verifymessage ` Copy Section

`ethkey changepassword ` Copy Section

Passwords Copy Chapter

JSON Copy Chapter

Overview (`cmd/evm/README.md`) Copy Section

EVM tool

State transition tool (`t8n`) Copy Chapter

Specification Copy Section

Command line params

Objects

`alloc`

`env`

`txs`

`result`

Error codes and output

EVM-based errors (`2` to `9`)

IO errors (`10`-`20`)

Forks

Basic usage Copy Section

Examples

Basic usage

About Ommers

Future EIPS

Block history

Chaining

Transactions in RLP form

Transaction tool Copy Chapter

Examples Copy Section

Block builder tool (b11r) Copy Chapter

Specification Copy Section

Command line params

Objects

`header`

`ommers`

`txs`

Overview (`README.md`)

Go Ethereum

Building the source

Executables

Running `geth`

Hardware Requirements

Full node on the main Ethereum network

A Full node on the Sepolia test network

Configuration

Programmatically interfacing `geth` nodes

Operating a private network

Contribution

Contributing to geth.ethereum.org

License

Overview (`metrics/README.md`)

Usage

Installation

Publishing Metrics

Overview (`accounts/scwallet/README.md`)

Requirements

Preparing the smartcard

Usage

Known issues

Overview (`cmd/devp2p/README.md`)

ENR Decoding

Node Key Management

Maintaining DNS Discovery Node Lists

Node Set Utilities

Discovery v4 Utilities

Discovery v5 Utilities

Combined Discovery

Discovery Test Suites

Eth Protocol Test Suite

Overview (`cmd/ethkey/README.md`)

`ethkey generate`

`ethkey inspect `

`ethkey signmessage `

`ethkey verifymessage
`

`ethkey changepassword `

Passwords

JSON

Overview (`cmd/evm/README.md`)

State transition tool (`t8n`)

Specification

Basic usage

Transaction tool

Examples

Block builder tool (b11r)

Specification

A Note on Encoding

Testing

Overview (`cmd/keeper/README.md`)

Overview

Building Keeper

Example Implementation

Ziren zkVM Implementation

Creating a Custom Platform Implementation

1. Create `getinput_myplatform.go`

Overview (`cmd/workload/README.md`)

Workload Testing Tool

Regenerating tests

Overview (`crypto/keccak/README.md`)

Overview (`metrics/influxdb/README.md`)

Note

Usage

License

Overview (`tests/fuzzers/README.md`)

Fuzzers

Notes

Overview (`core/vm/program/readme.md`)

What is this

Warning

Overview (`crypto/secp256k1/libsecp256k1/README.md`)

Implementation details

Obtaining and verifying

Building with Autotools

Building with CMake (experimental)

Building on POSIX systems

Cross compiling

Building on Windows