A DAG-Based Cryptocurrency Framework

This is a transcript of Christopher Carr’s presentation at Master Workshop: Layer 1 solutions, which took place at Primalbase AMS.

What’s a DAG? My talk will go along these lines. An introduction - what is a DAG and why do we want to use them? Then I will talk about the Graphchain framework, which was originally a STAG-based framework that we wrote about a while ago. We’ve called this Graphchain for the purposes of naming things. Then we will talk about the design choices, the main challenges, and then a conclusion.

Just in case you’re interested in where this came from, I originally wrote this paper — Graphchain: a Blockchain-free Scalable Decentralised Ledger — with Xavier Boyen and Thomas Haines, in 2016. We put this on ePrint and there’s a perhaps more readable version in an ERCIM News article. This work is also published in other places. but these are probably the easiest to find.

What Are DAGs?

First, what do we mean by DAG? We mean a Directed Acyclic Graph. This sort of comes from this mathematical term for a graph, and generally you have these sets which consist of vertices and edges. Edges are just ordered pairs of vertices and they are normally represented as arrows if you have a directed graph. A graph is acyclic if you can’t start at one vertex and get back to the other following the arrows. You might understand that that is not exactly a mathematical term.

The diagram (below) is an example of a DAG. Edges — the arrows, and vertices — the orange boxes. You can see by inspection here that there are no cycles. You can’t start at one of these orange boxes, follow the arrows and get back to an orange box. That’s a DAG. You can also label these DAGs.

If you do, you can have what is called a Partially Ordered Set. In the work that we did, we talk a lot about Partially Ordered Sets. The idea here is you have a partial ordering because, if you define an arrow going to something as being higher than the one that the arrow is coming from, you can easily see that k is above all of these other letters. You can also quickly see that for f and h, there is no ordering between the two of them. All that we know about f and h is that they’re above d and that they’re below i.

So, it’s a partial order, unlike another kind of DAG which we are all familiar with, which is the blockchain (below), which is totally ordered. Actually, it’s really fun if you start thinking about how you end up with these orphan blocks, and how many orphans you can have. I don’t have time to go into that but it is quite fun, trust me. You do get forks, but blockchain’s are essentially DAGs as well, they’re just far more constrained. You can’t have all these extra partial orders.

Why do we need a DAG?

What are we trying to address? The main things we are trying to address here are decentralisation and scale. There are a lot of problems with blockchain technology. These are perhaps two of the most talked about - there are some others as well, but the two that interest me the most are the decentralisation issue, which really boils down to security. Also the scalability issue, which is kind of about usability. Scale is still there. Where do these come from? Well, do these issues seem to stem from the use of blocks of transactions? That might be the case.

The aims of our entire project were: can we create a system where you are rewarded for individual effort? The major problem, and you’re probably all aware of this, are that mining pools are causing a bit of an issue. They are causing an issue because they essentially have a bit too much power — some people think they have too much power. I tend to think that. They’re not necessarily a bad thing, there are a lot of arguments for and against them, I don’t really want to get into that, but wouldn’t it be nice if we didn’t have to have them?

Can we remove the incentive for joining mining pools? That was one of the questions. Also, whilst we’re doing this, is it possible to also allow for faster transaction processing. What if we could just broadcast transactions with the proof-of-work attached, collate these transactions and build a graph out of them. Then, do we even need blocks? This is the DAG-based thinking, at least.

Why is this important? Because is 51% honest users enough? No! We’ve known that for ages. So what is decentralisation anyway? This one is a far trickier issue. It’s kind of mixed up with notions of distributed design, so you might rightly ask what we really mean by decentralisation. I think actually trying to answer that question is kind of tricky. There are a lot of people who have thoughts on what we really mean by decentralisation, especially in cryptocurrencies. Roughly, we want lots of independent machines all over the world running the same system. It would also be nice if we had it so the machines were computationally equivalent. Like I say, it’s nothing new, people have been saying this for a while.

What are these we’re talking about? We’re kind of talking about mining pools and mining farms. In the ‘independent machines all over the world running the same system’ — really machines are running one mining pool system. And, in terms of machines being computationally equivalent, we have mining farms. So we have, essentially, one machine that has a lot of power. The second issue is not something that I think DAG is going to necessarily deal with. It depends on the functionality.

But also, scale is a major issue as well. When we talk about blockchains, why are we concerned about scale? Well, because blockchain’s have this linear set of blocks where one transaction refers to the next. The problem is, no matter what sort of blockchain you’re dealing with, blocks contain a certain amount of transactions. They have a certain period in which transaction can come in. As we just heard, we know the limits for Ethereum, we know the limits for Bitcoin.

Part of the problem is because we have blocks and we stick them with so many transactions, so we might have two different blocks where one contains transactions T1 to Tn and one is T1 to Tn prime. We don’t know if they’re the same — maybe they’re the same list of transactions, maybe they’re not.

With a blockchain, if we get a split, we have to pick one. This is sort of a fork, right. So we’re now waiting to see which one will become extended before we can say which transactions we know. If I had some transactions in T prime, I now would have to wait for them to be included somewhere later. We can’t rely on the transactions being included.

Of course, this is a generalisation. You could imagine that by some freak occurrence you have tonnes and tonnes of blocks that are produced at the same time. With blockchains plus, which is Ethereum and the ghost protocol stuff, you have uncle blocks which can be included. Now, that’s a really smart idea, but you’re not including the transactions. So, you can still reward someone for their effort, which is a really smart idea in creating this extra block, because people should be rewarded for their trying.

Essentially, the whole idea was: can we also have a system like this, where you create a new block, and you include the transactions from both T and T prime, the sort of union of the transactions?

This is the Graphchain, essentially. The things we had were: What is there are no blocks? Transactions just refer to previous transactions and as many as you like. To post a transaction you simply collect transactions that you agree with and you refer to them, and you attach some proof of work to the transaction.

How can this Work?

We can define abstractly a sort of proof of work function. This is quite an abstract idea but it’s realised in practice quite easily, with hash functions. It’s quite easy to say a proof-of-work function S takes a puzzle a and a solution b. We can say S(a, b) is true if b is a solution to a. If you think about a blockchain, for example, the solution might be a nonce and your a is your set of transactions and your link to the previous block and all that other data.

What we want to be able to do is quantify the work, so we can say the work of this proof of work function = d. We can do this, most of the time we can do this. If you can partially invert a hash function, you can say it must have taken this much computational effort or we expect it to have taken this much computational effort.

So, we are able to do this, and this is happening already because mining pools are essentially doing the same thing. If you work for a mining pool, you’re not solving the block and then handing it to them, you’re proving you’re working for them by showing them that you have solved it to a lesser extent. So maybe if it’s in Bitcoin, you want to find the value below a certain threshold. You’re showing them that you have found solutions that are below a higher threshold — but at least it shows you’re working for them.

Essentially, we can use the same sort of thing. The idea is to quantify how much work has been directed toward solving a certain puzzle. Abstract function can be anything where we have somehow quantifiable as to how hard it is to find a solution for a puzzle. We don’t even need hash functions, you can imagine doing this with something else. Again, we kind of tried to envisage this as a framework. We can broadcast transactions with an associated work value. The point of doing this is that we can say: here’s a block, and it has work value 8, for example.

So, you take your DAG again, then you can maybe imagine some numbers and you can say: ok, now we’ve got all these numbers, what does that mean? Good question. What we do is we define these two notions of weight and height. This is very similar to blockchain in the respect that you have an accumulated amount of work. Once we label the graph with work values, we can now label it with other values.

For weight, for example, we have this cumulative work associated with the transaction and all of its descendants. The height is the cumulative work associated with the transaction and all of its ancestors. For example, you can see that essentially the weight is adding up all of the proof of work value to each of these transactions.

So, we’re able to say (below), the weight of a transaction is 61. Why do we want to say this? Because it gives us a slowly built up idea of how embedded this transaction is in the system. For height, you have a system where you count all the descendant transactions. Interestingly enough, you are also counting the transaction itself. So, for the second transaction (also below, in darker red), we can say it has a height of 80. Essentially, these are just two examples, but what we’re trying to say is we can build up this idea of how tall in the graph a transaction is based on the proof of work it’s built on.

There’s one other thing we need to do in a DAG-based system. We need to start to eliminate transactions that are further down. The reason that we have to do this is that if you are given a new graph, so you haven’t seen any transactions recently, and you have to suddenly work out how high they are, it quickly gets quite computationally expensive as the number of transactions in the system blows up. You have to limit this and eventually start to get rid of transactions that are further back. This is kind of a separate thing.

There is added complexity in doing this DAG-based design, which is quite tricky. In essence, if you can do this, what we want to do is get this property of convergence. If transactions can just refer to any other previous transactions, what is stopping users creating new transactions at very old nodes?

You need incentives. This is part of the framework as well. We need incentives, we want users to build from the top of the graph, so reward is tied to some function of the height. So, for simplicity, I have simply written this. However, it’s not quite as simple as that. If the function was, say, an inverse function, it wouldn’t work very well. But you do need some sort of function of the height in order to create this incentive for working from the front. The point in doing this is that we’re then able to perform transactions and encourage people to work at the very front of the transaction. We leave this unspecified because, again, we’re trying to develop a framework.

The point in convergence is that you end up with a green transaction that essentially is at the top of the list. It’s the converged transaction and every transaction below it is part of its ancestry. And, based on the function, everyone wants to go for this new green transaction — if you’re going to build a new transaction you will refer to this top one. That’s the idea.

We also have to worry about something else, though. We have to worry about something like double spending. Let’s consider a double spending scenario. You have a transaction graph like this (below), and suddenly these two red transactions are double spending some sort of money.

Ok, so how do you overcome this? You compare these. You end up in a situation where you have to compare these and decide which one you want to go on. Imagine you have an active adversary situation. We can kind of generalise the split in the systems to: what if the adversary wants to essentially keep the systems split forever. You can generalise this to, basically, two graphs that can’t be built upon, because you can’t refer to two conflicting transactions. Do they need to double spend and make sure the system never converges?

The adversary has a situation now where they have to build on one of these two transactions. They also have to outpace the rest of the network, which is trying to build on one of these transactions. So, imagine a situation where the honest or, rather, incentively compatible nodes first create a transaction which is significantly high enough to be like ‘this is the new realistic graph.’ The adversary then has to create a new transaction on the other chain. We can assign this some probability. Then this happens again and again, and so on, and you kind of end up with this probability (below).

You can see that this gets very small very quickly. But this only works provided the adversary doesn’t have the majority of computational power. This is one of the arguments for it.

Just to give you a bit of [Graphchain] overview: you create transactions at your own pace, you are rewarded for individual effort. You encourage transactions at the tip by incentives, and we allow for multiple transactions to gain convergence. Proof-of-work builds up closer to real time, so the hope is that you have these much smaller transactions that are created by people and the proof-of-work is established by the individuals transacting. And, finally, that the framework is agnostic towards proof of work functions, or even reward functions to some degree.

Differences with Existing DAG Systems

So, there are other DAG systems out there that you may have heard of. IOTA is probably the most well known, it had a significant market value for a while. The major differences are that there is not really any incentive — there is a sort of mining, but there are really no incentives. And they are currently using coordinators. But they are very similar in terms of diagrams and stuff, and their website uses diagrams similar to what I have just presented. You can look those up, they’re quite interesting actually.

Other implemented ones are Byteball — they’re kind of seemingly similar but they have this difference with trusted witnesses. Nano kind of uses a distributed proof-of-stake protocol and conflicts are removed by voting. Both of these systems are also really cool, I would recommend having a look into them. They obviously have pros and cons. Our framework tries to be a bit more agnostic and a bit more decentralised.

Conclusion

Not only did I work on this academically — we have this paper on it — I am also full-time at NTNU in Norway developing this framework as a working cryptocurrency. I gave a talk maybe six months ago on this Norwegian national TV, after which I got speaking to these TTO (technology transfer office) guys and now I’m working to develop this into a working cryptocurrency — for fun, which turns out to be really hard. But we are at the initial stage of the project. We recently just won some funding and we are looking for developers.

In summary, we are trying to keep or even expand the idea of a decentralised cryptocurrency and we also want a system that can scale. That’s the most important thing we have. Maybe the scalability will be limited at some point in a practical sense — this is something we are trying to find out — but hopefully it is attractive to a lot of users. Thank you for listening.

Q&A

Could you go back to the slide with the balancing attack? Where you showed the probability of the adversary? I think what you are missing here is that you are assuming that the honest nodes will have built on one chain, but actually, the honest nodes don’t know which one is the correct one.

You’re right about that, but the thing is, the adversary will have to build on both. If the adversary knew which one the honest nodes were building on, it could build on the other. But it doesn’t, so the adversary also has to build on both, so the adversary has to split its computing power as well. This is how this works. I am actually missing a term out here — normally there is a probability that the honest players will both create a chain at the same time, and I am missing that out. I kind of did that on purpose because I thought no one would notice. The major point, though, is that the adversary has to split its computing power to extend both because it also doesn’t know which is the chain that the rational players will extend first.

But still, you would like to make blocks in parallel, because that’s the whole point in scaling? Then you have honest blocks on one chain and honest blocks on the other chain, and they are approximately at the same rate. You need just a little bit of hash rate to balance both.

I think it’s approximately the same rate without them moving ahead in a significant point that becomes the term here. It still becomes quite small quite quickly. Obviously, it depends on the computing power of the adversary.