Directed Acyclic Graph (DAG)

Basics

• To assess the difference in capabilities between the Blockchain technology as used in the Bitcoin network and the Directed Acyclic Graphs (DAG) being used by Byteball, Faisal Ramdan Mulyadi, a software developer at Dunia, a financial information website, said: “In mathematics and computer science, a Directed Acyclic Graph (DAG), is a finite directed graph with no directed cycles. That is, it consists of finitely many vertices and edges, with each edge directed from one vertex to another, such that there is no way to start at any vertex v and follow a consistently-directed sequence of edges that eventually loops back to v again while Blockchain is a distributed database that maintains a continuously-growing list of ordered records called blocks.”
• In byteball this is called DAG (directed acyclic graph) - every new transaction references one or more earlier ones by including and signing their hashes. By including its parents, each new transaction also indirectly includes and confirms all parents of the parents, parents of the parents of the parents, and so on.
• Other well known DAG's are IOTA & Nano
• To learn more about DAG's: check here
• From a paper (Summer 2019) by Andrew Poelstra (Blockstream) and David Vorick (Sia) on it's advantages and on why it hasn't been adopted by Bitcoin:

"Ethereum uses a not-correct version of something called Ghost DAG. The bitcoin blockchain is a straight line, if you get forks or competing blocks then only one of them wins. You discard everything else. I think there was a 2015 paper called "inclusive lbockchain protocols" which presented an approach using directed acyclic graph approach to blockchain. Multiple miners can release blocks at the same time, and then there's an algorithm to linearize those blocks and the invalid transactions you just ignore. The DAG approach solves particularly miner challenges. It allows you to have faster block times, lower safe confirmation times, it reduces the pressure on miners to have fast propagation. So fast propagation is no longer as important. It doesn't help with initial block validation, you still have to check every output every spend. That resource bottleneck doesn't change, therefore this isn't seen as true scalability at least today because it doesn't solve our biggest bottleneck.

Another thing that slows down DAGs from being accepted in bitcoin is that it's a pretty serious hard-fork. It's a big deal to change how the blockheaders work. This makes SPV a lot more expensive because there's a lot more blocks. The other thing really holding this back is that it has deep game theory problems. I think there's a research paper that went and fully fleshed out the incentives. I've had it on my reading list for a while but I can't find it. Until we recover that paper, or someone else writes a new one, we don't have a formal outlay of the incentives and we don't have a convincing formal proof that selfish mining techniques are strictly less effective on DAG-based protocols than they are on bitcoin. I currently think this is true, but I don't think there's a proof out there. You wouldn't want to switch to this. The whole point of DAGs is to make selfish mining less bad, and we need a proof that it actually achieves this, and I don't think we have a fully fleshed out system yet.

Q: Would it be correct to say, a 51% adversary, block time isn't really reduced-- meaning the safe confirmation time?

A: Yes. Correct. DAGs are only advantageous in terms of confirmation security if we're assuming that nobody has greater than 51% of the hashrate. If someone does have greater than 51% of the hashrate, then things are falling more back to meta incentives anyway."