DagCoin: a cryptocurrency without blocks

[Sergio_Demian_Lerner]

DagCoin: a cryptocurrency without blocks

Back in 2012 I thought a lot on a new cryptocurrency that could merge the concepts of transaction and block. Each transaction would carry a proof-of-work and reference one or more previous transactions. The resulting authenticated data structure would be a Direct Acyclic Graph (DAG) of transactions where each transaction “confirms” one or more previous transactions. The confirmation security of a transaction would be measured in accumulated amount of proof-of-work referencing (or confirming) the transaction. This structure is well suited for a cryptocurrency without subsidy (such as a side-chain). On the past years I’ve read a couple of similar proposals on bitcointalk (although I cannot find the references now). When the GHOST paper was published, I perceived it as a reinforcement of my idea that a tree could give more security than a chain in case of high rate of transactions.

My open problems…

The problem that I could not solve in 2012 is how to limit the maximum cut of the generated DAG or, in other words, how to prevent all new transactions from referencing the same set of parent transactions. How to create the incentive to “move forward”? The DAG must not increase in “width”, and it should look more like a DAG-chain. Also one must prevent users from choosing old transactions to extend the DAG. I tried several monetary incentive structures to force users to choose newer transactions, but with no result. To know the last “ledger state” there must be a way to consolidate branches. Merging branches should be good, but not too good such that everyone starts merging the same branches over and over. The problem of spam was also less important, as no transaction would be able to get a “free ride” in a block, as each transaction carries PoW. Ultimately the owners of a computer that is being part of a spamming botnet would realize their computers have been hijacked based on the amount of CPU consumed. For instance, if a transaction requires a proof-of-work that takes 1 second in a standard PC, and each transaction is 400 bytes in size, then a botnet consisting in 10K computers may create transaction reaching 3 Mbytes/second. This high network bandwidth usage itself is not a problem, since it can disrupt the network only as long as the attack is active. However, there must be a way to prevent the DAG-chain from growing at that pace. It turns out that the election of an optimal data structure allows the DAG-chain to be compressed, but it requires us to change how we think about double-spends, and how we conceive the “ledger state”.

A Radical Change

The leap of faith required to find an out-of-the-box solution is to think about double-spends not as a boolean attribute, but as a probabilistic attribute, based on comparing the confirmation work on competing transactions. An the security of a transaction, as the confirmation work compared to the the work expected that an adversary may use. Also it requires to forget about the concept of a “global ledger state”. In Bitcoin there is a global ledger state. Chain reorganizations can always rollback the state, but the state is globally consistent. There is a certain probability of the last block rolling back, but the probability is the same for every transaction in that block. In this proposal, the ledger state is just the overlap of all possible transactions, each with its own confirmation probability, and there is no consistent global state.

Design Premise: “The cryptocurrency network benefits from creating a DAG growing as “thin” as possible.”

In other words, having the average maximal cut as low as possible. It seems that referencing many previous transactions (high out degree) can make the DAG thinner only if the following transactions reference the transaction with high out degree, but are themselves of low out degree. So we want high out degree some times, but low out degree another times.

I designed a DAG that tries to fulfill that premise, and an associated incentive structure such that:

 There is a benefit for users to reference as many previous transactions as possible
 Referencing many previous transactions is incentivized only when there are many previous transactions unreferenced.
 There is no competition between users to reference a previous transaction.

Here is the paper draft  –> DagCoin-v4 https://bitslog.files.wordpress.com/2015/09/dagcoin-v41.pdf

This same article can be found in my blog: https://bitslog.wordpress.com/2015/09/11/dagcoin/

[1713497548]

1713497548

[Come-from-Beyond]

Very interesting. I'm coding a very similar system right now. 80% is already done.

[tromp]

I would feel more convinced of the well behaviour of this DAG if every transaction
can be viewed as the end point of a totally ordered valid sequence of transactions.

That would prevent the situation you describe where two ancestor transactions are in conflict.
I think that should make the joint descendant transaction invalid.

For a transaction referencing k parents tx_1..tx_k, we would like to define its total
order in terms of those of its parents. Let TX be the last transaction in their
intersection. Then all these histories agree up to TX and we need to define
a valid merge of the k sequence suffixes. Some merges will have conflicts, which
is something to be avoided. The problem reduces to the question of
which of the next available transactions (whose number is between 2 and k)
should extend the total order defined so far.

Have you considered whether this approach to well-ordering is feasible?

[Tobo]

Very interesting. I'm coding a very similar system right now. 80% is already done.

Is it the quorum based Qubic?

[Come-from-Beyond]

Is it the quorum based Qubic?

No.

[bitcoinpaul]

Is it the quorum based Qubic?

No.

Woho, another one. Tell us more.

[Come-from-Beyond]

Woho, another one. Tell us more.

Just read the OP. That description suits on 90%.

[Tobo]

Is it the quorum based Qubic?

No.

Does it have anything to do with jl777's Crypto777? I remember you sold some technology to jl777.

[Come-from-Beyond]

Does it have anything to do with jl777's Crypto777? I remember you sold some technology to jl777.

That tech was about pegging.

[patmast3r]

This is very interesting.
I'm wondering though how this could ever be rolled out as it literally needs the network to be active (or not ?). If I wanna transact I need someone else to transact as well and confirm my tx with his tx. I guess I could also send some more tx myself but that's not really going to fly.

[Sergio_Demian_Lerner]

This is very interesting.
I'm wondering though how this could ever be rolled out as it literally needs the network to be active (or not ?). If I wanna transact I need someone else to transact as well and confirm my tx with his tx. I guess I could also send some more tx myself but that's not really going to fly.

It only works if there is a backlog of transactions.

The magic behind any new cryptocurrency token is that since you can create money, you can set an incentive to confirm old transactions. So you can bootstrap your cryptocurrency.

When Bitcoin has no or very low subsidy, it will need a backlog of transactions to go forward. So the problem with DagCoin is bootstrapping. If you have an application where you can keep a flow of transactions going, you can make it work. Also you can add a subsidy to each transaction that has a very high PoW, and create an inflationary cryptocurrency whose price varies with electricity cost and inflates with Moore's law.

[Sergio_Demian_Lerner]

I would feel more convinced of the well behaviour of this DAG if every transaction
can be viewed as the end point of a totally ordered valid sequence of transactions.

This is true for DagCoin. If a transaction references two parents having conflicting transactions, only one of them becomes valid, and that is the one with more PoW. If both have the same PoW, then the first one is the valid one. Never a transaction validates two conflicting recursively referenced txs.

The only drawback is that which one is the valid one is not immediate obvious: you need the appropriate data structure and the whole transaction tree (up to a checkpoint) to find which one is the valid one.

I think one of the new ideas about DagCoin is that the number of parents you can reference is not chosen by the user, but by the PoW found: the lower the hash, the higher the number of parents you must reference.

[tsoPANos]

It sounds to me quite interesting.
Actually, I had similar ideas over time, but I didn't bother messing with them.

[Tobo]

Comparing to Bitcoin, what are the advantages and disadvantages of Dagcoin?

[mcelrath]

Sergio, why are you worried about the "width" of the DAG?  I would think that every miner is incentivized to extend the "tips" of the DAG.  It really comes down to the metric for "work".  Bitcoin's measure of work is extremely simplistic because of its linear structure.  With a DAG you're looking at the "work" in the set of transactions upstream of the current transaction.  If miners "widen" the DAG, they are not contributing work...all the transactions have the same amount of work -- that of themselves plus their parent.  So this seems easy to solve by computing "work" in a smarter way.

I have a couple of preliminary formulas for calculating work in a DAG under certain constant-target assumptions that eliminate your concern, I think, but I feel there's still a better solution I haven't found yet.  I also want to get rid of the target difficulty and simply combine whatever hashes show up.  (This then frees "difficulty" to be a node-specific quantity that can be used for bandwidth control and DDoS protection)

In case you haven't seen it, I propose the same thing (DAG-chain) here:

http://blog.sldx.com/three-challenges-for-scaling-bitcoin/

I have a longer draft with a lot more specifics on the DAG/braid concept that I'm not ready to publish just yet.  Only as of last week am I paid to work on bitcoin, so can actually bring it to fruition.  We should see if we can collaborate, feel free to contact me privately.

[Come-from-Beyond]

So this seems easy to solve by computing "work" in a smarter way.

This smarter way may open the system to Sybil attacks if it removes "linearity", splitting/merging/recombination of transactions may give adversary an advantage in this case.

I also want to get rid of the target difficulty and simply combine whatever hashes show up.

Without difficulty you don't know if someone did a lot of work or just was superlucky (and got a lot of leading zeros).

[Sergio_Demian_Lerner]

Sergio, why are you worried about the "width" of the DAG?  I would think that every miner is incentivized to extend the "tips" of the DAG.  

As I didn't run simulations, I was worried about how would the width vary for different loads on the network. I want users to be able to reference many parent transactions if the braid is getting "thick", and reference only one if the braid is a chain. What would be the rule for the client wallet to decide ? As processing a transaction having many parents has a cost to the network, then this amount must be linked with the transaction PoW somehow.

I read your post and some other posts about this same matter the last months, so I decided to publish my old draft paper, so that others can use those ideas. But I'm not actively working on it.
 

[Carlton Banks]

I was just thinking to myself, "but how will the initial distribution be handled under this coin?"... and then I suddenly realised the problem is already solved  .

This, or similar such ideas, sound like a potential solution to the possible problems when bitcoin hits the zero block reward stage. To be exploring that area so early is an optimistic sign  

[ashour]

Really Interesting idea, a coin without blocks can solve many problems that bitcoin is having.

[crazyearner]

Nice ideas and innovation of a future coin. Hope you succeed in making it happen as need something different that stands out from the rest of them. Without blocks will be different but how is this going to be controlled or being accessed. How will the distribution be provided without blocks? Am guessing going to be using a different name or distribution service to provide miners if going to be mineable or another ICO? If this becomes ICO then CMO. Stuck on my watch list for the future to see how this turns out.