|
Title: Mining subsidy in a DAG Post by: monsterer on February 09, 2016, 06: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? Title: Re: Mining subsidy in a DAG Post by: yassin54 on February 09, 2016, 06:38:37 PM Thanks for the Thread, waitching now :)
Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 09, 2016, 06:39:41 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? Title: Re: Mining subsidy in a DAG Post by: monsterer on February 09, 2016, 07:36:54 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? Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 09, 2016, 08:11:41 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 09, 2016, 08:30:43 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. * 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. Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 09, 2016, 08:38:18 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. Title: Re: Mining subsidy in a DAG Post by: TPTB_need_war on February 09, 2016, 08:47:17 PM 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?)
Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 09, 2016, 08:57:48 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 09, 2016, 08:59:31 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? Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 09, 2016, 09:06:17 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 09, 2016, 09:34:19 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? Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 09, 2016, 09:42:48 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%. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 09, 2016, 10:04:41 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? Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 10, 2016, 12:05:29 AM 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 10, 2016, 08:59:53 AM 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? Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 10, 2016, 09:04:35 AM How are the transactions actually applied, i.e. how do you calculate the balance of an address/account? Plain sum in any order. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 10, 2016, 09:52:07 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 Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 10, 2016, 09:56:53 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 10, 2016, 10:06:15 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? Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 10, 2016, 11:07:39 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 (https://en.wikipedia.org/wiki/Fallacies_of_distributed_computing) 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://bitcointalk.org/index.php?topic=355644.0... Title: Re: Mining subsidy in a DAG Post by: monsterer on February 10, 2016, 11:15:45 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. The tie-breaker rule can't be used because it's a fallacy (https://en.wikipedia.org/wiki/Fallacies_of_distributed_computing) 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://bitcointalk.org/index.php?topic=355644.0... 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? Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 10, 2016, 11:37:28 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 10, 2016, 11:41:46 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. Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 10, 2016, 12:00:55 PM 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 10, 2016, 12:11:26 PM 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: https://i.imgur.com/wmgjSSx.png 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? Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 10, 2016, 04:31:17 PM This is from the DagCoin paper: https://i.imgur.com/wmgjSSx.png 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 10, 2016, 04:37:46 PM This is from the DagCoin paper: https://i.imgur.com/wmgjSSx.png 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? Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 10, 2016, 05:38:42 PM 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 10, 2016, 06:18:35 PM 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? Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 10, 2016, 06:34:56 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 10, 2016, 07:03:13 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? Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 10, 2016, 07:08:20 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 10, 2016, 07:23:01 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. Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 10, 2016, 07:34:31 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 10, 2016, 08:25:32 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? Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 10, 2016, 08:53:37 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 11, 2016, 08:34:04 AM 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: https://i.imgur.com/iNg4bQl.png 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? Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 11, 2016, 09:37:12 AM There is already an example of this from the DagCoin paper: https://i.imgur.com/iNg4bQl.png 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 11, 2016, 11:04:14 AM There is already an example of this from the DagCoin paper: https://i.imgur.com/iNg4bQl.png 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? Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 11, 2016, 11:09:22 AM 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 11, 2016, 11:34:28 AM 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? Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 11, 2016, 11:37:07 AM 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 11, 2016, 11:45:10 AM 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. Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 11, 2016, 11:48:51 AM 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 11, 2016, 12:14:18 PM 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} -- ... Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 11, 2016, 12:24:18 PM 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 11, 2016, 02:57:26 PM 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. Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 11, 2016, 03:16:48 PM ...and a deterministic transaction ordering. Looking forward to reading your paper on this matter... Title: Re: Mining subsidy in a DAG Post by: fbueller on February 11, 2016, 08:00:00 PM 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
Title: Re: Mining subsidy in a DAG Post by: monsterer on February 11, 2016, 08:23:09 PM 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 Title: Re: Mining subsidy in a DAG Post by: TPTB_need_war on February 16, 2016, 08:39:33 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: https://i.imgur.com/wmgjSSx.png 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 (https://bitcointalk.org/index.php?topic=1319681.msg13529994#msg13529994) 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). [...]
Title: Re: Mining subsidy in a DAG Post by: monsterer on February 16, 2016, 09:28:18 AM 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. Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 16, 2016, 10:20:13 AM 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... Title: Re: Mining subsidy in a DAG Post by: monsterer on February 16, 2016, 10:30:16 AM 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? Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 16, 2016, 11:48:13 AM 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 16, 2016, 12:07:57 PM 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? Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 16, 2016, 01:03:21 PM 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 16, 2016, 01:27:07 PM 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. Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 16, 2016, 01:39:06 PM 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 16, 2016, 02:03:14 PM 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. Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 16, 2016, 02:40:14 PM 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 16, 2016, 03:02:58 PM 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. Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 16, 2016, 03:44:45 PM 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 16, 2016, 04:11:15 PM 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%. 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. Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 16, 2016, 04:27:37 PM 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. 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 16, 2016, 04:46:18 PM 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. 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. Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 16, 2016, 05:08:13 PM 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? 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 16, 2016, 05:15:47 PM 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://bitcointalk.org/index.php?topic=1358760.msg13847669#msg13847669 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? Title: Re: Mining subsidy in a DAG Post by: Come-from-Beyond on February 16, 2016, 06:18:41 PM The consensus power of the network decreases linearly in the number of partitions. You've noted this yourself earlier in this thread: https://bitcointalk.org/index.php?topic=1358760.msg13847669#msg13847669 Some partitions disappear because transactions are reincluded into the DAG, no need to merge branches, leave some abandoned. 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. Title: Re: Mining subsidy in a DAG Post by: TPTB_need_war on February 17, 2016, 03:05:11 PM The system must have some means of converging on a consensus choice amongst competing double-spends. Your thread (https://bitcointalk.org/index.php?topic=1358760.msg13900610#msg13900610) 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 (https://bitcointalk.org/index.php?topic=1358760.msg13900610#msg13900610), not in this thread. I copied this post to your thread. Please continue to there. Please. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 17, 2016, 03:20:16 PM 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. Title: Re: Mining subsidy in a DAG Post by: TPTB_need_war on February 17, 2016, 04:07:27 PM 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 17, 2016, 04:11:26 PM 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? Title: Re: Mining subsidy in a DAG Post by: TPTB_need_war on February 17, 2016, 04:12: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. Title: Re: Mining subsidy in a DAG Post by: TPTB_need_war on February 17, 2016, 04:14:06 PM 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. Title: Re: Mining subsidy in a DAG Post by: monsterer on February 17, 2016, 04:16:47 PM 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? Title: Re: Mining subsidy in a DAG Post by: TPTB_need_war on February 17, 2016, 05:17:39 PM 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. ::) Title: Re: Mining subsidy in a DAG Post by: monsterer on February 17, 2016, 05:22:14 PM 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! :D An excellent observation - however, no one said anything about rewarding orphans. edit: my hint was to get you thinking along the right lines Title: Re: Mining subsidy in a DAG Post by: TPTB_need_war on February 17, 2016, 08:42:12 PM I finally found that link and inserted it into this quoted post from upthread:
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 (https://bitcointalk.org/index.php?topic=1319681.msg13529994#msg13529994) in his conceptualization on that diagram. |
