[Lightning-dev] A state machine.

[Rusty Russell]

Anthony Towns <aj at erisian.com.au> writes:
> On Fri, Aug 21, 2015 at 03:02:32PM +0930, Rusty Russell wrote:
>> Rusty Russell <rusty at rustcorp.com.au> writes:
>> > Yeah.  Let me generate a decent text flowchart for the normal cases...
>> I've taken out some transitions for simplicity (eg. ERR_ANCHOR_LOST and
>> ERR_INFORMATION_LEAK, which shouldn't happen):
>
> Some thoughs, fwiw.
>
> I think the two INIT states is odd. I guess I would have expected
> something more like:
>   INIT:
>     - (cmd_open_my_anchor) -> INIT_WITHANCHOR
>     - (pkt_propose_channel) -> INIT_NOANCHOR
>
> I think the "state" orientation of the dot output isn't great. ie rather
> than laying it out like how it is in the code with a state then all the
> transitions from that state:
>
>   NORMAL:
>     - UPDATE_HTLC -> X
>     - UPDATE_PKT -> Y
>     - COMPLETE_HTLC -> Z
>
> I'd rather see it laid out as the protocol steps:
>   UPDATE_HTLC
>     NORMAL -[UPDATE_HTLC]-> X -[ACCEPT]-> X2 ->...
>
>   UPDATE_PKT
>     NORMAL -[UPDATE_PKT]-> Y ->...
>
> ie, have multiple graphs, each starting at INIT/NORMAL with a single
> cmd/pkt and ending at NORMAL'/CLOSED/ERROR. I'd probably prefer
> including the decision points as nodes too.

Yeah, I plan on eventually creating an RFC-style document which lays
this out.

At its core, it's fairly simple, and I'm starting to think that diagrams
more than a simple ASCII flowchart don't add anything.

> A lot of the "an error occurred!" abort paths apply to a whole bunch of
> states, it would be nice to combine them in the output... Hmm, I think
> that's doable...
>
> I've had a go at doing this with code. C is hard, so I converted to
> python, and came up with:
>
>   http://azure.erisian.com.au/~aj/tmp/lightstate/statepy.svg
>
> (source bits in the lightstate/ directory)
> 
> 
> I was thinking it would be possible to update many HTLCs at once, so
> I was expecting a single PKT_UPDATE_CHANNEL rather than the ADD_HTLC,
> COMPLETE_HTLC, TIMEOUT_HTLC, etc variants. From a protocol POV, I guess
> that's something like:
>
>   UpdateChannel:
>      int  n_ops
>      op   ops[]
>      int  commitment_len;
>      byte commitment[]
>
> where an op would be ADD_HTLC, COMPLETE_HTLC, TIMEOUT_HTLC,
> ROUTEFAIL_HTLC, etc. That's a bit more complicated in the protocol,
> but I think it pays off in simplifying the state diagram and hence the
> software? (I think it's also kindof necessary for some fee models, and
> will be useful for batching updates when performance eventually
> matters)

This is the kind of optimization we may see later, but I really shy away
from doing it now.  Your diagram looks simpler because you removed all
the rest of the handshaking.  Try this:

A: ADD_HTLC --> B: DECLINE_HTLC
  OR
A: ADD_HTLC --> B: ACCEPT --> A: SIGNATURE --> B: COMPLETE

After success:

B: FULFILL_HTLC -> A: ACCEPT --> B: SIGNATURE --> A: COMPLETE
  OR
B: ROUTEFAIL_HTLC -> A: ACCEPT --> B: SIGNATURE --> A: COMPLETE
  OR
A: TIMEDOUT_HTLC -> B: ACCEPT --> A: SIGNATURE --> B: COMPLETE

This makes the constraints clearer, eg. you can't DECLINE_HTLC anything
but an ADD_HTLC.

> Hmm, I find the PRIO stuff pretty klunky. It's only used to choose who
> wins in the event of simultaneous/overlapping channel updates, no? Why
> not just have a constant tiebreak in that case, eg, where whoever has the
> lowest channel balance (or the lowest IP / key id), wins?

That could lead to livelock.

> Or alternatively, just have the high priority be given to whoever last
> went from WAIT_FOR_UPDATE_SIG -> NORMAL (and low priority to whoever
> went from WAIT_FOR_UPDATE_COMPLETE -> NORMAL). That way the priority
> would still swap

Well, that would alternate at least.  But that seems more complex than
basing priority on the lower bit of the commitment number, which we have
to remember anyway.

> AFAICS, you still have a potential deadlock atm if you think you're
> high priority but your counterparty also thinks they're high priority,
> or just missed your update packet. I think there might be a similar
> deadlock if both systems think they're low priority.

They can't get into that state.  And that's why it's spelled out in the
state machine, so I can exhaustively test (and have).

> If the INIT_NOANCHOR is meant to do to single-sided-anchor idea proposed
> in
>
>   https://bitcointalk.org/index.php?topic=1134319.msg11963141
>
> then it would probably be good to have a PKT_REBALANCE_VIA_BLOCKCHAIN
> option; ie something like:
>
>  0. channel is unbalanced: A has many funds, B has no funds
>  1. B proposes rebalancing by $x.
>  2. A accepts, chooses R, reveals #(R).
>  3. B proposes HTLC from A to B of x funds, conditional on R.
>  4. B posts $x in funds on the blockchain, payable to:
>       [SIG_B & R | SIG_A & TIMEOUT]
>  5. B tells A the transaction id (and p2sh details etc).
>  6. A waits for this to be "deep enough"
>  7. A claims the blockchain transaction, revealing R.
>  8. B completes the HTLC, rebalancing the channel.

We want A to be able to increase the channel too, so this doesn't quite
work.  I think we need to explicitly add a new anchor for that case.

But this idea is a subset of a more general "swap to X" HTLC, which
comes down to a routing problem, which is a layer up from this state
machine.

> Not being able to tack on orthogonal state makes things a little clumsy
> here...

The state machine is hard to work with, but the payoff is exhaustive
proof that it's sane, and handles all possible cases.

Cheers,
Rusty.