5 ms·

> 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

by ajnin 4y ago

> 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 ?

AndyKelley 4y ago
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.
- Arnavion 4y ago
  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.
  - edwintorok 4y ago
    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)
    - Arnavion 4y ago
      >Can the stage1 wasm binary be reproduced by the stage2 or stage3 executable? Yes, per (2) in https://news.ycombinator.com/item?id=33915480 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.
      - melony 4y ago
        But because of trusting trust, we cannot prove the security of the blob.
  - AndyKelley 4y ago
    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!
    - cryptonector 4y ago
      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?
      - Quekid5 4y ago
        > 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.
        cryptonector 4y ago
        That's my take as well.
  - cryptonector 4y ago
    That's essentially how OpenJDK's bootstrapping works.
- nerpderp82 4y ago
  Well you could project the wasm back to C with wasm2c, package maintainers can continue the illusion that they are bootstrapping from C.
  - AndyKelley 4y ago
    You clearly think of package maintainers as stupid and I can assure you that we are not.
    - nerpderp82 4y ago
      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?
      - AndyKelley 4y ago
        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 https://www.youtube.com/watch?v=stChOsejLEQ
        pabs3 4y ago
        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/ https://bootstrappable.org/
- cryptonector 4y ago
  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.
- ithkuil 4y ago
  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.
cryptonector 4y ago
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.
titzer 4y ago
> 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.
- pabs3 4y ago
  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/ https://bootstrappable.org/
  - cryptonector 4y ago
    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).
    - pabs3 4y ago
      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/ 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 https://bootstrappable.org/projects/java.html

by ajnin 4y ago

AndyKelley 4y ago

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.

Arnavion 4y ago
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.
- edwintorok 4y ago
  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)
  - Arnavion 4y ago
    >Can the stage1 wasm binary be reproduced by the stage2 or stage3 executable? Yes, per (2) in https://news.ycombinator.com/item?id=33915480 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.
    - melony 4y ago
      But because of trusting trust, we cannot prove the security of the blob.
- AndyKelley 4y ago
  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!
  - cryptonector 4y ago
    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?
    - Quekid5 4y ago
      > 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.
      - cryptonector 4y ago
        That's my take as well.
- cryptonector 4y ago
  That's essentially how OpenJDK's bootstrapping works.
nerpderp82 4y ago
Well you could project the wasm back to C with wasm2c, package maintainers can continue the illusion that they are bootstrapping from C.
- AndyKelley 4y ago
  You clearly think of package maintainers as stupid and I can assure you that we are not.
  - nerpderp82 4y ago
    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?
    - AndyKelley 4y ago
      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 https://www.youtube.com/watch?v=stChOsejLEQ
      - pabs3 4y ago
        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/ https://bootstrappable.org/
cryptonector 4y ago
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.
ithkuil 4y ago
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.

cryptonector 4y ago

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.

titzer 4y ago

> 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.

pabs3 4y ago
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/ https://bootstrappable.org/
- cryptonector 4y ago
  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).
  - pabs3 4y ago
    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/ 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 https://bootstrappable.org/projects/java.html