[Cryptography] DAG vs Blockchain

[Natanael]

Den 28 jan. 2018 22:09 skrev "Ray Dillinger" <bear at sonic.net>:


The proof-carrying Directed Acyclic Graph (the rough parallel to a
block chain) needs some additional magic to provide proof of
completeness.  IOW, you have to find a way for someone to guarantee
that they have all the information relevant to what they want to do.

This is a problem that probably has a good crypto solution, but so far I
haven't seen it solved in a way that would allow a secure cryptocurrency
application to scale better than a block chain.

In a cryptocurrency application, let's say Alice has a TxOut she got in
an earlier transaction (from Zebulon) and wants to make a payment to
Bob.  Alice can use either a block chain or a DAG to show Bob that the
transaction where she got the payment is valid. She can show the
block containing that transaction, and then show previous blocks,
with hashes that verify, in a path that leads all the way back to the
genesis block.  Nice enough.

But that isn't enough for Bob to know that the payment is valid.  He
must also know that Alice hasn't already used the tx output to pay
Carol, in transaction after she got it.  With a block chain, any such
transaction from Alice to Carol must be in one of the blocks on the
singular path from Zebulon's payment to Alice, to the present.  Bob
knows that if he follows the block chain back and doesn't see it, then
it doesn't exist.

But With a DAG, the payment from Alice to Carol (if it exists) may be on
some branch Bob hasn't seen.  So unless Bob has every block of every
branch from the moment Alice got that payment, that transaction
invalidating Alice's proposed transaction to him could be somewhere he
hasn't seen.


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.

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.

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.
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.

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.
There's no well known / well defined domain / space of what dataset in
which you would show non-existence.
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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20180129/f0ff3a7c/attachment.html>