Deep vs Shallow trace: Removing the tradeoff?

[ilmu]

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