Author: Peter Todd 2017-02-23 07:41:37
Published on: 2017-02-23T07:41:37+00:00
In this email exchange between Bram Cohen and Peter Todd, they discuss the soundness of proofs in a tree data structure. Todd explains that if validation is deterministic, it is impossible to construct two different proofs that prove contradictory statements. Cohen confirms that his code works this way and that proofs are serializations of a subset of the tree. He also mentions that his code now supports compact proofs of multiple inclusions and exclusions in the same serialization. Todd suggests thinking of missing pruned data as analogous to virtual memory and proposes that a proof should be whatever data is expected from the counterparty, ranging from none at all to 100% (modulo a root hash). An implementation should then do operations as normal, using parts of the proof on an as-needed basis where pruned data is encountered. Cohen asks for clarification on MMRs (Modified Merkle Roots), and Todd provides a link to an implementation of insertion ordered lists indexed by position that support append and update operations but not insertions, which is different from what Cohen recently published regarding UTXO commitments. Todd notes that Cohen's solution solves a different problem than MMRs solve.Finally, Cohen mentions that his code doesn't keep track of tree size, but it would be trivial to add that functionality to the library, and including it in the hashing creates complexity and doesn't seem to have any benefit over sending that data in a side channel.
Updated on: 2023-06-11T21:41:29.796694+00:00