Topic: Proposal: Transaction-Directed Acyclic Graphs (Read 6220 times)

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

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

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.

Self-reference...


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

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.

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

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)

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.

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.

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.

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.

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


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.


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.

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

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.

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?

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.

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.

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.

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.