[Cryptography] DAG vs Blockchain

[Ray Dillinger]

On 01/26/2018 06:09 PM, bexnews at gmail.com wrote:
> Much hype exists around DAG (directed acyclic graph) in some parts, as
> an improvement on blockchain crypto because, for one thing, it does away
> with mining. However isn't mining the thing that incentivizes increased
> computing power to verify the blockchain and protect against a 51%
> attack?  Would DAGs be less secure against attackers with lots of
> computing power *because* there is no mining?
> 
> Thanks

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.

Unless there is some property of a transaction that makes it possible
for Bob to prove that he has already looked at every block in the DAG
where that transaction might be, and the set of blocks he needs to
download in order to prove it is also much smaller than the total number
of blocks that have been created since the txOut was created, then there
isn't a scalability advantage over a block chain.  There probably is a
good cryptographic way to achieve this but I haven't seen it yet.  I'd
call it a six-banana problem, meaning probably in about three days of
thinking hard and ignoring everything else, I could either come up with
a practical protocol (which may work without being a solution for the
most general case) or become satisfied that there isn't a practical
protocol.

Now, everything I've seen so far has Bob either downloading every block
of every branch hunting for that transaction, or blindly (without proof)
accepting the assertion of other nodes that no such transaction exists.
Bearing in mind that those peer nodes have the same problem as Bob in
terms of not having complete information.

I don't believe blindly trusting peer nodes also in possession of
incomplete information, without proof, is an adequate guarantee for a
cryptocurrency application. And if Bob has to have every block of every
branch down to the current moment, then what's the scalability advantage
over a block chain?


					Bear

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20180128/76b64999/attachment.sig>