Bitcoin Forum
December 05, 2016, 04:48:52 AM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Is it possible for the blockchain to be a tree?  (Read 594 times)
BkkCoins
Hero Member
*****
Offline Offline

Activity: 784


firstbits:1MinerQ


View Profile WWW
September 19, 2011, 11:56:43 AM
 #1

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.




1480913332
Hero Member
*
Offline Offline

Posts: 1480913332

View Profile Personal Message (Offline)

Ignore
1480913332
Reply with quote  #2

1480913332
Report to moderator
1480913332
Hero Member
*
Offline Offline

Posts: 1480913332

View Profile Personal Message (Offline)

Ignore
1480913332
Reply with quote  #2

1480913332
Report to moderator
1480913332
Hero Member
*
Offline Offline

Posts: 1480913332

View Profile Personal Message (Offline)

Ignore
1480913332
Reply with quote  #2

1480913332
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1480913332
Hero Member
*
Offline Offline

Posts: 1480913332

View Profile Personal Message (Offline)

Ignore
1480913332
Reply with quote  #2

1480913332
Report to moderator
1480913332
Hero Member
*
Offline Offline

Posts: 1480913332

View Profile Personal Message (Offline)

Ignore
1480913332
Reply with quote  #2

1480913332
Report to moderator
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
September 19, 2011, 01:12:08 PM
 #2

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.

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
BkkCoins
Hero Member
*****
Offline Offline

Activity: 784


firstbits:1MinerQ


View Profile WWW
September 19, 2011, 01:38:29 PM
 #3

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.

BombaUcigasa
Legendary
*
Offline Offline

Activity: 1414



View Profile
September 19, 2011, 02:08:01 PM
 #4

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.
2112
Legendary
*
Offline Offline

Activity: 1708



View Profile
September 19, 2011, 03:21:02 PM
 #5

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.

Please comment, critique, criticize or ridicule BIP 2112: https://bitcointalk.org/index.php?topic=54382.0
Long-term mining prognosis: https://bitcointalk.org/index.php?topic=91101.0
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!