Hacker News Reader

Comment by ajnin | Hacker News Reader

> The idea here is to use a minimal wasm binary as a stage1 kernel that is committed to source control and therefore can be used to build any commit from source. We provide a minimal WASI interpreter implementation that is built from C source, and then used to translate the Zig self-hosted compiler source code into C code. The C code is then compiled and linked, again by the system C compiler, into a stage2 binary. The stage2 binary can then be used repeatedly with zig build to build from source from that point on.

1/ Wouldn't that be considered "cheating" to basically commit precompiled compiler binaries to source control ?

2/ I don't understand how that solves the "features need to be implemented twice" problem. Wouldn't you need to implement new Zig language features into that WASM kernel whenever they are used in the Zig compiler source ?

View on HN

1. Yes it is cheating. That is the downside of this approach. Contributors to Zig and users of Zig don't care about such cheating, but distribution maintainers such as Debian Developers do (rightly) care. This decision is a tradeoff that favors contributors and users at the expense of system package maintainers. I am counting on a third party implementation of Zig to arise someday and solve the bootstrapping problem for system package maintainers. But in the short term, it's more important to prioritize the needs of users and contributors.

2. Whenever this happens, the contributor runs `zig build update-zig1` and commits the updated wasm kernel to the repository.

Perhaps the distro devs could maintain their own golden WASM blobs that they compiled themselves and thus trust. Could be the same process as SecureBoot / package signing keys.

Can the stage1 wasm binary be reproduced by the stage2 or stage3 executable? Aside from a "trusting trust" type of attack that seems fine, and every modern distro relies on some bootstrap binary for C compilers anyway (usually older versions of them), so it wouldn't be that much different of a bootstrapping problem than bootstrapping GCC itself. (See the GNU Mes project which attempts to bootstrap from just a very small hex interpreter)

>Can the stage1 wasm binary be reproduced by the stage2 or stage3 executable?

Yes, per (2) in https://news.ycombinator.com/item?id=33915480

>and every modern distro relies on some bootstrap binary for C compilers anyway (usually older versions of them), so it wouldn't be that much different of a bootstrapping problem than bootstrapping GCC itself.

Yes, that's exactly my point. The zig-wasm-bootstrap package could just be a Build-Depends of the zig package.

But because of trusting trust, we cannot prove the security of the blob.

This is a brilliant idea which I hadn't thought of before. If the Debian folks are happy with this approach, this could save us a lot of trouble!

It's what OpenJDK does. OpenJDK releases very quickly nowadays, and requires version N or N-1 to build version N. If that works for OpenJDK, presumably it should work for Zig.

Does it really prevent the Ken Thompson attack though? Well, it means the attacker has to be a committer to keep the attack from eventually breaking, or that the attack will eventually break.

You could use a different compiler written by someone else to increase the amount of work and coordination needed by the attacker to pull it off, but this is not reasonable to require for new (or new-ish) programming languages -- it'd more likely squelch programming language research and development than aid it.

There are multiple Java implementations, but does Debian build the OpenJDK with non-OpenJDK implementations? Would that eliminate the trusting trust problem?

> Does it really prevent the Ken Thompson attack though? Well, it means the attacker has to be a committer to keep the attack from eventually breaking, or that the attack will eventually break.

If the attack is sufficiently well squirreled away in code that rarely changes then that "eventually" could be a very long way away.

However, I imagine the risks of Trusting Trust are a tad overblown considering how much other lower-hanging fruit there usually is to attack through. For example just sneaking in subtly broken commits containing security vulnerabilities.

That's my take as well.

That's essentially how OpenJDK's bootstrapping works.

Well you could project the wasm back to C with wasm2c, package maintainers can continue the illusion that they are bootstrapping from C.

You clearly think of package maintainers as stupid and I can assure you that we are not.

I do not think that at all. But I have witnessed tortured vivisection of codebases that were never meant to undergo that procedure, all to satisfy a fantastical taxonomy. In that regard, I am triggered, yes.

Is the argument you were alluding to that a distro wouldn't consume Zig until it can be bootstrapped by two compilers to show it hasn't been the victim of the Trusting Trust attack?

Oh sure, I won't deny that package maintenance has caused plenty of issues for upstream authors [1].

Yes that's right. More specifically they have rules about generated files. They are not allowed. Generated files such as binary blobs must be produced as part of the build process of the package.

[1]: https://www.youtube.com/watch?v=stChOsejLEQ

Distros like to compile from source, but generally don't mind bootstrapping off pre-built compilers not in the source package, since any other method means basically giving up on packaging software altogether.

The only exception that I am aware of is GNU Guix and the Bootstrappable Builds project, which aims to build a full distro starting with ~512 bytes binary, they have gotten quite far already.

https://bootstrappable.org/

Following that site, I find https://www.gnu.org/software/mes/

> GNU Mes is a Scheme interpreter and C compiler for bootstrapping the GNU System.

https://guix.gnu.org/en/blog/2020/guix-further-reduces-boots...

> The Scheme interpreter is written in ~5,000 LOC of simple C, and the C compiler written in Scheme and these are mutual self-hosting. Mes can now be bootstrapped from M2-Planet and Mescc-Tools.

This is important work these folks are doing. I'd love to see some distros pick it up and periodically show that they can start with some files on disk and a ten-key. USB drive and a UEFI console?

They got a lot further than GNU Mes now. The process starts with stage0, ~512 bytes of machine code. Their live-bootstrap project is another focus of work. Another thing being worked on is using the Fiwix kernel as a step towards getting Linux bootstrapped. Also higher-level languages like Ocaml are getting bootstrapped.

https://github.com/oriansj/stage0 https://github.com/fosslinux/live-bootstrap/ https://www.fiwix.org/ https://github.com/Ekdohibs/camlboot

I'm not aware of any overview/documentation of the entire process though, best check out their site and wiki and join the IRC channel.

If Zig was at version 19, like OpenJDK, then Zig could just not commit stage0 and instead say "download stage0 from ... or install from your friendly distro pkg repos".

Eventually, presumably, Zig will get to that level of maturity. In the meantime, to me, it seems like not-a-big-deal to commit a very small stage0.

It's only marginally less ugly than blessing one arch (like arm or x86) and running the bootstrapping with an emulator.

Don't get me wrong, I do like it more, but I realize it's mostly an aesthetic thing. Logically and functionally it's like if you just blessed a build jsing cosmopolitan libc or something like that.

> 1/ Wouldn't that be considered "cheating" to basically commit precompiled compiler binaries to source control ?

No, absolutely not. This is how Virgil bootstrapping works by design. There are 5 pre-compiled compiler binaries in the repo. The repo is completely self-contained so that any revision at any point can compile itself from source, except the very earliest versions that needed an interpreter in another language. The stable binaries are updated infrequently, about once every 3-6 months.

This would definitely be considered "cheating" by the Bootstrappable Builds folks, who build everything from source, including generated binaries and generated code files.

https://bootstrappable.org/

They can consider it cheating, but they themselves use previously-compiled compilers to build, do they not? The only difference is that their previously-compiled compilers are not in the same source repositories as the compilers they are used to build. That is no guarantee that the Thompson attack is defeated.

The best way to defeat the Thompson attack is to insist on multiple distinct implementations -by different authors- of the implementations of each programming language, and even this only makes Thompson attacks a lot harder to pull off -but not impossible- for determined attackers. But one cannot insist on multiple distinct implementations for every new programming language, as that would simply make new programming language R&D to be prohibitively expensive.

Zig could, and arguably should switch to an OpenJDK-style bootstrapping system to please the distros. Essentially this means that using new language features in the Zig compiler has to wait until those new language features appear in a released version. Whether this is realistic, idk. In any case, Zig can also keep the stage0 in the repository for use by developers (but not distros).

They do not use previously-compiled compilers, no.

Instead they are working on building an entire distro starting with ~512 bytes of machine code plus a ton of source. They aren't there yet, but are getting closer.

The Thomson defeat you mention sounds like diverse double compiling, by David A. Wheeler.

https://dwheeler.com/trusting-trust/

I don't think what OpenJDK has is something that Guix/Bootstrappable folks would like either, they had to bootstrap off the Jikes implementation in C++ instead:

https://bootstrappable.org/projects/java.html

The Virgil repo contains every stable compiler binary produced in an unbroken chain back to the first interpreter. You can literally check out every single one of the 2,200 commits and build the compiler from the source and binary checked into the repo. If that's not a bootstrappable build, I don't know what is.

A bootstrappable build (according to bootstrappable.org) is a bootstrap process where you don't use any binaries of the compiler itself to build the compiler. Unless the compiler already has a maintained source-only bootstrap, the usual way to do that is to write a smaller implementation in another language with just enough features that it can build the compiler. camlboot is an example of that. Another option is to build a chain of previous versions of the compiler that were written in other languages, before the compiler became self-hosting.

https://github.com/Ekdohibs/camlboot

1. No, why? OpenJDK version N requires an OpenJDK version N or N-1 to build, and you can download and install that if you need it. What's the difference between "you can download and install stage N-1" vs "stage N-1 is committed"? If the build artifact that is committed is small, then I would argue that there is not much real difference between those two.

2. To add a language feature, you edit the Zig-coded compiler. Then you build it, test it, and you're done. If you now want to change the Zig-coded compiler to use the new feature then you have to update the committed compiled-to-wasm Zig compiler.

Reply on news.ycombinator.com