On 06/19/2012 01:59 PM, Gregory Maxwell wrote:
On Tue, Jun 19, 2012 at 1:33 PM, Alan Reiner<etothe...@gmail.com> wrote:
One app developer updates their
RB tree code which updated the RB-tree optimizations/rebalancing, and
now a significant portion of the network can't agree on the correct
root. Not only would that be disruptive, it would be a disaster to
track down.
This is why good comprehensive tests and a well specified algorithim
are important. The tree update algorithm would be normative in that
scheme. Worrying that implementers might get it wrong would be like
worrying that they'd get SHA256 wrong.
The point is not that they get it *wrong*, it's that the implement it
*differently*. Given a set of 100 TxOuts, there's a seemingly-infinite
number of ways to construct a binary tree. Put them in in a different
order, and you get a different tree. *They're all correct and legal* in
terms of satisfying expectations of insert, delete and query runtime --
but they will produce different root hashes. And the differences in
underlying structure are completely transparent to the calling code.
I'm extremely uncomfortable with the idea the you can have all the nodes
in the tree, but have to replay X years of blockchain history just to
get the same tree configuration as someone else. However, a trie
configuration is history-independent -- given an unspent-TxOut list,
there's only one way to construct that tree. That's an important
property to me.
I can't tell if you're joking about Judy structures: I've never heard of
them. But I'll look into it anyway...
------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and
threat landscape has changed and how IT managers can respond. Discussions
will include endpoint security, mobile security and the latest in malware
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
_______________________________________________
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development
