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

cjmoles

legendary

Activity: 1176

Merit: 1016

Quote from: achow101 on May 01, 2016, 09:35:29 PM

Quote from: cjmoles on May 01, 2016, 09:33:39 PM

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?

achow101

staff

Activity: 3374

Merit: 6530

Just writing some code

Quote from: cjmoles on May 01, 2016, 09:33:39 PM

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

legendary

Activity: 1176

Merit: 1016

Quote from: gmaxwell on May 01, 2016, 09:19:12 PM

Quote from: cjmoles on May 01, 2016, 03:30:37 PM

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.

Quote

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.

gmaxwell

staff

Activity: 4172

Merit: 8419

Quote from: cjmoles on May 01, 2016, 03:30:37 PM

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.

Quote

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

legendary

Activity: 1176

Merit: 1016

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?

piotr_n

legendary

Activity: 2053

Merit: 1354

aka tonikt

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.

domob

legendary

Activity: 1135

Merit: 1161

Quote from: Kazimir on April 20, 2016, 08:27:34 AM

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.

Kazimir

legendary

Activity: 1176

Merit: 1001

Quote from: gmaxwell on April 20, 2016, 06:27:29 AM

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)

gmaxwell

staff

Activity: 4172

Merit: 8419

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

Kazimir

legendary

Activity: 1176

Merit: 1001

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?

Topic: txs in blocks: why Merkle tree instead of regular hash? (Read 1466 times)