Attachments, padding and erasure coding

Photos and files are encrypted on the device, cut into fixed-size parts, padded so the server can't tell the exact size, and spread across storage nodes so they survive failures.

Two layers of encryption Built

Primitives: ChaCha20-Poly1305 (RFC 8439), HKDF-SHA256, SHA-256.
Inner layer: a random key per file. Forwarding a file reuses it, so it isn't re-encrypted.
Outer layer: a fresh secret per upload, which also derives the part ids and fetch capabilities. A forwarded file looks unrelated to the original on the storage nodes.
Nonces work like STREAM: they carry the part index and a last-part flag, so parts can't be reordered or truncated.
ChaCha20-Poly1305 doesn't commit to its key, so the root of the file's hash tree includes a key commitment, which rules out a file that decrypts to different content under different keys.

Fixed-size parts Built

Every part of a multi-part file is exactly 1 MiB. Small files use one of four sizes: 16 KiB, 64 KiB, 256 KiB or 1 MiB, and nodes refuse any other length. The largest file is 2,048 parts, about 2 GiB.

Padmé padding Built

A file's exact size can identify it. Pigeon rounds the number of parts m up with Padmé: with E = ⌊log₂ m⌋ and S = ⌊log₂ E⌋ + 1, the low E − S bits are rounded up. With the 16 KiB floor that gives 95 possible stored sizes, at most about 6.6 bits of size information, a worst-case overhead of 11.6% and a mean of about 2.5%. Downloaders fetch the padding parts too, so download size reveals no more than upload size.

A maximum-privacy layout with only three sizes (16, 256 or 2,048 parts) is supported by the format, but the switch to use it isn't built yet Planned. Cover uploads are Planned.

What isn't padded yet

Attachments are padded; ordinary message envelopes aren't. An envelope has a minimum size of 1,202 bytes, so short messages look alike, but a long message is visibly longer. Padding envelopes to fixed buckets is Planned. Some smaller items already are: device-linking messages (4, 16 or 64 KiB), exported history (rounded up to a power of two) and the trusted circle (to a multiple of eight).

Erasure coding Built

Multi-part files use systematic Reed-Solomon RS(9,6) over GF(2⁸) (polynomial 0x11D, Cauchy matrix): six data shards and three parity shards, any six of which are enough to rebuild the data. Parity is sealed under the outer key like the data. At most three shards sit in one failure domain, and a write needs eight of nine. Single-part files and the first part of each file keep three plain replicas instead. Erasure coding switches on only once there are at least nine media nodes.

The Reed-Solomon code is implemented in the core, without an external library, and checked against generated test vectors.

Attachments in the apps

Sending, fetching and forwarding files works from the command-line tool Built. On a loopback test, a 64 MiB file went up in 1.9 s and came down in 1.6 s. The desktop app shows that an attachment arrived but doesn't fetch or send files yet Planned. Media runs on no public server yet: until the abuse controls ship, it is limited to Pigeon-run nodes.

Removal Built

When a file must be removed, nodes receive a signed (Ed25519) list of part ids to delete. The order holds no content, and identifies neither the reporter nor the uploader.

Sources: ADR-0009 (media), ADR-0012 (media stage 2), docs/specs/media-ec-v2.md, docs/specs/media-pointer-v2.md, docs/specs/media-takedown-v1.md; crates/pigeon-core/src/media/. Padmé is from Nikitin et al., “Reducing Metadata Leakage from Encrypted Files and Communication with PURBs”, PoPETs 2019.

Related: media tokens.