Bayer-Groth verifiable shuffles for network-layer privacy

Ring signatures and TAB hide the submitter on-chain. They don’t hide the packet: the TCP/QUIC frame that hits a Solana RPC node still has a source IP, a timing signature, and a propagation pattern. A passive adversary running a handful of nodes can do timing triangulation to identify which IP first broadcast a transaction, and that IP is enough to undo the cryptographic anonymity.

This is post 6 of 11 in the relayerless-privacy series. The construction here addresses the network layer with verifiable shuffles — a primitive that lets a third party shuffle and re-randomise a batch of encrypted transactions without learning the permutation, then prove they did so honestly.

What a verifiable shuffle is

A vector of ElGamal ciphertexts arrives at a “shuffler” — a party (or chain of parties) that:

1. Permutes the order of the ciphertexts.
2. Re-randomises each ciphertext (changes the encryption randomness without changing the plaintext).
3. Outputs a new vector that is provably a permutation-and-re-randomisation of the input.

Crucially, the shuffler’s permutation π is secret. The proof attests “this output is some valid shuffle of the input” without revealing which one.

Definition. Let vec(C) = (C_1, ..., C_n) be ElGamal ciphertexts encrypting messages M_i under a common public key pk_dec. A verifiable shuffle protocol produces:

where vec(C') is a re-randomised permutation of vec(C) and the proof π_shuffle allows public verification without revealing π.

For each i ∈ [n]:

with r'_i sampled fresh.

Bayer-Groth shuffle argument

The Bayer-Groth construction [BG12] gives an honest-verifier zero-knowledge argument with O(√n) proof size. The pieces:

1. Permutation matrix commitment

The shuffler commits to the permutation matrix M_π ∈ {0,1}^{n×n} using a Pedersen vector commitment:

where vec(a) encodes the permutation and H_1, ..., H_n are independent generators.

2. Multi-exponentiation argument

For a verifier challenge vec(x) = (x_1, ..., x_n), the shuffler proves:

This is a batched ElGamal homomorphism check that requires the shuffle to be a valid permutation with correct re-randomisation.

3. Permutation argument (Schwartz-Zippel)

The committed (a_1, ..., a_n) form a permutation of (1, ..., n) if and only if the polynomial identity

holds. The shuffler proves it by evaluating both sides at a random verifier-supplied x. Two degree-n polynomials that agree at a random point are identical with overwhelming probability.

Sublinear proof via recursive blocks

Bayer-Groth’s main contribution is the recursive block structure that pushes proof size to O(√n). Split the n elements into √n blocks of √n; commit to each block; recurse. Verifier cost remains O(n) multi-scalar multiplications for the main check, plus O(√n) pairings/exponentiations for the permutation argument.

Theorem 3.11 — shuffle privacy

Statement. Under the DDH assumption on the underlying group and the zero-knowledge property of the Bayer-Groth argument, for any two permutations π_0, π_1 ∈ S_n and any PPT adversary observing (vec(C), vec(C'), π_shuffle):

Proof sketch. Reduce permutation identification to DDH. The reduction B receives a DDH challenge (G, A = a·G, B = b·G, Z) and sets pk_dec = A. To simulate the shuffle:

• If Z = ab·G (real DDH tuple): B re-randomises position i using r'_i = b and the DDH structure correctly produces a valid shuffle under π_0.
• If Z is uniform random: the re-randomisation introduces a random group element, making the shuffled ciphertexts independent of any specific permutation.

B wins with 1/2 + ε/2 if D distinguishes shuffles with advantage ε. The proof itself is zero-knowledge by Bayer-Groth, leaking no additional information about π beyond what is already in (vec(C), vec(C')). ∎

Cascade shuffles

If k independent shufflers each shuffle in sequence, the adversary must corrupt all k to learn the overall permutation:

This is the standard mix-net argument — one honest shuffler is enough. A cascade of three shufflers means the adversary needs to compromise all three to deanonymise.

Integration with F_RP

The shuffle network sits between the user and the Solana RPC. Workflow:

1. User encrypts their SPST/PPST transaction under a shared public key pk_dec (held by a threshold-decrypter set).
2. User submits the ciphertext to a public mempool shared with other privacy-protocol users.
3. Shufflers (a chain of 2-5 independent operators) take the batch, shuffle, re-randomise, prove.
4. After the cascade, threshold-decrypter set decrypts the final shuffled ciphertexts.
5. Decrypted transactions are submitted to Solana validators directly.

The validators see no IP / timing correlation back to the originating user. The shufflers see ciphertexts but not plaintexts. The threshold decrypter sees plaintexts but not the originator-to-position mapping.

Tradeoffs vs. ring signatures + TAB

Shuffles and TAB compose. The recommended stack:

1. TAB (or ring sig) for on-chain submitter anonymity.
2. Shuffle cascade for network-layer source-IP anonymity.
3. Tor/I2P/Dandelion++ as belt-and-braces for IP-level anonymity even against in-mempool observers.

Practical anonymity bounds

For a TAB group of n_tab = 100 and a shuffle cascade of size n_shuffle = 50, with a network-leakage parameter μ ∈ [0, 1] capturing how much side-channel info bleeds through:

With μ = 0.3 (moderate leakage from timing patterns), this gives roughly 6.6 + 0.7·5.6 ≈ 10.5 bits of effective anonymity — about 1500 indistinguishable submitters. With μ = 0 (Tor + Dandelion++), 12.2 bits ≈ 4700 submitters.

Why this isn’t deployed yet

Shufflers are operational infrastructure. Each one is:

• A long-running Linux process holding a Bayer-Groth proof generator.
• Interactive with other shufflers and the threshold-decrypter set.
• Subject to liveness assumptions (one going offline pauses the cascade, but doesn’t break privacy).

For F_RP’s first deployment we ship without shufflers — TAB plus user-side Tor is enough for the initial threat model. The shuffle network is a Phase 2 hardening, designed to neutralise nation-state-level network observers.

Bibliography

• Bayer, S., Groth, J. (2012). Efficient Zero-Knowledge Argument for Correctness of a Shuffle. EUROCRYPT 2012.
• Chaum, D. (1981). Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms. CACM 24(2).
• Fanti, G. et al. (2018). Dandelion++: Lightweight Cryptocurrency Networking with Formal Anonymity Guarantees. SIGMETRICS 2018.
• Monero Project. Tor and I2P integration in monerod (master). https://github.com/monero-project/monero/blob/master/docs/ANONYMITY_NETWORKS.md

Previous: TAB: ring sigs and FROST ← · Next: UPEE: composing the framework →