How does a skip ratchet work?

You have a system, a list of messages $M$, a dynamic set of participants $P$, and you wish to encrypt each message you send to $P$
In the double ratchet setup used by Signal:
- Each message cranks the “ratchet”
- The “ratchet” is a cryptographic gadget used to derive a new key. It’s forward-facing, meaning you can’t derive the previous keys from current messages.

What is the hard problem?

How do you have an encrypted file system with a dynamic set of participants? ie. how do you ensure you can permissionlessly add people to this file system, without having to re-encrypt the data all of the time?
In Signal’s case:
- the signal server stores messages. they cannot read them.
- each participant encrypts their message with a message key, which is derived from the ratchet, a KDF chain (key derivation function chain).
- for each new participant, they input their public key, and the ratchet is cranked forward.
- a client wishing to get the latest message needs to recompute the chain, in $O(N)$ time.
In the “skip ratchet” use case:
- a client wishing to get the latest message needs to recompute the chain, in $O(log(N))$ time. (or O(1)).
- this is because they can “skip ahead” from any single message to the most recent state.
you can construct a file system out of an immutable list:

What is a skip ratchet?

A KDF chain protocol where:
- the time efficiency of deriving the current state is $O(log N)$ instead of $O(N)$

What is a KDF chain?

‹ Notes