SPST: a self-paying shielded transaction model

In the previous post I argued that on account-model chains the fee paradox is what forces relayer dependence. The cleanest resolution — Approach A — extracts the transaction fee from inside the ZK proof itself. This post specifies that resolution.

The construction is called SPST (Self-Paying Shielded Transactions). It is the foundation that PPST, TAB, and UPEE build on. It also stands alone as a complete protocol for private value transfer with self-paying fees — the Solana analogue to Zcash’s Sapling spend description, but adapted to a smart-contract environment.

The setting

Work over a prime-order elliptic curve group $\mathbb{G}$ of order $p$ with two independent generators $g, h \in \mathbb{G}$ for which no party knows $\log_g h$. Let $\mathbb{F}_p$ denote the scalar field. We use:

• Poseidon as the SNARK-friendly hash (width $t = 5$, HADES rounds $R_F = 8$ full + $R_P = 57$ partial, S-box $x^5$, ~324 R1CS constraints per 2-to-1 compression).
• PRF keyed by $sk \in \mathbb{F}_p$, instantiated as a domain-separated Poseidon evaluation.
• Groth16 over BN254 as the on-chain verifier (alt_bn128 syscalls on Solana).
• Indexed Merkle Trees for nullifier non-membership (depth-32 over 254-bit values; ~10,948 R1CS constraints per non-membership proof, vs 82,296 for naive sparse Merkle).

Definitions

Definition 3.1 (Shielded Note). A shielded note is a tuple

where $\mathsf{pk} = \mathsf{PRF}_{sk}(0)$ is the owner’s public spending key, $v \in \{0, \ldots, 2^{64}-1\}$ is the note value, $\rho \in \mathbb{F}_p$ is unique per-note serial randomness, and $r \in \mathbb{F}_p$ is the commitment trapdoor.

Definition 3.2 (Note Commitment).

Note commitments are appended as leaves to a global Merkle tree $\mathcal{T}$ of depth $d = 32$ (capacity $2^{32}$ notes). The Merkle root at any epoch is $\mathsf{rt}$.

Definition 3.3 (Nullifier).

Upon spending, $\mathsf{nf}$ is published to a global nullifier set $\mathcal{N}$. Double-spending is prevented by rejecting any transaction whose $\mathsf{nf}$ already lives in $\mathcal{N}$.

Definition 3.4 (SPST Transaction). With $n$ inputs and $m$ outputs:

where $f \in \{0, \ldots, 2^{64}-1\}$ is the public fee and $\pi$ is a Groth16 proof of the SPST relation.

The validator accepts iff (i) $\pi$ verifies, (ii) $\mathsf{rt}$ is a recent root, (iii) every $\mathsf{nf}_i \notin \mathcal{N}$, and (iv) $f \geq f_{\min}$.

The SPST relation

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

Public instance $x = \bigl(\{\mathsf{nf}_i\}, \{\mathsf{cm}_j\}, \mathsf{rt}, f\bigr)$.

Private witness $w = \bigl(\{(\mathsf{note}_i, \mathsf{path}_i, sk_i)\}, \{\mathsf{note}'_j\}\bigr)$.

Eight constraints, all enforced by the circuit:

C6 is the load-bearing constraint. It is what makes the transaction self-paying: the prover can only produce a valid proof if the input notes’ values sum to exactly the output values plus the fee.

The self-paying property (Theorem 3.1)

Theorem. Let $\mathsf{tx} = (\{\mathsf{nf}_i\}, \{\mathsf{cm}_j\}, \mathsf{rt}, f, \pi)$ be a valid SPST transaction. Then:

1. The fee $f$ is funded entirely from consumed shielded notes.
2. No external account, relayer, or gas sponsor is required.
3. Validators extract $f$ as inclusion compensation without learning the private inputs/outputs beyond $f$ itself and the validity of $\pi$.

Proof sketch. (1) follows directly from C6. (2) follows because $\mathsf{tx}$ is a self-contained data structure that any party can broadcast; the on-chain verifier decrements the privacy program’s lamport reserve by $f$ and credits the validator. (3) is the perfect zero-knowledge property of Groth16: the validator sees $f$ as a public input but learns nothing about $v_i$ or $v'_j$.

The full proof is in §3.1.3 of the paper. The takeaway: on Solana, the privacy program’s PDA holds a reserve. Each shield deposit increments it. Each SPST transaction’s proof authorises the validator to take $f$ from it. Replenishment is automatic.

Theorem 3.2 — Balance / value conservation

Statement. No PPT adversary can produce a valid SPST transaction that creates value (i.e., one for which $\sum_j v'_j + f > \sum_i v_i$) except with negligible probability.

The proof gives two complementary arguments — one from the SNARK’s knowledge soundness, one from an independent Pedersen commitment cross-check that provides defense in depth.

Argument 1 (SNARK soundness)

C6 enforces $\sum_i v_i = \sum_j v'_j + f$ over $\mathbb{F}_p$. C7 and C8 enforce $v'_j, f \in [0, 2^{64})$. With at most $n \leq 2^{16}$ inputs each bounded by $2^{64}$, $\sum_i v_i < 2^{80} \ll p \approx 2^{254}$ — so field arithmetic faithfully represents integer arithmetic and no modular wraparound is possible.

By Groth16 knowledge soundness in the AGM, an extractor $\mathcal{E}$ can recover the witness $w^*$ satisfying all constraints C1–C8. C6 in the extracted witness gives $\sum_i v_i = \sum_j v'_j + f$ as an integer equation. Contradiction with the assumed inflation.

Argument 2 (Pedersen cross-check)

As defense in depth, attach Pedersen value commitments to each note. With $C_{\mathsf{in},i} = v_i \cdot g + r^{(\mathsf{vc})}_i \cdot h$ and $C_{\mathsf{out},j} = v'_j \cdot g + r^{(\mathsf{vc})}_j \cdot h$, the verifier checks

where $r_\Delta = \sum_i r^{(\mathsf{vc})}_i - \sum_j r^{(\mathsf{vc})}_j$.

Suppose an adversary passes this check but with $\sum_j v'_j + f \neq \sum_i v_i$. Let $\delta = \sum_i v_i - \sum_j v'_j - f \neq 0$. Then $\delta \cdot g = r'_\Delta \cdot h$ for some $r'_\Delta$, which yields $\log_g h = \delta / r'_\Delta$ — contradicting DLOG. ∎

Theorem 3.3 — Double-spend resistance

Game. $\mathcal{A}$ may adaptively deposit and spend; wins if it produces two accepted transactions consuming the same note $\mathsf{note}^*$.

Cases.

• Case 1: The two transactions publish the same nullifier. Rejected by the protocol’s nullifier-set check.
• Case 2: They publish different nullifiers $\mathsf{nf} \neq \mathsf{nf}'$ but consume the same note. By C4 both proofs authenticate the same commitment $\mathsf{cm}^*$. By C1 we have $\mathsf{pk}^* = \mathsf{PRF}_{sk^*}(0) = \mathsf{PRF}_{sk'}(0)$.
  • If $sk^* = sk'$, then $\mathsf{nf} = \mathsf{nf}'$. Contradiction.
  • If $sk^* \neq sk'$, then $\mathsf{Poseidon}(sk^*, 0) = \mathsf{Poseidon}(sk', 0)$ — a collision in Poseidon. Reduces to collision resistance.

Both cases reach a contradiction. ∎

Theorem 3.4 — Transaction unlinkability

Statement. Under perfect zero-knowledge of Groth16 and computational hiding of Pedersen commitments under DDH, the SPST scheme satisfies transaction unlinkability: no PPT adversary can determine which input notes fund which output notes with non-negligible advantage.

Proof structure. Hybrid argument:

• Hybrid 0: real game.
• Hybrid 1: replace all Groth16 proofs with simulated proofs. By perfect ZK of Groth16, indistinguishable.
• Hybrid 2: in the simulated view, the multisets of nullifiers, commitments, roots, fees are identical for both branchings of the challenge. The fee is identical by construction. Each $\mathsf{cm}_j = \mathsf{Poseidon}(\mathsf{pk}'_j, v'_j, \rho'_j, r'_j)$ with fresh random $r'_j$ is computationally indistinguishable from a uniform field element. Each nullifier $\mathsf{nf}_i = \mathsf{PRF}_{sk_i}(\rho_i)$ with unique $\rho_i$ is pseudorandom. The Pedersen value commitments are computationally hiding under DDH.

Result: $\mathsf{Adv}_{\mathcal{A}} \leq \mathsf{negl}(\lambda)$. ∎

Theorem 3.5 — Non-malleability

Statement. No PPT adversary can take a valid SPST transaction and produce a distinct valid transaction with altered public inputs (e.g., a different fee), except with negligible probability.

Proof. Relies on the simulation-extractability of Groth16 in the Random Oracle Model — the Bowe-Gabizon construction (2019), refined by Ràfols-Baghery-Pindado (2023). An adversary mauling the proof to alter $f$ would need to extract a witness with a different $f'$ satisfying C6, but C6 plus the unchanged input commitments and output commitments uniquely determines $f$. Contradiction.

Circuit complexity

For an SPST circuit with $n$ inputs and $m$ outputs:

A canonical 2-in / 2-out transaction:

On commodity hardware (Apple M2, 8-core), Groth16 proving for ~24,000 constraints takes 0.5–1.5 seconds with arkworks or snarkjs. Proof size is 128 bytes compressed (BN254 G1/G2 compression on Solana). Verification is ~150,000–200,000 CU via sol_alt_bn128_* syscalls.

What SPST is not

SPST handles private value transfer — the Solana analogue of Zcash’s Sapling. It does not:

• Handle private computation. The next post (PPST) extends the relation to arbitrary arithmetic circuits over private state.
• Hide the submitter. The transaction submitter is still publicly identified by their Ed25519 signature on the wrapping Solana transaction. TAB addresses that.
• Hide the fee amount. $f$ is necessarily public for validator compensation.

But it does the load-bearing thing: the user becomes self-sovereign with respect to fee payment. Combined with TAB and PPST, that’s the whole framework.

Bibliography

• Ben-Sasson, E. et al. (2014). Zerocash. IEEE S&P 2014. https://eprint.iacr.org/2014/349
• Hopwood, D. et al. (2016–2026). Zcash Protocol Specification. https://zips.z.cash/protocol/protocol.pdf
• Groth, J. (2016). On the Size of Pairing-based Non-interactive Arguments. EUROCRYPT 2016. https://eprint.iacr.org/2016/260
• Bowe, S., Gabizon, A. (2019). Making Groth’s zk-SNARK Simulation Extractable. https://eprint.iacr.org/2019/197
• Ràfols, C., Baghery, K., Pindado, Z. (2023). Simulation Extractable versions of Groth’s zk-SNARK Revisited. https://doi.org/10.1007/s10207-023-00750-7
• Pedersen, T. P. (1991). Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. CRYPTO 1991.
• Grassi, L. et al. (2021). Poseidon: A New Hash Function for Zero-Knowledge Proof Systems. USENIX Security 2021. https://eprint.iacr.org/2019/458
• Aztec Documentation. Indexed Merkle Tree (Nullifier Tree). https://docs.aztec.network/

Previous: The fee paradox ← · Next: PPST: private programmable state →