UPEE: composing SPST + PPST + TAB into one framework

F_RP Construction IV. The five-algorithm tuple Setup/Deploy/Invoke/Verify/Finalize plus the simulation-based privacy theorem (3.12) and self-sovereignty theorem (3.13). The composition that makes the whole thing deployable.

SPST gave us self-paying private value transfer. PPST extended it to arbitrary computation. TAB and verifiable shuffles closed the submitter-identification gap. Each of those is a self-contained construction. This post is about how they compose into the deployable framework.

UPEE — the Universal Private Execution Environment — is a five-tuple (Setup, Deploy, Invoke, Verify, Finalize) that wraps the lower-level pieces in a single deployable interface. By the end of this post we’ll have stated the two main theorems of F_RP — simulation-based privacy and self-sovereignty — and shown how they fall out of the composition.

This is post 7 of 11 in the relayerless-privacy series.

The five algorithms

Setup(1^λ) → pp. Generate public parameters: SRS for the proof system (universal KZG or transparent FRI), Poseidon parameters, Merkle tree depth d = 32, Pedersen generators G, H, range-proof bit-length ℓ_v = 64, field 𝔽_p.

Deploy(C, pp) → vk_C. Compile a private program circuit C to an R1CS (or PLONKish) constraint system, run the proof system’s key generator to produce (pk_C, vk_C), register vk_C on-chain at a deterministic PDA addr_C = PDA("UPEE", H(vk_C)).

Invoke(C, state_priv, input_priv, pp) → (tx, π). Client-side, no chain interaction. Read current Merkle root, execute C locally on private state, build the witness, generate the Groth16 proof, assemble the transaction with encrypted note ciphertexts.

Verify(vk_C, tx, π) → {0, 1}. On-chain. Single Groth16 pairing check + nullifier-set check + recent-root check + minimum-fee check.

Finalize(σ, tx) → σ'. State transition. Insert nullifiers, append commitments to the Merkle tree, credit the validator with f.

Hybrid proof architecture (§3.4.2)

A single Groth16 proof can’t directly hold a Turing-complete program at scale. Big circuits → big provers. The fix is recursive composition:

The outer Groth16 proof’s circuit verifies the inner STARK or Nova accumulator. Composed soundness:

\epsilon_{\mathrm{hybrid}} \;\leq\; \epsilon_{\mathrm{inner}} + \epsilon_{\mathrm{outer}} + \mathsf{negl}(\lambda).

Concretely: STARK with FRI gives ε_inner ≤ 2^{-100} for the standard 30-query / blowup-4 parameters; Groth16 gives ε_outer ≤ 2^{-100} under q-PKE on BN254. Combined ε_hybrid ≤ 2^{-100} — no meaningful soundness loss.

Zero-knowledge composes too: outer Groth16 reveals nothing about the inner STARK; the inner STARK reveals nothing about the witness. Both layers contribute ZK and they don’t fight.

The ideal functionality `F_RP`

For the simulation-based proof we need a target. The ideal functionality:

On (invoke, sid, C, state_priv, input_priv) from user U:
1. Execute C locally, validate balance / range / membership.
2. Compute fee f.
3. Send (transaction, sid, f) to the adversary A. That’s all A learns.
4. On proceed from A, update ideal state, ack to U.
On (query, sid) from A: return (rt, N, f) (the public state).

F_RP never tells A:

which notes were consumed (only nullifiers);
which notes were created (only commitments);
the values, recipients, or program inputs;
the user’s identity beyond what the fee f and the fact-of-existence reveal.

This is the only thing the adversary should be able to learn in the real world either.

Theorem 3.12 — simulation-based privacy

Statement. For any PPT adversary A controlling the blockchain (full read of on-chain data, validator-side scheduling, transaction ordering), there exists a PPT simulator S such that:

\bigl\{\,\mathsf{View}_{\mathcal{A}}(\mathsf{Real}(\mathcal{A}, \mathcal{F}_{\mathrm{RP}}))\,\bigr\} \;\approx_c\; \bigl\{\,\mathsf{View}_{\mathcal{A}}(\mathsf{Ideal}(\mathcal{A}, \mathcal{S}))\,\bigr\}

where S learns only (sid, f) from F_RP.

Proof outline.

The simulator builds a fake transaction that is computationally indistinguishable from a real one without ever seeing the witness:

Simulated nullifiers. For each of n_in inputs, sample nf_i uniformly at random, verify it isn’t already in N, retry on collision.
Simulated commitments. For each of n_out outputs, sample r_j uniformly and set cm_j = Poseidon(r_j). Indistinguishable from real commitments by the hiding property of Poseidon.
Simulated proof. Invoke the ZK simulator of the hybrid proof system: π̃ ← Sim_ZK(vk_C, x̃) for x̃ = ({nf_i}, {cm_j}, rt, f). For Groth16, Sim_ZK uses the simulation trapdoor (α, β, γ, δ) from the CRS to forge a valid-looking proof without a witness.
Simulated encrypted notes. For each output, sample a uniform-random ciphertext of the right length. Indistinguishable by CCA2 of the encryption scheme.

The hybrid argument moves from the real distribution to the simulator’s output through four hybrids, each indistinguishable from the previous one under one cryptographic assumption:

H_0 → H_1: replace real proof with simulated proof. Bound: ZK advantage of Π_hybrid.
H_1 → H_2: replace real commitments with random Poseidon(r̃_j). Bound: n_out · PRF advantage of Poseidon.
H_2 → H_3: replace real nullifiers with uniform random values. Bound: n_in · PRF advantage.
H_3 → H_4 = Sim: replace real ciphertexts with random strings. Bound: n_out · CCA2 advantage of the encryption scheme.

By the triangle inequality, the total distinguishing advantage is the sum of four negligible quantities — itself negligible. ∎

Theorem 3.13 — self-sovereignty

This is the result that makes F_RP relayerless.

Game Game_RF(A, λ). Single honest user U. A controls all relayers, all other users, the entire network layer (delay/reorder/drop), and all off-chain infrastructure. U has a shielded note, the corresponding spending key, the ability to read the chain, and direct network access to at least one honest validator. Game_RF = 1 if U successfully completes withdrawal of v' ≤ v to a public address of their choosing, paying f from the shielded balance, in a polynomial number of steps.

Statement.

\Pr[\mathsf{Game}_{\mathrm{RF}}(\mathcal{A}, \lambda) = 1] \;=\; 1 - \mathsf{negl}(\lambda).

Proof. Walk through every phase of the withdrawal and confirm the user can do it alone:

Operation	Required resources	External party?
Read Merkle root	RPC (or direct ledger read)	No — public data
Compute Merkle path	Local tree + on-chain commitment data	No
Compute nullifier `PRF_sk(ρ)`	Local secret key	No
Build witness	Local	No
Generate Groth16 proof	Local CPU/GPU	No
Sign tx	Local Ed25519 key (or TAB share)	No
Broadcast tx	Direct connection to ≥1 honest validator	No (chain liveness)
Pay fee `f`	Inside the proof — extracted from shielded balance	No (SPST)

Every row’s “External party?” is “No”. The single assumption is (Δ, p_live)-liveness of the chain: any valid transaction is included within Δ blocks with probability ≥ 1 − negl(λ). On Solana, Δ ≈ 1-2 slots (sub-second finality) and p_live is bounded by Tower BFT’s safety guarantees.

The success probability is:

\Pr[\mathsf{Game}_{\mathrm{RF}} = 1] \;=\; \Pr[\text{liveness holds}] \cdot \Pr[\text{honest proof verifies}] \;=\; (1 - \mathsf{negl}(\lambda)) \cdot 1.

The second factor is 1 by completeness of the proof system. ∎

Corollary (Censorship Resistance). No adversary can prevent the user from exercising their private withdrawal right, assuming only chain liveness. This is strictly stronger than every relayer-dependent protocol, where adversarial control of the relayer set is sufficient to deny service.

Composability of UPEE programs

Three composition modes from §3.4.5:

Sequential composition `P_A ; P_B`

Run P_A to commit intermediate state, wait for finality, then run P_B consuming that state. Soundness composes additively:

\epsilon_{\mathrm{seq}} \;\leq\; \epsilon_A + \epsilon_B + \mathsf{negl}(\lambda).

Parallel composition `P_A ‖ P_B`

Both programs run in the same transaction over disjoint state. Combined circuit C_{A‖B} satisfies iff both C_A and C_B do. Soundness:

\epsilon_{A \| B} \;\leq\; \epsilon_A + \epsilon_B + \mathsf{negl}(\lambda).

Nested composition `P_A[P_B]`

P_A calls P_B as a subroutine. State passes through Pedersen-committed values:

\mathsf{call}(P_B, \mathsf{Com}(\vec{\mathrm{args}}), \pi_{\mathrm{args\_valid}}) \;\to\; (\mathsf{Com}(\vec{\mathrm{result}}), \pi_{\mathrm{exec}}).

The caller verifies π_exec recursively inside its own circuit. Soundness includes a recursion-overhead term:

\epsilon_{\mathrm{nested}} \;\leq\; \epsilon_A + \epsilon_B + \epsilon_{\mathrm{recursive}} + \mathsf{negl}(\lambda).

ε_recursive is bounded by Theorem 3.8 (composed soundness of the hybrid proof architecture).

Summary of security properties

Aspect	Pros	Cons
Simulation-based privacy	Theorem 3.12 — adversary learns only (fact of tx, fee).	Requires ZK of Π_hybrid + Poseidon PRF + nullifier PRF + CCA2 encryption.
Self-sovereignty	Theorem 3.13 — works against any adversary controlling all but the user.	Requires only chain liveness.
Sequential composability	Theorem 3.14 — multi-step private workflows.	Requires intermediate finality.
Parallel composability	Theorem 3.15 — atomic two-program transactions.	Requires disjoint state.
Nested composability	Theorem 3.16 — private function calls between programs.	Requires recursive proof verification (cost ~30K constraints).
Composed soundness	Theorem 3.8 — hybrid proof architecture.	Loose by epsilon_inner + epsilon_outer.
Ring anonymity	Theorem 3.9 — perfect (ROM).	Linear in ring size.
TAB privacy	Theorem 3.10 — perfect under DDH on Ed25519.	Constant-size sig but DKG cost.
Shuffle privacy	Theorem 3.11 — DDH + ZK of Bayer-Groth.	Off-chain coordination.

What’s left

We have the framework. We have the theorems. The question now is: does this actually fit on Solana? The next post drops the abstract Π_hybrid and gives concrete numbers — proof sizes in bytes, verification costs in CU, transaction layouts inside the 1,232-byte limit.

Bibliography

Canetti, R. (2001). Universally Composable Security: A New Paradigm for Cryptographic Protocols. FOCS 2001.
Goldwasser, S., Micali, S., Rackoff, C. (1985). The Knowledge Complexity of Interactive Proof-Systems. STOC 1985.
Groth, J. (2016). On the Size of Pairing-Based Non-Interactive Arguments. EUROCRYPT 2016.
Ben-Sasson, E. et al. (2018). Scalable, transparent, and post-quantum secure computational integrity (STARKs). https://eprint.iacr.org/2018/046
Kothapalli, A., Setty, S., Tzialla, I. (2022). Nova: Recursive Zero-Knowledge Arguments from Folding Schemes. https://eprint.iacr.org/2021/370

Previous: Verifiable shuffles ← · Next: Solana instantiation: 656 bytes →