Topic: DagCoin: a cryptocurrency without blocks - page 20. (Read 70869 times)
Very interesting. I'm coding a very similar system right now. 80% is already done.
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/
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/
Jump to: