Proposal: Transaction-Directed Acyclic Graphs

[TomHolden]

I recently stumbled across an old blog post (https://blog.ethereum.org/2014/07/05/stake/) by Vitalik Buterin in which he gave the following simplified version of Daniel Larimer's Transactions as Proof of Stake (TaPoS)(http://bravenewcoin.com/assets/Uploads/TransactionsAsProofOfStake10.pdf):

1. "Every transaction must contain a reference (ie. hash) to the previous transaction"
2. "A candidate state-of-the-system is obtained by calculating the result of a resulting transaction chain"
3. "The correct chain among multiple candidates is the one that has either (i) the longest coin-days-destroyed (ie. number of coins in the account * time since last access), or (ii) the highest transaction fees"

Source: https://blog.ethereum.org/2014/07/05/stake/ (The strike-through was just added here, as I will not discuss coin-days type schemes. Indeed, nothing here will look much like proof of stake, and this is better thought of as an alternative to Bitcoin's final stage in which all mining rewards come from transaction fees.)

I was really struck by the elegant simplicity of this proposal. It also solves the "nothing at stake" problem with PoS, as observed in the article.

Of course in practice, it would not scale at all well, as Vitalik Buterin points out. The question then is whether one could create an algorithm that keeps most of this wonderful simplicity, while improving the scaling. In the rest of this post, I'd like to discuss one possible solution. Any comments on whether this would actually work would be much appreciated, and if someone with more free time than me felt like implementing it, I would be incredibly flattered.

The chief change, is that rather than having a block-chain, or, as with TaPoS, a transaction-chain, we instead have a transaction-directed acyclic graph (transaction-DAG/TDAG), with each transaction containing a list/Merkle-tree of hashes of previous transactions.

If I understand correctly, the chief reason the simple TaPoS given above would not scale is that with high transaction volume, large numbers of transactions will all claim to be descended from a single parent transaction. Thus there will be huge volumes of "orphan-transactions", and probably even quite long orphan-chains. This would mean that it would be almost impossible for low value transactions to get into the chain. However, with transactions forming a DAG, this problem is potentially solvable. While large numbers of transactions may still share a common parent (or parents), providing they do not contradict each other (to be made clear), they may be brought back together by having the next generation of transactions "descend" from all of them.

A TDAG would need to satisfy the following properties to be accepted by the network:

1. The partial order associated with the DAG forms a bounded lattice, so in particular, there is a unique root node, and a unique childless node, which must be the transaction being submitted to the network.
2. Let P(N) be the set of all parents of a node N, and A(N) be the set containing N and all of its ancestor nodes (e.g. parents, grand-parents etc. all the way back to the root). Then for all N in the DAG, and all M1 in P(N), there is at least one node Q in A(M1) such that for all M2 in P(N), Q is not in A(M2). (I.e. a node can only claim a parent if doing so strictly increases its set of ancestors.)
3. For each node N in the DAG, there is a topological ordering of A(N), say M1, M2, ..., MK, with MK=N such that for all k in 1,...,K, the inputs to the transaction contained in Mk are unspent outputs from nodes in M1,...,M(k-1). (I.e. the DAG ought to be at least ex-post rationalizable as representing a chain of transactions.)

For this mechanism to work, people need to be incentivised to include as many childless transactions as the parent of their transaction as possible. They also need to be incentivised to add their transaction as near as possible to the bottom of the DAG. To do this, I propose the following.

1. As with Bitcoin, the difference between the sum of inputs and the sum of outputs on a transaction is interpreted as a transaction fee, which we treat as an unspent output when applying rule 3 above.
2. Whatever happens, half of all transaction fees are permanently discarded.
3. The maker of a new transaction N can include up to one half of the total transaction fees from P(N) as inputs within their transaction (i.e. up to all of the remainder).
4. Where selection between multiple irreconcilable TDAGs needs to be made (i.e. when it is not possible to form a new TDAG with a bottom node whose parents are the bottom nodes of the original TDAGs), the TDAG with the highest sum of total transaction fees paid should be picked. In the case of a tie, of those TDAGs with the same total transaction fees paid, the one with the highest total unclaimed transaction fees should be picked.

To understand the implications of this, suppose there is a node N with children M1, M2,..., MK each with no other parents. If K=1, and the one child has claimed the maximum allowable fee, then the minimum possible amount is discarded, i.e. just half the transaction fee. If they claim less than the maximum possible, then more than one half of the transaction fees will be discarded (although in reality, someone would realise some were still available, and would submit an additional child transaction to claim it). If K=2, and again each child has claimed the maximum allowable fee, then there can be no TDAG containing N, M1 and M2, since such a TDAG would feature spending already spent outputs. Thus, either the makers of nodes M1 and M2 are less greedy in their claims (the likely outcome), or one of these nodes will not be included in the eventual TDAG. If (say) M1 arrived significantly before M2, then they are likely to have more children of their own, and hence a TDAG containing M1  is likely to have higher total transaction fees than one containing M2, and so the one(s) containing M2 would not be selected. Ideally, wallets should dynamically adjust the claimed amount to give a high probability of transaction inclusion. I would then expect that opportunistic people with high network bandwidth would mop up the odd bit of remaining unclaimed transaction fees.

As far as I can see, as with the original TaPoS, this is still not vulnerable to the "nothing at stake" problem with PoS. There is no incentive to submit transactions to multiple TDAGs. What other problems am I missing?

As I said, any comments would be much appreciated. As would pinging any potentially interested parties.

Note: First posted here: https://www.reddit.com/r/btc/comments/4n6nq8/proposal_transactiondirected_acyclic_graphs/ (where it drowned in the noise).

[1715660811]

1715660811

[1715660811]

1715660811

[1715660811]

1715660811

[1715660811]

1715660811

[spartacusrex]

yo.

have you checked out DAGcoin.. ?

https://bitcointalk.org/index.php?topic=1177633.0

I think it's what you are proposing..

[TomHolden]

I hadn't heard of that before. It's interesting, but definitely not the same. Quite different structures, incentives and benefits.

[TomHolden]

It appears to have been developed into Iota: https://bitcointalk.org/index.php?topic=1216479.0 , and their white paper gives further references to other people talking about DAGs. So it seems using a DAG is not novel, though it also means it's not crazy. What hasn't been pursued though is the combination of the simple TaPoS idea with a DAG, as I suggest here.

One advantage of my scheme over this is that my scheme gives stronger incentives for adding to young nodes, both via transaction fees, and thanks to the rule that each parent must strictly expand the set of ancestors. It also doesn't rely on transactions "approving" other transactions to ensure internal consistency. Instead that is a requirement for any valid TDAG.

[spartacusrex]

Why burn any of the fees at all ?

What am I missing ?

[TomHolden]

Burning fees defends against a double spend attack in which someone secretly constructs an alternative TDAG in which they pay large amounts of transaction fees, then claim them themselves.

[iotatoken]

This is indeed quite similar to IOTA.

Join us on http://chat.iotatoken.com

[iamnotback]

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.

Sorry DAGs don't work. But I am not screaming to tell people not to invest in Iota, because frankly Satoshi's proof-of-work block chain centralizes as well, as is clearly on display.

You may want to quote this post before it is nuked by Hitler.

[klee]

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.

Sorry DAGs don't work. But I am not screaming to tell people not to invest in Iota, because frankly Satoshi's proof-of-work block chain centralizes as well, as is clearly on display.

You may want to quote this post before it is nuked by Hitler.

Anti-Nazi action

[TomHolden]

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

[Come-from-Beyond]

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.

You can't just claim that there is no a way to prevent double-spends. A blockchain is a special case of a DAG and if you are right then there must be a line after which everything breaks, because (as we see in Bitcoin) the special case of a DAG works pretty well. If this line is drawn between "single branch" and "multiple branches" then how does Ethereum manage to function?

[tonych]

I spent some time on DAG based designs and this one reminds me of something that I rejected early.

As far I understand, the level of security against double-spends basically depends on the total amount spent on fees on the legit DAG.  If so, an attacker just secretly builds a subDAG that includes a few double-spends, spends more on fees in the subDAG than was spent in the legit DAG, then publishes his subDAG.  Now everybody should switch to the subDAG as it has burnt more fees.  As long as the total amount of double-spends exceeds the fees, the attack succeeds.

[TomHolden]

Tonych suggests a double spend attack in which:

As long as the total amount of double-spends exceeds the fees, the attack succeeds.

However, as I stated in the more extensive discussion of double spend attacks above:

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.

This rules out the kind of double spend attack tonych considered. By the time the transaction is confirmed, at which point the attacker would like to publish their secret TDAG, it is already unprofitable for them to do this.

Providing individual transactions are small relative to the network, this will not be an infeasibly high barrier for confirmation.

[tonych]

Tom, the trick is in doing many double-spend attacks at the same time.  Each individual victim has a relatively small amount at stake, she will wait for relatively short time until as you say total fees = twice the value of the victim's transaction but she doesn't know that the attacker is profiting from several victims, therefore her analysis of the attacker's ROI is wrong.

The attacker has a sort of leverage in that he has to construct a shadow DAG and pay its fees only once but will profit from multiple unsuspecting and uncoordinated victims.

[TomHolden]

Smart, sorry, I'd missed that from your original post. But it seems like V. Buterin's argument from the link in the OP still applies:

"This seems weak, but in reality it isn’t; we know that in the case of Bitcoin, once the currency supply stops increasing mining will rely solely on transaction fees, and the mechanics are exactly the same (since the amount that the network will spend on mining will roughly correspond to the total number of txfees being sent in); hence, fee-based TaPoS is in this regard at least as secure as fee-only PoW mining."

(The premise of this argument is a standard "free entry" condition. Entry continues until returns are driven down to zero.)

I will have to think if an improved confirmation condition robust to multiple double spends could be thought up.

[TomHolden]

I will have to think if an improved confirmation condition robust to multiple double spends could be thought up.

It is easy to track the total spend on transaction fees of descendants of the original transaction. A confirmation test of equivalent robustness to the Bitcoin 6 confirmation tests would wait until the total spend on transaction fees of descendants was higher than the total expenditure of Bitcoin miners in mining 6 blocks at present (including electricity, premises rent and amortized costs of equipment). This is a large number, but so too are total transaction fees if the coin is actually being used.

[TomHolden]

While waiting for usage to be sufficiently high to get security by transaction fees, it is easy to introduce a PoW component (which also solves the initial distribution problem).

Rather than completely destroying half of all transaction fees, they would instead be set aside to be claimed by future PoW transactions. PoW transactions would be added to the TDAG much like any other transaction, but would contain a PoW instead of inputs. Additionally, PoW transactions would be restricted to only descend from TDAG-nodes with unclaimed transaction fees from the "burnt" half, to ensure that miners have an incentive to include recent transactions.

[Come-from-Beyond]

which also solves the initial distribution problem

How does it solve the initial distribution?

[tonych]

I will have to think if an improved confirmation condition robust to multiple double spends could be thought up.

It is easy to track the total spend on transaction fees of descendants of the original transaction. A confirmation test of equivalent robustness to the Bitcoin 6 confirmation tests would wait until the total spend on transaction fees of descendants was higher than the total expenditure of Bitcoin miners in mining 6 blocks at present (including electricity, premises rent and amortized costs of equipment). This is a large number, but so too are total transaction fees if the coin is actually being used.

As you increase confirmation time, you further inconvenience all users, while the attacker only has to find more victims.

Also, you assume total transaction fees is something large when the coin is actively used, but I can't see (or I overlooked it) how you incentivize each individual user to pay higher fees.

[TomHolden]

How does it solve the initial distribution?

Just because there's a PoW component (initially at least), which produces new coins. You might not like mining, but it's established enough that few would seriously object to using it for distribution. (Though it's of course always preferable if the PoW is GPU/ASIC resistant.)

[Come-from-Beyond]

Just because there's a PoW component (initially at least), which produces new coins. You might not like mining, but it's established enough that few would seriously object to using it for distribution. (Though it's of course always preferable if the PoW is GPU/ASIC resistant.)

Why would you extend my branches if by invalidating them you would earn more coins?

[TomHolden]

As you increase confirmation time, you further inconvenience all users, while the attacker only has to find more victims.

Also, you assume total transaction fees is something large when the coin is actively used, but I can't see (or I overlooked it) how you incentivize each individual user to pay higher fees.

Yes, high confirmation times are bad for users. But in a crazy hypothetical world in which Bitcoin users switched to this system, it doesn't seem like transaction times would be significantly worse. Indeed, many transactions could be confirmed much faster, as the lag to one confirmation in Bitcoin with low fees is much higher than the lag to having a child transaction (or many) would be.

The PoW system provides security in the transition to (hypothetical) high usage. Paying higher fees is incentivized as child transactions gain more from descending from transactions with higher fees, and so confirmation is likely to be faster, whatever the confirmation metric.

[TomHolden]

Why would you extend my branches if by invalidating them you would earn more coins?

I don't see why "invalidating" a branch/TDAG would enable you to earn more coins. That sounds equivalent to a double spend attack. But perhaps I'm not following you.

[Come-from-Beyond]

Why would you extend my branches if by invalidating them you would earn more coins?
[/quote

I don't see why "invalidating" a branch/TDAG would enable you to earn more coins. That sounds equivalent to a double spend attack. But perhaps I'm not following you.

If 50% of coins will be generated via subsidy then every time I invalidate your branches by making them reference doublespendings. Invalidated branches = not spent subsidy.

[tonych]

Paying higher fees is incentivized as child transactions gain more from descending from transactions with higher fees, and so confirmation is likely to be faster, whatever the confirmation metric.

It is not incentivized this way.  Descending from a low-fee transaction still doesn't hurt as there is no limit on the number of parents.

[TomHolden]

Why would you extend my branches if by invalidating them you would earn more coins?

I don't see why "invalidating" a branch/TDAG would enable you to earn more coins. That sounds equivalent to a double spend attack. But perhaps I'm not following you.

If 50% of coins will be generated via subsidy then every time I invalidate your branches by making them reference doublespendings. Invalidated branches = not spent subsidy.

I'm afraid I still don't understand your point. Perhaps I'm being stupid.

A broadcast transaction (be it standard of PoW) will not be accepted by the network if its ancestors contain a double spend. So any transaction fees the new transaction purported to claim will in fact remain unclaimed.

In this add-on proposal, I am not proposing that 50% of coins are generated via subsidy; rather, I am proposing that 100% of coins are generated via PoW.

[Come-from-Beyond]

I'm afraid I still don't understand your point. Perhaps I'm being stupid.

A broadcast transaction (be it standard of PoW) will not be accepted by the network if its ancestors contain a double spend. So any transaction fees the new transaction purported to claim will in fact remain unclaimed.

In this add-on proposal, I am not proposing that 50% of coins are generated via subsidy; rather, I am proposing that 100% of coins are generated via PoW.

Ok, 100% is fine.

Imagine that you are extending this branch: A -> B -> C -> D
My hashing power is higher, so I generate: N -> O -> P -> Q -> R -> S -> T
What will happen if N is a doublespending of A? Note that my branch becomes visible to you with some delay.

[TomHolden]

Paying higher fees is incentivized as child transactions gain more from descending from transactions with higher fees, and so confirmation is likely to be faster, whatever the confirmation metric.

It is not incentivized this way.  Descending from a low-fee transaction still doesn't hurt as there is no limit on the number of parents.

Well, it's not quite true that there's no limit on the number of parents. You can only include a parent if it strictly increases the set of ancestors (so, for example, none of a nodes parents can be parents of each other).

A transaction sent with zero fee may perhaps be picked up by an altruistic individual, but they would unambiguously be incurring a cost with no reward if they did this. Firstly, including a transaction may restrict the set of other transactions you can include, if it is not already childless. Secondly, there is some (albeit small) computational cost to hashing in another transaction as a parent. . Thirdly, there is some (albeit small) bandwidth cost to broadcasting a transaction with another parent. Fourthly, since transaction size is increasing in the number of parents, and fees required are likely to be increasing in transaction size (see below), including additional parents may require paying a higher transaction fee. In the face of positive costs (albeit small) and zero gain, it is not rational to include such a transaction.

For transactions with low fees, there is an additional two mechanisms. The makers of many transactions will seek to "gamble on inclusion" by including all remaining unclaimed fees. The more transactions a transaction descends from, and claims fees from, the higher the chance that it will be orphaned by another transaction which got to the network first, and which claimed at least some of the same fees. This is both because larger transactions will propagate slower, and because other transactions will be attempting to claim from the same parent transactions. Thus it is rational for makers of transactions claiming fees to restrict the set of parents to reduce the chance of being orphaned, meaning that transactions with low fees are likely to miss out, and hence face longer confirmation times. Transactions that do not attempt to claim all available fees are less likely to be orphaned, but rationally they should at least claim enough fees per parent to compensate for the costs of including a parent detailed above. So, if the equilibrium is that each transaction is attempting to claim 1% of the available fees of its parents (say), then the total transaction fees paid by a transaction need to be 100 times higher than the costs of including a parent. In this way, the small costs outlined in the previous paragraph are scaled up to something more significant.

Edit: There is one further mechanism. At least in times of low usage, any transaction which pays significantly less in transaction fees than it claims is likely to be replaced by an alternative transaction with the same parents, but which pays higher transaction fees.

[TomHolden]

Imagine that you are extending this branch: A -> B -> C -> D
My hashing power is higher, so I generate: N -> O -> P -> Q -> R -> S -> T
What will happen if N is a doublespending of A? Note that my branch becomes visible to you with some delay.

Since what you wrote was rather ambiguous, let me clarify how I'm understanding you: I presume all letters are PoW transactions, and arrows show inheritance. So by a double spend, you must mean a double claim of transaction fees (from the otherwise burnt half), since without access to my private keys, you obviously can't spend my outputs (and PoW blocks do not have inputs in any case).

As ever, the network selects the TDAG (in this case, branch) with higher total transaction fees paid. People making PoW transactions have very strong incentives to pay seriously high fees (e.g. 25%) because otherwise they risk their PoW transaction being replaced by another with the same parents but which pays higher fees. (Two people finding a solution to the PoW puzzle at roughly the same time is not that uncommon.)

So, if you are paying sufficiently high fees, the network may switch to your TDAG. But if mine is well enough embedded in other transactions (paying fees), then even if you pay 100% fees, you might not be able to produce a switch.

In any case, it seems that all you're describing is a classic 51% attack.

[Come-from-Beyond]

Since what you wrote was rather ambiguous, let me clarify how I'm understanding you: I presume all letters are PoW transactions, and arrows show inheritance. So by a double spend, you must mean a double claim of transaction fees (from the otherwise burnt half), since without access to my private keys, you obviously can't spend my outputs (and PoW blocks do not have inputs in any case).

As ever, the network selects the TDAG (in this case, branch) with higher total transaction fees paid. People making PoW transactions have very strong incentives to pay seriously high fees (e.g. 25%) because otherwise they risk their PoW transaction being replaced by another with the same parents but which pays higher fees. (Two people finding a solution to the PoW puzzle at roughly the same time is not that uncommon.)

So, if you are paying sufficiently high fees, the network may switch to your TDAG. But if mine is well enough embedded in other transactions (paying fees), then even if you pay 100% fees, you might not be able to produce a switch.

In any case, it seems that all you're describing is a classic 51% attack.

Arrows are showing timeline direction. My point is that if you subsidize transaction creation then miners will be invalidating each others branches with doublespends leading to consensus divergence.

[TomHolden]

Arrows are showing timeline direction. My point is that if you subsidize transaction creation then miners will be invalidating each others branches with doublespends leading to consensus divergence.

I still don't understand your point I'm afraid. I'm not subsidising transaction creation. PoW "transactions" are not really transactions at all, as they have no inputs.

Perhaps you could fully describe your purported double spend attack?

[iotatoken]

Arrows are showing timeline direction. My point is that if you subsidize transaction creation then miners will be invalidating each others branches with doublespends leading to consensus divergence.

I still don't understand your point I'm afraid. I'm not subsidising transaction creation. PoW "transactions" are not really transactions at all, as they have no inputs.

Perhaps you could fully describe your purported double spend attack?

Let's move this discussion to #math-around-iota at our chat (http://chat.iotatoken.com) so that it progressses faster and get more inputs.

[Come-from-Beyond]

I still don't understand your point I'm afraid. I'm not subsidising transaction creation. PoW "transactions" are not really transactions at all, as they have no inputs.

Perhaps you could fully describe your purported double spend attack?

Well, my claim is that it's impossible to have generation of new coins in a DAG-based currency without sacrificing the security. Unfortunatelly, I can't find the thread where all this was discussed...

[tonych]

It is not incentivized this way.  Descending from a low-fee transaction still doesn't hurt as there is no limit on the number of parents.

Well, it's not quite true that there's no limit on the number of parents. You can only include a parent if it strictly increases the set of ancestors (so, for example, none of a nodes parents can be parents of each other).

Of course, it is a natural requirement (Iota lacks it, btw) that is easy to satisfy by considering childless parents only.

A transaction sent with zero fee may perhaps be picked up by an altruistic individual, but they would unambiguously be incurring a cost with no reward if they did this. Firstly, including a transaction may restrict the set of other transactions you can include, if it is not already childless. Secondly, there is some (albeit small) computational cost to hashing in another transaction as a parent. . Thirdly, there is some (albeit small) bandwidth cost to broadcasting a transaction with another parent. Fourthly, since transaction size is increasing in the number of parents, and fees required are likely to be increasing in transaction size (see below), including additional parents may require paying a higher transaction fee. In the face of positive costs (albeit small) and zero gain, it is not rational to include such a transaction.

Obviously there is no point descending from a 0-fee transaction, but they still can be abused: a user could still build a long chain of his own transactions of which only the last one pays fees.

For transactions with low fees, there is an additional two mechanisms. The makers of many transactions will seek to "gamble on inclusion" by including all remaining unclaimed fees. The more transactions a transaction descends from, and claims fees from, the higher the chance that it will be orphaned by another transaction which got to the network first, and which claimed at least some of the same fees. This is both because larger transactions will propagate slower, and because other transactions will be attempting to claim from the same parent transactions. Thus it is rational for makers of transactions claiming fees to restrict the set of parents to reduce the chance of being orphaned, meaning that transactions with low fees are likely to miss out, and hence face longer confirmation times. Transactions that do not attempt to claim all available fees are less likely to be orphaned, but rationally they should at least claim enough fees per parent to compensate for the costs of including a parent detailed above. So, if the equilibrium is that each transaction is attempting to claim 1% of the available fees of its parents (say), then the total transaction fees paid by a transaction need to be 100 times higher than the costs of including a parent. In this way, the small costs outlined in the previous paragraph are scaled up to something more significant.

Edit: There is one further mechanism. At least in times of low usage, any transaction which pays significantly less in transaction fees than it claims is likely to be replaced by an alternative transaction with the same parents, but which pays higher transaction fees.

If you have a set of 10 childless transactions, of which 9 are normal-fee and 1 is low-fee, and the low fee is above some tiny threshold which is the cost of hashing etc, would you lose the opportunity to earn some pennies that are just lying on the road?  You can take 1% of the available fees if are are afraid of being orphaned.

In fact there are so many moving parts in the design (how much fees to pay, how much fees to claim, which parents to descend from) and so many dependent variables to optimize for (speed of confirmation, fees earned minus fees spent, chances of being orphaned) that the analysis of the design is already too complex, and chances that there are unforeseen abusive strategies look quite high.  Your attempt to mix in some PoW adds even more complexity.

I'm also concerned how easily you orphan or replace transactions.   Most people won't be happy to put their money into a system where there is such uncertainty about being able to send a payment.

[stdset]

If you have a set of 10 childless transactions, of which 9 are normal-fee and 1 is low-fee, and the low fee is above some tiny threshold which is the cost of hashing etc, would you lose the opportunity to earn some pennies that are just lying on the road?  You can take 1% of the available fees if are are afraid of being orphaned.

As far as I understand, the low fee transaction will likely be orphaned either by you, as you can inherit not from the low fee transaction but from it's parents, or by someone else. I agree though that the design is very complex.

[hv_]

Looks like Bob McElrath has similar work here and starts a test coin:


https://github.com/mcelrath/braidcoin

 Double spending issue should be eliminated by sharing the reward and evaluating the parent blocks properly.

[caseyfhp]

If you have a set of 10 childless transactions, of which 9 are normal-fee and 1 is low-fee, and the low fee is above some tiny threshold which is the cost of hashing etc, would you lose the opportunity to earn some pennies that are just lying on the road?  You can take 1% of the available fees if are are afraid of being orphaned.

As far as I understand, the low fee transaction will likely be orphaned either by you, as you can inherit not from the low fee transaction but from it's parents, or by someone else. I agree though that the design is very complex.

I am very new to this thread but very interested in this topic. Appreciate if anyone help to clarify my confusion here: I thought there is no fee involved in IOTA TDAG transactions? The 'weight' used (mentioned in Tangle white paper) is "defined to be proportional to the amount of computational hashing work that the issuing node invested into it". The weight is not the transaction fee right?  Thanks.

[iotatoken]

If you have a set of 10 childless transactions, of which 9 are normal-fee and 1 is low-fee, and the low fee is above some tiny threshold which is the cost of hashing etc, would you lose the opportunity to earn some pennies that are just lying on the road?  You can take 1% of the available fees if are are afraid of being orphaned.

As far as I understand, the low fee transaction will likely be orphaned either by you, as you can inherit not from the low fee transaction but from it's parents, or by someone else. I agree though that the design is very complex.

I am very new to this thread but very interested in this topic. Appreciate if anyone help to clarify my confusion here: I thought there is no fee involved in IOTA TDAG transactions? The 'weight' used (mentioned in Tangle white paper) is "defined to be proportional to the amount of computational hashing work that the issuing node invested into it". The weight is not the transaction fee right?  Thanks.

There are no fees in IOTA, right. In IOTA you verify 2 previous transactions when you send a transaction, meaning the verification is not decoupled from the network (as is the case with miners/stakers), and thus there are no people to compensate.

[mcelrath]

People seem to have repeatedly gotten hung up on the need to incentivise miners to lengthen the braid/chain, instead of widen it.  This isn't a need: miners will contribute to the highest work braid/chain simply because that is the one most likely to have other people contribute to it.  No extra incentive is needed.  If there exist two childless beads (blocks), it's in my best interest to name them both as parents.  That generates a higher work braid.  Naming only one of them creates a lower work braid.

Note that Satoshi's analysis and the "longest chain" rule is simplistic and only works for constant difficulty blocks.  It is very straightforward to combine the work from multiple blocks even having different targets and evaluate the total amount of work.  It's not equivalent to the chain "length" but the calculation is straightforward.  I leave it as an exercise for the reader.  ;-)

Note also that my work is entirely based on proof-of-work.  I don't think proof-of-stake works and you can't apply a profit maximizing rule to a set of numbers in your computer that fundamentally have zero marginal cost.  (For more on proof of stake, read my blog: https://blog.sldx.com/whats-wrong-with-proof-of-stake-77d4f370be15)

[Come-from-Beyond]

This isn't a need: miners will contribute to the highest work braid/chain simply because that is the one most likely to have other people contribute to it.  No extra incentive is needed.  If there exist two childless beads (blocks), it's in my best interest to name them both as parents.  That generates a higher work braid.  Naming only one of them creates a lower work braid.

This is not that simple, as Selfish Mining paper showed, a more sophisticated strategy may be more profitable.

[mcelrath]

This isn't a need: miners will contribute to the highest work braid/chain simply because that is the one most likely to have other people contribute to it.  No extra incentive is needed.  If there exist two childless beads (blocks), it's in my best interest to name them both as parents.  That generates a higher work braid.  Naming only one of them creates a lower work braid.

This is not that simple, as Selfish Mining paper showed, a more sophisticated strategy may be more profitable.

Selfish mining works because of the asymmetry between profit of a block that gets orphaned and one that ends up in the main chain.  There's no reason to have orphans at all with a braid.  Withholding a block doesn't buy you anything.

This is a concept I put forth in my most recent talk about braids: "equal pay for equal proof-of-work".  Selfish mining is killed by a combination of braiding (no more orphans), and removing the asymmetry by ensuring all valid PoW hashes earn a block reward.

[Come-from-Beyond]

This is a concept I put forth in my most recent talk about braids: "equal pay for equal proof-of-work".

Self-reference...

Selfish mining is killed by a combination of braiding (no more orphans), and removing the asymmetry by ensuring all valid PoW hashes earn a block reward.

...and a bold claim without any proof.

Sorry for disturbing you, I'm out from this discussion because I don't have time for a discussion in TPTB's style.

[iamnotback]

This isn't a need: miners will contribute to the highest work braid/chain simply because that is the one most likely to have other people contribute to it.  No extra incentive is needed.  If there exist two childless beads (blocks), it's in my best interest to name them both as parents.  That generates a higher work braid.  Naming only one of them creates a lower work braid.

This is not that simple, as Selfish Mining paper showed, a more sophisticated strategy may be more profitable.

Selfish mining works because of the asymmetry between profit of a block that gets orphaned and one that ends up in the main chain.  There's no reason to have orphans at all with a braid.  Withholding a block doesn't buy you anything.

This is a concept I put forth in my most recent talk about braids: "equal pay for equal proof-of-work".  Selfish mining is killed by a combination of braiding (no more orphans), and removing the asymmetry by ensuring all valid PoW hashes earn a block reward.

Vitalik seemed to conclude that rewarding all branches makes a 51% attack free.

Even with or without direct monetary rewards (e.g. minted coins or non-burned txn fees), selfish mining can be conceptualized more generally as the asymmetry (for different proof-of-work participants, aka miners in Bitcoin) of the cost of effective PoW (or burned txn fees), for whatever PoW (or burned txn fees) accomplishes in the consensus system. So even for Iota or DagCoin which afair don't monetarily reward the PoW (i.e. afaik the PoW is simply burned), the asymmetry still exists in terms of the value of what PoW can effect in the system. Thus as CfB wrote, "a more sophisticated strategy may be more profitable" given some externalities such as achieving a double-spend and shorting the token's exchange value.

[iamnotback]

I spent some time on DAG based designs and this one reminds me of something that I rejected early.

As far I understand, the level of security against double-spends basically depends on the total amount spent on fees on the legit DAG.  If so, an attacker just secretly builds a subDAG that includes a few double-spends, spends more on fees in the subDAG than was spent in the legit DAG, then publishes his subDAG.  Now everybody should switch to the subDAG as it has burnt more fees.  As long as the total amount of double-spends exceeds the fees, the attack succeeds.

Smart, sorry, I'd missed that from your original post. But it seems like V. Buterin's argument from the link in the OP still applies:

"This seems weak, but in reality it isn’t; we know that in the case of Bitcoin, once the currency supply stops increasing mining will rely solely on transaction fees, and the mechanics are exactly the same (since the amount that the network will spend on mining will roughly correspond to the total number of txfees being sent in); hence, fee-based TaPoS is in this regard at least as secure as fee-only PoW mining."

@TomHolden, I agree that Satoshi's PoW has the same potential vulnerability in that if double-spends exceed the value of what was burned to provide security, then a 51% lie-in-wait attack is possible funded by the value of the double-spends (possibly also shorting the exchange value in case the successful attack craters the price).

Thus, @tonych's concern applies to every consensus design (including Satoshi's) which is based on burning some resources as the metric of the longest-chain-rule (regardless whether multiple branches are merged to form the longest-chain, e.g. a DAG).

We really don't want a crypto-currency that is too liquid into fungible monetary equivalents, as it would not be secure except by overpaying for security. This points to future of crypto-tokens more for micropayments as a more viable reasonable security cost paradigm. As block rewards wind down for Bitcoin, then this may become more apparent.

[iamnotback]

3. "The correct chain among multiple candidates is the one that has either (i) the longest coin-days-destroyed (ie. number of coins in the account * time since last access), or (ii) the highest transaction fees"

Btw, in 2013 I apparently instigated or influenced Dan Larimer to make that change to his TaPoS design (that you indicated with strikethrough).