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