Bitcoin build systems and bitcoin build system security

Carl Dong, Chaincode Labs

https://twitter.com/kanzure/status/1137347937426661376

video: https://www.youtube.com/watch?v=I2iShmUTEl8

I couldn't make it to Amsterdam this year, but I hope the graphics I have prepared for this talk can make up for my absence. Let's say you want to be a good bitcoin citizen and start to run your own bitcoin node. Say you go to bitcoincore.org, you click the download button, and you open the disk image and you double click on Bitcoin Core. Then you get this warning.... If you're as paranoid as I am, you got this download and you got this notification, are you sure bitcoincore.org is the right website? Is it a phishing scheme? What about bitcoin.com? That website sounds much more official, right? Wrong.

Today I am going to go on a journey to go through bitcoin's build system, show you how to verify your bitcoin download is the right one and show you some improvements in the work. Going back to the downloaded disk image, maybe you will wonder where it came from and how it was made. We all know that software was source code at some point. In our case, we expect this to be the versoin from Bitcoin Core v0.18. Source code is fed into a toolchain of compilers, linkers and archivers which builds the source code into the binary format which is the disk image you downloaded. But how do we know that the binary we downloaded from bitcoincore.org corresponds to the Bitcoin Core v0.18 source code? How do we know that whoever uploaded this binary modified it to steal your coins and upload your keys?

Gitian ensures that given identical source code, we get identical binary outputs. This is deterministic builds. This makes sure that you can produce an identical disk image. We don't have to trust bitcoincore.org. Instead, we can verify ourselves that the binary came from the version of bitcoin we expected. There's in fact a repository called gitian.sigs.git where maintainers upload gitian assert files which are generated by the build process and declare what source code they use and what the resulting hash of the binary output is. This hash should be identical to the hashes of the binary we downloaded at the beginning of the talk from bitcoincore.org, and if they differ then we know that something is wrong.

These .assert files are generated whenever we do a gitian build from source. When generated from different people, these gitian assert files should still agree with each other. This is what we mean by reproducible builds. Gitian is one project from a wider project across many others to make sure we can do reproducible builds for everything.

I am here to tell you that reproducibility is not enough. The reason why goes back to trust. Before reproducibility, we had to trust that the bitcoin binary was not malicious. With gitian builds, you're still trusting something. If you scroll down the gitian dot assert file, which might take a while. All of these .deb files are what we're trusting. These are the tools that we use to make bitcoin and they are what makes up the toolchain that I mentioned before. The thing is that they are all trusted binaries that w edownloaded from archive.ubuntu.com, so we basically have the same problem we had before with the bitcoincore.org download. Again, we have to trust that nobody put anything malicious in these tools because these tools could have malware that modifies the Bitcoin Core gitian output.

Look at the quora.com question, what's a coder's worst nightmare? Nick describes debugging a program on a computer that had been poisoned by an ex-grad student. The program was very simple. It was designed to rpint a question and then wait for a response. However, what the program actually did was print some white supremacy message, wait half a second, and then overwrote it with the actual question. So obviously there's something wrong with the source code. So Nick deleted the line and then recompiled, thinking it would be fixed. He ran the program again and subliminal messages were still there. Somehow the source code had the offending lines re-inserted. He tried some other techniques, like recompiling the standard library, and even learning assembly language. On day 15, he realizes that it's in the toolchain. Every time you use a toolchain to compile the original code, it puts malicious code back into the source code meaning that the binary output would also be effected. Nick's story reveals why reproducibility is not enough. Completely clean source code is also not enough. Even if it was reproducible, the toolchain that gitian downloads and trusts and uses to build bitcoin source code can still be malicious. In other words, we might be reproducible but we might also be reproducibly malicious.

The problem with gitian is that although Bitcoin Core binaries can be reproducibly built, the tools to build that binary are hard to audit and difficult to make reproducible, resulting in a possibly malicious bitcoin binary. You might ask, where do these compilers and other things in the toolchain come from? I liken this to an old recipe for yogurt: how do you make yogurt? You take some milk, and add it to some existing yogurt you already have to make more yogurt. Similarly, the way you make a toolchain is you give a toolchain to one you already have and make more toolchains.

Here's where we come back to Nick's journey. After his epiphany, he got an AT&T tech to show up with 3.5 inch floppies and loaded the proper compiler and linker source so they can recompile the compiler, thus making the yogurt from yogurt. He thinks it would solve it, but he was wrong. The existing malicious compiler had another trick up his sleeve. He was able to recognize when it was building another toolchain and to inject the same malicious behavior to the output toolchain. The compiler was somehow able to replicate and poison successful generations of itself. This is truly the stuff of nightmares.

This is similar to an attack that Ken Thompson, the person behind golang, described in his 1984 turing award acceptance speech "Reflections on trusting trust". In that speech, he described by how toolchains are built by older versions of themselves, that you can poison an entire line of them just by poisoning one of them and it would propagate down to future generations even if the source code is completely clean. Similarly, in "reflections on rusting trust", someone was asking about the notoriously hard-to-bootstrap rust compiler.

So what can we do about the fact that our toolchain can have a bunch of trusted binaries that can be reproducibly malicious? We need to be more than reproducible. We need to be bootstrappable. We cannot have that many binary tools that we need to download and trust from external servers controlled by other organizations. We should know how these tools are built and exactly how we can go through the process of building them again, preferably from a much smaller set of trusted binaries. We need to minimize our trusted set of binaries as much as possible, and have an easily auditable path from those toolchains to what we use how to build bitcoin. This allows us to maximize verification and minimize trust.

How do we make sure bitcoin users are running the code they think they are running? We should be using functional package managers like guix, which is a package manager where bootstrappability and reproducibility are fundamental tenants. Every package from guix is a pure function of the source code and the toolchain used to build it. Every package built on guix can be traced back to a small set of trusted binaries. There's also a "guix graph bash" command to give a dependency tree for bash. You can also find its build-time dependencies, and the complete graph of dependencies right down to its minimal set of bootstrable binaries. In guix, every single package's dependency graph will include this subgraph- like gcc-bootstrap, glibc-bootstrap, gcc-cross-boot0, etc. Notice how this is a directed acyclic graph. Just for reference, and I don't want anyone to take this as badmouthing Debian... it's a miracle they are able to maintain their package set this well. For reference, debian has many loops in their dependency graph. They had a loop of 2000 packages. That strongly connected component has taken on a life of its own, and it has grown significantly since they started measuring its size.

What does all of this mean for our toolchain? Guix means that when we use it to build our toolchain, we can audit how each tool in our toolchain was built and easily bootstrap them from a small set of trusted binaries. This is in stark contrast from our current gitian process where we build bitcoin from trusted debian boundaries that we pull from an ubuntu package repository. The software heritage foundation has been focused on guix. Many scientific institutions choose guix for their reproducible scientific workflows in their high-performance computing environments.

I've been working on replacing gitian with guix so that we can have bootstrappable and reproducible builds for bitcoin. I currnetly have bitcoin builds for all supported linux architectures using guix. One of the nice side effects of guix being bootstrappable is the elimination of some nasty dependencies previoulsy used that caused our gitian build guides and scripts to be long and confusing and mostly distro/architecture-specific. With guix, we will be able to build bootstrappable reproducible builds on any distro and in the future maybe we will be able to do this on any architecture.

I also want to talk about the ongoing work to have a reduced binary seed botstrap in guix. Currently the guix bootstrap binaries weigh in at 232 megabytes, which is already a fraction of that from debian-based distros. But with the current version of mes, in guix's core update branch, we can eliminate gcc as a trusted binary, mitigating the "trust in trust" attack, and bringing our bootstrap collection down to 131 MB. His work has recently been funded. Eventually a C subset transpiler will be able to eliminate a lot of this. There's also hex0 which can be the only trusted binary, in a few hundred bytes of source code. It's the holy grail of reproducibility.

Thank you to Chaincode Labs for funding this, and Cory Fields for tolerating my questions, ryanofsky for telling me about bootstrappable package managers, and the good folks on IRC in bootstrappable, and guix people, and my friend Tales from the Crypt for giving me this awesome microphone setup. Thank you for listening to me ramble.