Rule 110

a cellular automaton proved in Bitcoin Script
waiting for the first generation…

What is Rule 110?

A row of cells, each one on or off, that rewrites itself over and over by the simplest rule you could write down. It turns out that is enough to compute anything.

A row of lights

Picture a row of lights. Each is on or off. Every tick, each light looks at exactly three things — itself, its left neighbour and its right neighbour — and decides whether to be on or off next. Every light decides at the same moment, and every light uses the same rule.

That is the whole machine. There is no memory beyond the row itself, nothing that counts ticks, and nothing that can see further than one cell away.

Draw each new row underneath the last one and you get the picture behind this box: the row runs across, and time runs down. Every horizontal line on that diagram is one generation of the row. Every vertical position is one cell, living out its life.

Eight questions, eight answers

A cell can only see three lights, and three lights can only be in eight arrangements: all off, one on, two on, and so forth. So a rule is nothing more than eight answers — one for each arrangement. On, or off.

Eight yes/no answers is eight bits, which is a number from 0 to 255. That is not a way of encoding the rule; it is what the rule is. There are 256 rules of this kind, and that is all of them, forever.

Rule 110 is the rule whose eight answers, written out, spell 110. Click any answer below to change it and watch the picture change with it.

This is rule 110 01101110

Try 0 — everything dies. Try 255 — everything floods. Try 90, and you get a perfect fractal that never surprises you again. Most of the 256 do one of those three things: die, freeze, or dissolve into noise.

Why this one is different

Rule 110 does none of the three. It settles into a striped background that repeats forever, and then things move across that background. Compact little patterns slide left and right at different speeds, surviving indefinitely, crossing an otherwise regular field. They are usually called gliders.

And when two gliders meet, something happens. They pass through each other, or they annihilate, or they collide and leave a different glider behind. Which one depends on what met what, and where.

That is the whole reason this rule is interesting. A glider is a thing that carries information from one place to another. A collision is a thing that acts on information. Once you have both, you are no longer describing a pattern — you are describing a machine.

Why it can compute anything

Matthew Cook proved it. The argument runs by translation: take any computer program, rewrite it as a Turing machine, rewrite that as a thing called a tag system, rewrite that as a stream of gliders fired into a Rule 110 row. Set the row up that way and let it run, and the collisions carry out the program. The answer is in the pattern when it stops.

So there is no program you could write, in any language, on any machine, that could not be run instead as a Rule 110 starting position. It is a universal computer whose entire specification is eight bits.

The chain of translations, and the fine print

Cook's construction goes Turing machine → 2-tag system (Cocke and Minsky) → cyclic tag system → gliders in Rule 110. Announced in 1998, published as Universality in Elementary Cellular Automata, Complex Systems 15(1), 2004.

Two honest caveats. First, the construction needs an infinite row whose background is that specific repeating stripe in both directions — it is not started from a finite blob on an empty line. Specialists call this weak universality, and it is the standard result for Rule 110. Second, Cook's original emulation was exponentially slow. Neary and Woods brought it down to polynomial time in 2006, and showed that predicting Rule 110 is P-complete — which is a formal way of saying there is no shortcut: to know what the row looks like at generation a million, something has to do the work.

Rule 110 is not alone: 124, 137 and 193 are the same rule reflected and inverted. But among the 256 it is the simplest thing anybody has proved universal in one dimension with two states and three neighbours. There is nothing left to take away.

What that means for this page

Not that this deployment is computing anything. It is a ring of N cells — finite, and wrapped end to end, so the leftmost cell's neighbour is the rightmost one. A finite ring has finitely many possible rows, so sooner or later it must repeat one and cycle forever. That is a fact about rings, not a defect.

What is running here is the rule itself, one generation at a time, with every single bit of it proved on the Bitcoin ledger. The pattern is the point; the proof is the point. Universality is just the reason this particular rule is worth the electricity.

Inside one transaction

Every cell in the ring is a coin. The coin's spending condition is the rule itself — so the only way to move a cell forward is to be right about it.

The one-sentence version

A Bitcoin coin is not really a coin, it is a locked box with a condition on it. Normally the condition is "show me a signature from whoever owns this". Here the condition is: "show me the next row, and I will check that my own bit of it is what Rule 110 says it should be."

So advancing one cell by one generation means spending its coin. If the bit being claimed is wrong, the spend is not merely dishonest — it is invalid, the same way a forged signature is invalid, and no node on the network will carry it. The rule is not enforced by this program. It is enforced by everyone.

N cells means N coins, N locks and N transactions per generation, each one on its own unbroken chain going back to the first row.

The coin carries the whole row

A lock in Bitcoin is a small program, and this one has the current row attached to the end of it as plain data. The row is packed one bit per cell: cell i lives in byte i÷8, at bit position i mod 8, counting from the least significant end. For this ring that is N bits in N/8 bytes.

Every one of the N coins carries the entire row, not just its own bit. A cell has to see its neighbours to apply the rule, and the only thing it can see is what it is holding.

Where exactly the row sits, and why OP_RETURN is not a burn

The lock ends with OP_RETURN followed by a length byte and the row. Ordinarily OP_RETURN means "this output is unspendable, the rest is data" — but here it is the compiler's boundary marker between the code and the state, sitting at the end of a script that is very much spendable. The bytes after it never execute. They are still readable by the code above, which is what lets a lock carry memory at all.

For a 256-cell ring the tail is literally 6a 20 <32 bytes of row>: 6a is OP_RETURN, 20 is 32, and then the row.

Six numbers make a cell

Every cell in the ring runs the same compiled program. What makes one of them cell 3 rather than cell 200 is six numbers baked into it: for each of its three neighbours, which byte to read and what to divide by.

Reading a single bit out of a row, in a language with no bit indexing, comes out as ordinary arithmetic: take the byte, divide by a power of two to shift the bit you want down to the bottom, then take the remainder mod 2.

of a N-cell ring

The ring wrap is in those numbers and nowhere else. Cell 0's right neighbour is the last cell of the ring purely because cell 0's constants say so. There is no wrap-around check anywhere in the program, no branch, no special case for the ends — just a different pair of numbers, which costs nothing.

Why a zero byte gets glued on first

Bitcoin's numbers are little-endian sign-magnitude: the top bit of the last byte is the sign. So a lone byte between 0x80 and 0xFF would be read as negative, and half of all possible row bytes would produce a nonsense neighbourhood. Gluing a zero byte on the end before converting forces the value into a plain 0–255. It is one OP_CAT, and without it the automaton would be quietly wrong exactly half the time.

The rule table is one number

Recall that the rule is a number, and that neighbourhood (l, c, r) is answer number 4l+2c+r. So looking up the rule is looking up one bit of the number 110 — the same divide-and-take-the-remainder move as before:

next = (110 / 2^(4l + 2c + r)) % 2

The whole transition table of the automaton is the literal 6e sitting in the lock. Deploy the identical program with 1e instead and you have Rule 30.

How it raises 2 to a power without branching

There is no exponentiation opcode, and an eight-way OP_IF tree would be both large and slow. But l, c and r are each 0 or 1, so the power factors exactly:

2^(4l+2c+r) = 2^4l · 2^2c · 2^r = (1+15l)(1+3c)(1+r)

Three multiplications and two additions, no branch, and the largest number in flight is 128. The rule lookup in the deployed script contains no conditional of any kind.

What the lock actually insists on

Three things, in order:

  1. the row being handed to it is the right length;
  2. its own bit of that row is the answer the rule gives for the three bits it just read;
  3. the coin this spend creates is this same lock again, carrying the new row.

The third is what makes it a chain rather than a one-off. Without it you could prove one correct step and then walk away with a coin that had nothing to do with the automaton. With it, the only thing a cell's coin can ever become is the same cell, one generation later.

How a lock can see the transaction spending it

Here is the difficulty. Bitcoin Script cannot look at the transaction that is spending it. It has no opcode for "what are my outputs". So how can a lock demand anything about the coin being created?

The trick is to make the spender supply that information, and then make it impossible to lie about it. The spender pushes a description of the spending transaction as an argument. The lock then takes those bytes and builds a signature out of them, using a private key of 1 and a fixed, published number for the random nonce — no secrets, just arithmetic on constants everyone knows. Then it checks that signature the ordinary way.

A signature check only passes if the signature matches the transaction the node is actually validating. So it passes only if the bytes the spender pushed really are a true description of this spend. Push anything else and the check fails. The lock has, in effect, made the network read its own transaction back to it.

From there it is easy. That description contains a hash of all the outputs, so the lock rebuilds the output it wants — its own code, with the new row glued on — hashes it, and demands the two match.

The mechanism in full

The pushed description is the BIP-143 sighash preimage: version, the transaction's inputs and outputs in hashed form, the outpoint being spent, its value, and the scriptCode — a copy of the lock itself, state included. The lock computes s = (hash256(preimage) + r)·k⁻¹ mod n with a fixed nonce k = 2 (so r is the x-coordinate of 2G, the constant c6047f94…09ee5 you can see in the script), packs it into DER, and runs OP_CHECKSIGVERIFY against the public key for private key 1 — which is just the generator point G, 0279be667e…16f81798. OP_CHECKSIG hashes the real transaction itself, so it agrees only if the pushed bytes hash to the same thing.

Immediately afterwards the script re-reads the last four bytes of the preimage and requires them to be 0x41. That pins the signature hash type: without it a spender could choose a mode that blanks out the outputs field, and the covenant would be checking its continuation against nothing.

This construction is why these scripts need the Chronicle upgrade. Normalising the signature to its low form uses OP_2MUL, an opcode that was disabled for years. A node validating under the older Genesis rules rejects every one of these transactions with "attempt to execute disabled opcode OP_2MUL".

The key that unlocks it is not a key

Nothing signs anything here. The unlocking side of a cell transaction is six pushed values and not one opcode:

codePart | nextRow | changePKH | changeAmount | newAmount | txPreimage

The code, the row being claimed, where the leftover money goes, how much, how much stays in the cell, and the description of the transaction. There is no signature and no password. Anyone at all can advance a cell — they just cannot advance it wrongly.

The real thing

All of the above compiles to 916 opcodes. That number is the same whether the ring has 8 cells or 256; only the row it carries gets longer. Here is the actual lock for cell 1 of an 8-cell ring, with the machinery elided and the automaton left in full:

  0  OP_DUP
  1  OP_CODESEPARATOR        everything below is what the description commits to

    … 523 opcodes that rebuild a signature from the pushed
       description and check it — the part that makes the lock
       able to see its own transaction …

525  OP_VERIFY
526  OP_DUP OP_SIZE OP_4 OP_SUB OP_SPLIT OP_NIP OP_BIN2NUM
533  41
534  OP_NUMEQUALVERIFY       pin the hash type, so no field can be blanked

    … cut the row back out of the description …

630  OP_DUP OP_FALSE OP_4    left neighbour: byte 0, divide by 4
641  OP_SPLIT OP_NIP OP_SWAP OP_SPLIT OP_DROP
646  00 OP_CAT OP_BIN2NUM    the zero byte that keeps it positive
649  OP_SWAP OP_DIV OP_2 OP_MOD

655  OP_FALSE OP_2           itself: byte 0, divide by 2
666  OP_SPLIT OP_NIP OP_SWAP OP_SPLIT OP_DROP
671  00 OP_CAT OP_BIN2NUM
674  OP_SWAP OP_DIV OP_2 OP_MOD

681  OP_FALSE OP_TRUE        right neighbour: byte 0, divide by 1
691  OP_SPLIT OP_NIP OP_SWAP OP_SPLIT OP_DROP
696  00 OP_CAT OP_BIN2NUM
699  OP_SWAP OP_DIV OP_2 OP_MOD

704  OP_TRUE OP_15 OP_6 OP_ROLL OP_MUL OP_ADD   1 + 15l
710  OP_TRUE OP_3 OP_5 OP_ROLL OP_MUL OP_ADD    1 + 3c
716  OP_MUL
717  OP_TRUE OP_ROT OP_ADD OP_MUL               × (1 + r)  =  2^(4l+2c+r)

722  6e                      110. the entire rule table.
723  OP_SWAP OP_DIV OP_2 OP_MOD                 the answer

730  OP_FALSE OP_2           now read the same bit out of the CLAIMED row
740  OP_SPLIT OP_NIP OP_SWAP OP_SPLIT OP_DROP
745  00 OP_CAT OP_BIN2NUM
748  OP_SWAP OP_DIV OP_2 OP_MOD
753  OP_NUMEQUALVERIFY       — and they had better match.

    … rebuild this same lock carrying the new row, add the
       change output, hash the pair …

896  OP_HASH256
897  OP_6 OP_ROLL OP_SIZE 28 OP_SUB OP_SPLIT OP_NIP 20 OP_SPLIT OP_DROP
907  OP_EQUAL                must equal the outputs the network sees

914  OP_RETURN               end of code
915  02                      the row: cell 1 is alive

Line 722 is worth a second look. That single byte is the entire transition table of the automaton, sitting in a lock on a coin.

Reproducing this yourself

The contract is contracts/Cell.runar.go in this repository — 87 lines that are simultaneously the source compiled to Bitcoin Script and ordinary runnable Go, so go test ./contracts executes the same logic natively. internal/cellscript compiles it and binds the six constants per cell. The listing above is the output of cellscript.Compile(8, 110) then LockingScript(1, row), disassembled.

What is proved, and what is not

This is the part it would be easy to overstate, so plainly:

Each transaction proves exactly one bit — its own. Cell 3's lock reads three bits out of the row it holds, computes the rule, and checks bit 3 of the row it is handed. It does not look at bit 4. It will accept a next row whose every other bit is nonsense, so long as bit 3 is right. Cell 4 will do the same for bit 4.

Nothing in Bitcoin Script forces the N chains to be handed the same next row. There is no opcode anywhere comparing one cell's row to another's, and no shared output they all have to agree on. That independence is precisely what lets a whole generation be proved in parallel, and this is what it costs.

So a complete correct generation is proved by N transactions plus the claim that all N were handed the same row. The first half the network enforces. The second half it does not.

That second half is checkable by anybody, though, and not on trust: every cell's row is public, sitting in its lock, and the row a cell's covenant actually read is recoverable from the transaction's own unlocking data. The repository ships rule110 audit, which re-derives every row from its predecessor and compares it against what each covenant demonstrably saw. That check is real, and it is cheap. It is just not something a miner would reject a transaction for failing.