From pm+lists at acinq.fr Thu Aug 20 18:20:04 2015 From: pm+lists at acinq.fr (Pierre) Date: Thu, 20 Aug 2015 20:20:04 +0200 Subject: [Lightning-dev] A state machine. In-Reply-To: <87si7eiehg.fsf@rustcorp.com.au> References: <87si7eiehg.fsf@rustcorp.com.au> Message-ID: Hello all, First, bravo for the great work on lightning ! @Rusty I'm the guy who recently made two dummy PR on your github project, thanks for merging them ;-) I've just got one remark : from OPEN_WAITING state, you seem to be assuming that the event BITCOIN_ANCHOR_DEPTHOK will always happen before receiving the other party's PKT_OPEN_COMPLETE ; but that won't necessarily be the case depending on each party's minDepth, right ? Also, can you please confirm that the following is correct in an Alice->Bob->Carol->Dave scenario if we look at the state of *Bob* ? 1) Bob is in NORMAL state - Bob receives update_add_htlc from Alice - Bob sends update_accept to Alice 2) Bob switches to WAIT_FOR_UPDATE_SIG state - Bob receives update_signature from Alice - (Bob sends update_add_htlc to Carol on another channel) - (Bob receives update_complete_htlc on another channel) 3) Bob switches to NORMAL state - Bob sends update_accept to Alice 4) Bob switches to WAIT_FOR_UPDATE_SIG state - Bob receives update_signature from Alice 5) Bob switches to NORMAL state Thanks, Pierre 2015-08-20 9:52 GMT+02:00 Rusty Russell : > Hi all, > > I've written a state machine for the wire protocol (though it > covers more than that). It's a bit of a monster, handling all the > commands as well as bitcoin event notifications. It's had some > simulation testing, but it's not wired up to anything yet. > > You can read it in all its glory in my "state" branch: > > https://github.com/ElementsProject/lightning/tree/state > > In particular, I've pasted state_types.h below. > > I'll do a proper RFC eventually, including all the transactions, but > here's a quick protocol summary: > > The basic protocol state alternates between high and low priority: this > resolves the conflict if they both try to do an update at once. They > respond to protocol violations with an error packet and unilateral > close. > > Simplified (high and low prio merged): > http://ozlabs.org/~rusty/diagrams/lightning/simplified-states.svg > Normal: > http://ozlabs.org/~rusty/diagrams/lightning/normal-states.svg > Everything (don't bother opening): > http://ozlabs.org/~rusty/diagrams/lightning/full-states.svg > > PKT_CLOSE is allowed at any time, though currently if you want to close > with outstanding HTLCs you need to do so unilaterally. > > The protocol should handle re-transmits (for which the response is to > retransmit any packet since that packet was received). This means if > you save state after every transition, you should be able to recover. > > Cheers, > Rusty. > > #define STATE_CLOSE_STEAL_BIT 1 > #define STATE_CLOSE_SPENDTHEM_BIT 2 > #define STATE_CLOSE_CLOSE_BIT 4 > #define STATE_CLOSE_OURCOMMIT_BIT 8 > #define STATE_CLOSE_SPENDOURS_BIT 16 > > enum state { > STATE_INIT_NOANCHOR, > STATE_INIT_WITHANCHOR, > > /* > * Opening. > */ > STATE_OPEN_WAIT_FOR_OPEN_NOANCHOR, > STATE_OPEN_WAIT_FOR_OPEN_WITHANCHOR, > STATE_OPEN_WAIT_FOR_ANCHOR, > STATE_OPEN_WAIT_FOR_COMMIT_SIG, > STATE_OPEN_WAITING_OURANCHOR, > STATE_OPEN_WAITING_THEIRANCHOR, > STATE_OPEN_WAIT_FOR_COMPLETE_OURANCHOR, > STATE_OPEN_WAIT_FOR_COMPLETE_THEIRANCHOR, > > /* > * Normal update loop. > * > * NOTE: High and low prios must alternate! > */ > STATE_NORMAL_LOWPRIO, > STATE_NORMAL_HIGHPRIO, > > STATE_WAIT_FOR_HTLC_ACCEPT_LOWPRIO, > STATE_WAIT_FOR_HTLC_ACCEPT_HIGHPRIO, > > STATE_WAIT_FOR_UPDATE_ACCEPT_LOWPRIO, > STATE_WAIT_FOR_UPDATE_ACCEPT_HIGHPRIO, > > STATE_WAIT_FOR_UPDATE_COMPLETE_LOWPRIO, > STATE_WAIT_FOR_UPDATE_COMPLETE_HIGHPRIO, > > STATE_WAIT_FOR_UPDATE_SIG_LOWPRIO, > STATE_WAIT_FOR_UPDATE_SIG_HIGHPRIO, > > /* > * Closing. > */ > /* We told them to close, waiting for complete msg. */ > STATE_WAIT_FOR_CLOSE_COMPLETE, > /* They told us to close, waiting for ack msg. */ > STATE_WAIT_FOR_CLOSE_ACK, > > /* > * They can broadcast one or more revoked commit tx, or their > latest > * commit tx at any time. We respond to revoked commit txs by > stealing > * their funds (steal). We respond to their latest commit tx by > * spending (spend_them). They can also (with our help) broadcast > * a mutual close tx (mutual_close). > * > * We can also broadcast one of the following: > * 1) Our latest commit tx (our_commit). > * 2) After delay has passed, spend of our tx (spend_ours). > * 3) Mutual close tx (mutual_close), already covered above. > * > * Thus, we could be waiting for the following combinations: > * - steal > * - spend_them > * - steal + spend_them > * - mutual_close > * - steal + mutual_close > * - spend_them + mutual_close > * - steal + spend_them + mutual_close > * > * - our_commit > * - steal + our_commit > * - spend_them + our_commit > * - steal + spend_them + our_commit > * - mutual_close + our_commit > * - steal + mutual_close + our_commit > * - spend_them + mutual_close + our_commit > * - steal + spend_them + mutual_close + our_commit > * > * - spend_ours > * - steal + spend_ours > * - spend_them + spend_ours > * - steal + spend_them + spend_ours > * - mutual_close + spend_ours > * - steal + mutual_close + spend_ours > * - spend_them + mutual_close + spend_ours > * - steal + spend_them + mutual_close + spend_ours > */ > STATE_CLOSE_WAIT_STEAL, > STATE_CLOSE_WAIT_SPENDTHEM, > STATE_CLOSE_WAIT_STEAL_SPENDTHEM, > STATE_CLOSE_WAIT_CLOSE, > STATE_CLOSE_WAIT_STEAL_CLOSE, > STATE_CLOSE_WAIT_SPENDTHEM_CLOSE, > STATE_CLOSE_WAIT_STEAL_SPENDTHEM_CLOSE, > > STATE_CLOSE_WAIT_OURCOMMIT, > STATE_CLOSE_WAIT_STEAL_OURCOMMIT, > STATE_CLOSE_WAIT_SPENDTHEM_OURCOMMIT, > STATE_CLOSE_WAIT_STEAL_SPENDTHEM_OURCOMMIT, > STATE_CLOSE_WAIT_CLOSE_OURCOMMIT, > STATE_CLOSE_WAIT_STEAL_CLOSE_OURCOMMIT, > STATE_CLOSE_WAIT_SPENDTHEM_CLOSE_OURCOMMIT, > STATE_CLOSE_WAIT_STEAL_SPENDTHEM_CLOSE_OURCOMMIT, > > STATE_CLOSE_WAIT_SPENDOURS, > STATE_CLOSE_WAIT_STEAL_SPENDOURS, > STATE_CLOSE_WAIT_SPENDTHEM_SPENDOURS, > STATE_CLOSE_WAIT_STEAL_SPENDTHEM_SPENDOURS, > STATE_CLOSE_WAIT_CLOSE_SPENDOURS, > STATE_CLOSE_WAIT_STEAL_CLOSE_SPENDOURS, > STATE_CLOSE_WAIT_SPENDTHEM_CLOSE_SPENDOURS, > STATE_CLOSE_WAIT_STEAL_SPENDTHEM_CLOSE_SPENDOURS, > > /* All closed. */ > STATE_CLOSED, > > /* > * Where angels fear to tread. > */ > /* Their anchor didn't reach blockchain in reasonable time. */ > STATE_ERR_ANCHOR_TIMEOUT, > /* Anchor was double-spent, after both considered it sufficient > depth. */ > STATE_ERR_ANCHOR_LOST, > /* A commitment tx we didn't recognise spent the anchor > (impossible) */ > STATE_ERR_INFORMATION_LEAK, > /* We ended up in an unexpected state. */ > STATE_ERR_INTERNAL, > > STATE_MAX > }; > > enum state_input { > /* Packet inputs. */ > PKT_OPEN = PKT__PKT_OPEN, > PKT_OPEN_ANCHOR = PKT__PKT_OPEN_ANCHOR, > PKT_OPEN_COMMIT_SIG = PKT__PKT_OPEN_COMMIT_SIG, > PKT_OPEN_COMPLETE = PKT__PKT_OPEN_COMPLETE, > PKT_UPDATE = PKT__PKT_UPDATE, > PKT_UPDATE_ADD_HTLC = PKT__PKT_UPDATE_ADD_HTLC, > PKT_UPDATE_ACCEPT = PKT__PKT_UPDATE_ACCEPT, > PKT_UPDATE_SIGNATURE = PKT__PKT_UPDATE_SIGNATURE, > PKT_UPDATE_COMPLETE = PKT__PKT_UPDATE_COMPLETE, > PKT_UPDATE_COMPLETE_HTLC = PKT__PKT_UPDATE_COMPLETE_HTLC, > PKT_UPDATE_TIMEDOUT_HTLC = PKT__PKT_UPDATE_TIMEDOUT_HTLC, > PKT_UPDATE_ROUTEFAIL_HTLC = PKT__PKT_UPDATE_ROUTEFAIL_HTLC, > PKT_UPDATE_DECLINE_HTLC = PKT__PKT_UPDATE_DECLINE_HTLC, > PKT_CLOSE = PKT__PKT_CLOSE, > PKT_CLOSE_COMPLETE = PKT__PKT_CLOSE_COMPLETE, > PKT_CLOSE_ACK = PKT__PKT_CLOSE_ACK, > PKT_ERROR = PKT__PKT_ERROR, > > /* Non-packet inputs. */ > INPUT_NONE, > > /* > * Bitcoin events > */ > /* It reached the required depth. */ > BITCOIN_ANCHOR_DEPTHOK, > /* It didn't reach the required depth in time. */ > BITCOIN_ANCHOR_TIMEOUT, > /* It reached the required depth, then was forked off. */ > BITCOIN_ANCHOR_UNSPENT, > /* Anchor was spent by our commit, and we can now spend it. */ > BITCOIN_ANCHOR_OURCOMMIT_DELAYPASSED, > /* Anchor was spent by their commit tx. */ > BITCOIN_ANCHOR_THEIRSPEND, > /* Anchor was spent by another commit tx (eg. expired). */ > BITCOIN_ANCHOR_OTHERSPEND, > > /* Our spend of their commit tx is completely buried. */ > BITCOIN_SPEND_THEIRS_DONE, > /* Our spend of our own tx is completely buried. */ > BITCOIN_SPEND_OURS_DONE, > /* Our spend of their revoked tx is completely buried. */ > BITCOIN_STEAL_DONE, > /* Bitcoin close transaction considered completely buried. */ > BITCOIN_CLOSE_DONE, > > /* > * Timeouts. > */ > INPUT_CLOSE_COMPLETE_TIMEOUT, > > /* Commands */ > CMD_SEND_UPDATE, > CMD_SEND_HTLC_UPDATE, > CMD_SEND_HTLC_COMPLETE, > CMD_SEND_HTLC_TIMEDOUT, > CMD_SEND_HTLC_ROUTEFAIL, > CMD_CLOSE, > > INPUT_MAX > }; > _______________________________________________ > Lightning-dev mailing list > Lightning-dev at lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev > -------------- next part -------------- An HTML attachment was scrubbed... URL: