Handle concurrent payments

[acharb]

Right now the SDK is enforcing that only one unconfirmed payment can be in play at a time. A channel can't propose two payments, as well as a channel can't confirm a different payment if they just proposed one. This was done so a channel is protected from unintentionally signing a payment they don't want.

eg. Channel A proposes p1, and is blocked from confirming a different payment until p1 is finished. Also, A is blocked from proposing p2 until p1 is complete.

However this introduces a deadlock, if two channels propose a payment at the same time. One solution could be a channel discards its unconfirmed payment for the new payment it just received. However if both channels do this then they are no longer in sync.

Adding this discussion to discuss possible solutions.

[leighmcculloch]

This problem also exists if the channel supports queuing payments and sends or accepts multiple payments without waiting for confirmation.

I think if define some general pattern for how to merge payments we'll end up with logic that will work in both situations, where payment queuing is supported, or where queueing isn't supported but we use it to deal with concurrent payments.

[leighmcculloch]

One way we could merge payments is to have both participants accept the others and repost their own, which should result in the same agreement:

1. Assume channel exists and A owed B 100 so far, i.e. balance=100.
2. A sends B iteration=4 amount=20, i.e. balance=100+20=120.
3. At the same time B sends A iteration=4 amount=15, i.e. balance=100-15=85.
4. A sends B iteration=5 amount=20, i.e. balance=100-15+20=105.
5. At the same time B sends A iteration=5 amount=15, i.e. balance=100+20-15=105.

Both A and B have agreed that at iteration 5 their balance is 105.

[nikhilsaraf]

would either A or B create a new transaction with "combined operations" from both transaction? that seems like what you were going for in the description but the example does not show any such combined transaction. Great idea though to merge tx.

[leighmcculloch]

Transactions in step 4 and 5 are identical and after 4 and 5 the net balance is consistent. It's possible explicit merge agreements would be required, although I think how we have the agreements defined today an explicit merge might not be required. Either way it would work the same.

[leighmcculloch]

I discussed this with @stanford-scs and @MonsieurNicolas and they raised the fact that a channel between two businesses will likely have messaging at a higher layer that are coordinating why payments are occurring and that layer could handle signaling of whose payment can be the next payment without needing to build that into the payment channel explicitly, or at least not into the state machine.

[nikhilsaraf]

wrote up a suggestion here around how we could use lock-free synchronization techniques to potentially resolve these deadlocks, although I think @leighmcculloch's solution of merging is pretty good.

https://docs.google.com/document/d/16ouWgE_qRlmWBA2-K7PT8ABlVRfnX95mpn1NG13i4UI/edit

[leighmcculloch]

Lifting the contents of your doc:

Idea on how to overcome serialization problem in Payment Channels

how to overcome serialization issue in payment channels -- look at lock-free synchronization approaches.

anybody that is waiting for a confirmation when they receive a request with the same seq number should look at a "discriminator" field to determine how to order these requests (their own vs the one they received.

1. The discriminant can be timestamp, however hard to sync clocks and there's no common server.
2. It could be a random number -- this can be gamed because you just gen a random number that is probabilistically very low all the time when submitting so you get priority
3. use hash of the tx being submitted

Hash of tx seems reasonable

However, this creates an incentive to hold on to the other person's tx until you want to submit one, and if your hash is lower than theirs then they will automatically select yours too, causing starvation.

Combine with timestamp

So to eliminate this, we can keep a time window of less than 1 second, assuming that timestamps are within 1s of each other -- we can go to the extend of synchronizing clocks too (or adding an offset to the requests so it can use this offset when comparing with your time).

I think this is a little different to a lock-free sync because synchronization is still lost because there is a fork in the history. This is similar to merging except without the need to actually merge because both participants agree quickly to move ahead with only one history. Until both participants sign another agreement the fork could be valid, but that's fine, the merging makes the same assumption.

A challenge with this is that if conflict happens frequently it maybe be more overhead than coordinating who should have the next turn since one payment gets discarded. But this idea of selecting who wins can be applied to who gets to propose the next tx.