Ultimate blockchain compression w/ trust-free lite nodes

[etotheipi]

Perhaps that's another reason to use insert-order-invariant tree structure.  If you have to reverse some transactions, you don't have to worry how you undo them.  Undoing a block/tx is just as easy as adding it in the first place.

You still have to have the complete data that you would remove. E.g. when I spend txn X,  I don't specify all of X's data to spend it (thats burried elsewhere in the chain) only the hash. Order invariant wouldn't let me recover that. I need some kind of undo data, even if its just the location of the original txn so that I could fetch it. (though more efficient if you can serve me up a whole undo block)

Yeah, I actually realized that and was editing my previous post to say this:

It's not actually trivial to reverse blocks in any particular pure-pruned scheme, since adding blocks involves deleting UTXOs.  So reversing the block means you have to re-add UTXOs that are not defined by the block you are reversing (it only references the OutPoint by hash:index, not the whole UTXO).  So you have to either save them or request them from another node.  Perhaps the solution is to keep a circular buffer of the last N UTXOs that were removed, as long as N is enough to cover the last, say 50 blocks.  Any time you use map.delete when updating the tree, you use a buffer.add to save it (which will also discard the oldest element in the buffer).  Then when you need to reverse a tx, you know the OutPoints that need to be re-added, and if N is large enough, you'll have it in the buffer.  Worst case, you have to fetch some data from another node, which isn't terrible.

[casascius]

It's probably fodder for another topic, but I am of the opinion that in the event of a very large reorg (where more than 6 blocks are rolled back), the proper behavior of a bitcoin client should be to stop functioning and demand that a new client be downloaded from the developer(s) of that client, and to assist the user in exporting their wallet and ensuring their replacement client is properly signed by the developer.  This is based on philosophizing that it would be better for the bitcoin network to go down in an orderly fashion in the event of an attack - long enough for developers to agree on countermeasures tailored to the attack - just like the recent space rocket that changed its mind and aborted the launch at the last second - rather than for it to stay up and operate chaotically and at a financial loss to users.

Mentioning that is not intended to derail the thread - I am certain there isn't a consensus on what I just said, and it may very well be an unacceptable idea.

But I am saying it because: If it were ever to be debated and determined that what I threw out IS in fact a good idea, it would also settle the question as to how to ensure the tree can be rolled back.  The answer would be simple: at a minimum, keep a copy of the tree as it looked at the point representing the maximum amount we're willing to roll back without ceasing to function.

[jgarzik]

It's probably fodder for another topic, but I am of the opinion that in the event of a very large reorg (where more than 6 blocks are rolled back), the proper behavior of a bitcoin client should be to stop functioning and demand that a new client be downloaded from the developer(s) of that client, and to assist the user in exporting their wallet and ensuring their replacement client is properly signed by the developer.  This is based on philosophizing that it would be better for the bitcoin network to go down in an orderly fashion in the event of an attack - long enough for developers to agree on countermeasures tailored to the attack - just like the recent space rocket that changed its mind and aborted the launch at the last second - rather than for it to stay up and operate chaotically and at a financial loss to users.

During the output overflow incident, we were all rather glad that the collective client base did not do this.  Once miners upgraded, everyone reorg'd back into working order.

This is just one of many reasons why there is a 120-block new-bitcoin confirmation policy in place.

[etotheipi]

But I am saying it because: If it were ever to be debated and determined that what I threw out IS in fact a good idea, it would also settle the question as to how to ensure the tree can be rolled back.  The answer would be simple: at a minimum, keep a copy of the tree as it looked at the point representing the maximum amount we're willing to roll back without ceasing to function.

I think it's an interesting idea, and as you suggested, I don't want to derail the thread.  However, I think that the amount of history to maintain is not a critical question.  Standard reorgs on the main chain are rarely more than 1 block.  We save enough info for 10 blocks, and if a reorg happens further back than that (and the client is willing to continue), then the node can just request the missing information from peers.  It's all verifiable information, and if you are trying to catch up to the longest chain there should be plenty of peers who can supply it.

[socrates1024]

It's probably fodder for another topic, but I am of the opinion that in the event of a very large reorg (where more than 6 blocks are rolled back), the proper behavior of a bitcoin client should be to stop functioning and demand that a new client be downloaded from the developer(s) of that client, and to assist the user in exporting their wallet and ensuring their replacement client is properly signed by the developer.  This is based on philosophizing that it would be better for the bitcoin network to go down in an orderly fashion in the event of an attack - long enough for developers to agree on countermeasures tailored to the attack - just like the recent space rocket that changed its mind and aborted the launch at the last second - rather than for it to stay up and operate chaotically and at a financial loss to users.

Mentioning that is not intended to derail the thread - I am certain there isn't a consensus on what I just said, and it may very well be an unacceptable idea.

But I am saying it because: If it were ever to be debated and determined that what I threw out IS in fact a good idea, it would also settle the question as to how to ensure the tree can be rolled back.  The answer would be simple: at a minimum, keep a copy of the tree as it looked at the point representing the maximum amount we're willing to roll back without ceasing to function.

Perhaps one reason to prefer a balanced binary tree is that if you want to store a snapshot of every previous blockchain, you only have to store the differences. There is a "Persistent Authenticated Datastructure" that would let you handle roll backs efficiently.


(This image is from "Persistent Authenticated Dictionaries and their Applications" by Anagnostopoulos Goodrich and Tamassia http://cs.brown.edu/people/aris/pubs/pad.pdf )

I do not know if this is possible with tries.

[etotheipi]

Perhaps one reason to prefer a balanced binary tree is that if you want to store a snapshot of every previous blockchain, you only have to store the differences. There is a "Persistent Authenticated Datastructure" that would let you handle roll backs efficiently.

[Image suppressed]

(This image is from "Persistent Authenticated Dictionaries and their Applications" by Anagnostopoulos Goodrich and Tamassia http://cs.brown.edu/people/aris/pubs/pad.pdf )

I do not know if this is possible with tries.

I'm not 100% sure I understand that picture.  It looks like you are saving the pointer-tree of each state, though there's only ever one copy of each piece of underlying data.  Multiple trees will be maintained, but leaf nodes will point to global copies of TxOut data.   Is that correct?

In that case, saving the state of the tree at a previous time means storing a whole lot of pointer data.  If I consider a basic binary search tree and use 8-byte pointers (assuming it's all in memory), then each node in your binary tree is going to store at least two pointers (prtLeft & ptrRight) and probably a few more bytes for random stuff like isLeaf and isRedOrBlack, etc.  So I assume 20 bytes per tree node.  For a tree of 2 million unspent TxOuts, then that's about 40 MB of storage for each state you want to store (each block).  And that's going to go up linearly with the size of the tree. 


(NOTE: I'm discussing this as if it's a single tree full of TxOuts, even though my proposal is about a main tree full of addresses containing unspent TxOuts, and subtrees of TxOuts.  However, the concepts are still valid, it's just easier to make my points as if it's a single tree of TxOuts).

On the other hand, if you're using a trie, you don't have to save the state of the entire trie since its structure is purely deterministic for a given set of addresses.  You only have to save the nodes that were removed that might have to be re-added later in the event of a rollback.  You look at the OutPoints of the TxIns in each tx of the block that need to be reversed, and re-add them to the trie.  Then remove the ones that were added by those transactions.  This is all standard O(1) trie operations.

Thus, the data that needs to be stored in order to rollback a block in the trie (besides the blockdata itself) is proportional to the transaction volume on the network.  And transaction volume is capped by network rules.  Currently, each block could be up to 1MB.  If you filled a block full of transactions that were entirely TxIns with nothing else, it would result in removing about 7200 TxOuts from the tree.  That means that that absolute upper limit for storage per block you want to be able to roll back is about 250 kB, regardless of tree size.

[socrates1024]

I'm not assuming it's all in memory. I'm not talking about pointers, but about a graph of hashes.

To be sure we're on the same page - we are talking about a merkle trie with one hash at the root, and hashes at each level, right?

Also you keep saying O(1) when you mean O(log N). I don't think you would agree with the following statement:
    "Each transaction is associated with a unique hash. There are only 2^256 hashes, therefore the number of transactions is O(1)."

Still, I am leaning towards thinking the simplicity of the trie outweighs any marginal cost benefits of the balanced binary tree. They're of the same order in all operations.

[etotheipi]

I'm not assuming it's all in memory. I'm not talking about pointers, but about a graph of hashes.

To be sure we're on the same page - we are talking about a merkle trie with one hash at the root, right?

There does appear to be a disconnect here.  Let me explain what my understanding of your proposal is:

(1) There is a database of TxOuts.  It has all current, unspent TxOuts in it.  TxOuts are added and deleted (or marked deleted) when blocks come in.
(2) The TxOuts need to be organized into a tree of some sort in order to come up with the single "merkle root" to be included in the meta-chain header ("merkle" is in quotes, because using a binary tree or trie it's no longer a "merkle" tree).  The relationship between DB elements (1) will be represented either as a Binary Search Tree or trie using "pointers".
(3) Thus, after every block, you update the database of TxOuts (1), and the pointers in binary search tree or trie (2).  I was focusing on (2) when I say that you need to store pointers.  Not necessarily in RAM... but somewhere, data needs to be held that identifies the structure of the tree/trie associated with the TxOuts in database (1). 
(4) In a classic binary search tree held in RAM, it uses pointers -- specifically a left pointer and a right pointer for each node.  In this context, whether it's held in RAM or on disk, there's still 8 bytes needed (at minimum) per pointer to represent the relationships.  And a binary tree will use about 1 such pointer per node.

This is not a negligible amount of data.   If TxOuts are 35 bytes, pointers are 8 bytes, then a "tree" of pointers will be about 25% of the size of the entire TxOut database.  It's a rough estimate, not intended to be exact.

So now back to my original point:  it looks to me that in order to "save the state" of the tree, you need to save the entire tree of pointers between nodes (2).  And you need the full tree.  Sure the TxOuts database stores each TxOut once, but saving all the pointers to represent the past states of the tree will triple your space requirements to save just 8 blocks.

Also you keep saying O(1) when you mean O(log N). I don't think you would agree with the following statement:
    "Each transaction is associated with a unique hash. There are only 2^256 hashes, therefore the number of transactions is O(1)."

Another disconnect here.  I'm not sure where your example came from, but here's what I'm referring to -- let's compare a binary search tree full of Bitcoin addresses to a trie of Bitcoin addresses (the entire set of all addresses on the network containing unspent TxOuts).  Assume at a given time there are N such addresses.

Binary Search Tree (red-black or any balanced tree) -- depth is O(log(N)).   
   -- Querying an element is O(logN)
   -- Inserting an element is O(logN)
   -- Deleting an element is O(logN) 
Basic trie:  depth of the tree is equal to the length of the longest key:  so the depth is 20 (because addresses are 20 bytes).
   -- Querying an element is O(1) -- it takes 20 hops to get from the root node to the leaf you want
   -- Inserting an element is O(1) -- it takes 20 hops to get from the root node to the leaf you want
   -- Deleting an element is O(1) -- it takes 20 hops to get from the root node to the leaf you want

So even if there are 100 quintillion bitcoin addresses with unspent TxOuts in the master alt-chain tree, it still takes you exactly 20 hops to query, insert or delete a value in the trie (and less if you're using a patricia tree).

[socrates1024]

Could you describe how you would update the root hash for the trie?

Also, it most certainly takes fewer than 40 hops* to get from the root of the balanced binary tree to any leaf. Log N is less than 20.

*Assuming one hop is actually "8 hops". I don't feel like I'm making this point too clear. You can have a 'balanced B tree' that has up to 8 children at each level. Then there are only 20 hops.

Or to put it another way, if there are so many transactions that we have collisions by birthday paradox, then we would need to pick a bigger hash.

[etotheipi]

Could you describe how you would update the root hash for the trie?

In both BSTs and trie structures there will be leaf nodes and branch nodes.  In some structures (such as the BST) branch nodes may also contain leaf data.  In the context of this proposal, the master tree will be the set of all addresses containing any unspent TxOuts.  So a given leaf represents one such address.  

--For the purposes of organizing the tree/trie, that leaf's value will be the 20-byte address.  So the 20-byte address is the "key" of the master tree.
--For the purposes of computing the root hash, that leaf's value is the root of the subtree of unspent TxOuts for that address (which is constructed in a similar way to the address tree)
--For the purposes of computing the root hash, all branch nodes' hash values are the hash of the concatenation of its children's hash values.

In the simplest case, you have only pure branch nodes and pure leaf nodes.   This looks very much like the merkle trees we already use.  Then each node's "hash value" is the hash of the two children "hash values" concatenated.  [LeftPtrNodeValue || RightPtrNodeValue].  You walk up the tree computing this for every node until you get to the root.

In the BST case where nodes are actually both branch nodes and leaf nodes, then you just use hash([LeafValue | LeftPtrNodeValue | RightPtrNodeValue]).  

In the Patricia/Hybrid Tree case, there are purely branch nodes and leaf nodes, though the branch nodes may have "skip strings".  So a leaf node's hash value is just the root hash of the subtree.  And a branch node's value is the hash of the concatenated skip string and its non-null child node values.

When you add or remove a node from the tree, you are changing the hash value of its parent, which changes its parent, etc.  So for a BST, you to add or delete a node, you have to recompute/update O(logN) other nodes hash values to get the new root value.  Same thing for the trie, except there is exactly 20 parents to update, regardless of the size of the tree (and see below for why this will ultimately be only 4-6).

I really need to make a picture...  (coming soon)

It most certainly takes fewer than 40 hops to get from the root of the balanced binary tree to any leaf. Log N is less than 20.

Right, number of hops of a red-black tree will be 2*logN worst case.  So your point is well-received that N will probably never get high enough in this environment for the query/insert/delete time of a basic trie to absolutely beat the binary search tree.  Both of them have completely acceptable query/insert/delete times.  So two things to mention:
(1) It's still entirely accurate to label trie operations as O(1).  It just not be relevant for this application.
(2) I'm actually proposing a Patricia tree, which is level-compressed.  So a typical access time will be 4-6 hops.  Even with trillions of nodes in the tree.  The absolute max is 20 but it would never be realized.

[ripper234]

Perhaps it's time to formulate this in the wiki?
Maybe as a BIP draft?

Or is it too soon?

[etotheipi]

Pictures!

I love inkscape.  Here is a visual explanation of tries, Patricia trees, Patricia-Brandais Hybrid trees, and the technique for getting "hash values" out of each node.  I need a better name than "hash values", which is kind of vague... "signature" of the node?  "shape" of the node?  Ehh, whatever, enjoy the pictures!

A basic trie on base-10 keys (which in this proposal would be base-256, and either address strings or TxOut values)


Patricia trees are the same, but with level compression.  This is critical since trees/tries will be very sparse relative to the fact they can theoretically hold 2^160 or 2^256 nodes.  One remaining problem is that all branch nodes still store 256 pointers, even when 255 of them are NULL.


The hybrid tree is what I would propose.  The pointer-arrays are converted to linked lists and only non-null children are stored


Since this data structure would also be used for the TxOut subtrees, it should have a compact representation for one-node trees.  Indeed it does:


The "values" of each leaf is just the root of the sub tree, and the value of each branch is the skip-string concatenated with all its children's values.

[socrates1024]

Ah but etotheipi, let's focus on the last image, since that is the first one to mention hashes.

You have taken the hash of the values of the child nodes, but not the hash of the children's hashes. You cannot securely traverse this tree from the root hash.

[etotheipi]

Ah but etotheipi, let's focus on the last image, since that is the first one to mention hashes.

You have taken the hash of the values of the child nodes, but not the hash of the children's hashes. You cannot securely traverse this tree from the root hash.

I don't follow your logic.  Did I miss something?  Can you elaborate?

[casascius]

I haven't been following the tree logic as I only understand them to a certain extent, but I just wanted to make sure that whatever tree structure is chosen, that updating the tree to accommodate new incoming transactions is nearly always instantaneous no matter what the size.  You are surely aware that with growth incoming transactions can start to number into the hundreds and the thousands per second.  If updating the tree for each incoming transaction is burdensome in resources, it will create a perverse incentive for miners toward taking shortcuts in transaction processing or omitting transactions from blocks.  I'm sure you already know this, just wanted to make sure this weighed somewhere decent on the requirements list for what structure is eventually chosen.

[etotheipi]

I haven't been following the tree logic as I only understand them to a certain extent, but I just wanted to make sure that whatever tree structure is chosen, that updating the tree to accommodate new incoming transactions is nearly always instantaneous no matter what the size.  You are surely aware that with growth incoming transactions can start to number into the hundreds and the thousands per second.  If updating the tree for each incoming transaction is burdensome in resources, it will create a perverse incentive for miners toward taking shortcuts in transaction processing or omitting transactions from blocks.  I'm sure you already know this, just wanted to make sure this weighed somewhere decent on the requirements list for what structure is eventually chosen.

Inserting, deleting or changing nodes only involves modifying the branch on which that node operates.  So you find the node to be modified, then you recalculate its parent, then recalculate its parent, and so on up to the root node.  Given the structure of the tree, that's likely to only be 4-6 node recalculations per update.  However, each of those nodes might be dense, meaning you might be concatenating a couple hundred values.  However, the total computation is completely independent of tree size (well, it will always be less than 20 nodes to update, though the actually number will asymptotically increase towards 20 as the tree gets bigger [though in reality it will probably never exceed 8 even if 100% of the world switched to BTC]).

[maaku]

You are surely aware that with growth incoming transactions can start to number into the hundreds and the thousands per second.

Can it really? Current limitations on block sizes limit the number of transactions to no more than a thousand per block, or a few per second. Changing those limitations would result in a hard-fork.

Or am I missing something?

[socrates1024]

I don't follow your logic.  Did I miss something?  Can you elaborate?

Yes! You're missing the step where you take a hash of the children's hashes, not just their values. For example, suppose your root node is fully stocked and contains "0123456789". You seem to be saying its hash would be H("0123456789"). That tells you the values of the children, but it does not let you look up (and validate) the rest of the data in the next node. For a hash tree to work, you need to take the hash-of-a-hash at each step.

[casascius]

You are surely aware that with growth incoming transactions can start to number into the hundreds and the thousands per second.

Can it really? Current limitations on block sizes limit the number of transactions to no more than a thousand per block, or a few per second. Changing those limitations would result in a hard-fork.

Or am I missing something?

That's true in regards to current limitations, but one day we'll be thinking about how to scale past them.  It would be preferable for that scaling process to be able to happen without the requirement that the tree algorithm be rethought with it because the chosen candidate ended up becoming the slowest link in the chain.

[casascius]

I know it's been a while since this topic has been visited, but I'd like to make a proposal here:

Rather than settle on the "best" way to implement this tree, how about settle on the "simplest", so that way the community can catch the bug and start cranking their brains on the best way to implement this tree with the right balance of features and complexity when the time comes to consider making it part of the protocol standard.

By "simplest", I mean implemented as follows:

1. A simple binary tree that starts out balanced, but maintaining the balancing from block to block is optional.  A miner has the choice to rebalance the tree for the next block, but doesn't have to.  The lack of a requirement to keep the tree balanced is meant as an effort to discourage mining empty blocks because a miner doesn't want the CPU burden or any delay associated with rebuilding the whole tree with each incoming transaction.

2. No ability to roll back.  Rolling back must be accomplished either by rebuilding the tree from scratch, or by starting with a known good backup and rolling it forward.  Backups are systematically deleted such that the backup burden grows O(log n) relative to the total block height.  More specifically, the backup of any given block's tree should have a lifetime of 2^n blocks where n is the number of contiguous zero bits at the end of the block height.  Block 0x7890's tree backup should last sixteen blocks because 0x7890 ends in four zero bits.  The backup for the tree of block 0x10000 should last 0x10000 blocks.

Now, why would I suggest a methodology that clearly avoids taking advantage of features that would make a "better mousetrap" so to speak?  Here are the most prominent reasons:

1. At some point, the Bitcoin community may come to a consensus that we should redefine a valid Bitcoin block to incorporate the root hash of a valid meta-tree rather than having it be optional coinbase clutter.  Until then, this is merely an optional performance-enhancing and usability-enhancing feature without any hard commitment to a standard.  We should help people understand the base case for what it is, and then move on to derivative cases that do the job better.

2. There is serious value in simplicity.  The more things are needlessly complex, the higher the barrier to entry for new developers of bitcoin software.  We are at a point where we need more developers on board than we need the disk space saved by what would be (for the current block height and all block heights for the foreseeable future) about 20 backups of the meta tree on each user's disk.  Besides being much more difficult for the average developer to understand, requiring a tree that must do a moonwalk during a rare edge case which is very difficult for a developer to reproduce and test makes for an exploitable danger that implementations may fail to do the right thing when the right thing is needed the most.

3. The Bitcoin community could use the lessons learned in a basic "proof of concept" implementation of this without being committed to any specific methodology for optimizing it.  This will help the community at large understand which use cases evolve from the availability of the tree, and then come to an intelligent consensus as to what features and attributes of a meta tree are the most valuable and which bargains of complexity versus power are worth making.