* git stores a tree of *commits* * Each commit is hashed and the hash is its *commit id* * Each commit references its parent(s) by their hashes

* Suppose somebody knows the root node hash *`f910ba..`* and nothing else * Let's say we want to prove to them that the "bugfix!!" commit exists in the tree

* You send them the highlighted commits and they can re-compute the hash themselves to verify * The purple is the node you are proving exists * The red nodes are called "witnesses"

1. Hash the bugfix node and verify the "fix tests" witness node includes this hash 1. Hash the "fix tests" witness and verify the "merge commit" witness includes this hash 1. Hash the "merge commit" witness and verify the trusted hash matches this hash

* Note that the verifier never needed any of the grey nodes to verify the proof * If a secure hash function is used, there is no way to modify the "bugfix" commit and use it to make a valid proof

* A merkle tree is a way of structuring a data-base so it can be verified with proofs * Here is a DB with 8 elements in it * 3 bit paths required, because: * log2(8) = 3

* What do you do if you have an odd number of items on a layer?

* Bitcoin protocol unconventionally duplicates last item * This was a security bug because there are 2 possible DBs with same root: * [0,1,2,3,4,5,6] * [0,1,2,3,4,5,6,6]

* Better approach is to just move the odd node up a level * In this case the proof for `6` would use the path `11` and only provide 2 witnesses

* Project that tries to keep SSL Certificate Authorities honest * So they can't sign SSL certificates for spy agencies without getting caught

* Merkle Patricia Trie is a way to efficiently handle *sparse* paths, like the output of hash functions * First implemented in Ripple, popularised by Ethereum