TAB: hiding the submitter with ring signatures and FROST

SPST hides what value moved. PPST hides what program ran. Neither hides who submitted the transaction. On any chain that requires a signature on the outer transaction (Solana, Ethereum, Aptos, Sui — all of them), the public key of the submitter is right there in the transaction header.

Without a relayer, the submitter must sign with their own key. The Ed25519 public key tells the chain exactly which private actor authorised the proof. ZK on the inside; perfect plaintext on the outside.

This is post 5 of 11 in the relayerless-privacy series. Here we close the submitter-identification gap with two complementary network-layer primitives.

The submitter identification problem, formally

Definition (Active Participant Set). $\mathcal{S} = \{(\mathsf{pk}_i, \mathsf{sk}_i)\}_{i=1}^N$ — the set of active F_RP participants at a given epoch. Each holds a Curve25519 keypair registered on chain.

Definition (Anonymity Set Reduction Attack). Adversary $\mathcal{A}$ with full read access to $\sigma$. Define:

Naive relayerless setting: $|\mathcal{A}_{\text{eff}}| = 1$. Ed25519 signatures are strongly unforgeable — there is exactly one $\mathsf{pk}_i$ that verifies. Conditional entropy:

Worst possible. Even though the contents of the transaction (the SPST/PPST proof) reveal nothing about which notes were spent, the submitter’s pubkey reveals exactly who authorised the spend. Off-chain metadata (IP, timing, prior-deposit history, exchange KYC) collapses any remaining anonymity.

Approach A — Fujisaki-Suzuki ring signature over Ed25519

Adapt the linkable ring signature framework of Fujisaki and Suzuki (2007) to the Ed25519 group. Let $\mathbb{G}$ be the prime-order Ed25519 subgroup with generator $G$ and order $\ell$. Two random oracles: $\mathsf{H}_p : \{0,1\}^* \to \mathbb{Z}_\ell$ and $\mathsf{H}_G : \{0,1\}^* \to \mathbb{G}$.

Sign with ring $R = \{\mathsf{pk}_1, \ldots, \mathsf{pk}_n\}$ at signer index $s$:

1. Key image. $I = \mathsf{sk}_s \cdot \mathsf{H}_G(\mathsf{pk}_s)$ — deterministic linkability tag, hides $s$.
2. Commitment. Sample $\alpha \xleftarrow{R} \mathbb{Z}_\ell$. Compute $L_s = \alpha G$, $R_s = \alpha \mathsf{H}_G(\mathsf{pk}_s)$.
3. Challenge propagation. For $i = s+1, s+2, \ldots, s-1 \pmod{n}$ sample $c_i, r_i \xleftarrow{R} \mathbb{Z}_\ell$ and compute $$L_i = r_i G + c_i \mathsf{pk}_i, \quad R_i = r_i \mathsf{H}_G(\mathsf{pk}_i) + c_i I, \quad c_{i+1} = \mathsf{H}_p(m, L_i, R_i).$$
4. Close. Set $c_{s+1} = \mathsf{H}_p(m, L_s, R_s)$, propagate to obtain $c_s$, compute $r_s = \alpha - c_s \mathsf{sk}_s \pmod{\ell}$.
5. Output. $\sigma_{\text{ring}} = (I, c_1, r_1, \ldots, r_n)$.

Verify. Recompute every $L_i, R_i, c_{i+1}$. Accept iff $c_{n+1} = c_1$.

Signature size. $I \in \mathbb{G}$ (32 B compressed) + $c_1 \in \mathbb{Z}_\ell$ (32 B) + $n$ scalars $r_i$ (32 B each) = $64 + 32n$ bytes.

Solana transaction-size constraint

With ~300 bytes reserved for transaction metadata + nullifiers + Groth16 proof + recent blockhash, ~930 bytes are available for the ring signature inside the 1,232-byte limit:

Under SIMD-0296 (4,096-byte transactions, approved late 2025), this jumps to $n_{\max} \approx 119$.

Verification cost: each ring member needs 2 scalar multiplications + 1 hash ≈ 5,300 CU. For $n = 27$, that’s $\sim 143{,}100$ CU on top of the ~150,000-200,000 CU for SPST verification. Total: ~340,000 CU — about 24% of the 1.4M CU budget.

Theorem 3.9 — Ring anonymity

Statement. In the random oracle model, for any ring $R$, any indices $i, j \in [n]$, and any PPT distinguisher $\mathcal{D}$:

Perfect (information-theoretic) anonymity in the ROM.

Proof sketch (two steps).

Step 1 — Key image indistinguishability. $I_s = \mathsf{sk}_s \cdot \mathsf{H}_G(\mathsf{pk}_s)$. Since $\mathsf{H}_G$ is a random oracle independent of $G$, $\mathsf{H}_G(\mathsf{pk}_s)$ is a uniform random group element. The product $\mathsf{sk}_s \cdot \mathsf{H}_G(\mathsf{pk}_s)$ is uniform over $\mathbb{G}$ from the adversary’s view (one-more discrete-log assumption).

Step 2 — Transcript simulation. For any $s$, the tuple $(c_1, r_1, \ldots, r_n)$ is uniform over $\mathbb{Z}_\ell^{2n}$ subject to the ring-closure constraint. The simulator $\mathsf{Sim}(m, R)$ that knows no secret key produces an identically distributed output by sampling all $(c_i, r_i)$ uniformly and programming the random oracle to close the ring. The marginal distributions are identical for every $s \in [n]$, so $\mathsf{Adv}_{\mathcal{D}}^{\text{anon}} = 0$. ∎

Corollary. Ring signature of size $n$ provides $\log_2(n)$ bits of submitter anonymity. For $n = 27$ that’s $\sim 4.75$ bits; for $n = 119$ (SIMD-0296) that’s $\sim 6.9$ bits. Real-world anonymity is bounded by side-channel leakage (timing, IP) but the on-chain view alone provides exactly $\log_2(n)$.

Approach B — FROST threshold Schnorr (TAB proper)

Ring signatures grow linearly with $n$. For high-throughput deployments where $n \gg 27$ is desired, we want a constant-size signature. Threshold Schnorr is the answer.

Setup. $n$ participants run a one-time Distributed Key Generation (Feldman VSS) producing:

• A group public key $\mathsf{pk}_{\text{group}} = \mathsf{sk}_{\text{group}} \cdot G$ (the group secret is never reconstructed).
• Individual shares $\mathsf{sk}_{\text{share},i}$ for each participant.
• A threshold $t \leq n$.

Sign (FROST round structure): Any subset $T \subseteq [n]$ with $|T| = t$ can co-produce a Schnorr signature on message $m$:

1. Commitment round. Each $i \in T$ samples nonces $d_i, e_i \xleftarrow{R} \mathbb{Z}_\ell$ and broadcasts $D_i = d_i G$, $E_i = e_i G$.
2. Signing round. Each $i$ computes $$\rho_i = \mathsf{H}(i, m, \{(D_j, E_j)\}_{j \in T}), \quad R = \sum_{j \in T} (D_j + \rho_j E_j),$$ $$c = \mathsf{H}(R, \mathsf{pk}_{\text{group}}, m), \quad \lambda_i = \prod_{j \in T \setminus \{i\}} \frac{j}{j - i} \pmod \ell,$$ $$z_i = d_i + \rho_i e_i + c \lambda_i \mathsf{sk}_{\text{share},i} \pmod \ell.$$
3. Combine. $\sigma_{\text{threshold}} = (R, z)$ with $z = \sum_{i \in T} z_i$.

Verify. Standard Schnorr verification against $\mathsf{pk}_{\text{group}}$:

Signature size. $(R, z)$ = 32 + 32 = 64 bytes. Independent of $n$ and $t$. Identical to a standard Ed25519 signature.

Theorem 3.10 — TAB privacy

Statement. For any two subsets $T, T' \subseteq [n]$ with $|T| = |T'| = t$, and any PPT $\mathcal{A}$ controlling up to $t-1$ participants, the threshold signature produced by $T$ is computationally indistinguishable from the one produced by $T'$.

Proof structure. Hybrid argument over the FROST protocol:

• Hybrid 0: real $T$. Adversary observes final $(R, z)$ + $t-1$ partial signatures from corrupted parties.
• Hybrid 1: replace $R$ with a uniform random $\mathbb{G}$ element. Honest participants’ nonces $d_j, e_j$ for $j \in T \setminus \mathcal{C}$ are uniform; sum is uniform. Distribution identical.
• Hybrid 2: replace $z$ with the deterministic value $z = R/G + c \cdot \mathsf{sk}_{\text{group}}$ (well-defined given $R, c, \mathsf{pk}_{\text{group}}$). Same distribution.
• Hybrid 3: real $T'$. Same argument.

Honest partial signatures are never revealed to $\mathcal{A}$ (they’re consumed in combination). The final $(R, z)$ depends only on the honest contribution to $R$ — uniform regardless of $T$. ∎

Anonymity: Unbounded. As long as $|T| \geq t$ and at least one honest participant in $T$ exists, the adversary cannot determine which subset signed. With $n$ in the thousands and $t$ in the hundreds, $|T|$ choices are combinatorial and indistinguishable.

Tradeoffs at a glance

Why both, not one or the other

The two approaches cover different deployment regimes:

• Bootstrapping / low coordination: ring signatures. No DKG required; any user can sign with any ring composed of $n$ on-chain pubkeys. Anonymity scales to the size of the ring you can pack into the transaction.
• Established network with stable participants: TAB / FROST. One-time DKG cost amortises across all transactions; signatures are minimum-size; anonymity is bounded by the group size, not the transaction size.

In practice, F_RP starts in the ring-signature regime and migrates to TAB once the network has enough committed participants for a meaningful DKG. The constructions are not mutually exclusive — the on-chain verifier can accept either type and the wrapping Solana transaction looks identical in size in the TAB case.

What’s still missing

Even with TAB, two leakage channels remain:

1. Network metadata. The TCP/QUIC packet that hits a Solana RPC node has a source IP. Without Tor, I2P, or Dandelion++, that IP links directly to the user. Post 6 addresses this with verifiable shuffles at the network layer.
2. Timing correlation. A user who shields and spends within the same minute is still linkable via temporal proximity, regardless of how many ring members they hide in. Mitigations are about user behaviour and client-side delay sampling.

Bibliography

• Fujisaki, E., Suzuki, K. (2007). Traceable Ring Signature. PKC 2007.
• Komlo, C., Goldberg, I. (2020). FROST: Flexible Round-Optimized Schnorr Threshold Signatures. SAC 2020. https://eprint.iacr.org/2020/852
• Feldman, P. (1987). A Practical Scheme for Non-Interactive Verifiable Secret Sharing. FOCS 1987.
• Goodell, B., Noether, S. (2020). Concise Linkable Ring Signatures and Forgery Against Adversarial Keys (CLSAG). https://eprint.iacr.org/2019/654
• Bernstein, D. J. et al. (2012). High-speed high-security signatures. Journal of Cryptographic Engineering.

Previous: PPST: private programmable state ← · Next: Bayer-Groth verifiable shuffles →