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?