txs in blocks: why Merkle tree instead of regular hash?

[Kazimir]

What's the advantage of using a Merkle tree for the transactions in a block, instead of just a single regular hash (like sha256) for all the tx data?

[gmaxwell]

Because then I can prove to you that a block contained a particular transaction without sending you the whole block.

[Kazimir]

Because then I can prove to you that a block contained a particular transaction without sending you the whole block.

Right, but then wouldn't it be easier to just take one hash of all the txs' hashes? That way you could just send a list of tx hashes, instead of actual tx data, to prove that one or more particular txs are in the block.

Or is the merkle tree a construction to optimize even further on this? So it only requires to send or check one branch of tx hashes up until the leave that includes the intended tx? (I'm not exactly familiar with merkle trees, but I can sort of see how that could work)

[domob]

Or is the merkle tree a construction to optimize even further on this? So it only requires to send or check one branch of tx hashes up until the leave that includes the intended tx? (I'm not exactly familiar with merkle trees, but I can sort of see how that could work)

Exactly this.  You only have to send a branch, so it will be on the order of size log(N) if there are N transactions in the block.

[piotr_n]

It is also to improve mempool management.

If you want to replace one tx inside a block that is being mined, it requires less computation with the merkle tree system.

[cjmoles]

I have a similar question: is the Merckle trie the most efficient data structure for blockchain management or might there be a more efficient radix trie?  This is something that has been rolling around in my thoughts lately....Has there been any substantial study done on developing a more efficient system, either real or theorized?  I've been thinking Mandelbrot functions....Anything on that?

[gmaxwell]

I have a similar question: is the Merckle trie the most efficient data structure for blockchain management or might there be a more efficient radix trie?  This is something that has been rolling around in my thoughts lately....Has there been any substantial study done on developing a more efficient system, either real or theorized?

A "merkle tree" is what you need to cryptographically harden a tree. The words "merkle tree" do not say much about the particular tree construction being used.

Most efficient for what?  For simply showing membership, which is all it's used for in Bitcoin, it's very hard to even match a plain binary tree (we do not use a trie) with anything else.

For doing other things, many other kinds of data structure have been proposed at various times.

I've been thinking Mandelbrot functions....Anything on that?

Perhaps you were looking for the ethereum blog? Please don't waste our time here by asking about random semi-relevant collections of technical terms. ("Hey guys, have you considered using a post-quatum NoSQL skip-list?!? I hear it has webscale!")

[cjmoles]

I have a similar question: is the Merckle trie the most efficient data structure for blockchain management or might there be a more efficient radix trie?  This is something that has been rolling around in my thoughts lately....Has there been any substantial study done on developing a more efficient system, either real or theorized?

A "merkle tree" is what you need to cryptographically harden a tree. The words "merkle tree" do not say much about the particular tree construction being used.

Most efficient for what?  For simply showing membership, which is all it's used for in Bitcoin, it's very hard to even match a plain binary tree (we do not use a trie) with anything else.

For doing other things, many other kinds of data structure have been proposed at various times.

I've been thinking Mandelbrot functions....Anything on that?

Perhaps you were looking for the ethereum blog? Please don't waste our time here by asking about random semi-relevant collections of technical terms. ("Hey guys, have you considered using a post-quatum NoSQL skip-list?!? I hear it has webscale!")

No, I wasn't looking for the ethereum blog....interesting project though....I was just thinking about how long it takes my core wallet to synchronize if I leave it closed for a few weeks and was imagining how large the ledger would become years into the future.  It'd be nice to somehow be able to access the information on the blockchain without having to download the entire ledger....that's all.

[achow101]

No, I wasn't looking for the ethereum blog....interesting project though....I was just thinking about how long it takes my core wallet to synchronize if I leave it closed for a few weeks and was imagining how large the ledger would become years into the future.  It'd be nice to somehow be able to access the information on the blockchain without having to download the entire ledger....that's all.

The time to sync the blockchain and index the data has nothing to do with merkle trees. The time to calculate the hash is insignificant compared to the time it takes just to download all of the data.

[cjmoles]

No, I wasn't looking for the ethereum blog....interesting project though....I was just thinking about how long it takes my core wallet to synchronize if I leave it closed for a few weeks and was imagining how large the ledger would become years into the future.  It'd be nice to somehow be able to access the information on the blockchain without having to download the entire ledger....that's all.

The time to sync the blockchain and index the data has nothing to do with merkle trees. The time to calculate the hash is insignificant compared to the time it takes just to download all of the data.

Yes, that's my point (I think).  The serial nature of the blockchain and the means by which we access and process the information it contains seems to be mismatched.  In other words, would it be possible to insure the validity of the ledger, access its information, and secure the network with a pruned data structure?