Proof-Carrying Authorization (PCA): Private Authorization Without Identity

1. Introduction

Authorization is typically organized around stable identities: users, accounts, or public keys. This yields persistent linkability, makes privacy hard to achieve, and forces verifiers to rely on identity governance or key management. PCA asks a simpler question: does there exist a witness that satisfies the policy predicate for this action and context? If yes, authorization is granted without revealing which member satisfied the predicate.

Design Goals

We designed PCA and the demo program around the following system goals:

• Privacy by construction: hide the authorizer identity while keeping asset transfers transparent.
• Explicit binding: cryptographically bind authorization to action, context, and policy to prevent proof reuse or redirection.
• Replay resistance: ensure each authorization is one-time via nullifiers.
• Deterministic encoding: fixed byte layouts and public-input order to avoid cross-implementation mismatch.
• Deployable runtime: fit within Solana compute and account limits without specialized infrastructure.

Diagram Style Guide

The figures use a consistent notation for readability and mathematical alignment:

• Nodes: rounded rectangles are actors or programs, cylinders are on-chain storage (accounts), and plain rectangles are computations.
• Arrows: labeled arrows indicate data flow; unlabeled arrows indicate control flow or invocation.
• Notation: $H()$ denotes a hash function; $\mathsf{dom}$, $\mathsf{scope}$, and $\mathsf{nf}$ follow Section 3 definitions; byte concatenation uses $\|\|$.
• Encodings: byte order is explicit in the text (e.g., amount_le8), and field elements are shown as 32-byte big-endian values when applicable.
• Public inputs: appear in the exact order supplied to the verifier.

Contributions.

• We formalize PCA as proof-based authorization over NP relations with explicit action, context, and public-input bindings.
• We define domain and scope hashing that prevent cross-protocol and cross-policy reuse, and nullifiers that provide replay resistance.
• We specify security properties and adversarial games for PCA, with proof sketches under standard assumptions.
• We present a Solana implementation and a private-payments example built on Pinocchio and Groth16 verification.

2. Background and Related Work

PCA connects proof-carrying code (PCC) ideas with privacy-preserving authorization. PCC [1] attaches proofs to code or data so that verifiers can check properties without trusting the producer. PCA applies this pattern to authorization decisions, replacing identity checks with statements about policy satisfaction.

Anonymous and attribute-based credentials [2,3] allow selective disclosure of attributes, while privacy-focused payment systems use membership proofs and nullifiers to prevent double spends [5,6]. PCA adopts the spent-set concept and the binding of authorization to a transaction context but separates authorization from value transfer: the asset is public, while the authorizer is private.

ZK membership systems such as Semaphore [8] demonstrate anonymous signaling and access control, but PCA emphasizes explicit domain/scope binding and replay policies that can be reused across programs. Our implementation relies on Groth16 [4] proofs generated with Circom and snarkjs [9] and uses Merkle-tree membership [7] for group inclusion.

3. Model and Definitions

3.1 Statement encoding

Let $A$ be the set of actions, $C$ contexts, $W$ witnesses, $P$ public inputs, $\mathsf{NF}$ nullifiers, and $\Pi$ proofs. Assume canonical encodings $\mathsf{enc}_A, \mathsf{enc}_C, \mathsf{enc}_P$ and define the statement:

3.2 Policies as relations

A policy is an NP relation $R \subseteq W \times A \times C \times P$ with language:

3.3 Domain and scope binding

Define a domain tuple $\mathsf{dom}=(\mathsf{pid},\mathsf{rid},\mathsf{vid})$ containing protocol id, policy id, and verifier id. Split context into stable and fresh components $c=(c_{\mathrm{stable}}, c_{\mathrm{fresh}})$.

Domain and scope are hashed on-chain and embedded into field elements for the proof system. In our implementation we split 32-byte hashes into two 128-bit limbs and left-pad each limb into a 32-byte field element.

3.4 Nullifiers and spent state

Let the witness include a secret $\mathsf{sk}$ and a derived nullifier secret $\mathsf{sk}_{\mathrm{spend}} := \mathsf{KDF}(\mathsf{sk})$. Define:

The verifier accepts at most one proof per nullifier under a fixed domain/scope.

4. Construction

We assume a NIZK system $(\mathsf{Setup}_{\mathrm{zk}},\mathsf{P},\mathsf{V})$ for NP and a collision-resistant hash $H$. The prover demonstrates knowledge of $\widetilde{w}=(w,\mathsf{sk}_{\mathrm{spend}})$ such that:

The verifier checks the proof, validates public inputs, and records the nullifier as spent.

5. Threat Model and Security Goals

We assume a network adversary who can observe transactions, reorder them, front-run, and submit arbitrary proofs. The adversary cannot break the security of the hash function or the underlying NIZK system and cannot forge valid signatures for system accounts. The verifier is honest-but-curious: it follows the protocol but attempts to learn which member authorized an action.

Security goals:

• Authorization soundness: invalid actions cannot be authorized without a valid witness.
• Zero-knowledge privacy: proofs reveal no information about which witness satisfied the policy.
• Domain/scope non-malleability: proofs cannot be reused across protocols, policies, or contexts.
• Replay resistance: each nullifier can be used at most once within the defined domain and scope.

6. Security Analysis (Informal)

This paper takes a system-first approach; we provide concise security arguments to justify design choices and threat mitigations. Full cryptographic proofs are out of scope here.

6.1 Correctness (informal)

If the prover knows a witness $w$ satisfying $R(w,a,c,p)$ and computes $\mathsf{nf}$ as specified, then the proof system accepts and the verifier accepts the statement.

6.2 Authorization soundness (informal)

If an adversary produces an accepting proof for a statement not in $L_R$, then it breaks the soundness of the NIZK system or finds collisions in $H$.

6.3 Privacy (informal)

By the zero-knowledge property of the NIZK system, proofs reveal no information about $w$ or $\mathsf{sk}_{\mathrm{spend}}$ beyond statement validity. The verifier only sees public inputs committed to the action and context.

6.4 Binding and replay resistance (informal)

Domain and scope hashes bind proof to context. Replay is prevented by the nullifier check.

7. Implementation on Solana

We implement PCA as an on-chain runtime (pinocchio-pca) and a demo program (private_payments) written in Rust using Pinocchio. The runtime computes SHA-256 domain and scope hashes with explicit domain separation, checks context freshness using the Clock sysvar, verifies Groth16 proofs via groth16-solana, and consumes a nullifier PDA to prevent replay.

The demo program maintains a vault SPL token account owned by a program-derived address. A config PDA stores the Merkle root, mint, and vault address. The withdrawal instruction computes action bytes as:

Context bytes are issued_at_slot_le8 || valid_until_slot_le8.

Engineering Tradeoffs

• Proof system: Groth16 offers small proofs but requires trusted setup.
• Hashing split: SHA-256 on-chain, Poseidon in-circuit.
• Nullifier storage: Minimal PDA per spend.
• Public inputs: Fixed vector to limit verify cost.
• Compute budget: Withdraw path is heavy (near ~200k CU).

8. Case Study: Private Payments

The private-payments circuit proves membership in a Merkle tree of authorized members and binds the proof to a withdrawal action. The public inputs are:

The on-chain scope hash uses action/context bytes and these inputs.

9. Evaluation

Preliminary measurements from solana-program-test:

Storage overhead involves 140 bytes for Config and 112 bytes per Nullifier. The withdraw instruction payload is 601 bytes.

10. Limitations and Open Problems

• Front-running: Proofs can be copied.
• Trusted setup: Groth16 requires ceremony.
• Spent-state growth: Nullifier set grows linearly.
• Policy safety: Malicious policies can leak info.

11. Conclusion

PCA replaces identity-based authorization with proof-based authorization, enabling private approval without revealing which member authorized an action. We provide formal definitions, security properties, and a working Solana implementation.

Appendix A: Formal Model (Optional)

A.1 Private-payments relation

Witness $w = (sk, path, idx)$. Public inputs $p = (scope, dom, nf, root, epoch)$.

Define the relation $R_{pp}(w, a, c, p)$ to hold if:

• $\mathsf{Merkle}(sk, path, idx) = root$
• $nf = \mathsf{Poseidon}(dom\_hi, dom\_lo, scope\_hi, scope\_lo, epoch, sk)$

A.2 Encoding notes

• Action bytes: SHA256 of params including recipient/amount.
• Context: Slot ranges.
• Hash to field: Split 32-byte hashes into two 16-byte limbs.

References

[1] G. C. Necula. Proof-Carrying Code. POPL 1997.

[2] J. Camenisch et al. Anonymous Credentials. EUROCRYPT 2001.

[3] J. Camenisch et al. Signature Schemes... CREDENTIALS ... CRYPTO 2004.

[4] J. Groth. On the Size of Pairing-based Non-interactive Arguments. EUROCRYPT 2016.

[5] Zerocash (IEEE S&P 2014).

[6] Zerocoin (IEEE S&P 2013).

[7] R. Merkle. Digital Signatures.

[8] Semaphore Protocol.

[9] Circom and snarkjs.