Hacker News Reader

If you are indexing all transactions you are right that merkle trees are not very useful. They become useful when you aren't, for example, when running a lightweight client that only stores block headers.

Let's say you are running a lightweight wallet and import a private key, your client will download all transactions that spend from/to that private key from a node that does index all transactions (a "full node"). With the block hash and merkle branch of each transaction, your client will be able to independently verify that each transactions were included in a block and are therefore valid. This of course assumes that the longest chain (in terms of proof of work) is valid, which is usually a reasonable assumption.

We use them when we replicate very complex dependency trees. Often with 1e6+ heterogeneous objects in the tree.

If we replicate a tree, say, for regression testing, we can trivially confirm that it replicated identically. If not, we can use the partial trees to, very quickly, triage the discrepancies to the earliest divergence point.

We also have a number of cases where we want to quickly confirm that 2 (or more) trees have identical dependencies in parts of the tree even though the overall trees diverge substantially. A Merkle tree approach works nicely here too.

Indexing doesn't help in these cases as what we're doing is, effectively, fast content matching.

I see your confusion, from that perspective, you're absolutely right. But the usefulness of Merkle trees isn't in its 'fast lookup', it is rather in its bandwidth efficient way to prove that something remained unaltered.

I still don't get it. For example, if each block contains the hash of the previous block (including the hash of all its transactions), then it's already possible to verify if a block was illegally substituted for another (e.g. secretly behind the scenes) because the following block hash would become inconsistent. The verification step would be O(1) time complexity because you just need to check the block hash and the hash of its two neighbors which is faster than Merkle Proof which is O(log n).

The clue is in "all transitions" part. If you have n blocks adding values, you have to verify O(n) blocks on average to check, that the value is in the chain leading to the current head.

With Merkle tree you just need a path from leaf to the root - so O(log n) hashes required.

Is it related to Bitcoin's design with input and output transactions and the double spend problem?

It still seems that the problem can be solved by including a hash of the previous record as part of each new record. Then to verify the validity of any given record, you just fetch that record, its predecessor and its successor. If the record's hash cannot be computed using the predecessor's hash plus the hash of the current record's transactions (in a way that it's consistent with the successor's hash), then you know the current record is invalid.

It's about anchoring your knowledge/trust. If you start with zero data, you're saying that it's enough to just fetch that record. How to do that? You need to query full nodes specifically for the block that contains your record. But how do you know it is part of the "real" blockchain? They could provide you fake block - even faking whole history, just to fake your record is there.

That is not possible when you are querying many full nodes for current node, without telling them what you are looking for. They cannot return different results based on your query. You can trust that one piece of information - newest block.

In order to verify validity of the record, you need the block containing that result and checking that it is in history of the current block. That requires fetching O(n) blocks. Keep in mind that you need to trust just the head - even if someone wanted to provide you fake history, they are not able to, as it is infeasible to create block matching specific hash.

But instead of having linear block chain (corresponding to list datatype) you can have a Merkle tree (corresponding to tree datatype), where it is possible to compute hash of each node having just its two children. You can anchor your knowledge in the hash of the root (e.g. by having all nodes provide you the same value). Than anyone can prove you in a trustless way, that the tree contains specific leaf: by providing way to verify the hash of all nodes on the path from the leaf to the root. That requires O(log n) data, compared to O(n) in linear blockchain.

Merkle trees allow for verification; I don't think they are particularly beneficial for lookup? For example, this paper is about a better way to verify the integrity of a "sparse Merkle multiproof".

My point is that lookups and simple `if then else` comparisons can be used to do verification too with similar performance characteristics and a lot simpler to implement.

Is it related to zero-knowledge proofs? The industry makes it seem like Merkle trees are required for all blockchains which is definitely not the case since most blockchains are public and each full node has a full record of the history.

I mean, each node doesn't have a literal full record of the history embedded in it, right? There's just a back pointer to the previous node. And the Merkle Tree part verifies that the thing the node points back to is legit and not just a fake block you pulled out of thin air.

I was talking about nodes as independent machines which have the full history (full nodes). Maybe you were thinking of nodes in a mathematical sense like blocks in a blockchain.

My point stands that if each block ID is computed from:

1. A hash of all the transactions inside the block. AND

2. The hash from the previous block.

Then you can verify that the block is legit without a merkle tree. Tampering or substitution of any block would result in the hash not being consistent with the neighboring blocks.

I mean, isn't that literally a Merkle Tree?

But in order to prove that to someone that doesn't have full history, they would have to synchronize it, by downloading all the data and verifying all the transitions. With Merkle tree (identified with its root hash, just as blockchain is identified by hash of its head) it is possible to verify there is a value inside without full synchronization.

It's not about Bitcoin or blockchains and nothing about zero knowledge proofs or anything. You did just describe a merkle tree though.

Here is another example. BitTorrent uses merkle trees for torrent and piece identification.

You request peer list from a tracker via the torrents merkle tree root hash. These are visible in torrent files and sometimes magnet links. That root hash corresponds to a certain tree of piece hashes whose data that when reassembled will recreate the torrent. The tree of piece hashes is included with the torrent file.

You can now ask peers for those pieces by their hash and know the peer sent you the correct data because it hashes correctly. Furthermore you can know you reassembled the original torrent because you can verify all the piece hashes hash back up to the merkle tree root this verifying the torrent was downloaded correctly.