Lazy negotiation is unsound

[Stebalien]

Setup:

• Peer A supports protocol protocolA.
• Peer B supports protocol protocolB.

Using the lazy handshake protocol, peer A can send:

<len>/multistream/1.0.0
<len>/protocolA/1.0.0

Then, as the first message (without waiting for a response), it can send:

<len>/protocolB/1.0.0
other data

Unfortunately, if peer B supports protocolB but not protocolA, it will respond with:

<len>/multistream/1.0.0
<len>na
<len>/protocolB/1.0.0

And then think it's speaking protocolB. It will then intrpret other data in the context of protocolB.

---

Unfortunately, there are perfectly valid uses for multistream where this can happen. For example, switching. Let's say that peer A wants to talk to a sub-identity C hosted on peer B. One might reasonably support this using the multistream muxer by registering peer IDs with the muxer (treating them as "services"). One could then end up with the following conversation:

<len>/multistream/1.0.0
<len>/p2p/peerC
<len>/multistream/1.0.0
<len>/protocol/1.0.0

If peer B doesn't have a peerC registered, it would respond as follows:

<len>/multistream/1.0.0
<len>na
<len>na
<len>/protocol/1.0.0

At this point, peer A will be talking the protocol with peer B instead of with the sub identity C.

---

Unfortunately, I don't know of a good fix that won't break everything (without upping the version and adding a mandatory round trip).

[Stebalien]

Note, lazy negotiation is absolutely necessary for performance. Having two round trips (no lazy select) would kill performance.

[Stebalien]

So, there is a sort-of OK solution.

1. For new transports, switch to a new protocol (without all the round-trips).
2. For old transports, use the non-lazy handshake.

---

Proposed Protocol

This is a variant on an addition to the multistream protocol that @whyrusleeping proposed earlier for stream reuse.

Assumptions:

1. Protocol names contain no whitespace.
2. There is an initiator (asymmetry). The side that is the initiator depends on the use-case and underlying transport but it must be consistent.

Messages

There are 5 messages in this protocol:

• select - select a protocol
• use - use a protocol
• stop - stop using a protocol (nak)
• recover - recover a stream for reuse
• resume - resume using a recovered stream

SELECT

The select message tells the other side to select one of a set of protocols. Example:

<len>select /protocol-a/1.0.0 /protocol-b/1.0.0\n

The select message should always be sent by the initiator and the initiator must wait for a response from the other side before continuing. The order in which the protocols are listed is the order of preference.

USE

The use message tells the other side that we've decided to use the given protocol. Example:

<len>use /protocol-a/1.0.0\n

The other side must send use /same/protocol before responding (or stop, see below).

We can immediately follow up with data without waiting for a response.

STOP

A stop message can be sent in response to a use to tell the other side that we don't support the given protocol.

Example:

<len>stop /protocol-a/1.0.0\n

(we send back the protocol name for completeness).

RECOVER

A recover message (with a random 256bit nonce) can be sent following a stop to allow the other side to resume using the underlying stream. Example:

<len>recover NONCE\n

After sending a recover, the sender should wait until it receives the appropriate resume message, throwing away any data sent before then. Implementations should also consider timing out after receiving some amount of garbage data or after some period of time.

RESUME

After receiving a recover message, the other side may send back a resume message along with the bit-inverted NONCE (XORed with a bit pattern TBD) to "resume" using the stream.

\n
\n
<len>resume TICKET ⊕ BIT_PATTERN \n

The probability of sending this message by accident is negligible. We XOR TICKET with a bit pattern to avoid accidentally sending it back (just to be paranoid).

USE-SELECT

(the 6th message...)

Example:

<len>use-select /protocol/a /protocol/b /protocol/c\n
...data...

So, we may want to consider a 6th use-select message. However, I'm not sure if it's really necessary. Basically, you'd send use-select protocol list... to use the first protocol but tell the other side that you support the others. If the other side doesn't support the specified protocol, it would send back a stop, then a recover, and then a use message (the response to the select message).

In theory, this is tempting. It can shave off a round-trip when recovering a stream. However, I'm not sure this will be that common of an issue. Thoughts?

[raulk]

@Stebalien the way that this is built in go, the API for optimistic selection only allows us select a single protocol at a time:

go-multistream/lazyClient.go

Line 18 in 8d87044

func NewMSSelect(c io.ReadWriteCloser, proto string) Multistream {

So if either /multistream/1.0.0 or the user protocol fail, the caller will receive an error. If the caller is well-behaved, it should abort any subsequent negotiations on the connection or stream.

I too thought this was an issue at the protocol level, but the multistream-select specification defines it as an interactive protocol.

go-libp2p leverages length-prefixing and TCP ordering in a hack to eagerly select two protocols in a row, but this is an implementation-level optimisation that the spec does not condone, yet it shouldn't cause interoperability issues.

[Stebalien]

go-libp2p leverages length-prefixing and TCP ordering in a hack to eagerly select two protocols in a row, but this is an implementation-level optimisation that the spec does not condone, yet it shouldn't cause interoperability issues.

Note: go-libp2p never actually negotiates two protocols in a row. The example in the original issue is just an example. This issue is about the theoretical unsoundness of lazy negotiation. Specifically specifying the protocol we want to speak and then speaking the protocol without waiting for a response.

Unrecorded history: This was supposed to be a feature in the spec.

[raulk]

go-libp2p never actually negotiates two protocols in a row.

I meant the /multistream/1.0.0 protocol, followed by protocol X. As seen by multistream-select, these are two distinct protocol proposals that we pipeline.

Unrecorded history: This was supposed to be a feature in the spec.

😆

[Stebalien]

I meant the /multistream/1.0.0 protocol, followed by protocol X. As seen by multistream-select, these are two distinct protocol proposals that we pipeline.

Sending /multistream/1.0.0 immediately followed by the first protocol isn't the part that's unsound, I added that a few months ago.

The issue here is sending:

/multistream/1.0.0
/foo/bar
<arbitrary data> <-- THIS

Where <arbitrary data> may end up looking like a valid multistream message. If /foo/bar succeeds, this will work fine. If /foo/bar doesn't succeed, <arbitrary data> will be treated like the next multistream protocol choice.