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?

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.

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.

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.

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.

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.

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

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.

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.

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.

Tonych suggests a double spend attack in which:


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


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.

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

I made a proposal recently on improving the scaling of Transactions as Proof of Stake with a DAG instead of a blockchain. Someone pointed me to DAGCoin, which led me on to Iota, both of which are clearly related.

Any thoughts would be much appreciated: https://bitcointalk.org/index.php?topic=1504649.new#new

Best regards,

Tom

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.

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.

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

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

This is all now resolved to my satisfaction. They're just linking to the original article.

I've already emailed both your personal and your support address. The content was originally at http://www.tholden.org/files/CommentsOnVeriCoin.pdf

Yes, sorry amesterdamer. I wrongly assumed you were associated with the site.