An Instruction Table Is History

On 8 January 2019 I committed the first draft of FATE's data representation to the æternity node. The file opens with a comment I wrote myself:

%% First draft of FATE data representation.
%% Very likely to change.

The serialization module beside it is blunter:

%% TODO: This code is not production ready yet.
%% TODO: The FATE side of data is not set at all yet and will
%% probably change.

Lima, the protocol upgrade that shipped FATE, activated in November. Ten months separate that comment from a format that can never change again.

FATE, the Fast æternity Transaction Engine, is the virtual machine that runs smart contracts on the æternity chain. I designed it. I learned the EVM by implementing it in Erlang, a machine we called AEVM, before we designed the one that replaced it. The EVM was modeled after a computer, with stack slots, memory addresses, a word length, and arithmetic that could overflow or silently fail; the design of what replaced it is a post of its own. The instruction table and the git history are public, along with every mistake in both. This post reads them as a record of what a chain freezes at genesis.

Why nothing can move

The first commit states the property that makes everything after it permanent. The serialization has to satisfy one rule: exactly one byte sequence for each unique value.

Canonical encoding is a consensus requirement. Two implementations that produce different bytes for the same value compute different hashes, and the chain forks. The encoding is therefore part of what the chain is, and no later version can revise it.

Opcodes work the same way. An instruction's number is the byte sitting in deployed bytecode. Renumber it and every contract already on the chain means something else. You can add instructions. You cannot reorder them, remove them, or (as I will get to) change what they cost.

The table as stratigraphy

FATE's opcode table is a record of history. Arithmetic sits where you would expect. ADD is at 0x14, followed by SUB, MUL, DIV, MOD and POW.

The bitwise operations on integers sit at 0xab through 0xb0, roughly a hundred and fifty opcodes later. They also arrive after the complete BLS12-381 pairing suite at 0x81 to 0x98. Integer bit shifts landed later than elliptic curve pairings, though on a whiteboard they would be adjacent to the arithmetic.

Opcode numbers record the order in which the world asked for things. The table keeps that order for as long as the chain runs.

What cannot be taken back

The git log is a list of things that stopped being fixable.

On 1 November 2019, days before launch: "Disable unused INT_TO_ADDR operation". The instruction is disabled. Opcode 0x43 remains listed and spent.

On 27 June 2019: "DECA should be dec, not inc". A decrement instruction that incremented, caught four months before Lima. Caught four months later, it would have been correct behavior forever, and every implementation since would have reproduced it.

On 6 November 2019: "Add height check for maps gc bug fix". The next day: "Updated height for fix to take effect". A garbage collection bug in nested store maps could not simply be fixed, because mined blocks already depended on the broken behavior. The fix had to be gated on block height, and then the height had to be revised.

On 31 January 2020: "Remove buggy code kept for compatibility reasons". That commit message contains the whole argument.

In April 2021, on one day around the Iris upgrade: "Well defined compare from IRIS", "Restore old behaviour before IRIS", and "Load map ordering on node start". Map ordering was undefined. We defined it going forward, and the undefined version stays canonical below that height. The node loads the historical ordering at startup so it can agree with its own past.

There is a commit called "Split aefa_stores for lima/iris". The store implementation forked in two, and both live on, because both are correct somewhere in the chain.

Gas freezes as well

Gas costs freeze on the same terms as the instructions that consume them.

Through the autumn of 2019 the log is one long run of discovering unpriced operations: state gas, chain-object gas, memory gas, gas for bytes.concat and bits operations, gas for the size of log entries, gas for checking delegation signatures. We found them one at a time.

We benchmarked, we were careful, and the numbers were still wrong. We were pricing operations for workloads that did not exist yet, on hardware that did not exist yet. The payload shapes we assumed differed from what real contracts produced, and the machines moved underneath us. The costs became good approximations once there was chain data to measure.

By 2021 that produced a recalibration: traversal gas, gas for typerep size, gas for remote calls, and a guard so the new traversal gas applied only from Iris. One line from that batch stays with me: "0 should have a non-zero int_size". Zero has no bits set, so under the cell-counting rule it was free.

The old numbers stay. BLOCKHASH costs 1000 gas under Iris and 10 under Lima. SPEND is 5000, then 100. The oracle instructions drop from 10000 to 100. The same opcode carries two prices, both permanently correct at different heights.

Any implementation that validates the chain from genesis carries the entire pricing history. FATE has a specification per block height.

This does not stop. In 2026 the commits are still "Size-proportional FATE store-read gas at Arcus", with a placeholder for the protocol version after it, and "Gas calculation coverage: protocol-dimension every consensus gas site". Every gas site, indexed by protocol version, seven years on.

The mechanism is worth stating plainly. Learning the right cost requires running the chain, and running the chain is what makes the wrong cost permanent.

What we did about it

We left room. The opcodes run contiguously to 0xb5, then stop until 0xfa, where DEACTIVATE, ABORT, EXIT and NOP anchor the top of the byte. Sixty-eight slots sit reserved in the middle.

The same instinct appears in the first commit, before there were any opcodes at all. The serialization tag scheme already has slots commented FREE.

In November 2021 one commit landed in that gap: "Implement bitwise operations, Address.to_bytes and Crypto.poseidon in FATE". The reservation paid off two years later, and there is still room.

What cannot be first class

Sixty-eight slots remain, and two things I wanted are still outside the machine. Layer 2 handling, and non-fungible tokens.

Both work on æternity today. Tokens live as a convention inside contract code, the way ERC-721 does on Ethereum, and the state a layer 2 arrangement needs can be managed the same way. What neither gets is support from the virtual machine.

FATE's first-class objects are the chain's first-class objects: accounts, oracles, names, channels and contracts. The instructions operate directly on the state tree, with types checked by the machine, which is what keeps the bytecode small and the failure modes clear. A convention written in Sophia gets none of that. It re-implements ownership and transfer in contract code, pays gas for work the VM could have done in one instruction, and carries whatever bugs the contract author wrote.

The chain's set of first-class objects was settled before genesis, and no reserved opcode can extend it.

Three kinds of developer in one log

Going back through this history for the article turned up something I have written about elsewhere. Mike Williams sorts developers into Monkeys, Tigers and Elephants, by whether they prototype, productionize or maintain. I am a Monkey, and the January 2019 commits show what that looks like: a data representation labeled likely to change, and a serialization module marked not production ready.

The rest of the log holds the other two. Through the middle of 2019 someone picks up the prototype and handles the cases I skipped, the error paths, the type checks on remote calls, the reentrancy guards. Someone else is still there in 2025, gating fixes on block heights and carrying two store implementations because both are correct somewhere in the chain. The three types have a post of their own, Developer Types.

What to take from this

If you are designing a virtual machine for a chain, the opcode gap is the easy part. Reserve one, anchor your terminators at the top of the byte, and you have room for operations you have not thought of yet.

The harder work happens before genesis. Decide what your machine is about, since the state tree objects and the encoding are the parts you can never revise. Write down what a contract should be able to reason about in five years, then check whether your first-class objects can express it.

Gas deserves the same attention with less confidence. Assume your first numbers are wrong, and design the pricing so it can be versioned by protocol from day one rather than retrofitted after the first recalibration.

The same three developer types turn up in my novel, The Chain, where an engineer under pressure does what a monkey knows how to do and reaches for a lever he can pull without understanding all of it. I wrote that before I went back through this log. Why the technology in it had to be right is a post of its own: Why I wrote a tech thriller. The book also carries an appendix with an instruction table and a note that a chain freezes whatever history it launched with. The plot turns on a property of frozen instruction tables. I am not going to tell you which one.