Proposal: Transaction-Directed Acyclic Graphs

[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?

[1713859440]

1713859440

[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.