📅 Original date posted:2012-06-19
📝 Original message:On 06/19/2012 01:59 PM, Gregory Maxwell wrote:
> On Tue, Jun 19, 2012 at 1:33 PM, Alan Reiner<etotheipi at 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...
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20120619/5426be15/attachment.html>;
Alan Reiner [ARCHIVE] /
npub1sm…mnq7h
2023-06-07 10:18:18
in reply to nevent1q…0e6p
Author Public Key
npub1sm6zhjmk5scuz294jmpkw99wwwjzetjgwp4fu4gn6utqgdz87hkqamnq7hPublished at
2023-06-07 10:18:18Event JSON
{
"id": "51fea348d3a3e86bd11a0b4d7934488b82c59522f0e0e7f9699c06de8b6152c9",
"pubkey": "86f42bcb76a431c128b596c36714ae73a42cae48706a9e5513d716043447f5ec",
"created_at": 1686133098,
"kind": 1,
"tags": [
[
"e",
"330d8e7bde9735c3f2b971e767f7ffbe4f47b36f7ea2112bca899a8b62371b85",
"",
"root"
],
[
"e",
"78ef59152803ace90bf60768fe5649bf2e284d6f0d77466bd3f62fee9e084c70",
"",
"reply"
],
[
"p",
"4aa6cf9aa5c8e98f401dac603c6a10207509b6a07317676e9d6615f3d7103d73"
]
],
"content": "📅 Original date posted:2012-06-19\n📝 Original message:On 06/19/2012 01:59 PM, Gregory Maxwell wrote:\n\u003e On Tue, Jun 19, 2012 at 1:33 PM, Alan Reiner\u003cetotheipi at gmail.com\u003e wrote:\n\u003e\u003e One app developer updates their\n\u003e\u003e RB tree code which updated the RB-tree optimizations/rebalancing, and\n\u003e\u003e now a significant portion of the network can't agree on the correct\n\u003e\u003e root. Not only would that be disruptive, it would be a disaster to\n\u003e\u003e track down.\n\u003e This is why good comprehensive tests and a well specified algorithim\n\u003e are important. The tree update algorithm would be normative in that\n\u003e scheme. Worrying that implementers might get it wrong would be like\n\u003e worrying that they'd get SHA256 wrong.\n\nThe point is not that they get it *wrong*, it's that the implement it \n*differently*. Given a set of 100 TxOuts, there's a seemingly-infinite \nnumber of ways to construct a binary tree. Put them in in a different \norder, and you get a different tree. *They're all correct and legal* in \nterms of satisfying expectations of insert, delete and query runtime -- \nbut they will produce different root hashes. And the differences in \nunderlying structure are completely transparent to the calling code.\n\nI'm extremely uncomfortable with the idea the you can have all the nodes \nin the tree, but have to replay X years of blockchain history just to \nget the same tree configuration as someone else. However, a trie \nconfiguration is history-independent -- given an unspent-TxOut list, \nthere's only one way to construct that tree. That's an important \nproperty to me.\n\nI can't tell if you're joking about Judy structures: I've never heard of \nthem. But I'll look into it anyway...\n\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20120619/5426be15/attachment.html\u003e",
"sig": "74d887cfb6b41e4fa2490f92df269ca859c41e4e3c4095d2602decf17db5a3c5c3fcbd945c49db87efc844dc2be3d15a4c81ec7f0de65453fc9621077a36667c"
}