Author: Alan Reiner 2012-06-19 18:12:19
Published on: 2012-06-19T18:12:19+00:00
In a discussion about an app developer updating their RB tree code, Gregory Maxwell emphasizes the importance of good comprehensive tests and a well-specified algorithm to avoid discrepancies in implementation. Alan Reiner expresses concern that even if implementers don't get it wrong, they may still implement it differently due to the infinite ways of constructing a binary tree. This can cause different root hashes even though they are all correct and legal in terms of insert, delete, and query runtime. Maxwell suggests using a trie configuration which is history-independent and only has one way to construct the tree given an unspent-TxOut list. Finally, he mentions looking into Judy structures after someone else brings it up.
Updated on: 2023-06-06T05:51:05.654318+00:00