PPST: extending SPST to arbitrary private computation

SPST gave us private value transfer with self-paying fees on a smart-contract chain. That’s the Solana analogue of Zcash’s Sapling — and exactly what every existing relayer-dependent privacy mixer (Tornado, RAILGUN, Light v1) does, just without the relayer.

But Tornado-style protocols are not the goal. The goal is Turing-complete private computation: a Solana program that runs on encrypted state and produces a proof of correct execution without leaking what the state was, what the inputs were, or what the program output. That’s PPST.

This is post 4 of 11 in the relayerless-privacy series. Reading post 3 first will help, but the construction here stands alone.

What “private program” means here

Definition (Private Program). A private program is an arithmetic circuit

over the BN254 scalar field, specified by an R1CS constraint system $(A, B, C)$ of size $N_C$. Each program is identified by

where $\mathsf{vk}_C$ is the Groth16 verification key. The program identifier is a public, deterministic commitment to the program’s logic.

Definition (Private State). A vector $\mathsf{state} \in \mathbb{F}_p^k$ committed as

State commitments are leaves in a state Merkle tree $\mathcal{T}_S$ of depth 32, root $\mathsf{rt}_S$. This is a separate tree from the SPST note-commitment tree.

Definition (State Transition). A triple $(\mathsf{state}_{\mathsf{pre}}, \mathsf{aux}, \mathsf{state}_{\mathsf{post}})$ where $\mathsf{aux}$ is private auxiliary input and

The transition consumes $\mathsf{cm}_{\mathsf{pre}}$ via nullification and produces $\mathsf{cm}_{\mathsf{post}}$ as a new tree leaf. The program logic $C$ is never revealed to the verifier — only $\mathsf{program\_id}$ is.

The PPST relation

The relation $\mathcal{R}_{\mathsf{PPST}}$ is the set of $(x, w)$ pairs:

Public instance $x = \bigl(\mathsf{rt}_{\mathsf{pre}}, \mathsf{rt}_{\mathsf{post}}, \mathsf{nf}_{\mathsf{state}}, \mathsf{cm}_{\mathsf{post}}, \mathsf{program\_id}, f\bigr)$.

Private witness $w = \bigl(\mathsf{state}_{\mathsf{pre}}, r_{\mathsf{pre}}, \mathsf{path}_{\mathsf{pre}}, sk_{\mathsf{state}}, \mathsf{aux}, \mathsf{state}_{\mathsf{post}}, r_{\mathsf{post}}, \mathsf{vk}_C\bigr)$.

Nine constraints, all enforced by the outer PPST circuit:

P5 is the heart of the construction. The user-defined program $C$ — written in Circom, Noir, Leo, or any high-level circuit DSL — is embedded as a sub-circuit inside the outer PPST relation. The R1CS for $C$ becomes constraints inside the R1CS for $\mathcal{R}_{\mathsf{PPST}}$.

How the program embedding works

The outer circuit sizes look like:

where $N_{\mathsf{overhead}} \approx 25{,}000$ R1CS constraints (Merkle paths, commitment hashes, PRF evaluations — see SPST §3.1.6) and $N_C$ is the program circuit size.

Complex programs need IVC. PPST extends naturally: decompose the computation into $T$ uniform steps each running $C_{\mathsf{step}}$, fold them with Nova or SuperNova, then wrap the final accumulator in a Groth16 decider proof. The on-chain verifier always sees a constant-size 128-byte proof regardless of $T$. Off-chain proving is $O(T \cdot |C_{\mathsf{step}}|)$ but the chain doesn’t care.

Theorem 3.6 — PPST soundness

Statement. If Groth16 is knowledge-sound and Poseidon is collision-resistant, no PPT adversary can cause the PPST verifier to accept a transaction corresponding to an invalid state transition (one where $C(\mathsf{state}_{\mathsf{pre}}, \mathsf{aux}) \neq \mathsf{state}_{\mathsf{post}}$) except with negligible probability.

Proof sketch. Suppose $\mathcal{A}$ produces a valid PPST transaction whose underlying transition is invalid. By Groth16 knowledge soundness, the extractor $\mathcal{E}$ recovers a witness $w^*$ satisfying constraints P1–P9 — including P5: $C(\mathsf{state}^*_{\mathsf{pre}}, \mathsf{aux}^*) = \mathsf{state}^*_{\mathsf{post}}$. Direct contradiction. ∎

Corollary (State Integrity). The state tree $\mathcal{T}_S$ maintains the invariant that every leaf is a commitment to a state that resulted from a valid execution of an authorized program starting from a previously valid state. By induction on accepted transactions, this invariant holds at all times.

Theorem 3.7 — PPST zero-knowledge

Statement. PPST reveals nothing about $\mathsf{state}_{\mathsf{pre}}$, $\mathsf{state}_{\mathsf{post}}$, $\mathsf{aux}$, or the internal logic of $C$ beyond the public outputs.

Proof sketch. Direct from perfect ZK of Groth16. The simulator $\mathcal{S}$ depends only on the public instance $x$, not on the witness. For any two valid witnesses $w_0, w_1$ consistent with the same $x$, the proof distributions are identical.

What does leak:

• program_id is intentionally public. It identifies which program executed so the verifier can pick the right verification key. Full function privacy (hiding the program identity) requires a universal circuit or a commitment-to-vk argument and is left as a future extension.
• The fact that some state transition occurred under that program.
• The fee $f$.

What does not leak:

• The specific state values.
• The auxiliary inputs.
• Which specific leaf in $\mathcal{T}_S$ was consumed.

Theorem 3.8 — PPST-SPST composability

This is the magic. PPST and SPST compose into a single atomic transaction: execute a private program AND transfer shielded value, in one ZK proof.

Construct the composite relation $\mathcal{R}_{\mathsf{PPST+SPST}} = \mathcal{R}_{\mathsf{PPST}} \wedge \mathcal{R}_{\mathsf{SPST}}$ with a linking constraint:

binding the PPST state nullifier to the SPST input nullifiers. Both sub-proofs reference the same link value as a public input.

Cross-constraint (Value Mediation): if the program outputs a transfer amount $\Delta v$, the SPST component enforces

That is — value flowing from the SPST shielded pool into the program’s state (or out of it) is reconciled inside the proof. An observer cannot tell whether the program consumed value, produced value, or merely transferred it.

Practical realisation. For a moderate program ($N_C \sim 50{,}000$):

Groth16 prover time on commodity hardware: 5–10 seconds. Single 128-byte proof on-chain. ~200,000 CU verification cost on Solana.

Comparison with Aleo and Aztec

The thing PPST gets that Aleo and Aztec don’t is deployment as a protocol layer on a high-performance Layer-1. Aleo and Aztec each require running their own consensus or sequencer. PPST runs as a Solana program on the same validators as Jupiter and Helium — inheriting Solana’s TPS, finality, and infrastructure.

What’s left

PPST plus SPST gives us private value + private computation. That’s two of the three privacy properties. The remaining gap is submitter anonymity: even with a perfect ZK proof, the wrapping Solana transaction is signed by an Ed25519 key whose public key is on-chain. Address graph analysis trivially links the “private” transaction to the submitter’s identity.

The next post is about closing that gap — without a relayer, without a mixing service, and without a separate L1.

Bibliography

• Bowe, S., Chiesa, A., Green, M., Miers, I., Mishra, P., Wu, H. (2020). ZEXE: Enabling Decentralized Private Computation. IEEE S&P 2020.
• Chiesa, A., Hu, Y., Maller, M., Mishra, P., Vesely, N., Ward, N. (2020). Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS. EUROCRYPT 2020. https://eprint.iacr.org/2019/1047
• Aztec Network. Client-side Proof Generation. https://aztec.network/blog/client-side-proof-generation
• Kothapalli, A., Setty, S., Tzialla, I. (2022). Nova: Recursive Zero-Knowledge Arguments from Folding Schemes. https://eprint.iacr.org/2021/370
• Noir Language Documentation. https://noir-lang.org/docs/

Previous: SPST: self-paying shielded transactions ← · Next: TAB: threshold-anonymous broadcast →