[nadahalli]

Merkle trees are everywhere in Bitcoin (full node or otherwise).

The block header has the merkle root of all transactions that are a part of that block. The witness merkle root is stored in the coinbase transaction (if the miner is segwit enabled).

And proof of work is done for the block header, which includes all these merkle roots.

[nadaviv]

They are used in Bitcoin since day one in the full node implementation, but full nodes don't benefit from the merkle tree structure in any way. The first client that did benefit from it was bitcoinj, which was released several years after Satoshi birthed Bitcoin.

If light SPV clients weren't a consideration, we could just concatenate all txids together and use the hash of that in the block header instead of a merkle root, and get the same effect.

What merkle trees give you is an efficient way to prove that a certain txid is committed to within a block, without the verifier having to fetch the full list of txids. Instead, he just needs a valid merkle path from the txid to the root, which is much smaller to communicate and to store.

For a full node that has the full list of txids regardless, this is basically meaningless. Full nodes don't (ever) verify merkle inclusion proofs, only that the merkle root in the header matches the full list of block txids.

I would still consider Satoshi's invention to be an incredible breakthrough even if he didn't consider light SPV clients since day one and only described the full node operation mode, therefore I don't consider SPV to be a core component of the Bitcoin breakthrough.

(And also, we know today that SPV is not as great as it was once hoped to be. It puts users at the whims of the miners, with XT/Classic/Unlimited/S2X/BCash being marvelous examples of how that can go terribly wrong. The fraud proof concept that Satoshi described in the whitepaper as part of the SPV model (under the name "alerts") was discovered to not actually be workable due to the data withhold problem, giving this model much weaker security guarantees. And privacy is totally and utterly broken in traditional SPV -- though Neutrino is making good progress on that front.)

[nadaviv]

From #bitcoin-core-dev on Freenode (shesek is me, sipa is Pieter Wuille [0], one of the most veteran bitcoin core devs)

<shesek> does bitcoin core ever verify merkle inclusion proofs? (I assume not, it only verifies that the merkle root matches the set of txids. but maybe I'm missing some other ways its being used?)

<sipa> i don't think anything verifies them

<sipa> shesek: they don't even ever receive any

<sipa> though they were an essential part of BIP37 [related to light SPV clients]

<phantomcircuit> shesek, for a full node theres no real difference between receiving a merkle tree and a hash of a list

<sipa> yeah, for a full-blocks-only bitcoin like protocol, the "merkle root" stored in the block header could just be a flat hash of all txids

[0] http://pieterwuillefacts.com/

[WorldMaker]

I pretty strongly believe that "blockchain" is a misnomer given how much the structure relies on Merkle Trees. Forks aren't some aberration in the data structure, but a direct exploration of branches in the Merkle Tree. Most blockchain algorithms, Proof of Work especially, are just very rigorous "rebase operations" in git terms.

[nadaviv]

Blocks are not organized into merkle trees in Bitcoin. Full nodes pick the longest (PoW wise) valid chain and discards any other competing chains and their blocks.

There are some alternative cryptosystem designs that do take blocks in "losing chains" into consideration using a DAG structure, like GHOST and its successor SPECTRE (by Aviv Zohar et. al). Ethereum also has a concept of "uncle blocks", which are rewarded and contribute to chain selection.

[WorldMaker]

> Blocks are not organized into merkle trees in Bitcoin. Full nodes pick the longest (PoW wise) valid chain and discards any other competing chains and their blocks.

That's pretty much the definition of "rebase" and again, that's a functionality of the algorithm on top of the data structure (Proof of Work) not the data structure. The raw data structure is still a merkle tree even if in practice the algorithm suggests to people there is only one rebased trunk. But even that isn't entirely true in practice because there are still multiple rebased "branches" among the Bitcoin forks such as Bitcoin Classic, Bitcoin Gold, etc. All of those are branches that share the same conceptual merkle tree. Even if they aren't "Bitcoin" that's more of an algorithmic and political distinction at that point, not a technical one by means of data structure. It's not the data structure that makes it a chain, it's the algorithm and the politics, hence why I think blockchain is a misnomer for the data structure itself.

[nadaviv]

Are you sure you mean merkle trees specifically and not just a tree structure in general?

A merkle tree is a very specific type of hash tree, which Bitcoin only uses for transactions and not for blocks. Merkle proofs are used to prove that a txid exists within the root hash committed in the header block. What would be the reason to organize blocks into a merkle tree? What would that let you prove?

See this SE question for more information on how Bitcoin uses merkle trees: https://bitcoin.stackexchange.com/questions/69018/merkle-roo...

> here are still multiple rebased "branches" among the Bitcoin forks such as Bitcoin Classic, Bitcoin Gold, etc. All of those are branches that share...

Bitcoin, BCash and BGold each have incompatible rule sets; A full node will only accept chains that are valid according to its own local set of rules (embedded in it software), so chains of different coins will not even be considered for chain selection, regardless of the proof-of-work backing them. They just don't exists from the full node's PoV. Validity of blocks/transactions comes first, everything else is second.