I think you can make DAG work but you will end up with divergent partions that can't be remerged
Why? If there are no conflicting tx's, someone can issue a tx referencing 1 tx from partition 1 and 1 tx from partition 2, et voila. Due the quoted Prisoner's Dilemma that I outlined (for which I believe your response was inadequate for the following reason) in that no one has an incentive to be first to lengthen the tips, the game theory is going to devolve to everyone agreeing to blacklist double-spends without actually abandoning branches containing conflicting transactions where they have transactions.The Prisoner's Dilemma is only solved in favor of lengthening if double-spends won't cause a branch to be illegitimate. Thus the branches will diverge while they lengthen. Your preferred algorithm will not hold over time. CAP's theorem is guidance, and now you just need to model it or put it into the wild and observe. You might try to formulating some fencing or "longest-path" algorithm, but you are just going to end up back at a block chain (giving up Partition tolerance) once you have solved the Consistency and Access issues. Any way if I am wrong, then kindly be the first to disprove the CAP theorem. Good luck with that. If, for example, I'm a merchant who accepted a payment in the "smaller" branch, then I have all the motivation to do some more PoW to make the branches re-merge and therefore increase my safety. And please stop randomly citing Big Important Theorems that have only a vague connection to what we are discussing. In academic circles such behaviour is not welcome. |
|
|
|
I think you can make DAG work but you will end up with divergent partions that can't be remerged
Why? If there are no conflicting tx's, someone can issue a tx referencing 1 tx from partition 1 and 1 tx from partition 2, et voila. |
|
|
|
Contrary to my initial upthread enthusiasm, I am leaning towards this DAG concept can not work because it appears to attempt to defeat the CAP (Brewer's) Theorem
Could you please elaborate? In particular, we don't claim this Consistency (all nodes see the same data at the same time) should be true in iota. |
|
|
|
Possible? I don't see how it's possible to draw a picture to have longest-path-as-the-score rule to be broken by an adversary.
"Longest-path-as-the-score" differs from what is proposed in the whitepaper. We were talking about another algo. Еxactly  Just wait a bit until we finish our internal discussion... |
|
|
|
He would have to attach it "below" the merchant's tx, but yes, you're right, it's a possible attack vector. Anyhow, the referencing algorithm is not yet finished, so we are discussing it with CfB right now.
Possible? I don't see how it's possible to draw a picture to have longest-path-as-the-score rule to be broken by an adversary. Remember that the "longest path algo" is not what's written in the whitepaper Anyhow, let's finish our private discussion in slack and only then make the results public. |
|
|
|
But the cumulative weight of that tx is not so big, so why the merchant should accept it?
NP, the merchant waits of course for normal amount of confirmations. On your picture it has 1 confirmation only?.. I can draw more pictures. But I don't think it's necessary. Imagine that the attacker started preparing for the attack a month ago. He spent the whole month to accumulate PoW on top of the second doublespend. He published no transactions during the month. Then he publishes the first doublespending transaction, provides the first confirmation, thus attaching it to recent part of the tangle, waits for the merchant to send him his puchase. Then publishes his secret subtangle and attaches in to the legit subtangle. The first doublespending transaction now is rejected by the network, the second doublespend has more weight. He would have to attach it "below" the merchant's tx, but yes, you're right, it's a possible attack vector. Anyhow, the referencing algorithm is not yet finished, so we are discussing it with CfB right now. ... there is also a complication that the current height calculation algorithm is not very computationally efficient. We'll have to modify it in any case, and there are already several good candidates. |
|
|
|
But the cumulative weight of that tx is not so big, so why the merchant should accept it?
NP, the merchant waits of course for normal amount of confirmations. On your picture it has 1 confirmation only?.. I can draw more pictures. But I don't think it's necessary. Imagine that the attacker started preparing for the attack a month ago. He spent the whole month to accumulate PoW on top of the second doublespend. He published no transactions during the month. Then he publishes the first doublespending transaction, provides the first confirmation, thus attaching it to recent part of the tangle, waits for the merchant to send him his puchase. Then publishes his secret subtangle and attaches in to the legit subtangle. The first doublespending transaction now is rejected by the network, the second doublespend has more weight. He would have to attach it "below" the merchant's tx, but yes, you're right, it's a possible attack vector. Anyhow, the referencing algorithm is not yet finished, so we are discussing it with CfB right now. |
|
|
|
We know that mining can't be used here because CfB has stated that it undermines the security model.
Can someone link me to that and/or the relevant page of the white paper? Seems to be mining could be used to generate check points. That was one of tweaks I had in mind. PoS can be used for that as well. |
|
|
|
But the cumulative weight of that tx is not so big, so why the merchant should accept it?
NP, the merchant waits of course for normal amount of confirmations. On your picture it has 1 confirmation only?.. |
|
|
|
The attacker doesn't publish it untill he has enough transactions referencing the second doublespending transaction.
The second doublespending won't be referenced because the longest tip already contains the legit transaction. Anyhow, we are discussing now with CfB ways to define better referral algorithms, which would permit to fence off such attacks in a more efficient way. |
|
|
|
Then why the merchant would accept it?
It is released and confirmed. If necessary the attacker himself provides the first confirmation, which connects it to a recent tip. The transaction looks legit. But the cumulative weight of that tx is not so big, so why the merchant should accept it? |
|
|
|
in the event a honest guy tries to reference a legit tip and the attacker's tip, he'll detect the contradiction and won't do it. Therefore, the attacker's subtangle will be abandoned.
This requires not just an honest guy, but a diligent one as well. The risk is that honest guys will be lazy and rely on others to go far back in history to check all tx for double spending. The lazy guys risk that their tx's will be abandoned, because the majority of the nodes won't reference them. That is precisely how I would have answered. It is quite clear that everyone has a strong incentive to be on a correct branch, else any time down stream someone can broadcast a notice that a branch is incongruent then that branch gets abandoned. But doesn't this mean that there is a great incentive to not include tips in your branch, because these don't yet have enough veracity to be sure they won't end up being a double-spend. In your system there is often no way to prove which of the double-spends were first, so they both are invalid. Seems to me no one has an incentive to lengthen instead of broaden the tree. But I haven't absorbed the white paper. Did you address that? Yes. As mentioned somewhere above on this page (or maybe on the previous one), the (default) referencing algorithm works in such a way that it prefers tips with bigger height. So, if you're too lazy and reference some very old tx's, you take the risk that your tx won't be referenced by others. But that default doesn't seem to be the correct game theory? This is Prisoner's Dilemma game. Afaics, lower incentive to go first on including a new tip. Just noticed yesterday this research on cases where the pessimistic Nash equilibrium is claimed not to hold (but on quick glance I ponder if they have overly simplistic assumptions in their models). Obviously if everyone defects to making their own branches (maximally broaden the tree), then no one's tips get lengthened and thus the entire system doesn't function. But is the optimum strategy the default that you assume? We assume that the node knows that most nodes will behave well, and so it's obliged to behave well too. |
|
|
|
Our point is that normally the left yellow tx would be referenced e.g. already by the second green tx.
The attacker doesn't publish it untill he has enough transactions referencing the second doublespending transaction. Then why the merchant would accept it? |
|
|
|
This is the scenario I'm talking about. Green filled, black edged are transactions of the honest network. Red edged - are transactions of the attacker. The doublespends are filled with yellow. As far as I understand your algo, weight of the red tip is greater by 3 than weight of the green tip.  Does this assume that the merchant waited for enough confirmations? Because his transaction seems to have very little confirmation. My picture contains as low amount of transaction as possible, just to express the idea. You can imagine several more transactions of the honest network on top of the green tip, but many more red transactions above the second doublespend. Our point is that normally the left yellow tx would be referenced e.g. already by the second green tx. |
|
|
|
This is the scenario I'm talking about. Green filled, black edged are transactions of the honest network. Red edged - are transactions of the attacker. The doublespends are filled with yellow. As far as I understand your algo, weight of the red tip is greater by 3 than weight of the green tip. Does this assume that the merchant waited for enough confirmations? Because his transaction seems to have very little confirmation. Yes, normally the left yellow tx would have been referenced by many green ones already. |
|
|
|
In your system there is often no way to prove which of the double-spends were first, so they both are invalid.
If we can provide deterministic way to order double-spends then we can include both and ignore the younger one. It's not related to Iota though, just an idea. Anyhow, for that to happen, both double-spending tx's need to be broadcast more or less at the same time. Doesn't sound as a good idea for the attacker... |
|
|
|
in the event a honest guy tries to reference a legit tip and the attacker's tip, he'll detect the contradiction and won't do it. Therefore, the attacker's subtangle will be abandoned.
This requires not just an honest guy, but a diligent one as well. The risk is that honest guys will be lazy and rely on others to go far back in history to check all tx for double spending. The lazy guys risk that their tx's will be abandoned, because the majority of the nodes won't reference them. That is precisely how I would have answered. It is quite clear that everyone has a strong incentive to be on a correct branch, else any time down stream someone can broadcast a notice that a branch is incongruent then that branch gets abandoned. But doesn't this mean that there is a great incentive to not include tips in your branch, because these don't yet have enough veracity to be sure they won't end up being a double-spend. In your system there is often no way to prove which of the double-spends were first, so they both are invalid. Seems to me no one has an incentive to lengthen instead of broaden the tree. But I haven't absorbed the white paper. Did you address that? Yes. As mentioned somewhere above on this page (or maybe on the previous one), the (default) referencing algorithm works in such a way that it prefers tips with bigger height. So, if you're too lazy and reference some very old tx's, you take the risk that your tx won't be referenced by others. |
|
|
|
The algorithm for choosing the tips to reference "prefers" tips with larger cumulative weight. Those precomputed legit transactions will have much smaller cumulative weight (than other tips), and so they will probably not be referenced by others.
Isn't there are problem with merger of a split tangle then. If the network was split, then tips of the stronger part will have greater cumulative weight and will always be chosen to be referenced. The weaker subtangle just dies off. The party which is interested in the survival of the weaker subtangle would "connect" it to the stronger subtangle by referencing 1 tx from here and 1 from there. If both subtangles are legit, they'll quickly merge. |
|
|
|
in the event a honest guy tries to reference a legit tip and the attacker's tip, he'll detect the contradiction and won't do it. Therefore, the attacker's subtangle will be abandoned.
This requires not just an honest guy, but a diligent one as well. The risk is that honest guys will be lazy and rely on others to go far back in history to check all tx for double spending. The lazy guys risk that their tx's will be abandoned, because the majority of the nodes won't reference them. |
|
|
|
If the attacker started to create his double-spending subtangle long time ago, then the initial tx's of this subtangle reference some rather old tx's, with not-so-big cumulative weight. While the attacker waits, the cumulative weight of the legit tangle continues to grow, so he won't be able to catch up.
Of course, this assumes that the attacker's max possible tx's rate is much less then the "usual" tx's rate of the rest of the network.
The first (legit) transaction references the same old transactions as the doublespend. The attacker doesn't need to compete with the rest of network. OK, but the legit tx quickly starts to accumulate weight (as the honest nodes reference it, directly or indirectly), so, by the time the merchant accepts it, most of the tips of the legit tangle are already referencing it. Even if the attacker publishes his subtangle at that moment, why the honest guys would reference it? The tips from the attacker's subtangle have smaller cumulative weight, and, in the event a honest guy tries to reference a legit tip and the attacker's tip, he'll detect the contradiction and won't do it. Therefore, the attacker's subtangle will be abandoned. |
|
|
|
|
Show Posts
