feat(pir_shielded_pool): PoC proposal, PIR for shielded pools (path retrieval & note discovery)

[Meyanis95]

Draft proposal for discussion. Posting as an issue to gather feedback before writing a full REQUIREMENTS.md / SPEC.md. Open questions are intentional.

Motivation

• Shielded pools (Railgun / Privacy Pools style) give on-chain privacy, but client interactions can leak the same secrets they protect:
  • Path retrieval: to spend a note, the client needs its Merkle inclusion path. Asking an RPC/indexer reveals which note is about to be spent.
  • Note discovery: detecting incoming notes naively requires trial-decrypting every note, or revealing identity to a discovery service.
• PIR (and adjacent primitives like OMR / FMD) plug these leaks. The design space is wide; latency and cost trade-offs aren't obvious until built.

Relation to iptf-map

• Strengthens pattern-shielding: the pattern's privacy rating is partial partly because metadata leaks at the indexer/relayer layer. This PoC closes that gap for the query path.
• Extends approach-private-payments: the approach already lists iptf-pocs/pocs/private-payment/shielded-pool as its reference; PIR-backed retrieval is a natural follow-on PoC and could be added as a sub-pattern under this approach.
• Composes with:
  • pattern-stealth-addresses and pattern-recipient-derived-receive-addresses: unlinkability constructions that the note-discovery angle either complements or partially replaces (tags-with-PIR vs. stealth scanning).
  • pattern-user-controlled-viewing-keys: recipient key material is what gates PIR-backed discovery queries.

What the PoC would demonstrate

• Client/server flow for Merkle-path retrieval via PIR against a shielded-pool state tree.
• (Stretch) Note-discovery flow on the same substrate.
• Benchmarks vs. naive retrieval: latency, server CPU, bandwidth, client compute.

Candidate building blocks (reuse, don't reimplement)

PIR is a heavy primitive on its own. The PoC should wrap and benchmark an existing library, not build a PIR scheme from scratch. Candidate stacks:

• SimplePIR / DoublePIR: reference impl at github.com/ahenzinger/simplepir (Go, MIT, ~1.2k LoC). Single-server, lattice-based, cheap client, heavy server.
• FrodoPIR: paper eprint.iacr.org/2022/981; C++ port at github.com/itzmeanjan/frodoPIR. Essentially SimplePIR with different lattice params; small dependency surface.
• Spiral (Menon–Wu 2022): alternative single-server scheme; check authors' repo if benchmarked.
• Oblivious Message Retrieval (OMR): Liu–Tromer 2022, useful specifically for the discovery angle. Check the authors' reference repo.
• FMD (Fuzzy Message Detection, Penumbra): weaker but cheap discovery baseline; useful as a comparison point.
• Sharded PIR design for the Ethereum state (ethresear.ch/t/sharded-pir-design-for-the-ethereum-state/24552): community proposal that sharded PIR can scale to Ethereum-state-sized databases. Directly relevant if our shielded-pool tree is large or grows on L1 timescales; informs how to partition the state for tractable server-side PIR cost.

Open questions

• Target substrate: extend the existing pocs/private-payment/shielded-pool (Noir/UltraHonk) PoC, hook into Aztec's tag-based discovery layer, or stand up a minimal toy tree?
• One PoC covering retrieval + discovery, or split into two (multi-approach pattern à la CLAUDE.md)?
• Trust model for the PIR server(s): same entity as RPC, separate indexer, or decentralized?
• Is end-to-end latency for single-server PIR realistic for a UX demo, or do we only benchmark in isolation?
• Do we explicitly position this as a step toward, or inspired by, Tachyon's design, or stay scheme-agnostic?

Prior art

• Project Tachyon (Zcash): tachyon.z.cash, new post-quantum shielded pool that bakes in PIR; closest existing initiative to what this PoC would demonstrate. Aztec is collaborating with the Tachyon team on a PIR-based note-discovery design.
• Aztec note discovery: docs.aztec.network/.../note_discovery, plus the Aztec Note Discovery Summary HackMD. The current tag-based scheme has the exact IP/correlation leak this PoC targets.
• SimplePIR / DoublePIR (Henzinger et al., USENIX Security 2023).
• FrodoPIR (PoPETs 2023).
• OMR (Liu–Tromer 2022).
• Penumbra FMD design.
• Sharded PIR design for the Ethereum state (ethresear.ch).

[Meyanis95]

Update

Resources to add to the references

• Brechy / PSE write-up on Ethereum Privacy with PIR — benchmarks Respire against LeanIMTs on r7i.8xlarge, surfaces the dynamic-state and trust open questions directly.
• [brech1/tree-pir](https://github.com/brech1/tree-pir) — the benchmarking codebase behind the PSE post.
• [AMACB/respire](https://github.com/AMACB/respire) — Rust impl of Respire (Burton-Menon-Wu, CCS 2024).
• eprint 2025/2031 — useful for TPS framing.

Resolved

• Target substrate: we compose with our existing private-payment shielded-pool PoC. No respec.
• Scope: retrieval + discovery layer only. PIR sits on top of the existing pool.
• Latency: not optimised. PSE benchmarks set the regime we demo against (seconds at $2^{21}$, minutes at $2^{25}$).
• Epoch-based vs classic nullifiers: orthogonal. PIR sits on the receiver-side retrieval path, doesn't touch the spend path. Only coupling is snapshot cadence = worst-case nullifier-conflict latency window.

Still open

• Trust: PIR result can't be trusted on its own; couple with a light client to verify integrity against the L1 state root. PIR is used to fetch Merkle path siblings (not leaves) without revealing path indices to the indexer; light client + on-chain pool_root provides the verification anchor.
• Network privacy: out of scope for the PoC, but call out in the writeup as a residual assumption (timing correlation between sync traffic and PIR queries needs Tor/mixnet to be fully addressed).
• PIR scheme choice: Respire by default (256-byte records, batch queries, no client hint). Open to Plinko/RMS24 if updatability against a growing pool justifies it. (sent a message to Keewoo to get his stance)

Credits: Respire authors, Keewoo Lee (rms24-plinko-spec), PSE / Brechy, broader Zcash OMR / note-discovery lineage.

[Meyanis95]

Rough notes

design	server work	recipient bandwidth	privacy	who uses it
trial-decrypt all	none	O(N) ciphertexts	perfect	Zcash sapling (pre-UA)
FMD Mode 1 (local scan)	none	O(N) flags + O(real)	perfect	view-tag wallets
FMD Mode 2 (delegated, tunable p)	O(N) cheap flag ops	O(pN) ciphertexts	quantifiable leak	Penumbra
OMR	O(N) FHE ops	O(real) ciphertexts	perfect	research
keyword PIR	O(N) per query	O(real)	tag-fingerprint problem	not viable for receive
PIR (spend-side)	O(N) per query	O(real)	perfect	Zcash, Penumbra, Aztec

• PIR for spend-side data retrieval (paths, anchors, contract state). The RPC node learns nothing about which note you're spending.
• FMD for receive-side scanning with a tunable scanner-trust knob (what Penumbra ships). The knob is "how much the scanner learns" vs "how much you download": high precision = scanner learns ~your exact incoming set, you save bandwidth; low precision = scanner sees a big fuzzy set, you eat the cover traffic. Your full viewing key never moves either way.
• OMR is the ideal for receive-side with no leak, but server cost (per-tx FHE eval) is currently impractical at chain scale. Tooling is research-grade.
• Trial-decrypt is the always-correct fallback when devices and bandwidth allow it.
• Keyword PIR doesn't apply to payment scanning because of the tag-derivation dilemma: deterministic tags fingerprint the recipient in the server's table, per-tx randomized tags can't be enumerated by the recipient without O(N) work. OMR resolves this by evaluating the tag-match predicate homomorphically.

FMD Mode 1 (local scan):

• Recipient downloads every flag and runs the filter check locally with their detection key
• No third party, O(N) flag bandwidth, perfect privacy

FMD Mode 2 (delegated scan):

• Recipient hands a filtering key (tuned by FPR p) to an untrusted scanner; scanner returns ~p·N flagged txs (real + cover) for the recipient to trial-decrypt
• Quantifiable leak tunable via p; detection secret key never leaves the device

Penumbra's choice

Penumbra ships FMD Mode 2 with a user-tunable precision parameter (the p from the FMD paper). Each user has a clue key parameterized by precision; they hand it to an untrusted scanner ("view service") which returns ~pN flagged txs. The full viewing key never leaves the device.

The privacy ↔ bandwidth knob is exposed to users: paranoid users pick low precision (heavy cover traffic), mobile users on metered data pick high precision (near-exact subset, scanner learns more).

They didn't pick OMR because OMR's per-tx FHE eval is seconds of server CPU vs FMD's microseconds, three orders of magnitude difference at chain scale.

Privacy primitives (receive side)

• Fuzzy Message Detection - Beck, Len, Miers, Green
• Oblivious Message Retrieval - Liu, Tromer
• PerfOMR - Liu, Tromer, Wang
• Penumbra protocol docs on FMD
• Penumbra Sender/Receiver FMD generalization
• decaf377-fmd Rust crate docs

Privacy primitives (PIR)

• PQ OMR by Nam
• insPIRe paper
• insPIRe implementation in Rust

[rymnc]

@Meyanis95 can we close this?

[Meyanis95]

Closing, resolved with #74