A Merkle tree, also known as a binary hash tree, is a data structure used to efficiently summarize and verify the integrity of large data sets. Merkle trees are binary trees that contain cryptographic hashes.
Merkle trees are used in bitcoin and other blockchains to summarize all transactions in a block, producing a complete fingerprint of the entire set of transactions, providing a very efficient process to verify if a transaction is included in a block. A Merkle tree is built by running a hash function on pairs of nodes recursively until only a single hash remains, which is called a root or merkle root.
When N data elements are taken, each one of them is hashed and summarized in a merkle tree, it can be checked if any data element is included in the tree with a maximum of 2 * log 2 (N) calculations, making it a very efficient data structure.
In the case of the blockchain, the leaf nodes or nodes at the bottom are the transactions included in the block and the tree is generated upwards by applying the corresponding hash function.
Topic: Is it possible for the blockchain to be a tree? (Read 926 times)
For example, if blocks were stored in nodes containing all transactions with a certain address. And the tree of those nodes was organized by address such that any address could be looked up quickly (and requested quickly from another network node).
I think blkindex.dat already contains something close to what you are describing. The internal structure used is a B-tree (if I recall correctly, the Oracle DB Documentation website is down at the moment). As you can see the blkindex.dat is about 1/3 of the size of the raw blockchain. 
This would be an alternate representation of the chain that allows tracing transactions without having to have the whole blockchain.
You would need to validate transactions sent/received by you. Even when not mining yourself. Otherwise how do you know that someone really has the coins he broadcasted in a transaction to your wallet? Without this, you wouldn't have anonymity and security.
Yes, I understood that the blocks always depend on the previous one since it includes a hash of that block. And that would still be the case. But I'm wondering if perhaps there is a way to store the block chain as some form of tree, along with probably some additional hashes, that allow chaining back only the blocks needed to test a transaction.
I haven't by any means got this formally worked out. I'm probably not the person to figure that out as there are people who understand the math and logic much more than I do. This would be an alternate representation of the chain that allows tracing transactions without having to have the whole blockchain.
For example, if blocks were stored in nodes containing all transactions with a certain address. And the tree of those nodes was organized by address such that any address could be looked up quickly (and requested quickly from another network node).
There may need to be hashes of entire tree leafs as you walk up/down. Or some additional hashes present to verify that each such address node was "complete and true".
Anyway, this is just a rough idea right now. And if someone has math to show that it's not feasible then it wouldn't be worth pursuing. But if it can be done then it seems like a possible way to code a light client that would only validate a trail of addresses/transactions relevant to the user.
I haven't by any means got this formally worked out. I'm probably not the person to figure that out as there are people who understand the math and logic much more than I do. This would be an alternate representation of the chain that allows tracing transactions without having to have the whole blockchain.
For example, if blocks were stored in nodes containing all transactions with a certain address. And the tree of those nodes was organized by address such that any address could be looked up quickly (and requested quickly from another network node).
There may need to be hashes of entire tree leafs as you walk up/down. Or some additional hashes present to verify that each such address node was "complete and true".
Anyway, this is just a rough idea right now. And if someone has math to show that it's not feasible then it wouldn't be worth pursuing. But if it can be done then it seems like a possible way to code a light client that would only validate a trail of addresses/transactions relevant to the user.
The block chain is a chain because each node depends on the node just before. A tree won't help this.
The transactions, however, are already in a sort of a tree, in that each input is either a coinbase, or a pointer to a previous transaction (which eventually ends in a coinbase). Forest might be a better word than tree, or maybe "tangled mess of overlapping trees" would be better yet.
No one really knows what a light client is going to look like yet, but my guess is that it will involve a small application asking a trusted node for blocks on an as-needed basis so that it can verify accounts and generate new transactions. Actually, it will probably ask two or more nodes just to be sure the first one isn't lying, but that's just a detail.
The transactions, however, are already in a sort of a tree, in that each input is either a coinbase, or a pointer to a previous transaction (which eventually ends in a coinbase). Forest might be a better word than tree, or maybe "tangled mess of overlapping trees" would be better yet.
No one really knows what a light client is going to look like yet, but my guess is that it will involve a small application asking a trusted node for blocks on an as-needed basis so that it can verify accounts and generate new transactions. Actually, it will probably ask two or more nodes just to be sure the first one isn't lying, but that's just a detail.
I'm wondering it it is possible to represent the blockchain in a tree structure. This just occurred to me and I'm sure someone who fully understands the math/logic could say whether it's possible.
My idea was that blocks could be stored in a tree keyed on input/output address. So some sort of "sparse" view of the tree would be sufficient for validation. (No doubt additional hashing may be required to make that true)
I was thinking of this because it seemed like this may allow validating transactions without having the entire blockchain. Addresses could be checked fairly quickly by downloading only the actual tree nodes that are needed. Of course any previously download nodes could be cached.
Any particular user isn't going to need to download that many nodes in order to validate their own transactions. I'm sure there are some problems with this. Maybe each parent node of the tree needs to also have a hash of lower nodes or something.
If something like this were feasible then it could alleviate issues related to the massive blockchain download and perhaps client storage needs.
I'm saying there would still be a linear blockchain but maybe a client tree representation could be devised that ensures the "known" nodes are sufficient to validate some given transaction.
My idea was that blocks could be stored in a tree keyed on input/output address. So some sort of "sparse" view of the tree would be sufficient for validation. (No doubt additional hashing may be required to make that true)
I was thinking of this because it seemed like this may allow validating transactions without having the entire blockchain. Addresses could be checked fairly quickly by downloading only the actual tree nodes that are needed. Of course any previously download nodes could be cached.
Any particular user isn't going to need to download that many nodes in order to validate their own transactions. I'm sure there are some problems with this. Maybe each parent node of the tree needs to also have a hash of lower nodes or something.
If something like this were feasible then it could alleviate issues related to the massive blockchain download and perhaps client storage needs.
I'm saying there would still be a linear blockchain but maybe a client tree representation could be devised that ensures the "known" nodes are sufficient to validate some given transaction.
Jump to: