<div dir="auto"><br><div class="gmail_extra" dir="auto"><br><div class="gmail_quote">Den 28 jan. 2018 22:09 skrev "Ray Dillinger" <<a href="mailto:bear@sonic.net">bear@sonic.net</a>>:<blockquote class="quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="elided-text">
<br>
</div>The proof-carrying Directed Acyclic Graph (the rough parallel to a<br>
block chain) needs some additional magic to provide proof of<br>
completeness.  IOW, you have to find a way for someone to guarantee<br>
that they have all the information relevant to what they want to do.<br>
<br>
This is a problem that probably has a good crypto solution, but so far I<br>
haven't seen it solved in a way that would allow a secure cryptocurrency<br>
application to scale better than a block chain.<br>
<br>
In a cryptocurrency application, let's say Alice has a TxOut she got in<br>
an earlier transaction (from Zebulon) and wants to make a payment to<br>
Bob.  Alice can use either a block chain or a DAG to show Bob that the<br>
transaction where she got the payment is valid. She can show the<br>
block containing that transaction, and then show previous blocks,<br>
with hashes that verify, in a path that leads all the way back to the<br>
genesis block.  Nice enough.<br>
<br>
But that isn't enough for Bob to know that the payment is valid.  He<br>
must also know that Alice hasn't already used the tx output to pay<br>
Carol, in transaction after she got it.  With a block chain, any such<br>
transaction from Alice to Carol must be in one of the blocks on the<br>
singular path from Zebulon's payment to Alice, to the present.  Bob<br>
knows that if he follows the block chain back and doesn't see it, then<br>
it doesn't exist.<br>
<br>
But With a DAG, the payment from Alice to Carol (if it exists) may be on<br>
some branch Bob hasn't seen.  So unless Bob has every block of every<br>
branch from the moment Alice got that payment, that transaction<br>
invalidating Alice's proposed transaction to him could be somewhere he<br>
hasn't seen.<br></blockquote></div></div><div dir="auto"><br></div><div dir="auto">There's no proof of non-existence possible unless everybody can agree on the scope of the proof (this includes proof of non-knowledge). Unbound scope means proof is impossible. </div><div dir="auto"><br></div><div dir="auto">I can prove there's no black swan in my box by showing it is empty. The problem becomes exceedingly difficult as the physical space gets larger.</div><div dir="auto"><br></div><div dir="auto">In terms of a blockchain you can prove no doublespending by referencing the UTXO set (unspent transaction outputs), which can include either showing all later transactions (as you described), or fancier math like a combination of the relevant UTXO ID, the latest block hash and an Zero-knowledge proof (ZKP) that there exists no transaction spending that UTXO in the blockchain which has this block hash as the latest hash. </div><div dir="auto">As new blocks arrive its easy in the short term to prove there's no doublespend as the full dataset is a few MB at most, while in the long term you create a more fresh ZKP when requested. </div><div dir="auto"><br></div><div dir="auto">In terms of acyclic graphs, there exists no way to completely prove non-knowledge. You can only prove non-existence of conflicts within branches which you admit to knowing about, but since you can't be expected to know all branches it is likewise impossible to produce meaningful proofs of knowing there's no conflicting doublespend transaction. </div><div dir="auto">There's no well known / well defined domain / space of what dataset in which you would show non-existence. </div><div dir="auto">At best you can have a challenge-response protocol where both parties show what branches they admit to knowing, and then a ZKP would be generated which cover those branches. This is only a complete proof if the given combined sets of branches is complete. </div><div class="gmail_extra" dir="auto"><div class="gmail_quote"><blockquote class="quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"></blockquote></div></div></div>