Bitcoin Forum
April 25, 2017, 08:51:59 AM *
News: Latest stable version of Bitcoin Core: 0.14.1  [Torrent]. (New!)
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 3 4 5 6 7 8 9 10 »  All
  Print  
Author Topic: DagCoin: a cryptocurrency without blocks  (Read 26804 times)
Sergio_Demian_Lerner
Hero Member
*****
expert
Offline Offline

Activity: 534


View Profile WWW
September 11, 2015, 11:10:14 PM
 #1

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/
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1493110319
Hero Member
*
Offline Offline

Posts: 1493110319

View Profile Personal Message (Offline)

Ignore
1493110319
Reply with quote  #2

1493110319
Report to moderator
1493110319
Hero Member
*
Offline Offline

Posts: 1493110319

View Profile Personal Message (Offline)

Ignore
1493110319
Reply with quote  #2

1493110319
Report to moderator
1493110319
Hero Member
*
Offline Offline

Posts: 1493110319

View Profile Personal Message (Offline)

Ignore
1493110319
Reply with quote  #2

1493110319
Report to moderator
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 1554

Newbie


View Profile
September 11, 2015, 11:50:52 PM
 #2

Very interesting. I'm coding a very similar system right now. 80% is already done.
tromp
Hero Member
*****
Offline Offline

Activity: 494


View Profile
September 12, 2015, 12:02:13 AM
 #3

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
Hero Member
*****
Offline Offline

Activity: 706


View Profile
September 12, 2015, 01:53:29 AM
 #4

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

Is it the quorum based Qubic?
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 1554

Newbie


View Profile
September 12, 2015, 07:43:21 AM
 #5

Is it the quorum based Qubic?

No.
bitcoinpaul
Hero Member
*****
Offline Offline

Activity: 700



View Profile
September 12, 2015, 10:16:08 AM
 #6


Woho, another one. Tell us more.
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 1554

Newbie


View Profile
September 12, 2015, 10:22:45 AM
 #7

Woho, another one. Tell us more.

Just read the OP. That description suits on 90%.
Tobo
Hero Member
*****
Offline Offline

Activity: 706


View Profile
September 12, 2015, 11:19:22 AM
 #8


Does it have anything to do with jl777's Crypto777? I remember you sold some technology to jl777.
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 1554

Newbie


View Profile
September 12, 2015, 11:38:29 AM
 #9

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

That tech was about pegging.
patmast3r
Hero Member
*****
Offline Offline

Activity: 952


View Profile
September 12, 2015, 12:02:24 PM
 #10

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
Hero Member
*****
expert
Offline Offline

Activity: 534


View Profile WWW
September 12, 2015, 12:15:42 PM
 #11

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
Hero Member
*****
expert
Offline Offline

Activity: 534


View Profile WWW
September 12, 2015, 12:23:27 PM
 #12

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
Hero Member
*****
Offline Offline

Activity: 546

Don't let them take away your potential. Fight.


View Profile
September 12, 2015, 12:54:31 PM
 #13

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

Activity: 706


View Profile
September 12, 2015, 01:45:18 PM
 #14

Comparing to Bitcoin, what are the advantages and disadvantages of Dagcoin?
mcelrath
Newbie
*
Offline Offline

Activity: 4


View Profile
September 12, 2015, 01:49:13 PM
 #15

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
Legendary
*
Offline Offline

Activity: 1554

Newbie


View Profile
September 12, 2015, 09:44:04 PM
 #16

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
Hero Member
*****
expert
Offline Offline

Activity: 534


View Profile WWW
September 13, 2015, 12:38:55 PM
 #17

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
Legendary
*
Offline Offline

Activity: 1610



View Profile
September 13, 2015, 02:35:06 PM
 #18

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  Wink.

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  Smiley

Vires in numeris
ashour
Sr. Member
****
Offline Offline

Activity: 462


View Profile
September 13, 2015, 06:12:13 PM
 #19

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

crazyearner
Legendary
*
Offline Offline

Activity: 1624



View Profile
September 14, 2015, 02:17:41 AM
 #20

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.
Pages: [1] 2 3 4 5 6 7 8 9 10 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!