Sparse registry indexes should be viewable atomically

[Eh2406]

Problem

With git-based registries any one commit from the registry represented an atomic picture of what all packages were up to at that point in time. This had a number of useful properties:

• It was possible to list all available crates.
• If a publish was visible, then all earlier publishes (in the servers timeline) would also be visible.
• It was possible to list all crates that had changed between two versions of the index.
• The commit hash was a unique identifier of that state of the world.
• It would've been possible to sign the commit to show it came from a crates.io server.

None of these are possible with the current design of the sparse http-based registries.

Proposed Solution

Its possible to re-obtain the list of all available crates by adding a names-file that lists all crates alphabetically at the root of the index. For crates.io this file would be large but probably compress well enough to be usable.

If we add to that names-file the hash of each index file, then it uniquely identifies a snapshot of the index! Of course, being mostly pseudorandom numbers it will compress really badly. At crates.io scale it will be too big to live in one file. We could split it up into several files, say one per folder in the current index structure. In order to get an atomic picture we would now need a meta-file recording the hashes of the names-files. This works but would be a lot of overhead for smaller registries. (An RFC for this idea will require describing if/how the number of hash files is configurable.)

What happens if the index file is updated after the names-file cargo was looking at? cargo will get a index file whose hash does not match the atomic picture requested. So there needs to be some kind of cash buster that makes sure that the received version of the file matches the requested version. We could put this in the name 3/f/foo can become 3/f/foo-abcdef123456. However this would require crates.io to have the same content at both of those locations (assuming stabilization of the current design of #2789), which is just asking for things to come out of sync. We could use a query parameter, 3/f/foo get you the latest version no matter the hash and 3/f/foo?hash=abcdef123456 gets you the version with the hash abcdef123456. However this requires the backing server to be able to look up versions of a file by their hash. Crates.io is currently using S3, which does not provide this functionality; you can look up old versions of a file but only by the versionID S3 generated. So let's double the size of our names-files by recording for each crate a cash busting string (crates.io can use S3s versionID) and the hash. With the semantics that if you ask for that crate with the cash buster appended, you should always receive a response with that hash.

Notes

If this is so much better design than the current sparse registry proposal, why should we ever stabilize the current proposal?

Fundamentally this design is going to be more work for server to implement. The current sparse registry design has exactly the same contents as a git registry, and is therefore very easy for registries to upgrade to. There will be many users for whom the additional complexity is not needed, and the current sparse registry proposal is a better fit.

I did want to open this discussion to make sure we have a path to this more atomic design that is compatible with what we are stabilizing in sparse registries. If changes need to be made to sparse registries, now is the time.

[tarcieri]

Coming from withoutboats/rfcs#7 I was asked how The Update Framework (TUF)'s snapshots feature might help here. For context, TUF is a framework for cryptographically authenticating software updates, and its snapshots feature provides git-like consistency across several files.

TUF has 4 roles:

• Targets: these are files you'd like authenticated, e.g. the files that make up the sparse index. You can think of them like git objects. The "targets" role makes a manifest of them, their hashes, a version counter which is monotonically incremented whenever changes are made to a given file, and then signs the manifest. For e.g. crates.io, this is a role that would probably be held by @bors
• Snapshots: in TUF terminology, consistent snapshots are like git commits. The snapshot role creates manifests of targets and their version numbers which can be seen as a consistent grouping, kind of like how git commits name a manifest of object hashes. For e.g. crates io, this is another role that would probably be held by @bors
• Timestamp: the timestamp role identifies the current snapshot. It's separate from the snapshot role because it has a shorter TTL to ensure clients check back frequently in order to ensure that a MitM isn't trying to block them from software updates. The timestamp metadata needs to periodically be resigned, even if the current snapshot hasn't changed, in order to ensure that it is "fresh". This is, once again, a role that would probably be held by @bors
• Root: this is the root of trust for the system, which can rotate the keys held by the other roles. In the event @bors were to be compromised, the root role can be used to rotate keys. TUF supports a k-of-n threshold signing model, so you can imagine these keys being held by members of the core team and/or HSMs, with signatures from e.g. at least 3 different keys required to rotate the keys for the other roles held by @bors

Separately TUF also supports a notion of delegated targets where you can specify policies for how 3rd party keys are allowed to sign specific files, which would be useful for letting end users sign crates, but that's not necessary to implement to use TUF for the sparse index and something that can be pursued as followup work as part of e.g. a Sigstore integration (see https://internals.rust-lang.org/t/pre-rfc-using-sigstore-for-signing-and-verifying-crates/18115/2)

If you're curious if it's bad for @bors to hold three roles, not necessarily. TUF splits them up to give you the option of eventually factoring them into separate systems which reduce the overall attack surface of each system and cross-check each other. But you can assign several roles to @bors to get started, and just having the root role separate gives you survivable compromise of @bors.

[Eh2406]

Does TUF have any advice/recommendations on how we get from a bunch of files to a "snapshot"? The link suggests that the snapshot should include a list with all the files each with its hash, but this is impractical at the scale of crates.io. For GIT indexes we already have a Merkel tree, so the snapshot can just be the commit hash (or the tree hash) as suggested in your RFC. For sparse registries we will probably have to invent our own thing, but it might as well learn lessons from and take advice from those who went before us.

[tarcieri]

You'd probably need to talk to a TUF expert about that. I can point one at this issue if you'd like.

It might be possible to use delegated targets as something akin to git tree objects.

[mnm678]

I'm a TUF maintainer and happy to answer any questions here.

Does TUF have any advice/recommendations on how we get from a bunch of files to a "snapshot"? The link suggests that the snapshot should include a list with all the files each with its hash, but this is impractical at the scale of crates.io. For GIT indexes we already have a Merkel tree, so the snapshot can just be the commit hash (or the tree hash) as suggested in your RFC. For sparse registries we will probably have to invent our own thing, but it might as well learn lessons from and take advice from those who went before us.

This is very similar to a proposal in TUF for this exact problem. The short version is that you can make separate "snapshots" for each file (with the name, version number, and hash), then combine them using a Merkle tree, and sign the root of that Merkle tree with the timestamp role. A sparse Merkle tree would likely make this more efficient, but give the same properties. The proposal is a draft that is mostly pending real-world implementation and validation.

[Eh2406]

That is an extremely interesting read. Thank you!
If I read it correctly it has the contents of the files (and the files metadata) put in a Merkel tree, and then one signature on the root of that tree is sufficient to sign the entire thing.
In that way it is similar to the original proposal in this issue.
The proposal uses a binary Merkel tree, where is this issue suggests a per folder Merkel trie. I understand that a trie only make sense for certain kinds of repository data. Are there significant advantages to a binary system over a trie system?
Similarly, I had not heard of sparse Merkel tree before. Can you speak to their benefits in this context?

[tarcieri]

Sparse Merkle trees work well for hashmap-like key/value data, and many are designed to scale well with constant updates.

Here's a Rust implementation of one:

https://github.com/diem/diem/blob/main/storage/jellyfish-merkle/src/lib.rs

This paper describes a similar idea:

https://eprint.iacr.org/2018/955.pdf

[mnm678]

That is an extremely interesting read. Thank you! If I read it correctly it has the contents of the files (and the files metadata) put in a Merkel tree, and then one signature on the root of that tree is sufficient to sign the entire thing. In that way it is similar to the original proposal in this issue. The proposal uses a binary Merkel tree, where is this issue suggests a per folder Merkel trie. I understand that a trie only make sense for certain kinds of repository data. Are there significant advantages to a binary system over a trie system? Similarly, I had not heard of sparse Merkel tree before. Can you speak to their benefits in this context?

The tree shape should only affect performance, and not the security properties, so splitting the tree per folder would work as long as all data is included.

As @tarcieri mentioned, the sparse Merkle tree has has performance benefits for frequent updates as less of the nodes have to change when a leaf is updated.