[Lightning-dev] A state machine.

[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
};