Mining subsidy in a DAG - page 4. | Bitcointalksearch.org

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 10, 2016, 04:56:53 AM

Quote from: monsterer on February 10, 2016, 04:52:07 AM

What about adopting a similar scheme to DagCoin?

DagCoin allows double spends as well, but the way they update their confirmation scores is different to Tangle, I think, because a double spend at the same score which becomes merged doesn't have it's score updated as more transactions get added:

https://bitslog.files.wordpress.com/2015/09/dagcoin-v41.pdf#page=2

What should Bob do if he is catching up downloading all transactions from Alice? He didn't see transactions generated in real time.

You refer to this line?

Quote

Whenever a transaction references a list of previous transactions, if there are two
conflicting transactions, then the one with highest score prevails. If both have the same score, then
the order of referencing establishes preferences over the conflicting transactions, such that the first
transaction gets its score increased but any following double-spend will not

Because there is no objective measure of which was 'first'? I guess that's why you need a tie-breaker rule, like lowest txid?

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 10, 2016, 04:52:07 AM

What about adopting a similar scheme to DagCoin?

DagCoin allows double spends as well, but the way they update their confirmation scores is different to Tangle, I think, because a double spend at the same score which becomes merged doesn't have it's score updated as more transactions get added:

https://bitslog.files.wordpress.com/2015/09/dagcoin-v41.pdf#page=2

What should Bob do if he is catching up downloading all transactions from Alice? He didn't see transactions generated in real time.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 10, 2016, 04:04:35 AM

Quote from: monsterer on February 10, 2016, 03:59:53 AM

How are the transactions actually applied, i.e. how do you calculate the balance of an address/account?

Plain sum in any order.

What about adopting a similar scheme to DagCoin?

DagCoin allows double spends as well, but the way they update their confirmation scores is different to Tangle, I think, because a double spend at the same score which becomes merged doesn't have it's score updated as more transactions get added:

https://bitslog.files.wordpress.com/2015/09/dagcoin-v41.pdf#page=2

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 10, 2016, 03:59:53 AM

How are the transactions actually applied, i.e. how do you calculate the balance of an address/account?

Plain sum in any order.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 09, 2016, 07:05:29 PM

Quote from: monsterer on February 09, 2016, 05:04:41 PM

I think I see why this can't work for you - tell me if I'm correct: if you adopted the rule that double spends didn't cause an orphaned branch, the cumulative weight of a legitimate transaction and it's double spend could continue to increase together, leading to a situation where the MCMC would give a misleading confidence reading on the legitimate transaction, because although on the macro scale the transaction has a high confidence, on the micro scale the double spend may have a tiny priority edge, meaning it gets applied first?

First half is correct. I'm not 100% sure about the bolded part, you should ask mthcl who created that algorithm.

How are the transactions actually applied, i.e. how do you calculate the balance of an address/account?

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 09, 2016, 05:04:41 PM

I think I see why this can't work for you - tell me if I'm correct: if you adopted the rule that double spends didn't cause an orphaned branch, the cumulative weight of a legitimate transaction and it's double spend could continue to increase together, leading to a situation where the MCMC would give a misleading confidence reading on the legitimate transaction, because although on the macro scale the transaction has a high confidence, on the micro scale the double spend may have a tiny priority edge, meaning it gets applied first?

First half is correct. I'm not 100% sure about the bolded part, you should ask mthcl who created that algorithm.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 09, 2016, 04:42:48 PM

Quote from: monsterer on February 09, 2016, 04:34:19 PM

The metric should provide some confidence indicator to the merchant, though - if there was a double spend at exactly the same weight as the legitimate transaction, surely this confidence indicator would show 0?

Weight doesn't matter much in Iota. If 97 tips will contain legit transaction and 3 other ones doublespending transaction (or none) then confidence level will be 97%.

I think I see why this can't work for you - tell me if I'm correct: if you adopted the rule that double spends didn't cause an orphaned branch, the cumulative weight of a legitimate transaction and it's double spend could continue to increase together, leading to a situation where the MCMC would give a misleading confidence reading on the legitimate transaction, because although on the macro scale the transaction has a high confidence, on the micro scale the double spend may have a tiny priority edge, meaning it gets applied first?

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 09, 2016, 04:34:19 PM

The metric should provide some confidence indicator to the merchant, though - if there was a double spend at exactly the same weight as the legitimate transaction, surely this confidence indicator would show 0?

Weight doesn't matter much in Iota. If 97 tips will contain legit transaction and 3 other ones doublespending transaction (or none) then confidence level will be 97%.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 09, 2016, 04:06:17 PM

Quote from: monsterer on February 09, 2016, 03:59:31 PM

Well, presumably the merchant needs some kind of metric to know it is safe to accept the payment? Whatever the case, you need a tie-breaker rule of some kind otherwise how do you tell which identically weighted branch not containing double spends to extend?

This metric is the percentage of tips picked with MCMC algorithm that contain his transaction of interest. Because of probabilistic nature of MCMC it can't be used as a trigger for paying the subsidy.

The metric should provide some confidence indicator to the merchant, though - if there was a double spend at exactly the same weight as the legitimate transaction, surely this confidence indicator would show 0?

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 09, 2016, 03:59:31 PM

Well, presumably the merchant needs some kind of metric to know it is safe to accept the payment? Whatever the case, you need a tie-breaker rule of some kind otherwise how do you tell which identically weighted branch not containing double spends to extend?

This metric is the percentage of tips picked with MCMC algorithm that contain his transaction of interest. Because of probabilistic nature of MCMC it can't be used as a trigger for paying the subsidy.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 09, 2016, 03:38:18 PM

Quote from: monsterer on February 09, 2016, 03:30:43 PM

With identical PoW, you'd need a tiebreaker rule, such as lowest TXID.

This gives an easy way to doublespend: buy coffee with high TXID, send the same tokens to your another account but with lower TXID and in a "distant" region of Internet.

Well, presumably the merchant needs some kind of metric to know it is safe to accept the payment? Whatever the case, you need a tie-breaker rule of some kind otherwise how do you tell which identically weighted branch not containing double spends to extend?

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: TPTB_need_war on February 09, 2016, 03:47:17 PM

Thus no one wants history in their parent chain that can be voided by a double-spend, so the incentive is to maximally broaden the DAG.

Transactions that have no parents won't be confirmed too. The sweet spot is somewhere in the middle.

TPTB_need_war

sr. member

Activity: 420

Merit: 262

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

Thus no one wants history in their parent chain that can be voided by a double-spend, so the incentive is to maximally broaden the DAG.

(Notwithstanding how could a subsidy even work in a DAG when there are no blocks to win?)

[1]	https://bitcointalksearch.org/topic/m.13530099 https://bitcointalksearch.org/topic/m.13530264 https://bitcointalksearch.org/topic/m.13632887

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 09, 2016, 03:30:43 PM

With identical PoW, you'd need a tiebreaker rule, such as lowest TXID.

This gives an easy way to doublespend: buy coffee with high TXID, send the same tokens to your another account but with lower TXID and in a "distant" region of Internet.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 09, 2016, 03:11:41 PM

* Then users would be unable to come to consensus. Could you decide which of doublespending is legit if both have near-equal PoW confirming it?

With identical PoW, you'd need a tiebreaker rule, such as lowest TXID.

Quote from: Come-from-Beyond on February 09, 2016, 03:11:41 PM

* This brings us back to blockchain which is vulnerable to quantum computers.

Quite possibly. If that was an overwhelming concern designed to address a realistic scenario.

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 09, 2016, 02:36:54 PM

So, the optimal strategy for profit in this case is to always pollute the 'other guy's branch with a double spend such that it becomes orphaned, thereby decreasing the chances of your own branch from being orphaned?

Some questions to explore:

* what if a double spend did not create an orphaned branch?

* what if you employ adjusting difficulty for the subsidy only (leaving non subsidised transactions at regular difficulty), such that it becomes extremely obvious which branch is at the best height, because the frequency of such blocks would be very low compared to other transactions?

I'm not sure that it's the optimal strategy but the state where everyone doesn't do doublespendings, obviously, is not an equilibrium.

* Then users would be unable to come to consensus. Could you decide which of doublespending is legit if both have near-equal PoW confirming it?

* This brings us back to blockchain which is vulnerable to quantum computers.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 09, 2016, 01:39:41 PM

Now, taking the above into account, tell what strategy you would use to maximize your profits if doublespending is very cheap (very low difficulty of finding a nonce).

Another question, what would change in your strategy if there was no subsidy at all?

Which of these strategies allow the system to settle in one of Nash equilibria?

So, the optimal strategy for profit in this case is to always pollute the 'other guy's branch with a double spend such that it becomes orphaned, thereby decreasing the chances of your own branch from being orphaned?

Some questions to explore:

* what if a double spend did not create an orphaned branch?

* what if you employ adjusting difficulty for the subsidy only (leaving non subsidised transactions at regular difficulty), such that it becomes extremely obvious which branch is at the best height, because the frequency of such blocks would be very low compared to other transactions?

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 09, 2016, 01:16:54 PM

I've noticed both public designs for a DAG were careful to avoid a mining subsidy. I'd like to discuss why this was the case, and if there would be any way around the problem.

One argument is that is rewarding every node in the DAG creates an incentive to widen the DAG; but I'm not entirely clear why this must be the case.

In bitcoin there is an incentive to mine on the best block of the chain, because you stand a greater chance of having your block orphaned by the majority hash rate if you do not.

Why can't the same be true for a DAG?

I can speak only about Iota, which uses a DAG instead of a chain.

A case when there are 2+ branches is very common in high-load regime (high TPS rate). Let's imagine that there are branches A and B. And every graph node gets X tokens of subsidy. Eventually these branches will merge together and everyone will be happy with those earned tokens. There are computers on the network that see only branch A and some that see only branch B. Someone who sees the both branches can spend a token in one branch and doublespend in another. Those who see the both branches will ignore one of the nodes and won't extend the graph on top of it. The others will extend the branch they see and hope that they will get the earned subsidy. Unfortunatelly, because of the doublespending these branches will never merge and only one will survive making the other one orphaned and the earned tokens disappearing.

Now, taking the above into account, tell what strategy you would use to maximize your profits if doublespending is very cheap (very low difficulty of finding a nonce).

Another question, what would change in your strategy if there was no subsidy at all?

Which of these strategies allow the system to settle in one of Nash equilibria?

yassin54

legendary

Activity: 1540

Merit: 1000

Thanks for the Thread, waitching now

monsterer

legendary

Activity: 1008

Merit: 1007

I've noticed both public designs for a DAG were careful to avoid a mining subsidy. I'd like to discuss why this was the case, and if there would be any way around the problem.

One argument is that is rewarding every node in the DAG creates an incentive to widen the DAG; but I'm not entirely clear why this must be the case.

In bitcoin there is an incentive to mine on the best block of the chain, because you stand a greater chance of having your block orphaned by the majority hash rate if you do not.

Why can't the same be true for a DAG?

Topic: Mining subsidy in a DAG - page 4. (Read 4527 times)