Topic: Ultimate blockchain compression w/ trust-free lite nodes - page 14. (Read 87937 times)

Since the alt-chain can only update as often as the main chain, would using a different difficulty mechanism make sense? Of course adherer or not merged mining is used matters.

For example: Instead of saying that the first hash below difficulty wins, is there any way to say that the absolute lowest hash wins? The biggest issue I can see without an obvious answer is how to keep the chain from backpedaling if someone releases a better block N-1 while everyone else is working on block N , but it might just be a variant on the 51% attack.

TL;DR - would a different difficulty mechanism be warranted?

Sent 2.5BTC.

FYI, I opened a bounty jar for this project at booster.io. Please add a link to the OP.

The way I understand it, the miners will be supporting the block chain, regardless of whether they have part of it or all of it.

The only thing a miner is supporting at any given time is the hash of the latest block and the new transactions he is adding into his block.  Nothing more.  All of the history is covered simply by reference to the prior block hash.  Whether or not he has a local copy of the first billion rolls of Satoshi Dice on his hard drive is irrelevant toward his ability to mine.

I don't worry for one bit that the original unabridged block chain will ever go extinct.  Enough people care about it, the cost to maintain it is low, all it takes is one historian to seed it for the rest of everyone else and everyone who wants it will have it.

The way I see it, the only real critical reason one should demand full blocks all the way to point-in-time X is to maximize the probability that he is not being fed an attack fork without enough information to detect it.  A reasonable hunch of what a good value of X might be for the average client might be a week, and for a miner, a few months.  It could be argued someone investing in a serious mining operation (like a pool) arguably "needs" more assurance, but someone running a serious mining operation also likely has the skills to determine for himself whether he has the correct block chain and that assurance is arguably just as good as having more block history.

yes, that is the correct answer. I'm just concerned that miners will be convinced that they are "supporting" the block chain with only the compressed/pruned version on their disk drive.
That is why I'm asking etotheipi to clarify how this will be presented to the miner community. That is, its a tool for the miners and everyone else, but the miners should still support the full blockchain.

Oh, if I had stopped typing so fast into google, I probably would've notice the autocompletion answer.  Interesting that I always thought it "brandia" instead of "brandais".  That's what I get for never going to class... (though I did stay up all night debugging the insert function for a Patricia tree).

Speaking of that, when I do a search for the correct name, I get a lot of links to the exact class I took when I attended UIUC:
http://www.cs.uiuc.edu/class/fa05/cs225/cs225/_notes/_section/cs225ta4/Documents/bsttries.pdf

It's not the most exhaustive introduction to the trie strcutures, but if you are already familiar with the concepts, you can get the gist of it.  And in fact, I was really proposing the Patricia/Brandais hybrid tree.  A pure "Brandais" tree uses linked lists but is not level-compressed.

The linked list may also make it easier to combine children to produce the "hash" of a particular node:  You only need to concatenate the non-null children hashes, which will frequently be very few elements (and the "skip string").  And in those cases, you just hash consecutively through the linked list.  And the dense nodes near the top can be cached for when they need to be recalculated.  This will also reduce the amount of data that needs to be transmitted to communicate a branch of the tree to a node (though, it's probably still more than I originally estimated). 

Unfortunately, my understanding of the correct path forward once these structures need to move from RAM to disk is beyond me. 

Not sure if this helps:

http://wiki.postgresql.org/wiki/IndexingXMLData#Patricia_Trie
http://stackoverflow.com/questions/355051/how-do-you-store-a-trie-in-a-relational-database

Did you notice that over the last 2-3 years google search gradually became really smart, it feels like there is a full scale AI behind it. I found the data structure that you were looking for, it's called "De la Briandais" tree.

FYI, I have been too swamped with work-work and keeping Armory from breaking under the increased blockchain load to spend too much time on this specific proposal.  I have not lost interest by any means, I just need to catch my breath after some big deadlines.  Then I'll be taking some time off to work explicitly on some Bitcoin stuff... including this proposal.

I'm going to spend some time in the near future looking at space efficiency of a couple variants of the trie data-structure.  I'm not sure exactly how this theoretical datastructure can be merged with a disk-based DB engine (I imagine that what I have in mind is not used by an existing, acceptable DB engine) but maybe there's a way to make a hybrid.  This is a problem that still needs to be resolved before we can move forward with an implementation:  Once we agree on a datastructure, how do we use it but avoid re-inventing the wheel in terms of robust, scalable disk-based database engines?

The more I've been thinking about it, the more I have become convinced that a trie-like structure is necessary.  Note only are query and insert times are constant, the determinism of tree structure for a given set of tree nodes means that queries and inserts can be parallelized.  For instance, the tree could be implemented with the first layer (the first 256 nodes of a 256-way trie) split into a different files/DBs/processes/servers for each branch.  Then every new piece can be distributed and queued for its particular destination.  It could even be distributed amongst different, independent servers.  This seems to be advantageous.

For reference, I learned of this particular tree in my data structures class in college, but I find no reference that anyone else has ever heard of it.  In my class it was called a "De La Brandia Tree/Trie".  A Patricia tree is a level-compressed trie.  A "de la brandia tree" is a Patricia tree that uses a linked-list of pointers, instead of a constant-size array.  i.e. -- in a 256-way trie or patricia tree, each branch node contains 256 pointers (8 bytes each), which could point to other nodes.  However, the sparseness of lower-level nodes means that the nodes will frequently have 255 null pointers, with only one relevant pointer.  The de-la-brandia tree will represent all child pointers with an ordered linked list.  It has some extra overhead for nodes that have mostly-full child lists, but it I think such near-full nodes will be tiny compared to the amount of space saved on sparse nodes.

When I get some more time, I'll make some pictures, and update the original post with the updated proposal.  

Finally had the time to parse and understand the first message in this thread.

+1 for the initiative, it's a good addition to Bitcoin.

Does this information appear in the wiki somewhere?
Does anyone care to TL;DR the rest of the thread for me?

Is there a bounty jar for this? (We can use Booster.io to open one)

The transaction cost just needs to be increased so it serves as an incentive for miners to support the main block chain...I think.

Read some more of your proposal today and I now have a better idea of how it works and what you are accomplishing. Good proposal BTW.
I'm still very concerned that this development will make it so the full blockchain database will not be as accessible for download.
Its important for Bitcoin that anyone can fully audit the blockchain and only need to trust in math and cryptography and not the miners (even though it would be an extremely low probability that enough miners would conspire to get coins in the compressed blockchain).

I completely agree that there are many applications and situations that a compressed blockchain would be extremely useful. Please update us on your perspective of the balance between systems that should have the full block chain and ones that should use the compressed version. The way I read the OP proposal and probably because of my fears is that this compressed form is to replace the full block chain in all instances.

Same here. So far more than 20 coins have been pledged  to the person or persons that implement this: https://bitcointalksearch.org/topic/pledging-coins-for-ultimate-blockchain-compression-93606 Hopefully more pledges soon...

Thanks, I think I understand it now, the Merkle tree is arranged so that there's always a path from the latest hash to each unspent-TxOut, so only headers are required.

I think this idea is very clever and elegant. Of course the devil is in the implementation details. I'd very much like to see this implemented.

Yes, I should have been more explicit. I interpreted the original question as “what is the minimum necessary action that needs to be taken by a client to verify the status of a TxOut”. Maged's solution is perfectly valid and would result in the correct answer, but would also be more work for the client than is strictly necessary.

"Pruning the trees" is a red herring. Here is another way of explaining what this proposal is about.

Bitcoin already supports a Zero-Trust validation technique that is also 100% pruned - it only requires storing a single O(1) block hash. The problem is that it's blatantly inefficient. What we are doing with Merkle trees is altering the blockchain to make this technique, which is inherently fully pruned and zero-trust, more efficient.

[Inefficient O(N), Zero-trust, 100%-pruned technique] (It's just a counter example, bear with me) The entire bitcoin blockchain is already represented by the current block hash. Every client, even the lightest of light clients, stores the current block hash. If you know your current block hash, then you can't be fooled about any of the data in the chain. For example, if you want to check that a particular txoutput hasn't been spent, you iterate backwards through the blocks all the way to that transaction, checking that there's no previous transaction that spends it.

This isn't efficient. It literally involves processing the whole damn chain each time you validate a transaction. So, current light clients certainly don't do this - instead they have to trust a helper to validate that the transactions aren't double-spends. Full nodes have an easier time because they have the storage available to maintain an indexed database of unspent txouts.

[Merkle trees O(log N), Zero-trust, 100%-pruned] What we are all proposing in various ways is to alter how the blockchain history is represented in the current block hash. In addition to the previous block data, we will also include a 'snapshot' of the unspent txoutputs database in each block hash. This snapshot is the root of a Merkle tree, which gives us little shortcuts so we can validate a transaction much more efficiently, O(log N) per validation.

Still trying to understand if pruning the block chain is a good idea. I need a little help understanding.
One of the premises of bitcoin is that we only need to trust math and cryptography. So, anyone can download
the entire block chain and verify all the signatures, hashes, etc. and verify that it 100% complies with the math, cryptography, and bitcoin's protocols; however,
is this still possible once transaction with spent outputs are removed? It would seem that you would have to start putting trust in the mining community that
there wasn't a mass conspiracy to give themselves bitcoins.

Sorry, I really want to understand the detailed technicals so please have patience with my lack of understanding.
I'll do my best to understand if someone will explain it.

I can definitely see pruned/compressed blockchains would be beneficial for many applications, but it worries me that it would be the norm for everyone.

Thanks to all working on what I also see as one of the more pressing issues with bitcoin right now.

Between the above two conflicting answers, the bottom one is the one I consider to be the more correct one.

Neither answer is false, but as I understand it, the way the OP wants to structure the tree, it would be possible to both prove or disprove the existence of funds with a simple query to someone else, and trust it with nothing more than the hash of the latest block.  Trusting that latest hash would typically require downloading the block headers, but not the entire blocks themselves.  What Maged says you can do, you can do, but what Maaku says you can also do, I believe you can also do.

No, the lite client need only download the alt-chain headers since the last checkpoint, and then can request a path through the Merkle-tree to the unspent TxOut (or the surrounding outputs, if it has in fact been spent).

Pretty much. That being said, keep in mind that this would allow someone to become a full node without much trust while ONLY having to download that much.