Coin Brief ENDE

jam-lean runs Polkadot's JAM Gray Paper in Lean 4 and joins the conformance fuzzing

Many separate teams are building JAM clients, all working from a single written specification called the Gray Paper, and no reference client will ever exist, the developer ascrivener wrote on the Polkadot forum on 16 November. Their answer is jam-lean: a model of Gray Paper v0.8.0 in the Lean 4 language that can be executed, is measured against the official test vectors, and lets Lean's kernel verify theorems about compiled JAM services.

The post explains what this adds. Today, conformance is tested by a fuzzer that feeds blocks to each client one at a time and checks the resulting state root against Parity's PolkaJam. Those expected values therefore come from one client, and the fuzzer's documentation itself warns against treating it as a reference. jam-lean is derived only from the paper's equations, so when it disagrees with a client it can point to the equation it used. Its opcode and gas tables are generated from the paper's LaTeX source, and the author says no other client was consulted.

The model covers Appendix A - the PVM's decoding, instructions, memory, host calls and gas - and the protocol around it, including block import with every section-level transition. Its results: 364 of 364 PVM programs, 44,860 of 44,860 basic-block gas costs, every state-transition vector, and 61 of 63 accumulation vectors, the two misses following a rule introduced after v0.8.0. The proofs concern deployed bytes rather than source code. For the author's Witness service, refine returns exactly the encoded "bad payload" rejection for any malformed payload when given at least about 4.1 x 10^7 gas, a proof re-checked by a second, independent kernel. For Parity's Bootstrap service, the heap allocator is proved against a functional model and a first milestone for refine is proved, with the remaining assumptions listed.

To serve as a fuzzing target, the model also needed the cryptography that the Gray Paper imports from elsewhere. Ed25519, the Bandersnatch VRFs and the ring commitment over BLS12-381 are now implemented in plain Lean and checked against published vectors; a ring VRF proof takes about 0.2 seconds per ticket. With signing in place, jam-lean can build valid v0.8.0 blocks and send them to other clients. On the fuzzer's sample sessions it matches PolkaJam block for block, including all 97 responses in the session with forks and invalid blocks.

jam-lean runs Polkadot's JAM Gray Paper in Lean 4 and joins the conformance fuzzing
jam-lean runs Polkadot's JAM Gray Paper in Lean 4 and joins the conformance fuzzing — Coin Brief

Why it matters

Without a reference client, any dispute between JAM implementations ends with someone reading the paper. A model that runs, cites the equation behind each result and is tested against the same vectors as the clients turns that reading into something a machine can repeat.