Storing UTXOs in a Balanced Merkle Tree (zero-trust nodes with O(1)-storage)

Self-Balancing Merkle Search Tree - #bitcoin proposal (specification and reference implementation)

redblack.py : an implementation of Stefan Kahrs' red-black tree, with an extensible "digest" augmentation. Two "modes" are provided for each of the three operations: the Record mode operates on a full tree (represented as nested python tuples), and produces a Verification Object (VO) (i.e., an O(log N) path consisting of just the nodes that were accessed during this operation), while the Replay mode takes in a root-hash and an untrusted VO and verifies the operation by recomputing the hash at each step. utxo_merkle.py : a specialization of RedBlack by definining by the digest/serialization protocol described above merkle_scan.py : a script that iterates through the entire blockchain, from the genesis block to the head, incrementally updating the merkle tree as it goes (requires Gavin Andresen's python bitcointools )

Full article: https://bitcointalk.org/index.php?topic=101734.msg1112957...