BitcoinPIR
Contents 06 HarmonyPIR Relocation and the permutation

HarmonyPIR — relocation and the permutation

The previous page left a loose thread. The query into segment s revealed most of that segment to the server — every real DB index in it except the one at the target's slot, which got replaced by a random cell from outside. The target itself stays hidden behind the client's hint XOR, so a single request leaks nothing about what was asked for. The danger is reuse: if the client later needs to fetch another index whose original home is segment s, the protocol would have to use segment s again, and the two requests would look nearly identical — the same (T−1) real cells from segment s, just a different position swapped out for a different outside cell. Correlating the two lets the server reverse-engineer which position was "the replacement" each time, pinning down the permutation. So segment s has to retire after one use. But the DB indices it held still need to be reachable — they have to be re-homed into other segments.

Concretely: the real values in segment s (two in our running example; in general up to T) each move to a fresh random empty cell somewhere else in the hint row, one at a time. Segment s becomes all ⊥. The client updates its stored parities to match — each segment that received one of the moved values gets that entry XOR-ed into its parity. Once the bookkeeping is done, the hint table is back to the same shape it had before, only permuted differently and with fewer empty cells left over.

Before: query just happened on segment 0 3 6 ⊥ ⊥ 7 ⊥ 4 ⊥ ⊥ 5 0 ⊥ ⊥ 1 ⊥ 2 After: segment 0 is empty, values scattered into previously-⊥ cells ⊥ ⊥ ⊥ ⊥ 7 3 4 ⊥ 6 5 0 ⊥ ⊥ 1 ⊥ 2 Empty-cell budget Each query consumes T of the empty cells in the row. After ~M/2 queries they're all used up, and the offline phase has to run again against a fresh permutation.
After querying segment 0, its two real values scatter to random empty cells. Segment 0 is now all ⊥; two previously-empty cells elsewhere in the row now hold those values. Hint parities are updated accordingly.

The permutation backend

A design choice in HarmonyPIR is to use one random permutation of size 2N for the entire hint row, rather than separate per-partition shuffles. This lets the scheme plug in any off-the-shelf PRP large enough to cover the domain.

What BitcoinPIR actually wires in

The harmonypir crate keeps the permutation behind a Prp trait and ships two backends, each with a different trade. The BitcoinPIR SDK exposes the choice as a runtime flag, with FastPRP the production default.

  • HMR12. An AES-based card-shuffle PRP with a security reduction to AES; BitcoinPIR uses a tweaked variant (Algorithm 5 in the HarmonyPIR paper) that cuts AES calls by ~4× per evaluation via phase grouping. Pure AES, no extra dependencies, compiles cleanly to WASM. ~6 µs/op native, ~14 µs/op in a browser. Works at any database size. Based on Hoang, Morris & Rogaway, An Enciphering Scheme Based on a Card Shuffle (CRYPTO 2012) — hence the shorthand HMR12.
  • FastPRP (default). A small-domain PRP that builds a permutation cache (~60 ms at N ≈ 6M) and answers subsequent evaluations in O(√N log N); ideal for the server's one-off offline hint generation over many groups at once. Implements Stefanov & Shi, FastPRP: Fast Pseudo-Random Permutations for Small Domains (ePrint 2012/254).

Earlier versions of the SDK also shipped an ALF backend (Wang, Maximov & Johansson, Introducing the ALF family, ePrint 2025/2148). ALF was retired in May 2026 because its implementation panicked on domains smaller than 216, which the sibling-Merkle hint tables routinely hit. FastPRP is now the default; HMR12 remains as a pure-AES alternative.

The BitcoinPIR deployment runs HarmonyPIR per cuckoo-hash group: 75 INDEX groups plus 80 CHUNK groups in the current parameters, each with its own hint row and its own PRP instance, all under a single master client key. The group structure comes from the batch-code layer two sections from now — same pattern for every backend, so we'll cover it once there.