Stage Two

Stage Zero

Everything the Sabik runs is descended from four hundred and six bytes.

They are engraved on a nickel plate in the Toolchain Office, in hexadecimal, forty-one characters to the line. A person can read them. A person can type them back in, and people do, once a year, on the anniversary, because the point of the plate is that it needs nothing but eyes and hands. Those four hundred and six bytes are a program that reads hexadecimal and writes the bytes it names. It cannot add. It has no concept of a variable. What it can do is accept a slightly larger program, written in hexadecimal, which does understand labels — and that one accepts a larger one still, which understands functions, and so on up the ladder, twelve rungs, until you reach something you would recognise as a compiler, and then the compiler compiles itself and the ladder is thrown away.

I have run the ladder end to end four times in my career. It takes nine days. Nobody enjoys it.

The reason we keep the plate is an old argument, made on Earth before the Sabik was cut, and never answered. Suppose someone alters a compiler so that when it recognises the source of a login routine, it inserts a back door — and, further, so that when it recognises the source of itself, it reproduces the alteration in the new binary. Then remove the alteration from the source. The source is clean. Every subsequent compiler is built from clean source. Every subsequent compiler is poisoned. You can read the source for a hundred years and find nothing, because there is nothing in the source to find. The lie lives in the binary and copies itself forward, silently, for as long as the lineage continues.

Our lineage has continued for two hundred and six years.

Stage One

Marit Løvaas is eighty-one and keeps the Witness in a cabinet in the agricultural spine, because that is where they gave her a room in 2178 and she has never seen a reason to move.

The Witness is a compiler. It accepts the same language as ours and it is, by every measure anyone cares about, worse. It is about sixty times slower. The code it emits is roughly twice the size and runs at perhaps a third the speed. It has no optimiser at all; where our compiler reasons about the lifetime of a value, the Witness simply writes the value to memory and reads it back, every time, forever.

None of that is the point. The point is its parentage. In 2141 the Second Reading took the language specification — the document, not the implementation — into a sealed compartment and wrote a compiler from it by hand, in the bootstrap dialect, over forty-one years, without once consulting our source. Four hundred and ten thousand lines. Six of the original eleven died before it self-hosted. It has never been used to build anything the ship depends on. It exists to be different.

Marit’s grandmother was one of the six.

“You want to borrow it,” she said.

“I want to run the check.”

“You know it’s never come out clean.”

“I know it’s never been run properly.” That was the truth and she took it well. Twice before, in 2263 and in 2301, someone had tried the comparison and got a mismatch, and both times the finding had been written up as inconclusive and filed, which is what you write when you do not understand your own instrument.

The Procedure

It is a small procedure. You can state it in four lines and I will, because people are always surprised that it is not more.

Let s be the source of our compiler, which anyone may read. Let c be the binary in service — the one that built every piece of software aboard, and that was itself built by its predecessor, back and back to the plate.

1. Compile s using the Witness. Call the result stage one.
2. Compile s using stage one. Call the result stage two.
3. Compare stage two with c, byte for byte.

That is all of it. The trick is in the second step, and it is worth being slow about, because everyone I have ever explained it to nods too early.

Stage one is a terrible compiler. It is slow and bloated, because it was built by the Witness, and the Witness builds everything slowly and bloatedly. But stage one is not being judged on its own body. It is being judged on its behaviour, and its behaviour is whatever s says it should be — because stage one is what s means. So when stage one compiles s, the output it produces is the output that s, faithfully executed, produces for s. Which is exactly what c is supposed to be.

If c carries a lie that is not written in s, stage two will not carry it, and the bytes will differ.

For the check to fail to detect a poisoned c, the Witness would have to carry the same lie, expressed in a form that survives translation into stage one and out again — a compiler written by hand, in a sealed room, over forty-one years, by people whose entire motivation was distrust, would have to be corrupted in a manner precisely coordinated with the corruption of ours. It is not impossible. It is a different order of unlikely, and it is the only order of unlikely we are able to buy.

The Instrument

We spent eleven weeks not running the check.

The first thing we did was compile s with c twice, on the same machine, and compare the two outputs. They differed. They differed in eight hundred and sixty places.

That was not a back door. That was our compiler laying out its symbol table in the order the entries fell out of a hash table, and the hash was seeded from a memory address, and the address moved between runs. There were four other sources: an embedded build timestamp; the absolute path of the source directory, baked into an error string; the order in which the linker saw object files, which came from a directory read that was not sorted; and eleven bytes of padding inside a header structure that nobody had ever initialised, and which therefore contained whatever had been on the stack a moment earlier.

None of it mattered to the running of the ship. All of it made the question unaskable. A comparison is only worth making between things that are supposed to be identical, and until those eleven weeks were done, no two builds of our compiler had ever been supposed to be identical. That is why 2263 and 2301 were filed as inconclusive. They were not inconclusive. They were unasked.

We sorted the directory read. We fixed the timestamp to the epoch of the ship’s commissioning. We seeded the hash from the symbol’s own text. We initialised the padding. Then we compiled s with c forty times, on nine machines, and got one file.

Then we borrowed the Witness.

Stage one took six days. Stage two took eleven hours. The comparison took under a second, because comparison always does; it is the cheapest thing in the world and it is the reason for all the rest of it.

They matched.

Compare

Councillor Dunn asked me to come and say it to the chamber, and I said it, and then he asked me to say it again in a way that could go on the ship’s board, and that is where we stopped agreeing.

What he wanted was: the ship’s software has been proved safe.

What is true is: the binary we are running is the program its source describes.

He said that was the same thing said twice.

“No. Suppose I hand you a book and tell you I’ve verified the printing. Every letter on every page matches the manuscript, exactly, no substitutions.” I had thought about this on the way up. “I haven’t told you the book is true. I’ve told you nobody interfered between the manuscript and you.”

“Then what have we spent eleven weeks on?”

“Reading. We’ve spent eleven weeks making it possible for reading to be worth anything.”

He did not like it, but he is not a stupid man, and he understood before I finished that the second half was worse than the first. One million four hundred thousand lines of source, which anyone may read, and which, until the eleventh of March, nobody had any reason to bother reading, because a clean reading proved nothing about the thing that actually ran.

Now it does.

The Reading was chartered in the autumn. Four hundred lines a day, two readers who do not confer, a third who arbitrates where they disagree. At four hundred lines a day it is a nine-and-a-half-year undertaking, and then it begins again, because the source keeps changing. There is a roster. There is a waiting list for the roster, which I did not expect and do not fully understand.

Marit came to the first session. She sat at the back and read her four hundred lines with everybody else and found nothing, and went back down to the agricultural spine, where the Witness sits in its cabinet, having done the only thing it was ever built to do, and having done it once.