<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Wed, Feb 22, 2017 at 5:15 PM, Peter Todd via bitcoin-dev <span dir="ltr"><<a href="mailto:bitcoin-dev@lists.linuxfoundation.org" target="_blank">bitcoin-dev@lists.linuxfoundation.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br>
With that, notice how proving the soundness of the proofs becomes trivial: if<br>
validation is deterministic, it is obviously impossible to construct two<br>
different proofs that prove contradictory statements, because a proof is simply<br>
part of the data structure itself. Contradiction would imply that the two<br>
proofs are different, but that's easily rejected by simply checking the hash of<br>
the data.<br></blockquote><div><br></div><div>My code works this way. Proofs are serialization of a subset of the tree, and to validate a proof you ask a single function whether a particular value is included in that tree subset, and it answers yes or no, so obviously it's impossible for a single value to both validate and not validate. The proof code was quite terrifying before I made this change (which I did on your suggestion), and it's much cleaner and simpler now. It also in principle supports compact proofs of multiple inclusions and exclusions in the same serialization of a subset of the tree because the upper branches won't have to be repeated. I haven't written code for generating those, but the validation code will happily accept them.</div><div><br></div><div>I'm not sure what you mean by MMRs though. Are you talking about MMRs where each mountain is a set of diffs to the old things and are periodically consolidated? Or do later mountains refer to internals of earlier ones? Or do they have 'maybe' values which mean that the earlier mountain should be referred to? Are these patricia tries or something flatter and more fixed depth?</div><div><br></div><div>My code doesn't keep track of tree size, by the way. 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.</div></div></div></div>