When can a transaction be considered irreversable? (without COO)

In an interesting exchange between Come-From-Beyond (CFB) and a Nxt developer, the question is asked:

DEV. So when can a transaction be considered irreversable?

CFB. Never, look at formula #14 in http://188.138.57.93/tangle.pdf. Just like in Bitcoin there is always a chance of double-spending.

This is further clarified:

DEV. Not even when the weight cap is reached ? (The paper mentions the cap but I'm not sure it ever states if the cap will actually be applied)

CFB. No. The cap is related to another issue.

... and more here: https://bitcointalk.org/index.php?topic=1216479.msg12759162#msg12759162

DEV. So for a transaction to be considered confirmed, the number of approving transactions multiplied by the minimal PoW must exceed the maximal possible adversary's PoW?

CFB. No, it's not that easy, if transaction flow drops then an adversary can catch up and double-spend. It's a never ending race.

1. Is this true, that a double spend attack can happen at any time in the future?

2. If so, is it the case that the POW of the honest majority of the network must ALWAYS FOREVER outweigh the POW of an attacker?

When can a transaction be considered irreversable ? (without COO)

Strictly speaking: never.

In any really decentralized DLT any transaction have a probability to be valid... and this probability is always < 1 (except in the infinite future).

Is this true, that a double spend attack can happen at any time in the future?

In theory : yes (...because the probability to be valid is always < 1)

If so, is it the case that the POW of the honest majority of the network must ALWAYS FOREVER outweigh the POW of an attacker?

It's the opposite. To drive a successful attack : the attacker must have a hashing power greater than the rest of the network all the time during the attack. (an attacker doesn't run an attack forever... but the "honest network" does) (and it is a necessary but not sufficient condition)

• I don't think that is quite right. A double spend assumes that the first transaction is already considered confirmed and then the attacker overtakes the network to reverse it. This means there is some catching up to do so the attack must be sustained for much longer than an instant, especially since the random walk is weighted so the attacker tips wont be picked by honest nodes until they have caught back up to the front of the graph. (front being the current position where good honest tips are being added) Jul 12, 2018 at 0:46