Bootstrapping a C compiler
In “Reflections on Trusting Trust”,
Ken Thompson shows that you can’t trust a program on your computer,
even if you “compiled it from source” yourself,
because your compiler is also untrusted.
It’s not good enough to recompile your compiler,
because for that you need another untrusted compiler.
The gcc currently on your machine has a very long compilation ancestry,
completely lost to the sands of time.
In response, people say “it’s turtles all the way down”.
The saying implies the stack is infinite, but it’s not.
A fix to the trust problem is to rebuild the stack of turtles yourself.
Imagine a project called “BootstrapCC”.
BootstrapCC begins with a handwritten ELF x86 program, b0.
The program b0 has a tiny job: to transform ASCII hex into binary.
b0 is our first compiler,
and ensures that the rest of our source can be written in readable ASCII.
b0 is small and trivial enough to be hand-verified.
BootstrapCC builds the binary b1 using b0,
then builds b2 using both of those, and so on.
Eventually, BootstrapCC produces bn,
a compiler for the subset of C used by the Tiny C Compiler.
From here, BootstrapCC can compile TCC,
from which most other things in existence can be built.
Along the way,
BootstrapCC creates successively higher-level languages:
an assembler, an IR, perhaps a stack-based language or a Lisp.
BootstrapCC does not rely on the lost 70-year lineage of modern programs.
BootstrapCC does rely on some things, such as Intel hardware and the OS.
But this is a much smaller footprint.
People are aware of the “trusting trust” paper,
but they treat it as a curiosity.
Some people are fanatical about compiling their programs themselves,
but don’t take it to its logical conclusion.
Lots of people love creating new programming languages,
but all of them are written in some other language.
There are even lots of people creating new compilers,
but all of them need compiling with something else.
BootstrapCC, sadly, is fictional,
and I’m not aware of any project which performs this the bootstrapping process I described here.
Update!: BootstrapCC exists!
It’s a wonderful-looking project called stage0,
which describes itself thus:
This is a set of manually created hex programs in a Cthulhu Path to madness fashion.
Which only have the goal of creating a bootstrapping path to a C compiler capable of compiling GCC,
with only the explicit requirement of a single 1 KByte binary or less.
Additionally, all code must be able to be understood by 70% of the population of programmers.
If the code can not be understood by that volume,
it needs to be altered until it satisfies the above requirement.
Tagged .
Similar posts
More by Jim
What does the dot do in JavaScript?
foo.bar, foo.bar(), or foo.bar = baz - what do they mean? A deep dive into prototypical inheritance and getters/setters. 2020-11-01
Smear phishing: a new Android vulnerability
Trick Android to display an SMS as coming from any contact. Convincing phishing vuln, but still unpatched. 2020-08-06
A probabilistic pub quiz for nerds
A “true or false” quiz where you respond with your confidence level, and the optimal strategy is to report your true belief. 2020-04-26
Time is running out to catch COVID-19
Simulation shows it’s rational to deliberately infect yourself with COVID-19 early on to get treatment, but after healthcare capacity is exceeded, it’s better to avoid infection. Includes interactive parameters and visualizations. 2020-03-14
The inception bar: a new phishing method
A new phishing technique that displays a fake URL bar in Chrome for mobile. A key innovation is the “scroll jail” that traps the user in a fake browser. 2019-04-27
The hacker hype cycle
I got started with simple web development, but because enamored with increasingly esoteric programming concepts, leading to a “trough of hipster technologies” before returning to more productive work. 2019-03-23
Project C-43: the lost origins of asymmetric crypto
Bob invents asymmetric cryptography by playing loud white noise to obscure Alice’s message, which he can cancel out but an eavesdropper cannot. This idea, published in 1944 by Walter Koenig Jr., is the forgotten origin of asymmetric crypto. 2019-02-16
How Hacker News stays interesting
Hacker News buried my post on conspiracy theories in my family due to overheated discussion, not censorship. Moderation keeps the site focused on interesting technical content. 2019-01-26
My parents are Flat-Earthers
For decades, my parents have been working up to Flat-Earther beliefs. From Egyptology to Jehovah’s Witnesses to theories that human built the Moon billions of years in the future. Surprisingly, it doesn’t affect their successful lives very much. For me, it’s a fun family pastime. 2019-01-20
The dots do matter: how to scam a Gmail user
Gmail’s “dots don’t matter” feature lets scammers create an account on, say, Netflix, with your email address but different dots. Results in convincing phishing emails. 2018-04-07
The sorry state of OpenSSL usability
OpenSSL’s inadequate documentation, confusing key formats, and deprecated interfaces make it difficult to use, despite its importance. 2017-12-02
I hate telephones
I hate telephones. Some rational reasons: lack of authentication, no spam filtering, forced synchronous communication. But also just a visceral fear. 2017-11-08
The Three Ts of Time, Thought and Typing: measuring cost on the web
Businesses often tout “free” services, but the real costs come in terms of time, thought, and typing required from users. Reducing these “Three Ts” is key to improving sign-up flows and increasing conversions. 2017-10-26
Granddad died today
Granddad died. The unspoken practice of death-by-dehydration in the NHS. The Liverpool Care Pathway. Assisted dying in the UK. The importance of planning in end-of-life care. 2017-05-19
How do I call a program in C, setting up standard pipes?
A C function to create a new process, set up its standard input/output/error pipes, and return a struct containing the process ID and pipe file descriptors. 2017-02-17
Your syntax highlighter is wrong
Syntax highlighters make value judgments about code. Most highlighters judge that comments are cruft, and try to hide them. Most diff viewers judge that code deletions are bad. 2014-05-11
Want to build a fantastic product using LLMs? I work at
Granola where we're building the future IDE for knowledge work. Come and work with us!
Read more or
get in touch! This page copyright James Fisher 2018. Content is not associated with my employer. Found an error? Edit this page.
TigYog
Kickabout