Fountain codes in censorship circumvention rendezvous
Eleanor Cawthon, David Fifield
https://www.bamsoftware.com/papers/fountain-code-rendezvous/
PDF
This paper is an exploration of the potential of using fountain codes for the initial rendezvous/bootstrapping step of a censorship circumvention protocol. Fountain codes can help when the underlying carrier protocol has limited capacity, such that a rendezvous message must be broken up and sent in multiple pieces. They also cope gracefully with carrier protocols that may drop pieces or get them out of order (e.g., UDP-based protocols). The paper is an elaboration of an idea that originally appeared at Idea: rateless erasure codes for rendezvous over small fragments (e.g. DNS) · Issue #591 · net4people/bbs · GitHub. The idea of using fountain codes comes from the Assemblage paper, which is summarized at Assemblage: Chipping Away at Censorship with Generative Steganography (FOCI 2026).
Fountain are kind of a magic technology. Starting from a relatively large message (let’s say 500 bytes), you can generate an effectively infinite stream of small (let’s say 100 bytes), numbered “encoding symbols”. The receiver can decode the original message after receiving any subset of encoding symbols, in any order, whose combined length is at least the size of the message. In this case, with a 500-byte message and 100-byte encoding symbols, the receiver just needs any 5. It doesn’t matter whether it’s the symbols numbered (0, 1, 2, 3, 4); or (3, 4, 1, 2, 0); or (0, 1, 3, 4, 9); or (13, 108, 64, 18, 150): any combination of 5 will work. The really nice consequence of this fact is that the receiver does not need a back channel to tell the sender which symbols it has received and which it has not. The sender just keeps generating fresh encoding symbols and sending them until the receiver has received sufficiently many of them.
That’s the advantage, as the authors see it, of fountain codes for rendezvous, compared to alternative approaches. The problem of rendezvous over lossy or limited-capacity protocols might also be solved by TCP-like sequence numbers, acknowledgements, and retransmissions, but that approach is harder to manage and has more communication overhead. The authors hope that the flexibility and ease of use of fountain codes will make it possible to use new protocols for rendezvous that would have been too difficult to use before.
A large part of the paper consists of a fairly worked-out design for doing rendezvous over encrypted DNS (e.g. DoH, DoT, DoQ). A DNS query can reasonably encode only about 140 bytes of data; but they want to support Snowflake rendezvous, whose messages are about 400 bytes in size. The main idea is to represent a set of encoding symbols as a domain name, then send a query for that name through an encrypted recursive name server. The recursive name server forwards the query to the message receiver, which extracts the encoding symbols and decodes them. Assuming no packet loss, 3 queries are enough to send a complete rendezvous message. Snowflake’s rendezvous also needs a downstream response message, which is handled by representing encoding symbols as TXT responses. The representation of data is similar to dnstt’s, but crafted to store fountain code encoding symbols rather than transport-layer packets.