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

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 11, 2016, 04:37:12 AM

Quote from: monsterer on February 11, 2016, 03:34:04 AM

There is already an example of this from the DagCoin paper:

Transaction 10 is a competing double spend, which will need to redo all the PoW from itself to the tip of the DAG to become the canonical spend.

You must have something else in mind?

I mean a situation where [2] and [3] are doublespendings of each other and [10] is irrelevant.

This is covered by the tiebreaker rule, isn't it?

Here are the possible cases, as I see them:

1. Legitimate spend and double spend are both tips of the DAG with the same cumulative weight

Tiebreaker rule resolves in the favour of the lowest txid. Subsequent transactions are built on top of the lowest txid.

2. Legitimate spend is a DAG tip, the attacker produces a double spend with a lower txid to challenge it

Attacker must catch up to the cumulative weight of the legitimate spend, which should have been extended by the time the attacker's transaction gets placed. This is similar to outpacing the network in bitcoin.

3. Legitimate spend and double spend are at the same cumulative weight and their branches merge

Again, tiebreaker rule resolves to update the confirmation score of the transaction with the lower txid.

Any other cases I missed?

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 11, 2016, 03:34:04 AM

There is already an example of this from the DagCoin paper:

Transaction 10 is a competing double spend, which will need to redo all the PoW from itself to the tip of the DAG to become the canonical spend.

You must have something else in mind?

I mean a situation where [2] and [3] are doublespendings of each other and [10] is irrelevant.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 10, 2016, 03:53:37 PM

Quote from: monsterer on February 10, 2016, 03:25:32 PM

Can you give an example of a very hard situation to resolve?

Both transactions differ only in payment beneficiary part and the hacker is "promoting" one that loses the race.

There is already an example of this from the DagCoin paper:

Transaction 10 is a competing double spend, which will need to redo all the PoW from itself to the tip of the DAG to become the canonical spend.

You must have something else in mind?

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 10, 2016, 03:25:32 PM

Can you give an example of a very hard situation to resolve?

Both transactions differ only in payment beneficiary part and the hacker is "promoting" one that loses the race.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 10, 2016, 02:34:31 PM

Quote from: monsterer on February 10, 2016, 02:23:01 PM

For this to be robust, it should be as expensive to give priority to a double spend as redoing all the PoW from the point of the double spend to the tip with the most cumulative weight in the DAG.

And this is (almost) impossible when merging of conflicting branches is allowed.

Can you give an example of a very hard situation to resolve?

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 10, 2016, 02:23:01 PM

For this to be robust, it should be as expensive to give priority to a double spend as redoing all the PoW from the point of the double spend to the tip with the most cumulative weight in the DAG.

And this is (almost) impossible when merging of conflicting branches is allowed.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 10, 2016, 02:08:20 PM

Quote from: monsterer on February 10, 2016, 02:03:13 PM

Inserting transactions into past history is bad, no matter if you have a subsidy or not, isn't it?

It's not about changing the history, it's about manipulating score of legit and doublespending transactions.

For this to be robust, it should be as expensive to give priority to a double spend as redoing all the PoW from the point of the double spend to the tip with the most cumulative weight in the DAG.

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 10, 2016, 02:03:13 PM

Inserting transactions into past history is bad, no matter if you have a subsidy or not, isn't it?

It's not about changing the history, it's about manipulating score of legit and doublespending transactions.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 10, 2016, 01:34:56 PM

Quote from: monsterer on February 10, 2016, 01:18:35 PM

Can you describe how they can disrupt consensus with double spends?

By adding transactions there and here they can switch the doublespending status from legit to doublespending again, which will create an avalanche of depending transactions changing the status as well.

Inserting transactions into past history is bad, no matter if you have a subsidy or not, isn't it?

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 10, 2016, 01:18:35 PM

Can you describe how they can disrupt consensus with double spends?

By adding transactions there and here they can switch the doublespending status from legit to doublespending again, which will create an avalanche of depending transactions changing the status as well.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 10, 2016, 12:38:42 PM

Quote from: monsterer on February 10, 2016, 11:37:46 AM

I agree. But, in the general case, the cumulative weight would be different?

No, if the hacker keeps modifying the graph with intention to disrupt the consensus (it's another attack vector that appears if you allow doublespendings to be included). By trying to solve the subsidy problem we add other (more critical) problems.

Can you describe how they can disrupt consensus with double spends?

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 10, 2016, 11:37:46 AM

I agree. But, in the general case, the cumulative weight would be different?

No, if the hacker keeps modifying the graph with intention to disrupt the consensus (it's another attack vector that appears if you allow doublespendings to be included). By trying to solve the subsidy problem we add other (more critical) problems.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 10, 2016, 11:31:17 AM

Quote from: monsterer on February 10, 2016, 07:11:26 AM

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?

This is a very special case, the general case needs a more solid proof than cycling through (all) possible combinations of the graph.

I agree. But, in the general case, the cumulative weight would be different?

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 10, 2016, 07:11:26 AM

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?

This is a very special case, the general case needs a more solid proof than cycling through (all) possible combinations of the graph.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 10, 2016, 07:00:55 AM

Quote from: monsterer on February 10, 2016, 06:41:46 AM

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?

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 10, 2016, 06:41:46 AM

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.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 10, 2016, 06:37:28 AM

Quote from: monsterer on February 10, 2016, 06:15:45 AM

It is possible that the merchant doesn't see one branch right away, but the majority of the rest of the network will see both, and if they follow the tie breaking rule to build confirmation on the legitimate transaction, once the merchant eventually catches up to the network, the other branch will be revealed, and everything gets resolved?

Exactly. Resolved, and the tokens spent on the cup of coffee will return to the hacker's pocket.

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

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 10, 2016, 06:15:45 AM

It is possible that the merchant doesn't see one branch right away, but the majority of the rest of the network will see both, and if they follow the tie breaking rule to build confirmation on the legitimate transaction, once the merchant eventually catches up to the network, the other branch will be revealed, and everything gets resolved?

Exactly. Resolved, and the tokens spent on the cup of coffee will return to the hacker's pocket.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 10, 2016, 06:07:39 AM

I can generate 2 conflicting transactions which will reference exactly the same set of DAG nodes. In other words, they will be identical and differ only in payment beneficiary part. In this case you can't say which goes earlier, i.e. ordering is impossible. Am I right?

Right.

Quote from: Come-from-Beyond on February 10, 2016, 06:07:39 AM

The tie-breaker rule can't be used because it's a fallacy that merchant's computer will see the both transactions. Unless the system guarantees a better than eventual consistency, of course.

PS: There was a discussion somewhere about tie-breaker for Bitcoin blocks, unfortunatelly, can't find it right now, got only https://bitcointalksearch.org/topic/why-doesnt-bitcoin-use-a-tiebreaking-rulewhen-comparing-chains-of-equal-length-355644...

It is possible that the merchant doesn't see one branch right away, but the majority of the rest of the network will see both, and if they follow the tie breaking rule to build confirmation on the legitimate transaction, once the merchant eventually catches up to the network, the other branch will be revealed, and everything gets resolved?

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 10, 2016, 05:06:15 AM

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?

I can generate 2 conflicting transactions which will reference exactly the same set of DAG nodes. In other words, they will be identical and differ only in payment beneficiary part. In this case you can't say which goes earlier, i.e. ordering is impossible. Am I right?

The tie-breaker rule can't be used because it's a fallacy that merchant's computer will see the both transactions. Unless the system guarantees a better than eventual consistency, of course.

PS: There was a discussion somewhere about tie-breaker for Bitcoin blocks, unfortunatelly, can't find it right now, got only https://bitcointalksearch.org/topic/why-doesnt-bitcoin-use-a-tiebreaking-rulewhen-comparing-chains-of-equal-length-355644...

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