Mining subsidy in a DAG | Bitcointalksearch.org

TPTB_need_war

sr. member

Activity: 420

Merit: 262

I finally found that link and inserted it into this quoted post from upthread:

Quote from: TPTB_need_war on February 16, 2016, 03:39:33 AM

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

This is from the DagCoin paper:

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.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: TPTB_need_war on February 17, 2016, 12:17:39 PM

Quote from: monsterer on February 17, 2016, 11:16:47 AM

Quote from: TPTB_need_war on February 17, 2016, 11:14:06 AM

Total ordering is proven impossible by the Second Law of Thermodynamics and because the speed-of-light is not infinite.

For the same reason you can't reach the edge of the universe because there is no edge.

You're thinking about the problem in terms which are too concrete. Take bitcoin's blocks, for instance - if you take the genesis block and the current best block, would you say that sequence of blocks constitutes a total order? What about if you included orphans in the ordering?

If you monetize all orphans then orphans will be unbounded.

My generative essence point applies in spades.

Scary. That reminds me of a line from Dr.Strangelove! Cheesy

An excellent observation - however, no one said anything about rewarding orphans.

edit: my hint was to get you thinking along the right lines

TPTB_need_war

sr. member

Activity: 420

Merit: 262

Quote from: monsterer on February 17, 2016, 11:16:47 AM

Quote from: TPTB_need_war on February 17, 2016, 11:14:06 AM

Total ordering is proven impossible by the Second Law of Thermodynamics and because the speed-of-light is not infinite.

For the same reason you can't reach the edge of the universe because there is no edge.

You're thinking about the problem in terms which are too concrete. Take bitcoin's blocks, for instance - if you take the genesis block and the current best block, would you say that sequence of blocks constitutes a total order? What about if you included orphans in the ordering?

If you monetize all orphans then orphans will be unbounded.

My generative essence point applies in spades.

Sorry this discussion is unproductive until you explain precisely how you totally ordered the universe. I'll be waiting. Roll Eyes

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: TPTB_need_war on February 17, 2016, 11:14:06 AM

Total ordering is proven impossible by the Second Law of Thermodynamics and because the speed-of-light is not infinite.

For the same reason you can't reach the edge of the universe because there is no edge.

You're thinking about the problem in terms which are too concrete. Take bitcoin's blocks, for instance - if you take the genesis block and the current best block, would you say that sequence of blocks constitutes a total order? What about if you included orphans in the ordering?

TPTB_need_war

sr. member

Activity: 420

Merit: 262

Quote from: monsterer on February 17, 2016, 11:11:26 AM

Quote from: TPTB_need_war on February 17, 2016, 11:07:27 AM

You will end up right back to why Iota had to adopt a mathematical model of this. There is no structural (of the tree structure) model which will give you these consensus properties without a mathematical model driving what payers and payees choose.

Do you accept that this is possible with a total order of transactions?

Total ordering is proven impossible by the Second Law of Thermodynamics and because the speed-of-light is not infinite.

For the same reason you can't reach the edge of the universe because there is no edge.

For the same reason that the future and past don't collapse into one infinitesimal point in spacetime, because we have friction and speed-of-light is finite.

TPTB_need_war

sr. member

Activity: 420

Merit: 262

Quote from: Come-from-Beyond on February 16, 2016, 01:18:41 PM

Quote from: monsterer on February 16, 2016, 12:15:47 PM

I don't think the model in the paper fully includes all the factors it needs; IIRC it doesn't consider the payer's cheapest way to ensure timely confirmation in the face of the double spend branch orphaning problem. If a payer is required to choose between submitting his transaction N times, which costs (PoW x N), and submitting it further back in the history, but only once (PoW x 1), then it seems his cheapest choice is to widen the DAG?

Not enough information to make a conclusion. We need to do in-field testing.

As CfB wrote in response to me upthread, the optimal strategy has to be some balance between maximal and minimal breadth because in the former case then no one's transactions ever get confirmed.

The issue is which strategy do payers and payees choose? And what are the game theories? And is a Nash equilibrium created?

I argue it is very dubious and likely the math model will need to be centrally enforced. But I don't know if there is some math which convinces that I am incorrect.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: TPTB_need_war on February 17, 2016, 11:07:27 AM

You will end up right back to why Iota had to adopt a mathematical model of this. There is no structural (of the tree structure) model which will give you these consensus properties without a mathematical model driving what payers and payees choose.

Do you accept that this is possible with a total order of transactions?

TPTB_need_war

sr. member

Activity: 420

Merit: 262

Quote from: monsterer on February 17, 2016, 10:20:16 AM

Quote from: TPTB_need_war on February 17, 2016, 10:05:11 AM

In the meantime, payers need to know where to place their transactions in the DAG so the transactions don't become eventually invalid. And payees need to know NOW which transactions to honor.

Transactions never become invalid except for double spends and their payee chain - invalidation cascade is limited to the output involved in the double spend.

Payee's have a metric for transaction acceptability - point at which it becomes unprofitable for an attacker to double spend them.

You will end up right back to why Iota had to adopt a mathematical model of this. There is no structural (of the tree structure) model which will give you these consensus properties without a mathematical model driving what payers and payees choose.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: TPTB_need_war on February 17, 2016, 10:05:11 AM

In the meantime, payers need to know where to place their transactions in the DAG so the transactions don't become eventually invalid. And payees need to know NOW which transactions to honor.

Transactions never become invalid except for double spends and their payee chain - invalidation cascade is limited to the output involved in the double spend.

Payee's have a metric for transaction acceptability - point at which it becomes unprofitable for an attacker to double spend them.

TPTB_need_war

sr. member

Activity: 420

Merit: 262

Quote from: TPTB_need_war on February 17, 2016, 10:04:13 AM

Quote from: monsterer on February 17, 2016, 09:48:35 AM

Quote from: TPTB_need_war on February 17, 2016, 09:46:09 AM

The system must have some means of converging on a consensus choice amongst competing double-spends.

Your thread is a discussion about that. We don't need to repeat that discussion here.

Eventual total ordering.

In the meantime, payers need to know where to place their transactions in the DAG so the transactions don't become eventually invalid. And payees need to know NOW which transactions to honor. Please quote my reply and post your reply in your thread, not in this thread.

I copied this post to your thread. Please continue to there. Please.

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 16, 2016, 12:15:47 PM

The consensus power of the network decreases linearly in the number of partitions. You've noted this yourself earlier in this thread: https://bitcointalksearch.org/topic/m.13847669

Some partitions disappear because transactions are reincluded into the DAG, no need to merge branches, leave some abandoned.

Quote from: monsterer on February 16, 2016, 12:15:47 PM

I don't think the model in the paper fully includes all the factors it needs; IIRC it doesn't consider the payer's cheapest way to ensure timely confirmation in the face of the double spend branch orphaning problem. If a payer is required to choose between submitting his transaction N times, which costs (PoW x N), and submitting it further back in the history, but only once (PoW x 1), then it seems his cheapest choice is to widen the DAG?

Not enough information to make a conclusion. We need to do in-field testing.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 16, 2016, 12:08:13 PM

Quote from: monsterer on February 16, 2016, 11:46:18 AM

I'm using the wrong terminology. I should be saying 'partitions', rather than branches. The consensus power of the network decreases linearly in the number of partitions.

So what is the problem with partitions in DAG?

The consensus power of the network decreases linearly in the number of partitions. You've noted this yourself earlier in this thread: https://bitcointalksearch.org/topic/m.13847669

Quote from: monsterer on February 16, 2016, 11:46:18 AM

The model shows that in high-load regime DAG never converges into a single point, it pulses in cosine-like pattern (number of tips goes from low to high and back). A wide DAG is not good but it's not fatal.

I don't think the model in the paper fully includes all the factors it needs; IIRC it doesn't consider the payer's cheapest way to ensure timely confirmation in the face of the double spend branch orphaning problem. If a payer is required to choose between submitting his transaction N times, which costs (PoW x N), and submitting it further back in the history, but only once (PoW x 1), then it seems his cheapest choice is to widen the DAG?

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 16, 2016, 11:46:18 AM

I'm using the wrong terminology. I should be saying 'partitions', rather than branches. The consensus power of the network decreases linearly in the number of partitions.

So what is the problem with partitions in DAG?

Quote from: monsterer on February 16, 2016, 11:46:18 AM

Yes, 0-confirmation transactions. More specifically, the optimal referencing policy a transaction submitter should adopt - the probability that your transaction will not be orphaned is increased by only referencing transactions a few generations behind the tips. This widens the DAG, which is the opposite of consensus, which requires the narrowest possible DAG.

The model shows that in high-load regime DAG never converges into a single point, it pulses in cosine-like pattern (number of tips goes from low to high and back). A wide DAG is not good but it's not fatal.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 16, 2016, 11:27:37 AM

Quote from: monsterer on February 16, 2016, 11:11:15 AM

Merging branches is a requirement for convergence. Consider a DAG with infinite branches; the consensus power of the network is reduced to 0%.

Your edge case doesn't prove your claim. I can even say that merging of branches is not needed for consensus.

I'm using the wrong terminology. I should be saying 'partitions', rather than branches. The consensus power of the network decreases linearly in the number of partitions.

Quote from: monsterer on February 16, 2016, 11:11:15 AM

Are you talking about 0-conf transactions? Because if a transaction has made into 90% of branches then the attacker needs to outpace 90% of the network.

Yes, 0-confirmation transactions. More specifically, the optimal referencing policy a transaction submitter should adopt - the probability that your transaction will not be orphaned is increased by only referencing transactions a few generations behind the tips. This widens the DAG, which is the opposite of consensus, which requires the narrowest possible DAG.

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 16, 2016, 11:11:15 AM

Merging branches is a requirement for convergence. Consider a DAG with infinite branches; the consensus power of the network is reduced to 0%.

Your edge case doesn't prove your claim. I can even say that merging of branches is not needed for consensus.

Quote from: monsterer on February 16, 2016, 11:11:15 AM

Again, this implies that convergence has been lost because you are requiring participants to confirm their own transactions, which degenerates into a system where an attacker doesn't have to outpace the network anymore, he only has to outpace his victim.

Are you talking about 0-conf transactions? Because if a transaction has made into 90% of branches then the attacker needs to outpace 90% of the network.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 16, 2016, 10:44:45 AM

Branches don't need to be merged, we can have 100 branches all the time and still have a transaction in the past confirmed by 90%+ of total hashing power.

Wow, nice use of colour!

Merging branches is a requirement for convergence. Consider a DAG with infinite branches; the consensus power of the network is reduced to 0%.

Quote from: Come-from-Beyond on February 16, 2016, 10:44:45 AM

New parts will be extended by those who need their recent transactions confirmed and who can afford to do the same PoW 10 times. Even weak PoW hashers will make forward progress if odds that their PoW will be wasted is low enough.

Again, this implies that convergence has been lost because you are requiring participants to confirm their own transactions, which degenerates into a system where an attacker doesn't have to outpace the network anymore, he only has to outpace his victim.

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 16, 2016, 10:02:58 AM

Coming to consensus on some state in the past is ok, I agree. However, diverging from consensus by not merging partitions, or agreeing not to make forward progress by extending old parts of the DAG are both not ok results.

Branches don't need to be merged, we can have 100 branches all the time and still have a transaction in the past confirmed by 90%+ of total hashing power.

New parts will be extended by those who need their recent transactions confirmed and who can afford to do the same PoW 10 times. Even weak PoW hashers will make forward progress if odds that their PoW will be wasted is low enough.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 16, 2016, 09:40:14 AM

Sounds right to me. You are supposed to find a sweet spot and if you fail you'll be forced to do PoW again, maybe even several times.

DAG comes to consensus on some state in the past, check page 11 of http://188.138.57.93/tangle.pdf to get the idea.

Coming to consensus on some state in the past is ok, I agree. However, diverging from consensus by not merging partitions, or agreeing not to make forward progress by extending old parts of the DAG are both not ok results.

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: monsterer on February 16, 2016, 09:03:14 AM

Of course, but this is not the point. If I am submitting a transaction I want to maximise the chances that my transaction get's approved the most, but I cannot be sure when I submit if any of the parents I reference will be orphaned. So, in order to minimise the chance that my transaction gets orphaned, I must reference as few transactions as possible - or, I can try to reference very old transactions which I know are unlikely to get orphaned. So, on the one hand, I am incentivised to avoid merging branches, and on the other, I am incentivised to extend the DAG from a historical location. Both of these choices lead to the opposite of consensus for the DAG overall.

Sounds right to me. You are supposed to find a sweet spot and if you fail you'll be forced to do PoW again, maybe even several times.

DAG comes to consensus on some state in the past, check page 11 of http://188.138.57.93/tangle.pdf to get the idea.

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: Come-from-Beyond on February 16, 2016, 08:39:06 AM

Quote from: monsterer on February 16, 2016, 08:27:07 AM

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.

Of course, but this is not the point. If I am submitting a transaction I want to maximise the chances that my transaction get's approved the most, but I cannot be sure when I submit if any of the parents I reference will be orphaned. So, in order to minimise the chance that my transaction gets orphaned, I must reference as few transactions as possible - or, I can try to reference very old transactions which I know are unlikely to get orphaned. So, on the one hand, I am incentivised to avoid merging branches, and on the other, I am incentivised to extend the DAG from a historical location. Both of these choices lead to the opposite of consensus for the DAG overall.

Topic: Mining subsidy in a DAG (Read 4527 times)