Game theory for perfect solution to "stuck payment" attack

[Johan Nygren]

Ryan Fugger's original idea from 15 years ago to complete a payment from the direction of the seller and towards the buyer was invented to avoid the "stuck payment" attack problem, and this problem is the main problem in multi-hop payments. Ryan's idea had a race condition, and it could be removed by reducing the size of the penalty (in Ryan's idea 15 years ago the penalty was the full payment). Interledger STREAM payment does this by dividing the payment into small chunks, but, you can also achieve it in the opposite way, and in doing so avoid all the problems "stream payments" have (i.e., limits to how small amount packet and timeout size you can reach, countless transactions to do simple things as main problem). What you can do is instead of timing out full payment at once, you start to continuously cancel chunks of it after you reach the timeout. This is a very simple idea and easy to understand, but the next question is then: how to organize that? To organize it, you need to add two steps.

The first step, sets up an "all-or-nothing" payment that either succeeds, or, ends up being "cleared" slowly with penalties exactly on the users that caused the payment to get stuck (and everyone else gets financially compensated). This step I call "commit", and it goes from the buyer and towards the seller. To avoid stuck propagation, there is a penalty on the buyer once the payment times out which forces them to use "buyer cancels" (authenticated with preimage of payment ID or similar). This penalty results from that in "commit" the payments gets continuously finalized in "chunks" after the timeout (thus the opposite of during "finalize", i.e., when the payment completes). And, from that there is also "buyer fees" added on top of all this (paid out in proportion to how much of payment was "auto-cleared", up to 100%). The "buyer fees" achieve two things: they ensure everyone is financially compensated. And, they avoid an attack where buyer and seller (or user who commit reaches...) are both attackers (where the finalization would just end up with attacker sending money to themselves, thus successfully doing a "stuck payment" attack).

And then, the second step, between "commit" and "finalize", the buyer needs to revoke their right to cancel. This is done with "seal" and there the payment starts to be continuously cancelled such that an intermediary that is not propagating "seal" will start to finalize the payment towards the seller and cancel it towards the buyer, thus being penalized.

Three steps, "commit", "seal", "finalize". Three mechanisms, continuously cancel, finalize, and continuously pay out buyer fees.

Implementation is super easy, as you only need to account for the penalty effect when a decision happens (such as when the user who the payment was stuck at finally decides to propagate the signal, or when a payment was fully cleared by the penalty mechanism and thus removed in full).

99% of it is implemented on https://bitbucket.org/bipedaljoe/ripple/ (really only missing the "cleanupPayment" handler) and this article describes it well and also has illustrations: https://ripple.archi/multi_hop_payment_game_theory.pdf.

If I am right, this is what has been missing for a true multi-server Ripple. I originally built my implementation without having an "automated" solution to stuck payment problem (I assumed, and still think, it could be handled socially, manually, but I recognize the value of automating it as well), and based on the feedback I got here it seemed that "stuck payment" attack problem should be automated, so I came up with what might be the perfect solution.

It would be good for the idea if others chime in on if it sounds reasonable, or seems like shit. That way, it can grow in the Ripple community. Everyone here would like to see Ripple succeed and since Ripple is so simple, a true decentralized currency, it could be built by anyone and started from anyone and anywhere, and as many might be wanting to solve this problem, it might be meaningful to evaluate my solution since it seems to be an innovation, and one that is a logical continuation of the ideas Ryan Fugger had developed 15 years ago (just as STREAM payments are... but, theirs is not a good solution).

Peace, Johan

[Johan Nygren]

Very simple explanation:

To move a decision from buyer towards seller where everyone who made the decision leaves the payment ("buyer cancels"), gradually finalize the payment.

To move a decision from seller towards buyer where everyone who made the decision leaves the payment ("seller finalizes"), gradually cancel the payment.

To move a decision towards seller where everyone who made decision stays in the payment ("seal payment"), gradually cancel amount in on buyer side and  gradually finalize on seller side.

To handle case where attacker is both buyer and seller and decision is stuck at either (thus gradual cancel and gradual finalize is no penalty), add fees on top of the payment that goes from buyer to all users in proportion to how long the payment was stuck.

[Johan Nygren]

Very easy explanation of the rules now available over https://multihop.xyz/. So they are easy to pass around to be audited. The README with same content is on https://multihop.xyz/README.md...

Would be helpful to this idea if anyone who sees potential in it gave some feedback here, otherwise it can be seen as just me spamming, and if my solution works it would be sad it if was just labelled spam (socially by whomever else is in this community) and ignored... I have done what I can to respect the feedback I got here two months ago ("you do not solve stuck payment attack") and solve that problem, I have implemented it all: https://bitbucket.org/bipedaljoe/ripple/, and I have done the best I can to explain it in as comprehensive a way as possible, to make auditing the idea easier (or an animation would be even better but I have done the best I can with my limited resources and me just being one person).

Peace Johan

[Johan Nygren]

Now built a simulation (with generative AI): https://multihop.xyz/sim/

There you can attack at any step, and with any node. It shows the penalty system acting to enforce the decision that breaks the attack.

It would be helpful to this idea if anyone who sees potential in it gave some feedback here. Otherwise this would be me "spamming" but this is a bit sad if my mechanism actually works and is an innovation.

I also want to, again, publicly apologize for assuming Ryan Fugger got stuck at the user-to-user consensus part. I had to guess what the problem was. I was neglecting the "stuck payment attack" (that Ryan and people like Jorge Timon were discussing back in 2011 here on Sourceforge mailing list and probably way before that). But, I happened to come up with the necessary mechanism thanks to that. My design relied on that the buyer was the last with the right to cancel. This co-incidentally is exactly what is needed to enter the payment, whereas Ryan's mechanism from 15 years ago (finish payment from seller) is what is needed to leave the payment. These together, allow for a slow-acting penalty rather than the full payment that Ryan used 15 years ago. Every step of this is demonstrated in my simulation on https://multihop.xyz/sim/.

So, again, a public apology to making the wrong guess about why Ripple Inter Server Protocol progress got stuck. Ryan considered the user-to-user consensus as early as 2006 (here on Sourceforge mailing list), it was never ignored. I was wrong, and out of that came the potential to meet half way and find the solution to the actual problem: "stuck payment attack".

Peace, Johan