3 ms·

> It consists of a mutual self-hosting Scheme interpreter written in ~5,000 LOC of simple C and a Nyacc-based C compiler written in Scheme. I’m trying to under

• avhon1 8y ago
  Ultimately, the goal is to compile a trusted copy of the gcc source code with a trusted compiler. This means that you need a trustworthy c compiler binary. In order for the compiler binary to be trustworthy, you have to either: 1. read and understand the machine code of the compiler's binary, or 2. have an observable compiler that can compile itself and also gcc (or at least better compilers that can compile gcc). This project uses approach 2 - an interpreter to interpret a compiler compiling it's own interpreter, and also a better compiler. Because the compiler is interpreted, you can potentially intervene and observe the compilation progress. (To watch a compiled binary of a compiler compiling itself, you would need a trustworthy debugger binary, which you can't bootstrap unless you can already trust some other compiler, or read+understand the debugger's binary.) Because the interpreted compiler can compile its own interpreter, and the interpreter interprets its own compiler, you can read and understand the source code of each, observe the interpreted compiler compile the interpreter, verify that the result is bit-for-bit identical to what you have been running, and now you have an executable compiler that you can trust. So, having a mutually co-hosting compiler and interpreter is a neat way of closing the compiler trust loop -- instead of always having to trust some earlier compiler, this allows you to establish trust (or distrust) of a pair of programs by running them on themselves and comparing what you get to what you started with. The fact that the interpreter is written in scheme is incidental to the fact that this project is intended for GuixSD, a linux distribution that uses a package manager written and configured in scheme. I assume scheme was chosen because 1. people who work on GuixSD like scheme, and are comfortable reading and writing it, and 2. scheme is a language with a good complexity/power ratio, minimizing the amount of code that has to be written, read, and understood in order to trust the compiler toolchain. The fact that the compiler is a c compiler is more important, because with a trusted c compiler you can compile (old versions of) gcc. With only a trusted X compiler (where X is not C or C++), you would need to add another step, a C compiler written in X. This would still be feasible, but adds more code to the already-enormous pile that needs to be trusted.
  • specialist 8y ago
    Nice explanation, thanks. "Trusting Trust" makes my head hurt. Has anyone considered bootstrapping on completely different stacks and then diffing the results? Maybe even using cross compilers. I can imagine hostile actors compromising various Intel, AMD, ARM chips. But I can't imagine those compromised targets all behaving the same way. Or going back in time to port their compromises to obsolete architectures.
    • csense 8y ago
      > Has anyone considered bootstrapping on completely different stacks and then diffing the results? Yes. [1] https://news.ycombinator.com/item?id=12666923 https://news.ycombinator.com/item?id=12666923