From fabrice.drouin at acinq.fr Thu Apr 28 10:39:51 2016 From: fabrice.drouin at acinq.fr (Fabrice Drouin) Date: Thu, 28 Apr 2016 12:39:51 +0200 Subject: [Lightning-dev] Concurrent sigs in BOLT #2 In-Reply-To: <878u015cvn.fsf@rustcorp.com.au> References: <878u015cvn.fsf@rustcorp.com.au> Message-ID: Hi! On 26 April 2016 at 04:21, Rusty Russell wrote: > Pierre writes: >> Hello, > > Hi Pierre! > > I'm glad I'm not the only one who had trouble with this. I just > thought I was being dumb! Concurrent updates are conceptually harder > than the previous synchronous model, unfortunately. > >> I am trying to understand how we should handle concurrent signatures, >> and I am wondering if we couldn't use an ordering of some sort to >> resolve conflicts when they occur, for example by simply comparing >> signatures. If two nodes send each other a signature at the same time, >> they could agree that the one that sent the "greatest" signature has >> to immediately resend a new signature including all pending changes. >> This new signature would encompass all the changes both parties wanted >> in the first place so everybody would be happy. > > I originally had an alternating priority scheme which worked, but I don't > think it's necessary any more. > > This diagram is a simplification. Each node tracks two commitment > states: its own and the state of the other side. This is because they > can run independently. > > The rules are simple (though the results might not be!): > > 1) Nodes must process packets in order. > 2) When you send something, update their state. > 3) When you ack something, update their state. > 4) When you receive something, update your own state. > 5) When you receive an ack for something, update your own state. > > When you sign a commit tx, you sign their state at the time (this makes > sense: you're signing their commit tx, not yours). > > So, when a node sends an ADD HTLC, it modifies the other side's state. > It only modifies its own state when it receives an ack covering that ADD > HTLC. > > The ADD HTLC receiver modifies its own state, and modifies the other > side's state when it sends the next ack (in practice, we do that > immediately because it doesn't matter, but diagram below does it > strictly). > > Thus, in your case: > > NODE A NODE B > > Committed: [] Committed: [] > States: [] [X] States: [] [Y] > ADD HTLC X ---- ---- ADD HTLC Y > \ / > \ / > Committed: [] \ / Committed: [] > States: [] [X] \/ States: [] [Y] > SIG A0 --- /\ --- SIG B0 > \ / \ / > \/ \/ > /\ /\ > <--- \ / ---> > Committed: [] \/ Committed: [] > States: [Y] [X] /\ States: [X] [Y] > / \ > / \ > <---- -----> > Committed: [Y] Committed: [X] > States: [Y] [X] States: [X] [Y] > > Now, at this point both nodes have outstanding changes, so they can send > another SIG (which acks the received changes, thus modifying the other > state): > > Committed: [Y] Committed: [X] > States: [Y] [X Y] States: [X] [X Y] > SIG A1 --- --- SIG B1 > \ / > \ / > \ / > \ / > \/ > /\ > / \ > / \ > <---- -----> > PROCESS ACK: > Committed: [Y] Committed: [X] > States: [X Y] [X Y] States: [X Y] [X Y] > PROCESS SIG: > Committed: [X Y] Committed: [X Y] > States: [X Y] [X Y] States: [X Y] [X Y] > What if instead of immediately sending a new SIG, A and B then decide to send each other a new HTLC? Could we get stuck in an infinite loop where A and B never converge on a commitment tx? Or should it be specified that the only valid answer to a signature is either a signature (if there are outstanding changes) or a revocation ? Cheers, Fabrice