Bitcoin Forum
December 15, 2024, 06:21:37 PM *
News: Latest Bitcoin Core release: 28.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: « 1 2 [3] 4 »  All
  Print  
Author Topic: Mining subsidy in a DAG  (Read 4530 times)
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2142
Merit: 1010

Newbie


View Profile
February 11, 2016, 11:09:22 AM
 #41

Any other cases I missed?

[Doublespending #1] -- {A} -- {B} -- {C} -- {D} -- ...
[Doublespending #2] -- {N} -- {O} -- {P} -- {Q] -- ...

If others add E, F, G then the hacker adds R, S, T.
If others add R, S, T then the hacker adds E, F, G.
monsterer (OP)
Legendary
*
Offline Offline

Activity: 1008
Merit: 1007


View Profile
February 11, 2016, 11:34:28 AM
 #42

Any other cases I missed?

[Doublespending #1] -- {A} -- {B} -- {C} -- {D} -- ...
[Doublespending #2] -- {N} -- {O} -- {P} -- {Q] -- ...

If others add E, F, G then the hacker adds R, S, T.
If others add R, S, T then the hacker adds E, F, G.

The attacker must have more power than the rest of the network to pull this off?
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2142
Merit: 1010

Newbie


View Profile
February 11, 2016, 11:37:07 AM
 #43

The attacker must have more power than the rest of the network to pull this off?

No, the attacker must have less power than guys extending the other branch. There can be more than 2 branches and someone can extend attacker's branch too (because they don't see the other branch). In high-load regime with 10 near-equal branches 5% should be enough for that attack.
monsterer (OP)
Legendary
*
Offline Offline

Activity: 1008
Merit: 1007


View Profile
February 11, 2016, 11:45:10 AM
 #44

The attacker must have more power than the rest of the network to pull this off?

No, the attacker must have less power than guys extending the other branch. There can be more than 2 branches and someone can extend attacker's branch too (because they don't see the other branch). In high-load regime with 10 near-equal branches 5% should be enough for that attack.

I agree this could be possible. It seems you need an incentive for users to merge branches, such that the effect of this kind of partitioning is minimised.

edit: etherium pays an additional subsidy to miners who merge branches, that could be one way to approach the problem.
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2142
Merit: 1010

Newbie


View Profile
February 11, 2016, 11:48:51 AM
 #45

I agree this could be possible. It seems you need an incentive for users to merge branches, such that the effect of this kind of partitioning is minimised.

edit: etherium pays an additional subsidy to miners who merge branches, that could be one way to approach the problem.

Merging of branches that contain doublespendings creates this problem. Getting rid of the problem instead of creating it and trying to solve (and it's not clear that paying more solves it) leads to a better design.
monsterer (OP)
Legendary
*
Offline Offline

Activity: 1008
Merit: 1007


View Profile
February 11, 2016, 12:14:18 PM
 #46

I agree this could be possible. It seems you need an incentive for users to merge branches, such that the effect of this kind of partitioning is minimised.

edit: etherium pays an additional subsidy to miners who merge branches, that could be one way to approach the problem.

Merging of branches that contain doublespendings creates this problem. Getting rid of the problem instead of creating it and trying to solve (and it's not clear that paying more solves it) leads to a better design.

Merging of double spends fixes the problem because it forces the end of the partition (I've added confirmation scores to the transactions):

[Doublespending #1] -- {A3} -- {B2} -- {C1} -- {D0} -- ...
[Doublespending #2] -- {N3} -- {O2} -- {P1} -- {Q0} -- ...

after merge:

[Doublespending #1] -- {A5} -- {B4} -- {C3} -- {D2} -- ...
                                                                              -- {E1} -- -- {F0} --
[Doublespending #2] -- {N3} -- {O4} -- {P3} -- {Q2} -- ...
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2142
Merit: 1010

Newbie


View Profile
February 11, 2016, 12:24:18 PM
 #47

Merging of double spends fixes the problem because it forces the end of the partition (I've added confirmation scores to the transactions):

[Doublespending #1] -- {A3} -- {B2} -- {C1} -- {D0} -- ...
[Doublespending #2] -- {N3} -- {O2} -- {P1} -- {Q0} -- ...

after merge:

[Doublespending #1] -- {A5} -- {B4} -- {C3} -- {D2} -- ...
                                                                              -- {E1} -- -- {F0} --
[Doublespending #2] -- {N3} -- {O4} -- {P3} -- {Q2} -- ...

The score of #1 or #2 can be changed by attaching a transaction to any of A, B, C, D, N, O, P or Q even if E and F are already here. And if #1 starts winning the hacker will promote #2 and vice versa. Don't see how E and F fix the problem.

PS: Note that tie-breaker rule is not applied if difference between the scores of #1 and #2 is big enough, and the hacker can swing the balance from one to another indefinitely.
monsterer (OP)
Legendary
*
Offline Offline

Activity: 1008
Merit: 1007


View Profile
February 11, 2016, 02:57:26 PM
 #48

The score of #1 or #2 can be changed by attaching a transaction to any of A, B, C, D, N, O, P or Q even if E and F are already here. And if #1 starts winning the hacker will promote #2 and vice versa. Don't see how E and F fix the problem.

PS: Note that tie-breaker rule is not applied if difference between the scores of #1 and #2 is big enough, and the hacker can swing the balance from one to another indefinitely.

You're completely correct. Thinking about it some more, this is a significant problem with DagCoin; and it wouldn't be a problem except for double spends, because the completely arbitrary transaction ordering only falls over in the face of double spends, which is presumably why Tangle chose to orphan branches.

There is a way around this problem, but it requires a more structured DAG and a deterministic transaction ordering.
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2142
Merit: 1010

Newbie


View Profile
February 11, 2016, 03:16:48 PM
 #49

...and a deterministic transaction ordering.

Looking forward to reading your paper on this matter...
fbueller
Sr. Member
****
Offline Offline

Activity: 412
Merit: 287


View Profile
February 11, 2016, 08:00:00 PM
 #50

Out of the talks at Hong Kong, I enjoyed this video as an intro to DAG. https://www.youtube.com/watch?v=fst1IK_mrng&feature=youtu.be&t=2h17m20s

Bitwasp Developer.
monsterer (OP)
Legendary
*
Offline Offline

Activity: 1008
Merit: 1007


View Profile
February 11, 2016, 08:23:09 PM
 #51

Out of the talks at Hong Kong, I enjoyed this video as an intro to DAG. https://www.youtube.com/watch?v=fst1IK_mrng&feature=youtu.be&t=2h17m20s

That's actually a really good talk - do you know where I can get the slides?

edit: got it: https://scalingbitcoin.org/hongkong2015/presentations/DAY2/2_breaking_the_chain_1_mcelrath.pdf
TPTB_need_war
Sr. Member
****
Offline Offline

Activity: 420
Merit: 262


View Profile
February 16, 2016, 08:39:33 AM
Last edit: February 17, 2016, 08:41:11 PM by TPTB_need_war
 #52

Only if the merchant doesn't wait long enough, surely? At least this way, the ambiguity is removed.

How is it removed if the both are included into DAG and doublespending may eventually get more PoW? Even a year later.

This is from the DagCoin paper:



I've circled the tiebreaker rule, which for example, might use lowest txid. The only way for what you described to happen, is if that entire branch never gets extended, isn't it? Because if it continues getting extended, you can see the double spend doesn't get confirmed, but the legit transaction does?

Btw, you might want to reference the post I made within the past month or so (probably in my Decentralized thread in Altcoin Discussion) wherein I pointed out that Sergio had an egregious error in his conceptualization on that diagram.

...and a deterministic transaction ordering.

Looking forward to reading your paper on this matter...

Can't be done because of what I wrote upthread:

The simple answer is that without a longest chain rule there is no synchrony in distributed systems, thus there is no possibility that there won't be multiple branches (partitions) that can't converge (due to double-spends). This is also why monsterer's tree design can't function without blocks (and I had explained this to him in the Decentralization thread[1] but he is hard-headed).

[...]

[1]https://bitcointalk.org/index.php?topic=1319681.msg13530099#msg13530099
https://bitcointalk.org/index.php?topic=1319681.msg13530264#msg13530264
https://bitcointalk.org/index.php?topic=1319681.msg13632887#msg13632887

monsterer (OP)
Legendary
*
Offline Offline

Activity: 1008
Merit: 1007


View Profile
February 16, 2016, 09:28:18 AM
 #53

Btw, you might want to reference the post I made within the past month or so (probably in my Decentralized thread in Altcoin Discussion) wherein I pointed out that Sergio had an egregious error in his conceptualization on that diagram.

I'm not sure what post you refer to. The critical error, as I see it, is that you can change the weighting on historical transactions, which affects contemporary transactions.
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2142
Merit: 1010

Newbie


View Profile
February 16, 2016, 10:20:13 AM
 #54

Can't be done because of what I wrote upthread:

Well, my current knowledge lets me guess that you are right, but what if monsterer has done a break-through in distributed systems...
monsterer (OP)
Legendary
*
Offline Offline

Activity: 1008
Merit: 1007


View Profile
February 16, 2016, 10:30:16 AM
 #55

Can't be done because of what I wrote upthread:

Well, my current knowledge lets me guess that you are right, but what if monsterer has done a break-through in distributed systems...

What I'm looking at currently, is the incentive to merge branches. The rational behavior for a participant in lieu of an incentive is not to merge branches. That has dire consequences for the consensus of the chain. DagCoin's proposed incentives don't work either - how does Iota solve the problem?
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2142
Merit: 1010

Newbie


View Profile
February 16, 2016, 11:48:13 AM
 #56

What I'm looking at currently, is the incentive to merge branches. The rational behavior for a participant in lieu of an incentive is not to merge branches. That has dire consequences for the consensus of the chain. DagCoin's proposed incentives don't work either - how does Iota solve the problem?

More branches you merge - higher chance that someone approves your transaction.
monsterer (OP)
Legendary
*
Offline Offline

Activity: 1008
Merit: 1007


View Profile
February 16, 2016, 12:07:57 PM
 #57

What I'm looking at currently, is the incentive to merge branches. The rational behavior for a participant in lieu of an incentive is not to merge branches. That has dire consequences for the consensus of the chain. DagCoin's proposed incentives don't work either - how does Iota solve the problem?

More branches you merge - higher chance that someone approves your transaction.

Except in the case of double spends, where the more branches you merge, the lower the chance that your transaction gets approved?
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2142
Merit: 1010

Newbie


View Profile
February 16, 2016, 01:03:21 PM
 #58

Except in the case of double spends, where the more branches you merge, the lower the chance that your transaction gets approved?

In this case you ignore a doublespending and use the previous transaction.
monsterer (OP)
Legendary
*
Offline Offline

Activity: 1008
Merit: 1007


View Profile
February 16, 2016, 01:27:07 PM
 #59

Except in the case of double spends, where the more branches you merge, the lower the chance that your transaction gets approved?

In this case you ignore a doublespending and use the previous transaction.

But what about your example earlier? Temporary partitions caused by network latency mean a double spend is not necessarily visible as such to any given payer.
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2142
Merit: 1010

Newbie


View Profile
February 16, 2016, 01:39:06 PM
 #60

But what about your example earlier? Temporary partitions caused by network latency mean a double spend is not necessarily visible as such to any given payer.

Eventually one of the transactions will win.
Pages: « 1 2 [3] 4 »  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!