Quote from: iamnotback on June 10, 2016, 08:14:44 PM

Two people have PM'ed me this. They always expect AnonyMint to provide some analysis.

The issue seems to the be same as it was for Iota and Sergio's DAG design, which is that there is no way to prevent double-spends on multiple branches of the DAG. We covered this in great detail at the linked thread:

https://bitcointalk.org/index.php?topic=1319681.msg13830403#msg13830403

Iota "solves" this by hoping that all payers and payees run a Monte Carlo algorithm, but the only way to enforce it is to have centralized servers, which is what Iota has at launch.

You I suppose propose to incentivize one longest chain in another way, but game theory will always remain that without proof-of-work blocks then there is no Nash equilibrium resolving to one longest chain rule.

Apologies for the belated reply, and thanks for seriously engaging on this.

The linked post is conditioned on there not being a longest chain rule. But here, there is an equivalent to the longest chain rule, namely the "heaviest TDAG", where weight is the sum of total transaction fees, with the sum of spent transaction fees used for tie-breaking.

So let's analyse a double spend in more detail. Suppose a user broadcasts two alternate transactions, G and B. For simplicity, suppose that both transactions have the same parents, claim the same amount of the parents' transaction fees, use the same inputs, and pay the same transaction fees. They differ in that transaction G is a payment to a merchant for some good, whereas transaction B sends the coins to an alternative address owned by the same user.

In the proposal here, the two transactions can never be included in the same TDAG. Remember a TDAG is a bounded lattice, so there is some node that is a (...(great-)grand-)child of every other node, namely the transaction being submitted. Remember also that a node cannot descend from two parents if doing so would mean there was no serialized history without a double-spend. Because of this, valid TDAGs cannot contain double spends anywhere.

Thus, any subsequent transaction can only descend from either transaction G or from transaction B, else it will not be considered valid by the network. If clients obey the rules proposed above, by coincidence, one of the transactions G or B would arrive slightly earlier, and would rapidly obtain many child transactions. Soon then the network would settle on this one transaction, thanks to the "heaviest TDAG" selection rule, just as with Bitcoin. Even if B is eventually selected, the merchant should not lose anything, since, just as with Bitcoin, they ought to wait until the G transaction was sufficiently deep before sending goods.

But to play devil's advocate, suppose the network permanently forks, with one TDAG including G and one TDAG including B. And suppose that some users override their client to ignore the "heaviest TDAG" selection rule so as to maintain these forks. Do users have an incentive to submit transactions on both alternate TDAGs? I.e. is there any reason why one fork would not rapidly die even with some some users ignoring the heaviest TDAG selection rule? Well, suppose I am transacting with a merchant. If the merchant is "naive" in that they use the default client, without overriding the "heaviest TDAG" rule, then I certainly do not; rather, my incentive is to submit the transaction to the fork on which the merchant is on (which will be the heaviest TDAG), and not to submit the transaction on the other fork. If the other eventually fork wins, this means I will have obtained the good for free, without even paying transaction fees (the latter is why I strictly prefer to submit no transaction on the other fork than to submit a transaction to myself). This is essentially the argument of V. Buterin linked from the OP. So if an agent is transacting with someone obeying the "heaviest TDAG" rule, then they will strictly prefer to only submit transactions to the heaviest TDAG, further reinforcing that TDAG. What about if the merchant understands that the network has forked? Well then in that case, the merchant might require the transaction to be included on both forks, which would prolong the forks' lives. But is this reasonable in the long-term? For this to be maintained, every user must have downloaded an alternative version of the client which ignores the heaviest TDAG rule. As long as there are some users using a client that respects the rule, the initially heaviest fork will grow faster than the other one, and at some point, even the "awkward" users ought to forget about the other fork. Note too that one could maintain alternative Bitcoin chains if one started by assuming that everyone had modified their code to ignore the longest chain rule, so this is really a perverse hypothetical.

You might argue though that the maker of the original transaction that split the network might obtain a benefit from maintaining the split. In particular, in a classic double spend type attack, they would publicly build on G, sending transactions to their own addresses. This would eventually convince the merchant that G is sufficiently confirmed that they could send the goods. Meanwhile, in private, the maker of the original transaction would be building on B, with the intention of revealing their TDAG once the goods had been dispatched. For the network to later switch from the G fork to the B fork, the B fork would have to have a higher quantity of total transaction fees. Now, the maker of the original transaction can reduce the cost of this for themselves by including any public transactions that do not descend from G, as well as by claiming the maximum allowed transaction fees from their prior transactions. But neither of these approaches are particularly effective. Firstly, once G has been observed by a client, all the client's future transactions will descend from G. So there are unlikely to be many transactions on the good fork that do not descend from G. Secondly, by assumption, half of all transaction fees must remain unclaimed in a valid TDAG. This means that the maker of the original transaction must permanently lose at least half of all the transaction fees on the good fork of transactions that descend from G. Given that any given transaction is small compared to the network as a whole, this will be a huge amount. (And this gives the complete answer to spartacusrex's question previously. I clearly should have spelt out these details to start with.)

Hence, this "attack" leads to a simple confirmation acceptance rule for merchants that will guarantee that the attack is non-profitable: A transaction is considered confirmed when the sum of transaction fees of all transactions descending from the given transaction is more than twice the value of the original transaction.

So, iamnotback, I hope this answers your objections. I confess that the details of Iota remain rather murky to me (it doesn't seem to have managed to preserve the simplicity of TaPoS), but if it's correct that they are vulnerable to the problem you mentioned, and I am not, then thanks are in order for pointing this out to me.

Best,

Tom