Documentation for State Synchronization Protocol

[s5bug]

Proper documentation for State Synchronization Protocol other than a reference implementation would be much appreciated, and probably improve adaptation. Personally, it's hard to get a general flow of how to open a server running SSP or connect to a server via SSP from the C++.

[cddouma]

I agree that documentation of the protocol would be good and is typically seen as a requirement to build an alternative client. Getting putty to support mosh for example would likely require documentation of the protocol.

[bartgrantham]

I'd like to +1 this request, as well. mosh's state management is a good example of this kind of design, widely deployed with plenty of real-world testing and feedback, yet the use case is simple enough that the protocol documentation would be a great educational resource.

It would help the mosh community by supporting alternative clients, but many other projects would also benefit from the insights and lessons it would contain.

[keithw]

For design lessons and some documentation, you might find the extended version of the paper helpful (https://mosh.org/mosh-paper-draft.pdf) as well as the essay in ;login: (https://www.usenix.org/system/files/login/articles/winstein.pdf).

[bartgrantham]

That draft paper has some good stuff in it. Thank you for linking!

[cgull]

I'm not going to defend the documentation, but SSP is ultimately a fairly simple protocol: each message executes a transition from one state of the terminal (text presented on the screen, mostly) to another. The messages are basically streams of text/ANSI console commands to update the previous state to the new state. On top of that, there is a simple protocol for client and server to know which states have been seen by the other side, the message numbering is conceptually like the seq/ack values in TCP. There's lots of details about reliable keyboard streams and window resizes and bells and such, but once you understand that each message is a minimal repaint of the screen to a view at a later time, you're halfway through understanding the protocol.

[bartgrantham]

I've carefully read through the first two sections, enough to get a handle on SSP, I believe. I'm still digesting it, but if there's ever explicit documentation written for SSP, two questions that I think deserve more elaboration and the reasons as I understand them:

---

Why does the sender keep old states between the last acknowledged state and the current state? Isn't the diff between those two states enough to update the receiver?

Because the receiver may have only received one of the states in between those two points, and the acknowledgement of that intermediate state to the sender was lost. To update from this point will require a diff from that intermediate state, not the (older) last explicitly acknowledged state.

---

Why does the receiver keep old states?

So that it has a choice of older states to update from if packets are lost or reordered. Otherwise, a synchronization timeout would be required for the server to send a (large) diff from the last acknowledged state.

---

The part I'm still chewing on is the interaction between the 32-entry "state windows" between the sender and receiver, and what assertions need to be true to guarantee that there's at least one state in both of them to form a basis of an update. (or maybe there's a "full state update" instruction that I missed?)

Could anyone weigh in on why it is guaranteed that the sender and receiver will always have at least one state to build from? Is that the flip-side of the "throwaway" sequence number: to allow the sender to explicitly tell the receiver "this is the oldest source state I can diff, so don't delete it"?

[keithw]

I think you may be making it more complicated than it really is! Although honestly I did this long enough ago that my own understanding is a bit fuzzy at this point... Here's my best recollection.

The sender always sends diffs. There is no "full update" instruction. The diff has three important fields: the source, target, and throwaway number. The target of the diff is always the current sender-side state. The throwaway number of the diff is always the most recent state that has been explicitly acknowledged by the receiver. The source of the diff is allowed to be:

• The most recent state that was explicitly acknowledged by the receiver [this kind of diff will definitely be usable by the receiver because the source state was explicitly acknowledged and has not been thrown away], OR
• Any more-recent state that the sender thinks the receiver probably will have by the time the current diff arrives (e.g. the state that was the target of the last-transmitted diff).

The sender gets to make this choice based on what is most efficient and how likely it thinks the receiver actually has the more-recent state. (E.g. if the first kind of diff is only 5 bytes longer, it might as well send it that way so it knows it will be usable even if an earlier diff got lost. We call this a "prophylactic retransmission," or "p-retransmission.")

Upon receiving a diff, the receiver throws away anything older than the throwaway number and attempts to apply the diff. If it has the source state, and if the target state is newer than the receiver's current state, it succeeds and then acknowledges the new target state. Otherwise it fails to apply the diff and just acks its current state number.

So to answer your first question, "Why does the sender keep old states between the last acknowledged state and the current state?" the reason is efficiency. If the screen goes "a" (state no. 1) and then "ab" (state no. 2) and then "abc" (state no. 3), and the receiver has acknowledged state no. 1 and the sender has sent a diff from 1=>2 and then 2=>3 and then the screen goes to "abcd" (state no. 4), it would be more efficient for the sender to send a diff from 3=>4 (banking on the hope that its diffs from 2=>3 and 3=>4 will have arrived) than to have to send a diff from 1=>4. On the other hand, it's more robust for the sender to send a diff from 1=>4 since it knows it will be applicable -- the diff only depends on state that the sender knows is already at the receiver.

On the second question, the receiver only has to keep states that it has acknowledged and hasn't been told to throw away. The sender is entitled to use any such state as the source of a diff. (So that means the receiver might have to stop acknowledging new states if the sender never tells it to throw something away and it doesn't want to use up all its memory. This is sort of like a TCP window filling up -- the situation will resolve itself as soon as the sender gets one of the receiver's ACKs and then reflects it back as a throwaway number.)

Hope that clears it up but happy to answer more questions if you have them.

[keithw]

FWIW we used a similar approach for video in our subsequent Salsify work: https://snr.stanford.edu/salsify

[bartgrantham]

I think you may be making it more complicated than it really is!

It wouldn't be the first time I've done such a thing. :)

Seriously though, this writeup really did clear up a couple things I didn't quite cotton on to. The receiver sending an ack of its current state even in the case of a failed diff is a detail I missed. And the receiver's window filling up and dropping diffs makes more sense if it's also sending acks of an older state, giving it a chance to always say "try again with something I can use".

And the way you stated it above, "the source of the diff is allowed to be...the sender gets to make this choice based on...", really spells it out the algorithm.

https://snr.stanford.edu/salsify

Neat. Is this project current?

Tangent: have you ever heard of The Most Comprehensive Book on Multiplayer Game Development by "No Bugs" Hare? It's on kickstarter, a very large multi-volume project, the second volume just dropped. The first volume covers a lot of the same ground, as you might guess from the title, plus some ideas about compression protocol versioning.

Ok, back on-topic: thanks for the insight, I may try to code up a small project with a different but similarly simple model in order to really grok it.

Thanks again!

[kestasjk]

I don't suppose you've seen this Google originating algorithm for Differential Synchronization? https://www.youtube.com/watch?v=S2Hp_1jqpY8
Got quite familiar with this protocol and the philosophies at a glance seem similar.

It'd be good if you could do a talk or document along the same lines, explaining how SSP works by itself too

[manfred-kaiser]

Is it possible to provide some information about the packet structure?

I have created SSH-MITM, which is able to intercept ssh sessions and with the next release, it's also possible to decrypt MOSH sessions.

At the moment, it's possible to decrypt the messages, but I have some problems to find the structure of the message in the source code. According to your papers https://mosh.org/mosh-paper-draft.pdf and https://www.usenix.org/system/files/login/articles/winstein.pdf there are 2 different structures.

Following python script decrypts the message:

import base64
from cryptography.hazmat.primitives.ciphers.aead import AESOCB3

key = base64.b64decode("gy37yTEqclUSpFODXW2L+A" + "==")

nonce = bytes(bytearray.fromhex("000000008000000000000000"))
data = bytes(bytearray.fromhex("".join([
    '67', 'a3', 'a3', '8d', '18', '0b', '0c', '45', '44', '8b', 
    '6c', '8e', '85', '11', '60', '89', 'bf', '6e', '81', '40', 
    '50', 'ee', '80', '11', '31', 'b2', '1e', '68', 'ae', 'd8', 
    'aa', '29', '23', '41', '2f', '27', 'd5', '83', 'cb', 'ec', 
    '70', '8a', 'a2', '27', '81', '7a', '1b', '44', '97', 'e0', 
    'cb', '67', 'e7', '46', 'd8', '1f', '7f', '3f', '4a', '27', 
    '31', '04', 'c1', '06', 'a3', '8e', 'f3', '3a', 'eb', '2f', 
    'c5', '2f', 'ab', 'f8', '8e', 'aa', 'ea', 'f4', '9d', '81', 
    'ea', '4e', 'ed', 'a2', '09', 'a0', '03', '60', '60', '1e', 
    'a1', 'f5', '9f', 'ce', '94', '81', '69', 'af', 'dd', 'd8', 
    '4a', '75', '06', '47', '80', '13', 'df', '49', '66', '60', 
    'e6', 'aa', '1c', '17', '64', '3f', 'e1', 'ef', 'd1', '4d', 
    'd8', '4b', '54', '12', '6f', '47', '8f', '34', '31', 'd0', 
    '1f', '3f', '22', '54', 'cb', 'a7', 'de', '15', '91', 'b4', 
    '6d', '5d', '28', 'c8', '1c', 'a1', 'b5'
])))



aesocb = AESOCB3(key)
print(aesocb.decrypt(nonce, data, None))

I've got following data:

0000:    2b 90 2b 8e 00 00 00 00 00 00 00 01 80 00 78 9c e3 60 12    +.+...........x..`.
0013:    60 90 60 54 60 d4 60 30 3a cb c8 c5 2e c5 aa 71 86 d1 40    `.`T`.`0:......q..@
0026:    84 eb 20 a3 d0 3e 46 a5 dd 8c d2 d1 45 d2 d1 06 b9 d2 d1    .. ..>F.....E......
0039:    1e d2 d1 46 5e d2 d1 f6 46 a6 39 d2 d1 de 5c 54 c4 d2 d1    ...F^...F.9...\T...
004C:    86 d6 86 1e 60 a3 33 20 76 d9 1b 19 18 98 00 ad b1 37 34    ....`.3 v........74
005F:    30 30 86 d2 46 50 da 10 4a 1b 40 69 a8 3a 43 53 28 df 0c    00..FP..J.@i.:CS(..
0072:    4a 9b e6 58 b1 e9 1d 6d 50 35 17 04 00 d7 ff 31 8a          J..X...mP5.....1.

Is there some documentation available which describes this data?

[manfred-kaiser]

I found another issue ticket #778 about a wireshark dissector, which helped to get decoded fields from the payload.

While this helps me to understand the internal structure of ssp, this does not explain how to get user input or how to rebuild the output, which is printed to the terminal. So pleas share more information about the protocol.

[marcblanchet]

Have the authors (@keithw) of SSP ever considered submitting an IETF internet draft and getting it standardized? That would be very useful and possibly be used by other protocols. (I can help if people are not used to this process)

[cgull]

From my point of view, no.

SSP is not at all extensible, and it is strongly tied to the Mosh codebase. The general idea of a virtual text console is valuable but Mosh has lots of details.

It would be about like writing an RFC for SUPDUP.

Oh, wait...