Quote from: etotheipi on November 04, 2012, 07:00:58 PM

Either way, the developer has to get into the implementation details of the data structure. They have to understand it. And really, neither structure is particularly complicated. Perhaps some devs are more familiar with BSTs. But to say that a miner "has the option" to rebalance -- that doesn't make sense. Any rebalancing operation on a BST will change the root hash. It must be determined from the start exactly when and how rebalance ops will happen. Or else everyone gets different answers.

I will clarify. For every block, given the set of transactions contained in that block, there are 2 potential hash values that are acceptable as the root hash. One of them represents the tree with the transactions applied to them. This case is checked first, because it's the least expensive for a client to do so. The second one represents the tree after it has been completely rebalanced. A client should have no problem determining which way it went simply by trying the first case, and then the second.

Quote from: etotheipi on November 04, 2012, 07:00:58 PM

And as for the comment about "simulating numerous cases of rollbacks" -- This case is dramatically simpler with a patricia tree structure -- you just add and remove elements from the tree using standard insert & delete operations. It doesn't get much simpler than that (besides maybe keeping around the last few blocks worth of deleted TxOuts, which is probably a few kB). On the other hand, you may be talking about gigabytes of data to store "backups" or "snapshots" of the BST, just in order to accommodate the possibility of a rollback. And how many copies do you need to store? You can keep the last state of the tree, but what if there's a 2-block reorg? Well, now you need two copies. To handle arbitrary-sized rollbacks, you could really be thrashing your hard-drive, and in such a way that everything has changed while you were attempting to swap gigabytes of data around.

How do you envision rolling the tree back in the case where you have just determined that all of the blocks you have on hand are now invalid, and getting the now-correct state of the Patricia meta tree requires you to ask peers for orphaned blocks you don't have? Must future Bitcoin implementations be required to keep orphan blocks on hand and serve them to peers to support the ability of others to roll their tree backwards?

In perspective, it's not the idea of Patricia or any other kind of tree I am having a problem with, it's the added complexity of supporting this sort of roll back that goes well beyond understanding a new kind of tree.