Deep vs Shallow trace: Removing the tradeoff?

[ilmu <ilmu@rishi.is>]

Hi,

I had this idea while reading about authenticated datastructures, I would be very thankful if you could tell me why it doesn't work.

Bear in mind the following disclaimer as you read this:

My experience with these things is mostly theoretical, I have never used Bazel and although I was a user of Nix and am now moving to Guix I have not contributed to nixpkgs and only written simple expressions.

Without further ado.


The premise I am assuming is the framework introduced in Build Systems a la Carte. They talk about Bazel and Nix as representatives of two different dependency tracing strategies:

- Shallow tracing :: You hash immediate dependencies.
- Deep tracing :: You hash the whole transitive closure.

Now the tradeoff is basically the following:

- In Nix when you put a comment in curl you need to rebuild every single package in nixpkgs because they more or less all depend on curl in one way or another and therefore the curl source is in the transitive closure for almost every package.
- In Bazel when you put a comment in curl then the direct dependents need to be rebuilt but if they are the same as before after being rebuilt then the propagation is killed and nothing else needs to change.

However, in Bazel you will need to traverse the whole dependency tree all of the time to verify that everything is as it should be.


Now the idea I have is very simple:

We use recursive zero knowledge proofs with shallow traces, the rzkp caches the traversal and provides the same guarantee as the deep traces do (transitive closure is verified to be as it should be). Now if someone puts a comment in curl there is a small amount of packages that need to be rebuilt and then we redo only the proofs all the way up. This way we save ourselves a potentially massive amount of compilation.

As I said before I do not have much experience with the real implementations of these ideas so I am sure this is not as simple as it is in my head. However the distri experimental operating system (which implements a similar model to guix and nixos) does not put the hash in the store path but rather keeps a small metadata file for each path and then has a natural number suffix for the path of concurrent versions of the same package. This gives a better UX imho and is probably also easier to extend with more appropriate authenticated datastructures as they are discovered.


I hope I am not a raving madman and that this actually makes at least a slight amount of sense. Very much looking forward to takedowns :)


Kind regards,
- Ilmu