# 3-phase commit to deter Denial of Service (DoS) attacks in multi-hop payments

2-phase commit systems in multi-hop payments can be built in two different ways, depending on if the timeout defaults to cancel or finish the payment. In either alternative there will only be a penalty on one of the phases, and the penalty will be on the opposite phase for either alternative (on the first phase for finish on timeout and on the second phase for cancel on timeout). To have a penalty on both phases, both variants of 2-phase commits have to be combined, with an intermediary phase to change the timeout action between the phases (this intermediary phase also informs all nodes that the first phase succeeded and that it can no longer be cancelled).

### 2-phase commits

@startuml
start
:Prepare;
note right: No penalty
note left: Cancel on timeout
:Commit;
note right: Penalty
end
@enduml

@startuml
start
:Prepare;
note right: Penalty
note left: Finish on timeout
if (All agree?) then ([Yes])
:Commit;
note right: No penalty
end
else ([No])
:Cancel;
note right: Penalty
stop
endif
@enduml

### 3-phase commit

@startuml
start
:Prepare;
note left: Finish on timeout
note right: Penalty
if (All agree?) then ([Yes])
:Pre-Commit;
note left: Cancel on timeout
note right: Penalty
:Commit;
note right: Penalty
end
else ([No])
:Cancel;
note right: Penalty
stop
endif
@enduml

## Chunked penalty 

With 3-phase commit, the penalty is what prevents DoS attacks rather than the time until the pending payment has been fully timed out. The pending payment can remain open as long as the penalty is actively deterring an attacker. This allows for a slow and gradual penalty, and this reduces the risk that a non-attacker is punished disproportionally.

# The rules needed to coordinate decentralized multi-hop payments

The building block is a timeout that defaults to either finish or cancel the payment. It can enforce an action if it causes someone to end up with a net negative balance. When it defaults to finish the payment, it can penalize the person who has a pending outgoing balance but no pending incoming balance (initially the buyer). When it defaults to cancel the payment, it can penalize the person who has a pending incoming balance but no pending outgoing balance (initially the seller).

This building block can be used in either configuration to successfully coordinate a multi-hop payment. When it defaults to finish the payment at the timeout, the person who has a net negative balance is incentivized to cancel the payment unless they are certain everyone has agreed to it. When it defaults to cancel the payment at the timeout, each person who has their outgoing payment claimed from the next hop is incentivized to claim their incoming payment from their previous hop.

When either of those configurations is used alone, the penalty for not succeeding to make or pass on a decision before the timeout is the full payment. I.e., if the buyer does not cancel in time (or if an intermediary does not propagate the decision to cancel in time), they end up paying out the full payment to whoever is the last person in the chain. And if an intermediary does not finalize in time (when the timeout is set to default to cancel), they end up paying for the full payment to the seller.

The coordination relies on that people put away money and promise it to the payment. The timeout places a limit on how long the money can be locked. The longer the timeout gets, the bigger the problem with Denial of Service attacks, i.e., payment attempts that are done only to lock the money of other people or sabotaged in such a way that the payment gets stuck.

The penalty can also be done in chunks , i.e., after the timeout only a chunk  of the payment is cancelled or finalized, and then after the next timeout another chunk  is processed, etc. Such a gradual penalty tends to increase the time until the payment has fully timed out, and therefore worsen the problem with Denial of Service attacks.

To resolve the issue of Denial and Service in full, the attacker has to always be penalized. When the timeout is used in the second configuration (defaults to cancel and finishes from the seller), the initial agreement to do the payment (that starts the timeout, done from the buyer towards the seller) is not enforced by any penalty. When the timeout is used in the first configuration (defaults to finalize and starts from the buyer), the penalty is active from the start, but once the buyer decides that the payment succeeded (everyone agreed to start it), the penalty does not enforce that each intermediary forwards this decision (the penalty can only enforce that the decision to cancel is forwarded). So the solution is to combine both of these payment solutions, to first start the payment from the buyer with the penalty started right away, and then finish the payment from the seller. As DoS attacks are then prevented, there is no obstacle to using the chunked penalty  (that tends to increase the time until the payment has timed out in full).

The two-step payment (start from the buyer and finish from the seller, with the timeout initially defaulting to finalizing and then defaulting to cancelling) deters Denial of Service attacks in all scenarios except when the attacker controls both ends of the penalty (the person being penalized and the person receiving the penalty). To deter DoS attacks in that scenario, fees have to be added on top of the payment, paid out in proportion to how long the payment was stuck in DoS attack.

When the timeout is used in the first configuration, finalize on timeout to finish from the buyer and forwards, there is nothing to enforce propagation during the finalization of the payment, thus this configuration by itself is open to Denial of Service attacks.

@startuml
start
:Lock credit from buyer and forwards;
note right: Finalize on timeout
if (All agree?) then ([Yes])
:Finalize from buyer and forwards;
end
else ([No])
:Cancel from buyer and forwards;
stop
endif
@enduml

When the timeout is used in the second configuration, cancel on timeout to finish from the seller and backwards, there is nothing to enforce propagation during the initial payment request sent from the buyer and towards the seller, thus this configuration by itself is open to Denial of Service attacks.

@startuml
start
:Lock credit from buyer and forwards;
note right: Cancel on timeout
:Finalize from seller and backwards;
end
@enduml

To deter Denial of Service attacks, both configurations have to be combined, with the first configuration leading into the second at the branch where everyone agrees to start the payment.

@startuml
start
:Lock credit from buyer and forwards;
note right: Finalize on timeout
if (All agree?) then ([Yes])
:Pre-finalize from buyer and forwards;
note right: Cancel on timeout
:Finalize from seller and backwards;
end
else ([No])
:Cancel from buyer and forwards;
stop
endif
@enduml

# Decision-making process for decentralized multi-hop payments

The problem in decision-making in a person-to-person chain is that a single link in the chain can break it. Primarily, a link in a chain can block decisions (by not agreeing on and forwarding it). In person-to-person payments, a blocked decision results in credit being locked indefinitely as the payment cannot proceed (it simply gets stuck). It is possible to prevent attacks that block decisions by punishing the attacker. As organizing such a punishment is itself a decision that can get blocked, the payment has to be done in such a way that the decision to start the penalty is itself enforced by a penalty, and the decision to end the penalty (and the payment) is also itself enforced with a penalty. Logically, the decision to start the payment (and the penalty) has to affect the outgoing balance (and thus start from the buyer) and the decision to finish the payment (and the penalty) has to affect the incoming balance (and thus start from the seller). When finishing the payment, there is a gradual decrease in how much can be claimed, and when starting the payment, there is a gradual decrease in how much can be cancelled (along with fees added on top of the payment that are paid out in proportion to how long the payment was stuck). With this penalty system, the buyer will request an agreement to start the payment. Depending on if everyone agrees, the buyer will either cancel the attempt, or go through with it. For either outcome, each intermediary and the seller is incentivized (by the penalty) to conform to it. The decision to go through with the payment requires two steps. First, the buyer has to inform each intermediary that they decided to do the payment (i.e., that they revoke their right to decide to cancel the payment). Then, the payment has to be finished from the seller and backwards, so that the penalty can enforce it (i.e., the penalty when finishing the payment has to affect the incoming balance, by reducing it relative to how much had been finalized already at the outgoing balance).

# Incentive system for decentralized multi-hop payments

Multi-hop payments across one or more intermediaries has the problem that a decision can get stuck if an intermediary does not forward it to the next hop . The solution to this problem is an incentive system. With the correct incentives, the decision-making in a decentralized payment chain can be guaranteed to either end with a successful payment or with a cancelled payment. The incentives have to enforce that an agreement is made to either succeed with the payment or cancel the payment.

The decision to either succeed or cancel has to be centralized down to a single authority. When it comes to agreements along a chain of people, the only person who can be certain about if everyone agreed is the last person in the chain (the receiving end of a decision can be certain that previous hops agreed on it, but the sender cannot be certain that hops further down the chain will agree on it). Thus logically, the authority for the decision should be either the buyer or the seller.

The incentive needed is a penalty that forces the buyer to make the decision to either succeed with or cancel the payment, and, a penalty to enforce that this decision is agreed on by everyone else in the payment chain. To enforce that the buyer makes the decision, the penalty should gradually decrease the amount that the buyer can cancel, thus forcing the buyer to either cancel, or seal  the payment (and when sealed  the payment will always succeed, one way or another). To enforce that either decision is agreed on by everyone in the payment chain, the same gradual decrease in the amount that can be cancelled will enforce the cancel agreement, and a gradual decrease in the amount that can be finalized will enforce a finalize  agreement (with the seal  agreement in between enforced by a combination of both effects, acting on either end of an intermediary).

These two penalty mechanisms, that can act on either a person's outgoing balance (the continuous finalization) or a person's incoming balance (the continuous cancellation), enforce agreements in every scenario, except when both the buyer and seller attack the system (i.e., both the buyer and seller deliberately cause the payment decision-making to get stuck). When both the buyer and seller attack, the two penalty mechanisms have no effect (the attacker ends up sending money to himself or ends up cancelling the full payment). To deter stuck decision  attacks in that scenario, fees are added on top of the payment, paid by the buyer to everyone else in proportion to how long the payment got stuck. These fees also have a secondary effect of compensating victims of a stuck decision , and the buyer also gets compensated at the same time because the attacker ends up paying the seller.

Most of you are familiar with Ryan's "late-receipt penalty". By 2010-2012 this penalty was the full payment, but earlier back in 2006 it was continuous with a "late-receipt penalty rate" (mentioned on https://sourceforge.net/p/ripple/mailman/message/1307752/). The "late-receipt penalty" solves a "stuck decision" problem when finishing the payment, it enforces that each hop (from the seller towards the buyer) propagates the decision to finish the payment. But, the use of a continuous penalty (a "penalty rate") required a decision that could also get stuck, so Ryan abandoned that idea (but he did not abandon the "late-receipt penalty", instead he made the penalty the full payment. Interledger later by 2018 tried to "fix" the problem with the full payment penalty by reducing the size of the payment, but this is not the right approach).

The problem introduced with the "late-receipt penalty rate" (that it requires a decision that can get stuck) is solved with a "late-cancel penalty", that is also proportional to the same "penalty rate". This "late-cancel penalty" is the exact opposite of the "late-receipt penalty". The "late-receipt penalty" reduces the amount that can be finalized, whereas the "late-cancel penalty" reduces the amount that can be cancelled. While "late-receipt penalty" acts on whoever is at the end of the payment (thus at first the seller and then the next hop, etc), the "late-cancel penalty" acts on whoever is at the beginning of the payment (thus first the buyer and then next hop, etc).

The "late-receipt penalty" is a form of "continuous cancellation" (i.e., it reduces the amount that can be finalized), whereas the "late-cancel penalty" is a form of "continuous finalization" (i.e., it reduces the amount that can be cancelled).

The "late-receipt penalty" is used to finish the payment and the "late-cancel penalty" is used to start the payment.

Conveniently, the decision to go from the "continuous finalization" during the "late-cancel penalty" step to the "continuous cancellation" during the "late-receipt penalty" step, is naturally enforced as well (if that decision gets stuck, there is a net penalty on the person that caused it to get stuck).

These two penalty mechanism, the "late-receipt penalty" defined by Ryan 19 years ago and the "late-cancel penalty" defined by me this spring (does anyone know if it has been suggested by someone else earlier?) provides the incentive for true decentralized multi-hop payments. As what Ryan envisioned with Ripple Inter Server Protocol.

These two opposite penalty mechanisms work in every case except when the attacker is both the buyer and the seller (naturally). To also deter that scenario, fees have to be added on top of the payment (that are paid out to each person in the payment chain, in proportion to how long the payment got stuck).

# Rules to deter "stuck payment" attack in multi-hop payments

Multi-hop payments have the "stuck payment" attack problem, that any node in the payment can decide to not propagate a decision, thus causing the payment to get stuck at that node. This problem can be resolved by adding a penalty system that enforces propagation by penalizing any node that causes the payment to get stuck. As the payment can get stuck on any decision, and by any node, this penalty system consists of three mechanisms, used to account for every possible scenario.

The decisions in the payment need to move in three different ways:

1) From the buyer towards the seller, where each node who propagated the decision then leaves the payment.
2) From the seller towards the buyer, where each node who propagated the decision then leaves the payment.
3) From the buyer towards the seller, where each node who propaated the decision stays in the payment.

These movements can be eforced with two mechanisms, that are used either alone or combined. These mechanisms are:

A) "continuous finalization", all nodes continuously finalize small "chunks" of the payment
B) "continuous cancellation", all nodes continuously cancel small "chunks" of the payment

To enforce 1 you need to use mechanism A. To enforce 2, you need to use mechanism B, and to enforce 3 you need to combine A and B.

These two mechanisms can apply enforcement in either direction, and cover all scenarios except when the attacker is both the buyer and seller. This is where the third mechanisms is used. The third mechanism is the addition of fees that are paid on top of the payment by the buyer.

With these three mechanisms, the propagation of any decision is enforced at any hop.

## The three steps of a multi-hop payment

The movements described above, 1, 2, and 3, are building blocks for a secure multi-hop payment. They can be combined so that 1 is used to start the payment, 2 is used to complete the payment, and 3 is used to go from 1 to 2.

The first decision that is propagated with 1, ensures every node agrees to start the payment. It is a decision to cancel the payment (signed by the buyer) and is used in case the agreement to start the payment fails.

If every node agreed to the payment (the seller tells the buyer everyone has agreed), decision number 3 is used. This is the decision that the buyer revokes their right to cancel.

Once decision 3 reaches the seller, they send decision 2. This completes the payment.

# Rules to deter "stuck payment" attack in multi-hop payments

Multi-hop payments have the "stuck payment" attack problem, that any node in the payment can decide to not propagate a decision, thus causing the payment to get stuck at that node. This problem can be resolved by adding a penalty system that enforces propagation by penalizing any node that causes the payment to get stuck. As the payment can get stuck on any decision, and by any node, this penalty system consists of three mechanisms, used to account for every possible scenario.

The decisions in the payment need to move in three different ways:

1) From the buyer towards the seller, where each node who propagated the decision then leaves the payment.
2) From the seller towards the buyer, where each node who propagated the decision then leaves the payment.
3) From the buyer towards the seller, where each node who propaated the decision stays in the payment.

These movements can be eforced with two mechanisms, that are used either alone or combined. These mechanisms are:

A) "continuous finalization", all nodes continuously finalize small "chunks" of the payment
B) "continuous cancellation", all nodes continuously cancel small "chunks" of the payment

To enforce 1 you need to use mechanism A. To enforce 2, you need to use mechanism B, and to enforce 3 you need to combine A and B.

These two mechanisms can apply enforcement in either direction, and cover all scenarios except when the attacker is both the buyer and seller. This is where the third mechanisms is used. The third mechanism is the addition of fees that are paid on top of the payment by the buyer.

With these three mechanisms, the propagation of any decision is enforced at any hop.

# Game theory to enforce multi-hop payments (deter reserve credit attacks )

A major problem in multi-hop payments is the reserve credit attack , that a person can initiate a payment and then cause it to never finish, thus locking credit forever. This attack can be prevented by financially punishing the attacker. The mechanism for such penalty differs depending on who the attacker is, and a complete solution requires a three step payment agreement, commit , seal , finalize , with fees paid by the buyer added on top of the payment and agreed on beforehand.

The game theory can be explained by starting with the last step and then showing how the steps leading up to it are required to organize that last step. During finalize , each intermediary from the direction of the seller and towards the buyer will complete the payment. At the same time, the amount that can be finalized starts to gradually decrease after the timeout has been reached. Thus, an intermediary who does a stop-propagation attack  (the mechanism to cause the reserve credit attack ) will end up with less incoming payment than their outgoing payment they already finalized. They thus end up having to pay a penalty. This step thus requires that there is a continuous cancellation  on the buyer side of the intermediary who propagates finalize . This continuous cancellation  is set up using the two previous steps, seal  and before it commit .

The seal  step is a bridge between the first step commit  and the finalize  step. Primarily, seal  signals that the buyer has revoked their right to cancel (the right of the buyer to cancel is indispensable to organize the first step, commit ). It is very important that the buyer revokes this right and that each intermediary knows that they did. On top of that, any user who has propagated seal  will start to continuously cancel the payment (thus adding the enforcement penalty onto finalize ). This continuous cancellation  also serves as an enforcement to propagate seal  itself, but only because the previous step, commit , had set up a continuous finalization . Thus an intermediary who does a stop-propagation attack  on seal , will end up having their outgoing pending payment gradually finalized while their incoming pending payment is gradually cancelled (at equal rates seems best). They thus end up having to pay a penalty. This penalty that enforces seal  thus required the continuous finalization  to have been organized originally during the commit  step.

The commit  steps main role is to ensure everyone is on board with the payment and goes all-in  on it. To ensure this, we rely on that the buyer will be punished if everyone has not agreed yet and the payment times out (and thus forced to use buyer cancels  to cancel the payment). For this punishment, we need to add a fee on top of the payment, that has been agreed on by all people in the payment. This fee will be a percentage of the payment, and each person in the payment will demand a certain rate and the buyer will prefer the path with the lowest total fees. The fees are paid out at the same rate as the continuous cancellation  and continuous finalization  (i.e., a single rate that says how much of the payment has been either cancelled or finalized as well as paid out as fees yet ). The fees are paid out in every step of the payment (both commit , seal  and cancel ) and they compensate the people who are victims of a reserve credit attack  (and if no attack or network failure occurs and the payment finishes before timing out, no fees is paid out). The fees are paid out in proportion to how much of the payment had time to be processed , if the payment was stuck for a half of the time it would have taken to cancel/finalize the entire payment, half the fees are paid out.

So, we have single ticking rate for cancelling the payment, finalizing the payment, and paying out the fees. The fees deter the buyer from doing the reserve credit attack . The cancellation and finalization deters everyone else (for the seller, they are always guaranteed to get the full amount as long as commit  succeeds and the seller themselves do not do stop-propagation  at finalize , so the buyer will know that the payment was successful or that if it was not it was the seller themselves attacking and then the seller cannot claim that they were not paid).

## Agreeing on the buyer fees  and cleanup rate 

Simplest is that the buyer/seller says what fee the buyer will provide as well as what cleanup rate  (how fast the continuous cancellation, continuous finalization and fee payout happens, i.e., how fast a stuck payment is cleaned up and the pending payment object removed), and select paths that accept these values. People then have a lower bound for what fee they accept and a lower and upper bound for what cleanup rate  they accept. Thus a selection system is formed between buyer and intermediaries. Since penalty system exists to deter attackers, people would generally work to set good norms  for those two parameters, collectively (although in a decentralized way).

## Illustrations

A payment of 1000 XYZ gets stuck at D during the seal  step (D is doing a stop-propagation attack  or there was a network failure). The penalty rate  is 1 XYZ per hour (thus a little more than a month for 1000 XYZ), and 100 hours have passed (roughly 4 days), during which the payment has been stuck at D ever since it timed out (and the period until timeout was maybe 5 minutes then after the payment had been started 4 days prior to the moment illustrated below). The buyer fees  are 2%, i.e., for the full payment being cleaned up  each person would get 20 XYZ and now that only 10% has been cleaned up  each person has received 2 XYZ. The buyer thus has a negative balance of 8, while the seller has received 102. The buyer has thus been compensated with 92 XYZ (as their payment to E always succeeds as long as the buyer issued seal  and the seller themselves is not the attacker). Each intermediary as well as the seller has received 2 XYZ from the buyer fees, and thus been compensated for the stuck payment. Note, 900 is the pending payment amount, thus 1000 XYZ minus 100 XYZ.

Another payment also at 1000 XYZ and also at penalty rate  1 XYZ per hour as well as buyer fees at 2% that has been stuck for 100 hours (roughly 4 days) because of a problem at D (either a network failure or an attack). Here it is illustrated that the buyer A has an incentive to cancel the payment - and should have done so 4 days ago the moment it timed out 5 minutes or so after it was started! It would go without saying that the buyer cannot issue seal  here as they never got the signal from the seller E that commit  succeeded (since commit  never succeeded, it got stuck at D &)

And then a payment example also of 1000 XYZ with 1 hour per 1 XYZ penalty and having been stuck for 100 hours (with a 2% buyer fee). This time, it is stuck at C during finalize  (either because of a network failure or because C is an _attacker_). If C issued finalize  at the moment shown in the illustration below, they would be left with a penalty of 94 XYZ. The reason the illustration shows -994 is because they already finalized 1000 XYZ, but 94 XYZ is the actual penalty they would receive if the penalty period ended in the moment shown below (i.e., if C issued finalize ). Note that the buyer has here been rewarded with 992 XYZ as their payment still succeed (the payment always succeeds as long as the buyer does seal  and the seller is not the cause of the stuck payment).

And a final example, where the payment got stuck at commit  (at D) but then the cancel  signal also got stuck (at B), both either because of a network failure or an _attack_. Here the buyer is not penalized at all. Instead, the penalty starts to affect B, thus it enforces the propagation of buyer cancels  perfectly.

## Implementation

This game theory is very simple to implement. As it centers around a ticker  that is just the machine clock, any recordkeeping about how much was cancelled or finalized or paid out as fee only has to be done when there is a state transition such as from commit  to seal  or if the full payment was cleaned up  (the ticker reached the full payment amount) and then via a separate cleanup_payment  command handler. The game theory most likely works for something like Interledger and it also works for the person-to-person money system Ripple (i.e., it should work regardless of what a node  is defined as).

## Agreeing on the buyer fees  and cleanup rate 

Simplest is that the buyer/seller says what fee the buyer will provide as well as what cleanup rate  (how fast the continuous cancellation, continuous finalization and fee payout happens, i.e., how fast a stuck payment is cleaned up and the pending payment object removed), and select paths that accept these values. People then have a lower bound for what fee they accept and a lower and upper bound for what cleanup rate  they accept. Thus a selection system is formed between buyer and intermediaries. Since penalty system exists to deter attackers, people would generally work to set good norms  for those two parameters, collectively (although in a decentralized way).

# Game theory to enforce multi-hop payments (deter reserve credit attacks )

A major problem in multi-hop payments is the reserve credit attack , that a person can initiate a payment and then cause it to never finish, thus locking credit forever. This attack can be prevented by financially punishing the attacker. The mechanism for such penalty differs depending on who the attacker is, and a complete solution requires a three step payment agreement, commit , seal , finalize , with fees paid by the buyer added on top of the payment and agreed on beforehand.

The game theory can be explained by starting with the last step and then showing how the steps leading up to it are required to organize that last step. During finalize , each intermediary from the direction of the seller and towards the buyer will complete the payment. At the same time, the amount that can be finalized starts to gradually decrease after the timeout has been reached. Thus, an intermediary who does a stop-propagation attack  (the mechanism to cause the reserve credit attack ) will end up with less incoming payment than their outgoing payment they already finalized. They thus end up having to pay a penalty. This step thus requires that there is a continuous cancellation  on the buyer side of the intermediary who propagates finalize . This continuous cancellation  is set up using the two previous steps, seal  and before it commit .

The seal  step is a bridge between the first step commit  and the finalize  step. Primarily, seal  signals that the buyer has revoked their right to cancel (the right of the buyer to cancel is indispensable to organize the first step, commit ). It is very important that the buyer revokes this right and that each intermediary knows that they did. On top of that, any user who has propagated seal  will start to continuously cancel the payment (thus adding the enforcement penalty onto finalize ). This continuous cancellation  also serves as an enforcement to propagate seal  itself, but only because the previous step, commit , had set up a continuous finalization . Thus an intermediary who does a stop-propagation attack  on seal , will end up having their outgoing pending payment gradually finalized while their incoming pending payment is gradually cancelled (at equal rates seems best). They thus end up having to pay a penalty. This penalty that enforces seal  thus required the continuous finalization  to have been organized originally during the commit  step.

The commit  steps main role is to ensure everyone is on board with the payment and goes all-in  on it. To ensure this, we rely on that the buyer will be punished if everyone has not agreed yet and the payment times out (and thus forced to use buyer cancels  to cancel the payment). For this punishment, we need to add a fee on top of the payment, that has been agreed on by all people in the payment. This fee will be a percentage of the payment, and each person in the payment will demand a certain rate and the buyer will prefer the path with the lowest total fees. The fees are paid out at the same rate as the continuous cancellation  and continuous finalization  (i.e., a single rate that says how much of the payment has been either cancelled or finalized as well as paid out as fees yet ). The fees are paid out in every step of the payment (both commit , seal  and cancel ) and they compensate the people who are victims of a reserve credit attack  (and if no attack or network failure occurs and the payment finishes before timing out, no fees is paid out). The fees are paid out in proportion to how much of the payment had time to be processed , if the payment was stuck for a half of the time it would have taken to cancel/finalize the entire payment, half the fees are paid out.

So, we have single ticking rate for cancelling the payment, finalizing the payment, and paying out the fees. The fees deter the buyer from doing the reserve credit attack . The cancellation and finalization deters everyone else (for the seller, they are always guaranteed to get the full amount as long as commit  succeeds and the seller themselves do not do stop-propagation  at finalize , so the buyer will know that the payment was successful even if the seller tries to do such attack, the seller can never claim oh someone attacked and I got nothing  if they are themselves the one attacking, and if anyone else attacks the seller always gets the full amount, paid for by the attacker).

# Ripple Inter Server Protocol built on a fee system and single-hop consensus

In 2004 Ryan Fugger invented the money system Ripple, where each person was a bank. Since each person is a bank, it is possible to organize Ripple in a truly distributed way, computationally. Consensus is only needed at the user-to-user level, i.e., only ever between two people. To enforce agreements at the multi-hop level, a fee system can be used. The fee system enforces signal propagation at each hop, preventing stuck half finished payments. The fees compensate users who get stuck with a half-finished payment and they penalize the person who is causing the payment to not proceed. The fees are collected from the payment by users in a decentralized way where any cheating only impacts your own trust relationships.

## The fee system

Fees can enforce signal propagation when they can apply a net negative balance on the person who is causing the signal to not propagate. Fees work in a straightforward way when propagation is at edge nodes , i.e., when a signal originates from an edge node  (buyer or seller) and nodes that have propagated the signal then remove themselves from the payment so the next node is thus the new edge node . To enforce propagation at intermediaries, fees instead need to be balanced in an asymmetric way so that they are stronger on one side of the intermediary and weaker on the other.

The fee system uses two signals that are propagated by edge nodes : buyer cancels  and seller finalizes , and it uses one signal that is propagated by intermediaries: seal payment .

### Buyer cancels  signal

Buyer cancels  is used to commit to the multi-hop payment with the commit  signal. The commit  signal is itself not enforced by fees, instead it relies on buyer cancel  to avoid the payment getting stuck. If the commit  signal fails to reach the seller because it gets stuck at an intermediary, the fees will start to be collected and the buyer will be the one paying for them. The buyer therefore has an incentive to cancel the payment. When the buyer cancels (and remove themselves from the payment), the fees start to act on the next user in line (B in the illustration below), as they become the new edge node . The new edge node  (B) then has an incentive to propagate the cancel signal to C who then becomes the new edge node , etc.

### Seller finalizes  signal

Seller finalizes  is used to finish the payment, and it relies on the fee system as the incentive to enforce propagation of the decision. The fees are being collected by users between the person who does finalize  and the buyer. While the buyer is the one paying the fees to the intermediaries, the person currently doing finalize  is paying the buyer. As fees are paid out, the amount that the intermediary can finalize from the next hop is reduced. Thus the fees mean they pay more out than they receive in.

In the illustration above, note that if C were to propagate finalize  at the moment shown in the illustration, they would only be able to finalize 950 (900 + the 50 they already finalized as fees), and thus end up with a net negative balance of -50. B would likewise only be able to finalize 950 but as their outgoing balance with C ended up 950 as well, they have a net neutral balance. And A would finalize 1000 in full, which in the situation above is also what E received, thus A was not impacted financially.

### Seal payment  signal, asymmetric fees 

To avoid the attack where the buyer and seller issue both buyer cancels  and seller finalizes  at the same time, the buyer must revoke their right to cancel and inform every intermediary about doing so prior to finalize . This is the role of the seal payment  signal. Contrary to buyer cancels  and seller finalizes  the seal payment  is not propagated by an edge node  (every person who propagates it stays in the payment), it is propagated by an intermediary. Thus for fees to act on the intermediary, the fees must be asymmetric. Seal payment  propagates from the buyer and towards the seller, thus the fees must be higher on the seller side than on the buyer side. Thus we end up with two separate fee systems, a stronger one set up during commit  that acts on buyer cancels  and seal payment , and a weaker one during seller finalizes  (that also allows the stronger one to act as enforcement during seal payment ).

The weaker fee system set up during seal payment  is what incentivizes seller finalizes . The buyer is the one paying the fees for it. This means that when an intermediary does not propagate the seal payment  signal, the fees will also penalize the buyer even though the buyer is innocent. This is necessary. It is possible to guarantee the buyer never pays more than the attacker, but we cannot fully remove the penalty on the buyer.

To guarantee the attacker during seal payment  always pays more than the buyer (unless they are the friend of the buyer and then they pay the same amount), the first fee system (the one that acts on the seller side of the intermediary during seal payment ) has to operate at twice as fast as the second one (the one on the buyer side of the intermediary during seal payment ). The two illustrations below demonstrate this effect when the attacker is a few hops away from the buyer as well as when they are a direct friend of the buyer.

The penalty on the buyer can then be further reduced, by cancelling part of what would have been collected as fee. In the illustration below, on the buyer side half the amount that would have been claimed as fee was instead cancelled. This results in a net negative balance for fees paid of -50 for the buyer and -175 for the attacker.

### Decentralized (per-user) enforcement of fees
Fees can be collected in a fully decentralized way, as any cheating impacts only the next hop. Thus if you cheat you only hurt your own friends - there is no transitivity of trust problem. Users simply have a config parameter `FEE_RATE`, and keep track of how much fees should have been collected in total at a point in time. They always accept `PAYMENT_FEE` commands from their friends, but they only propagate them up to the amount they calculate should have been collected up to that point. Users periodically run a `collectFees()` routine and grab a random amount of fees they calculated are available. Users that always pick max fees disproportionately hurt their own friends.

## User-to-user consensus

A person-to-person Ripple requires that consensus at the person-to-person level is guaranteed. The issue with person-to-person decision making over the internet is the "two general problem", that it is impossible to be certain about if an acknowledgement was delivered. Thus it follows that agreement is impossible. The solution to the two-general problem is to agree on a single general. The ideal way to do so, is to take turns being the general.

### Lockstep, a single-hop consensus mechanism

People in a trustline-relationship agree to take turns to be "general" who gets to say which transaction should happen next. They coordinate this with the use of a counter, and agree that one person will validate when counter mod 2 is 0 and the other when counter mod 2 is 1. The person who is not the "general" at a turn can propose transactions to the "general". Each person stores the instruction they last validated in permanent storage until they receive the next rounds validated transaction (thus continuity is guaranteed.) In permanent storage you thus maintain a turn bit (0 or 1) for counter mod turnbit, and a turn counter for same operation, and the last validated instruction (an instruction being a command with arguments). The "state transition function" in Lockstep includes incrementing the turn counter and setting the last validated instruction, as well as the state changes that the instruction performed, and is "atomic", all-or-nothing. Thus, two accounts are in perfect agreement over every decision that they make.

### Integrating Lockstep with the role as an intermediary

With single-hop guaranteed, two-hop at an intermediary is guaranteed since it is on a single machine. But it still has to be organized practically, on that machine. A simple approach is that the command handler returns an "inter-lockstep" callback. This callback is executed only if the Lockstep state transition succeeded. Since such callback could fail, it is ideally combined with "failsafe" routines. For example, a callback that queues a transaction could fail because the queue is full. A failsafe routine can derive the same decision from the permanently stored data, and run periodically to catch any failures.

## Single-hop consensus and fee system allow multi-hop agreements

Lockstep solves the two general problem and guarantees that any signal that propagates over multiple hops has been agreed on by every previous hop. The fee system guarantees that signal propagation over multiple hops will either succeed, or fees are paid out to every person who is a victim of the stuck payment (paid by the person who caused the payment to get stuck). When combined they make multi-hop agreements possible.

Ripple Inter Server Protocol built on a fee system and single-hop consensus

Ripple is a person-to-person money system that was invented by Ryan Fugger in 2004. The new idea with Ripple was that everyone is a bank, thus Ripple took banking down to the smallest possible scale. Ripple as a money system is therefore unique in that the bookkeeping only needs consensus at the person-to-person level, and thus it is possible to design and build a Ripple Inter Server Protocol where the computation also only needs consensus at the person-to-person level (thus a person could run their own isolated server and share state only with their trusted relationships, if they wanted to). The main problem in multi-server Ripple is the reserve credit attack . A fee system can be used to deter such an attack. The users of a multi-hop payment that are affected by a reserve-credit-attack can simply collect fees, and thus get paid for being attacked. Fees can apply a force on whoever has a net negative balance. During multi-hop payment coordination this means that the fees can enforce a signal if each hop  gets stuck with the net negative balance. Thus both a cancel signal from the buyer and a finalize signal from the seller can be enforced with fees (Ryan Fugger originally focused on a seller-finalizes mechanism for this exact reason). The logical way to exploit the fees becomes a three step payment process: commit , seal , finalize , with the fee system applying a force on each of those steps.

The game theory of fees as an incentive

The fees can apply a force on a person during a payment coordination step if they are in a net negative balance. I.e., the fees act on whoever has a net negative balance. During multi-hop payment coordination this means that the fees can enforce a signal if each hop  gets stuck with the net negative balance. Such is the case for both a seller finalizes  mechanism as well as a "buyer cancels" signal. Thus, both those signals could reasonably be good building blocks for enforcing certain outcomes in multi-hop payment coordination (note that both have to be authenticated).

Ryan Fugger originally focused on the seller finalizes but with a very crude penalty: the full payment, enforced by a simple timeout (technically a staggered timeout  &) His idea could be practically usable if the penalty was reduced. A fee system where users themselves impose fees can be easily conceived. It can operate as soon as the users have begun to coordinate a multi-hop payment. But to reduce the penalty compared to Ryan's idea also means you reserve credit for longer periods of time. Thus it is important to make sure that everyone commits to doing so (that the path did not fail halfway). Conveniently, the buyer cancels  building block is ideal for ensuring this. The fact that buyer cancels  can be enforced by fees means you can simply let the buyer issue a commit  signal towards the seller, and then have the seller signal the buyer (in an authenticated way) if it succeeded. If the commit  failed, the buyer simply cancels. Since the buyer is the one with a net negative balance, the fee system that started at commit  will enforce that the long-term-reserve-credit  only starts if everyone has committed.

With this first commit step, we thus set up an agreement where the payment will either succeed, or, large penalties will be inflicted on those who prevented it and large rewards handed out to everyone damaged by the failure. The payment has been sealed  and can no longer be cancelled, it can only either succeed or failed.

Formally, the sealed  step (where the payment can no longer be cancelled, and everyone is stuck with it until it either succeeds or fails) starts when the buyer issues SEAL_PAYMENT. The fees as an enforcement mechanism here start to act on each intermediary, as they end up with a net negative balance when fees are collected from both sides (note, the buyer also has a net negative balance here). The propagation of SEAL_PAYMENT is then ensured to either succeed, or, to financially compensate each user who is damaged by the failure (while punishing the user who caused the failure).


Then with everything set up perfectly thanks to COMMIT_PAYMENT and SEAL_PAYMENT, the fee system will also enforce that FINALIZE_PAYMENT propagates once the seller issues it after receiving SEAL_PAYMENT.

The fee system

The fee system idea is very simple: any user affected by a reserve credit attack simply collects fees themselves, thus paying themselves for their damages. Any attempt to cheat the mechanism only affects your own friends. Each user in the payment chain thus acts as a buffer  to cheating (and the transaction history lets you prove if your friends cheat you). The fee system is coordinated in a very simple way: each user has a FEE_RATE parameter that defines how many seconds it takes to grab 1 XYZ as fee. They run a routine periodically where they grab a random amount from the so-far unclaimed fees. They then synchronize this claim in their accounts with the incoming and/or outgoing user. Their relationships will forward the claim if it is less than or equal to what they have calculated should be the fee so far. Thus the equilibrium is for people to use the same (or at least very similar) FEE_RATE.

The user-to-user consensus mechanism Lockstep 

A person-to-person Ripple requires that consensus at the person-to-person level is guaranteed. The issue with person-to-person decision making over the internet is the "two general problem", that it is impossible to be certain about if an acknowledgement was delivered. Thus it follows that agreement is impossible. The solution to the two-general problem is to agree on a single general. The ideal way to do so, is to take turns being the general. Here I will conceptualize such a mechanism and call it Lockstep .

Lockstep, a single-hop consensus mechanism

People in a trustline-relationship agree to take turns to be "general" who gets to say which transaction should happen next. They coordinate this with the use of a counter, and agree that one person will validate when counter mod 2 is 0 and the other when counter mod 2 is 1. The person who is not the "general" at a turn can propose transactions to the "general". Each person stores the instruction they last validated in permanent storage until they receive the next rounds validated transaction (thus continuity is guaranteed.) In permanent storage you thus maintain a turn bit (0 or 1) for counter mod turnbit, and a turn counter for same operation, and the last validated instruction (an instruction being a command with arguments). The "state transition function" in Lockstep includes incrementing the turn counter and setting the last validated instruction, as well as the state changes that the instruction performed, and is "atomic", all-or-nothing. Thus, two accounts are in perfect agreement over every decision that they make.

Integrating Lockstep with the role as an intermediary

With single-hop guaranteed, two-hop at an intermediary is guaranteed since it is on a single machine. But it still has to be organized practically, on that machine. A simple approach is that the command handler returns an "inter-lockstep" callback. This callback is executed only if the Lockstep state transition succeeded. Since such callback could fail, it is ideally combined with "failsafe" routines. For example, a callback that queues a transaction could fail because the queue is full. A failsafe routine can derive the same decision from the permanently stored data, and run periodically to catch any failures.

Guaranteed single-hop consensus makes multi-hop agreements possible

Lockstep guarantees that any signal that propagates over multiple hops has been agreed on by every previous hop. But it does not guarantee that a signal propagates, nor is it able to discover propagation failure. Thus, multi-hop agreements have to conform to the fact that propagated signals can be trusted but signal propagation cannot. The fundamentals are: assume perfect consensus about that propagated signals are honest, assume zero consensus about if a signal has propagated (i.e., the receiver can be certain, the sender cannot). It follows that only the end receiver of a signal can know if an agreement succeeded.

Multi-hop payment with honest signals but uncertain signal propagation

The coordination steps described for the multi-hop payment assumes honest signals but uncertain signal propagation. When the seller receives COMMIT_PAYMENT they can be certain that every intermediary has propagated it (i.e., the receiver can be certain, the sender cannot). Likewise, when the seller notifies the buyer of this, the buyer can be certain everyone has committed. When the buyer then submits SEAL_PAYMENT they can be certain that everyone is all-in  on the payment. When SEAL_PAYMENT reaches the seller, they can be certain the buyer revoked their right to cancel, i.e., that everyone is all in. When the seller then submits FINALIZE_PAYMENT, each person knows since before that the payment has been sealed and that they are penalized by fees if they do not propagate the finalize  signal.