Discussion of TAP 16: Snapshot Merkle trees

[mnm678]

This is a thread to discuss snapshot Merkle trees, introduced in #125.

Pull requests relating to TAP 16: #133

Outstanding issues and questions relating to this TAP (from @joshuagl in #125 (comment))

• A reader has to understand Merkle trees to implement this TAP, for example to understand how to compute the root hash from a leaf node. Is that a concern? Should we link to a good overview of Merkle trees? Should we specify how this is expected to work?
  • are the metadata extensions for the Merkle tree truly abstract enough to support arbitrary (non-Merkle) tree algorithms? Should we PoC some other algorithms? perhaps in a different implementation?
• Further PoC development of auditor integrations?
• Recommendations on specifying the algorithms for a POUF
• The Specification section suggests the snapshot Merkle tree replaces the single snapshot metadata file – is there any reason we shouldn't generate both? If we generate a Merkle tree only, should integrations still have a snapshot role with associated key? Should we explore this a bit more?
• In places the TAP seems to suggest an auditor is required, whereas in others it indicates auditors are optional. Let's be sure to clarify.

[joshuagl]

Merkle tree implementations are susceptible to a second pre-image attack (see, for example, here or here). Fortunately, there is a well-known fix (as implemented in Certificate Transparency): differentiating between leaf nodes and internal nodes in the tree by prepending different byte values for each node type to the hash data of the node.

With TAP 16, how can help implementors avoid opening themselves up to this kind of attack? Especially given that we are trying to avoid specifying the Merkle tree algorithm as part of the TUF specification. Is this an argument for including the algorithm in the specification (where we could specify the need for different byte prefixes for internal and lead nodes), rather than as part of an implementation's POUF?

I recognise that auditors help here detect this second preimage attack against the Merkle tree. However, as above, the TAP doesn't appear to have decided whether auditors are required or not.

[mnm678]

I hesitate to specify the exact algorithm, as there was some interest in using Verkle trees, or other variations. It also fits with the overall 'no judgement' philosophy of TUF.

That being said, I think the TAP should mention this attack, and perhaps other details about Merkle trees. This may also be a good fit for the secondary literature discussed in theupdateframework/specification#91.

[joshuagl]

Some additional issues/questions for consideration based on my final review before hitting approve:

• is there a more compact format for the metadata, rather than having a merkle_path and path_directions as separate fields in the object with indexed values?
• Does removing the snapshot key decrease our compromise resilience by increasing the value of compromising the timestamp key?
• the obvious auditor implementation would require us to continue to generate the snapshot metadata file, as well as snapshot Merkle trees. Are there less obvious auditor implementations that may allow a repository not to generate a (potentially very large) snapshot metadata file?

[jku]

(just leaving notes for future now that I'm reading this again)

the TAP "security analysis" section should talk about the increased attack surface and increased client complexity -- I'm still not totally convinced adding this into TUF as is, is the right move. If the repository can use (and switching between) all the different delegation models as it wishes, the clients have the classic TLS handshake issue: a compromised/malicious repository can just choose the delegation mechanism that it has found a client bug in.

We might want to consider calling this a different protocol (that only supports merkle delegation). Alternatively -- and I'm hand waving now -- we could consider making it possible for TUF root role to explicitly limit the features that are allowed in this repository (making it impossible to modify this selection with just lower level keys): in practice this could be a string array in the root payload that limits which features are allowed features: ["merkle-delegation"] or features: ["path-delegation", "bin-delegation"]

[trishankatdatadog]

We might want to consider calling this a different protocol (that only supports merkle delegation). Alternatively -- and I'm hand waving now -- we could consider making it possible for TUF root role to explicitly limit the features that are allowed in this repository (making it impossible to modify this selection with just lower level keys): in practice this could be a string array in the root payload that limits which features are allowed features: ["merkle-delegation"] or features: ["path-delegation", "bin-delegation"]

I agree. Right now, it's not obvious to a client which TAP(s), if any, a repo supports at all.

[jku]

TAP says

This information will be included in the following metadata format:

{ “leaf_contents”: {METAFILES},
  “merkle_path”: {INDEX:HASH}
  “path_directions”:{INDEX:DIR}
}

Where METAFILES is the version information as defined for snapshot metadata

I'm not sure if this tries to say that leaf_contents value matches the METAFILES defined in the spec itself... but it definitely is not the same type of value (In the spec METAFILES is a dict of dicts with the outer dict key being the role filename)

[jku]

On Client interaction with auditors:

Clients must ensure that snapshot Merkle trees have been verified by an auditor

I understand we would like this to happen but this cannot be a "must" for clients:

• A client cannot enforce the existence of trusted third party auditors
• The verification mechanisms described are either impractical (this covers the idea of including auditor signature in the timestamp) or not well defined (this covers the other two mechanisms)

[jku]

Things I believe are missing from TAP:

• client workflow changes. My impression is that changes are roughly these
  • snapshot is not used
  • for each targets metadata that needs to be downloaded
    • first download the merkle node for that targets role
    • verify that node is part of the merkle root (downloading the required other merkle nodes)
    • use the merkle node to find the targets metadata version (and hash), then download the actual targets metadata
    • continue normal client workflow (handle artifacts, delegations) based on contents of this targets metadata
• merkle node API definition (meaning where do clients download the nodes): this is not covered in TAP but based on the example code it seems the suggestion is to use <METADATA_URL>/<ROLENAME>-snapshot.json. This approach seems to make collisions possible (possibly only in the non-consistent repository case), I would like that not be the case. Maybe something like <METADATA_URL>/merkle/<ROLENAME>.json would work -- although see the next point WRT snapshot stability
• discussion on effects on snapshot consistency, aka the clients practical ability to fetch a working snapshot of the repository:
  • assumptions:
    • client needs to download 100 targets metadata files to find all the artifacts it needs
    • client wants to use a single repository snapshot for all those metadata
    • client has to work synchronously: it has to download and parse the first artifact to find out what is the second artifact it needs (this is how pypi still works right now)
    • repository uploads new artifacts once a minute
  • the assumptions lead to, let's say, a 5 minute window when the client is making merkle node fetches. This leads to an issue:
    • client wants to fetch nodes for a specific merkle root during the 5 min window
    • repository only makes the nodes available for the current merkle root which changes every minute: In other words the merkle node API returns different content for the same request at different times
  • possibly something like <METADATA_URL>/merkle/<MERKLE_ROOT>.<ROLENAME>.json would work for snapshot consistency? it does mean the server side is a bit more complicated as it now needs to link nodes to roots
• discussion on performance: this does likely lower the bandwidth requirements compared to a (PyPI size) traditional TUF repo but my guess is that number of HTTP requests is going to multiply several times. It's hard to guesstimate though, I would like to see some actual calculations (preferably for both ends of the use case spectrum: downloading a single artifact or downloading multiple hundreds of artifacts at a time).
• discussion on attack surface and client complexity increase as mentioned in an earlier comment: How do we manage the spec becoming more and more complex to implement and how do we prevent the handshake problem where even an online key compromise can lead to attacker selecting the protocol features needed to compromise a specific client

The main issue on that list seems to be that clients cannot download a consistent snapshot of the repository as the merkle node API is not consistent as far as I can tell. Maybe I've misunderstood something?

[jku]

discussion on performance

I don't claim to have really crunched the numbers but just to provide a reason why this should be looked at, a quick estimate:

Assumptions:

• repository is "pypi scale": 600000 projects, each gets their own delegation
• One level of "intermediate" delegations is enough to make targets metadata download sizes reasonable (average intermediate targets metadata will then have 774 delegations)
• A package installer installs a single package without dependencies. The installer has not been used in a few days: caches are cold

Comparison

baseline

number of requests: Today installers like pip do ~3 requests (pip version check, index download, package download)

bandwidth: TODO

Traditional TUF

number of requests: A TUF-enabled installer would do 9 requests (baseline + 6 tuf metadata downloads)

bandwidth: TODO (snapshot is very large, the 3 levels of targets metadata are significant)

merkle-TUF

number of requests: A merkle-TUF enabled client would do ~66 requests (baseline + traditional TUF + 3 merkle verifications, each requiring ~19 downloads)

bandwidth: TODO (nothing very large, the 3 levels of targets metadata are significant)

merkle-TUF with optimizations

Here we assume repository makes complete "inclusion proofs" available to clients (this is not in current TAP)

number of requests: A optimized-merkle-TUF enabled client would do ~12 requests (baseline + traditional TUF + 3 merkle inclusion proofs)

bandwidth: TODO (nothing very large, the 3 levels of targets metadata are significant)

[Omarmostafa18]

Hi everyone,

I’m looking into TAP 16 and had a few questions:

Would you recommend implementing TAP 16 as specified first, or should we focus on improving it before implementation?

If improvements are possible, should we explore a Merkle prefix tree to see if it performs better than the current design? What trade-offs should we consider?

If modifications to TAP 16 are needed, would they require a formal proposal, or could an improved version be implemented directly?

Auditor Validation & Role: Do auditors validate the full Merkle tree, or do they only check sampled proofs? Also, should auditors sign the Merkle root in timestamp.json, or is their role separate from signing?

@mnm678

[jku]

Take my responses with a grain of salt, it's been a while since I thought about this... Marina is certainly a better authority on it.

Would you recommend implementing TAP 16 as specified first, or should we focus on improving it before implementation?

This is the big question IMO. I have a feeling TAP 16 as specified is not acceptable for the use cases it is proposed for (see my previous comment for some back of the envelope numbers for a large scale HTTP TUF repo).

If improvements are possible, should we explore a Merkle prefix tree to see if it performs better than the current design? What trade-offs should we consider?

This seems like a worthwhile direction to experiment with. My vague recollection is that the main tradeoffs are

• I think a merkle prefix version (a Patricia Merkle trie IIRC) would mean that the TUF repository would need to be actual online software that responds to client requests -- compared to current situation where a TUF repository is just a bunch of json files that can be produced offline and made available on a file server
• it is even more complicated than just a merkle tree: TUF clients are tricky to implement already, more complexity is an unappealing idea

I might remember incorrectly but these are the issue I would keep in mind

If modifications to TAP 16 are needed, would they require a formal proposal, or could an improved version be implemented directly?

chicken-and-egg: I would say both are eventually needed but the order depends on what is practical

[tarcieri]

If there isn't a need to support TAP-16 wire formats, there's ample precedent in Rust for Merkle tree databases which e.g. implement sparse maps using Patricia tree-like techniques, including ones that are relatively decoupled from other dependencies (notably quite a few are built on RocksDB, which I would assume is undesirable here). An important question, however, is if any are fit-for-purpose.

It seems one of the most important parts will be a caching/verifying client that can operate on whatever Merkle proofs are desired (e.g. consistency / inclusion proofs).

I don't think it will be terribly hard to handle updates to either a database with full knowledge of the Merkle tree or these light clients with CDN-friendly static files, the harder part is having sufficient intelligence in the client to begin with.