This post is a report on Team DeBoot’s work at the ETH Lisbon hackathon, October 2022.1 Although we didn’t end up submitting code, we did manage to create something far more valuable: a new problem statement in decentralized package management (and some strategies to attack it).

We’d like to thank ETH Lisbon sponsors Lightshift Capital for subsidizing our trip. Without their support, this work would not have occurred.

The idea

Everyone is familiar with package managers that pull in sources or precompiled binaries from webservers. We wanted to investigate how this model could be improved by replacing webservers with a decentralized storage backend — that is, a public content-addressed, peer-to-peer distributed store. Such a store offers two benefits over the client-server model:

  • Resilient. P2P networks have no single point of failure.
  • Deduplication. Content addressing means that identical data has the same address regardless of who uploads or hosts it.

Some well-known examples of p2p content-addressed stores are IPFS and EthSwarm. In this post, I’ll use Swarm as a reference point because of its relevance to Ethereum. Little would change if we were to consider IPFS instead.

Now we need a package manager amenable to operation in concert with decentralized storage. Enter Nix. Nix is a package manager and build system that provides reproducible builds. This guarantee means that it makes sense to keep Nix resources (for example, build outputs) in a content-addressed store, thereby achieving similar deduplication properties to Swarm.

While Nix provides a far more expressive build language than Swarm — the latter only concatenates data blobs from trees of 4KiB chunks — it does not have any built-in support for a p2p network backed cache. Could the powers of these tools could be combined to yield some kind of universal decentralized Nix store?

To be able to formulate this properly, we need to understand a little of how Nix works. In particular, we need answers to the following questions:

  • What kinds of things live in the Nix store?
  • When does Nix read and write the Nix store?
  • Which of these are actually useful to host on a public p2p network?

Spoiler: figuring out answers to these questions took most of the weekend.

What does Nix do?

Nix separates the build process into two stages:

  • Instantiation. Evaluate a Nix expression to compute a derivation, as a side effect producing a file with .drv extension.

    A derivation is a machine- and human-readable expression that specifies a platform (such as x86_64-linux) and build with locked dependencies. The dependencies may be files specified directly in the input expression or references to build outputs of other derivations.

  • Execution. Interprets derivations and executes the instructions to produce build outputs. During this step, derivations and dependencies are read and build outputs are written. Arbitary programs may be invoked.

    This step should be reproducible on any system matching the platform specifier.

All files produced or referenced by either of these stages are copied to the store. The store consists of build outputs, derivations, static files, user profile information, and probably some other stuff we don’t know about. All objects are addressed by content hashing, but the details of the construction differ by the type of object.

In particular, the identifiers of build outputs are obtained by hashing (a reduced form of) the derivation used to produce them rather than the output objects themselves. This means that Nix build output identifiers can be computed at instantiation time, i.e. without actually running the build.

Towards decentralizing the Nix store

There are potentially a few points in the Nix process at which it would be reasonable to interpose a decentralized store, but we chose to focus on the case of build outputs. The idea is that when Nix is called on to construct a build output, it can first check to see if a cached copy is available on Swarm.

To perform this lookup, Nix must be able to obtain the Swarm (content) hash starting from the Nix output identifier. The only way to compute this directly is to know a derivation for that build output, run the build, and serialize and hash the result. Requiring users to run this locally in order to find the Swarm content would defeat the purpose of a cache. Thus for our decentralized Nix store to be useful, Nix needs to be able to access a mapping $$ \mathtt{nix\_id} \quad\mapsto\quad \mathtt{swarm\_id} $$

which we dub the content address translation (CAT) table. This table is the glue that will bind Nix’s invoker to its decentralized cache backend.

In the converse direction, if Nix does execute a build locally, we could ask it to automatically upload the result to Swarm and make it available to others. This comes with additional caveats: first, uploading to Swarm requires a payment, and second, much more serious, permissionless automated uploading seriously complicates the integrity issue discussed below.

Integrity

A key requirement of a package cache is that the user must be able to trust the integrity of the retrieved copy, that is, that it is indeed the output of executing the specified derivation.

In traditional package delivery systems (e.g. over HTTP), the DNS name owner de facto vouches for the content by providing TLS certificates. This approach is isn’t suitable in pseudonymous p2p settings — for example, because Swarm node operators do not choose which chunks they host.

A more robust approach has the package maintainer or some other authority add a cryptographic signature, certifying the authenticity in terms of a “web of trust.” For practical reasons we propose to pursue this strategy: builds are checked and signed by a trusted authority, say, a consortium of universities and reputable companies.2 The same consortium could provide a public copy of a CAT table on a (TLS-secured) web portal.

This leaves some question as to how the signed content should be addressed on Swarm; one approach would be to use the “owned chunks” feature.

Implementation

We could always modify Nix itself to explicitly integrate a Swarm-backed cache. Clearly, this approach is not satisfactory: it isn’t modular or extensible, and results in a Nix binary different from the one everyone else is using.

Much more elegant would be to construct a transparent middleware — invisible to the user unless they explicitly request to see it. This middleware would kick in when Nix checks the store for build outputs, pass the request through the CAT table and make a Swarm query.

Here are some approaches we thought of for hooking into the local CAT mapping:

Filesystem hooks. Mount a FUSE on the Nix store path with read/write hooks to perform the desired operations. The challenge of this approach is to distinguish build outputs from the other contents of the Nix store using only information available to the filesystem. That is, we need a way for the FS to determine whether a given path refers to a build output.

Fortunately for us, build outputs are listed in the DerivationOutputs table of the Nix db, a local sqlite database that keeps track of Nix internal state. Our FUSE could check whether a requested path is listed in this table and either invoke a hook or pass through to the underlying filesystem accordingly.

HTTP gateway. Nix can be configured to automatically attempt to retrieve build outputs from a webserver, the canonical one being https://cache.nixos.org/. Hence, one could interpose the address mapping with an HTTP-to-Swarm relay obeying the Nix binary cache protocol. We couldn’t find this protocol documented anywhere, but it could be deduced from Dolstra’s reference implementation.

Next steps

With this discussion out of the way, we aren’t far from being able to attempt an implementation. (Perhaps given another day at the hackathon, we could have made headway on these steps.)

  • Fully specify the approach to integrity. Since we are not expecting to break any new ground in the first iteration, this work should be straightforward.
  • Write down a specification for CAT mappings that takes signatures into account.
  • Implement a FUSE (with read hooks only) or HTTP gateway. The latter involves extracting a description of the Nix binary cache protocol from Dolstra’s server implementation.

The more daunting task is to actually build versions of the 70,000 packages listed in nixpkgs and onboard trustworthy organizations as signers. Let’s see if there’s any interest!

Here are some of the materials we found useful for getting into a Nix headspace:

For EthSwarm, the ultimate reference is the beautifully typeset Book of Swarm.

  1. DeBoot was formed at ETHBerlin earlier this year to tackle a problem with decentralizing network boots (github.com/awmacpherson/deboot). The primary team members are A. Hokoridani and A. Macpherson. ↩︎

  2. While trustless verification of Nix builds would indeed be cool, this amounts to verifying execution of arbitrary programs on any CPU instruction set, something we chose to consider out of scope for a weekend hackathon. ↩︎