PVUGC: Proof-Agnostic Verifiable Unique Group Commitments

Status: Experimental Research Implementation

1. Overview

This repository contains an implementation of PVUGC, a cryptographic protocol for extracting Key Encapsulation Mechanism (KEM) secrets from zero-knowledge proofs in a statement-dependent, proof-agnostic manner. The protocol enables decentralized key extraction without requiring trusted committees or knowledge of the masking secret.

The implementation specializes the Groth-Sahai commitment framework to Groth16 verification, yielding a simplified one-sided construction that achieves comparable security guarantees with reduced computational overhead.

2. Protocol Properties

PVUGC satisfies the following cryptographic properties:

• Proof-Agnosticism: Different valid proofs π₁, π₂ for the same statement extract identical keys K₁ = K₂
• Witness-Independence: Extracted keys depend only on the statement (vk, public_inputs), not on witness values
• Gating: Key extraction is impossible without a valid proof
• Permissionless Extraction: No committee, threshold cryptography, or additional coordination required at extraction time
• Statement-Independent Arming: Armed bases depend only on VK (not on public inputs); statement dependence isolated to target R(vk, x)
• Offline Arming: One-time setup phase; armer goes offline permanently

3. Technical Approach

3.1 One-Sided Groth-Sahai Framework

The protocol employs a specialized Groth-Sahai construction optimized for Groth16 verification. Unlike traditional two-sided approaches requiring rank decomposition of coefficient matrices, the one-sided variant leverages the fact that Groth16 verifying key components (β, δ, and witness b_g2_query) can serve as statement-independent pairing bases. Statement dependence is isolated to the target R(vk, x), which contains the γ-factor that is never armed.

The verification equation becomes:

∑_ℓ e(C_ℓ, U_ℓ) + e(θ, δ) = R(vk, x)

where C_ℓ are commitments to proof elements, U_ℓ are aggregations of VK bases, and δ is the Groth16 discrete logarithm base.

3.2 Three-Phase Execution

Phase 1: Offline Arming (Deposit)

• ARMER generates secret ρ, derives statement-independent bases from Groth16 VK
• Computes armed bases: [β + b_0]^ρ, [v_j]^ρ, δ^ρ
• Publishes armed bases; ρ never leaves ARMER

Phase 2: Online Proving (Spend)

• PROVER generates valid Groth16 proof π
• Constructs GS commitments from proof elements
• Publishes proof bundle (Groth16 proof + commitments)

Phase 3: Key Extraction (Runtime)

• DECAPPER receives attestation, validates all proofs
• Extracts K = R^ρ using paired commitment and armed bases
• No knowledge of ρ required; security via pairing hardness

3.3 Comparison with Traditional Two-Sided Approach

Property	One-Sided	Two-Sided
Setup	VK-derived, statement-independent	CRS-based, per-statement
Coefficient Matrix	Thin aggregation	Full rank decomposition
Bases Required	O(n)	O(rank²)
Proof Elements	Single (θ)	Multiple (θ, π per rank)
Integration	Native to Groth16	Via auxiliary recomposition
Statement Dependence	Isolated to target R(vk, x)	Spread across armed bases

4. Mathematical Foundation

For the complete mathematical specification including theorems, proofs, security analysis, and design rationale, see TECHNICAL.md.

Key results:

• Soundness: Discrete log hardness in G₂ ensures K cannot be computed without valid proof
• Completeness: Every valid Groth16 proof enables extraction of K = target^ρ
• Proof-Agnosticism: Extraction depends only on PPE verification result, not proof structure

5. Implementation Architecture

5.1 Core Modules

src/
  ├── lib.rs                  # Crate root; module declarations
  ├── arming.rs              # Base aggregation and arming logic
  ├── ppe.rs                 # PPE target computation from Groth16 VK
  ├── api.rs                 # High-level verification and extraction API
  ├── decap.rs               # Commitment building and decapsulation
  ├── poce.rs                # Proof of consistent encryption across arms
  └── ctx.rs                 # Context binding utilities

ark-groth16-pvugc/           # Standard Groth16 implementation

┌─────────────────────────────────────────────────────────────────────────────┐ │ LEVEL 0: APP PROOFS │ │ │ │ VDF₀ VDF₁ Fib₀ Fib₁ BTC₀ BTC₁ │ │ │ │ │ │ │ │ │ │ └───┬───┘ └───┬───┘ └───┬───┘ │ │ ▼ ▼ ▼ │ ├─────────────────────────────────────────────────────────────────────────────┤ │ LEVEL 1: LEAF VERIFIER AIRs │ │ │ │ VerifierAir₀ VerifierAir₁ VerifierAir₂ │ │ (verifies 2 VDFs) (verifies 2 Fibs) (verifies 2 BTCs) │ │ │ │ OOD uses: evaluate_child_constraints(VdfLike) │ │ evaluate_child_constraints(FibLike) ← APP-SPECIFIC │ │ evaluate_child_constraints(BTCLike) │ │ │ │ Output: VerifierAir proofs (all same AIR type!) │ │ │ │ │ │ │ └───────┬───────┴───────┬───────┘ │ │ ▼ ▼ │ ├─────────────────────────────────────────────────────────────────────────────┤ │ LEVEL 2+: AGGREGATOR VERIFIER AIRs │ │ │ │ VerifierAir₃ VerifierAir₄ │ │ (verifies VA₀ + VA₁) (verifies VA₂ + ...) │ │ │ │ OOD uses: evaluate_child_constraints(VerifierAir) ← SAME AS evaluate_all! │ │ │ │ Output: VerifierAir proofs │ │ │ │ │ │ └────────────┬────────────┘ │ │ ▼ │ ├─────────────────────────────────────────────────────────────────────────────┤ │ FINAL AGGREGATOR │ │ │ │ VerifierAir_final │ │ (verifies 2 VerifierAir proofs) │ │ │ │ OOD uses: evaluate_child_constraints(VerifierAir) │ │ │ │ Output: Single VerifierAir proof │ │ │ │ │ ▼ │ ├─────────────────────────────────────────────────────────────────────────────┤ │ GROTH16 (R1CS) │ │ │ │ Verifies: VerifierAir_final proof │ │ OOD uses: evaluate_verifier_air_constraints_gl() ← HARDCODED (~900 mono) │ │ (R1CS equivalent of evaluate_all) │ │ │ │ Output: Groth16 proof (constant size, instant verify) │ └─────────────────────────────────────────────────────────────────────────────┘

5.2 Build and Test

cargo build --release
cargo test

# Run with output
cargo test -- --nocapture

# Run specific test suites
cargo test test_one_sided_pvugc_e2e -- --nocapture
cargo test test_one_sided_security -- --nocapture

6. Usage

6.1 Setup and Arming

use arkworks_groth16::OneSidedPvugc;

// Arm bases at deposit time (one-time)
let rho = Fr::rand(&mut rng);
let (_bases, arms, _r, _k) = OneSidedPvugc::setup_and_arm(&pvugc_vk, &vk, &public_inputs, &rho)
    .expect("setup_and_arm");

// Publish: arms, R = target^1 (computable from vk + public_inputs)
// Secret: rho

6.2 Verification and Extraction

// Prover generates complete attestation
let bundle = PvugcBundle {
    groth16_proof,
    gs_commitments,
};

// Verifier validates all components
let valid = OneSidedPvugc::verify(&bundle, &pvugc_vk, &vk, &public_inputs);

if valid {
    // Extract key
    let k = OneSidedPvugc::decapsulate(&bundle.gs_commitments, &arms)
        .expect("decapsulate");
    // k = R^ρ (same for any valid proof of same statement)
}

See tests for complete working examples.

7. Security Assumptions

The protocol relies on standard assumptions in pairing-based cryptography:

1. Discrete Logarithm Problem (DLP): Hard in both G₁ and G₂
2. Pairing Hardness: Computation of pairings is efficient; extracting discrete logs from pairings is hard
3. Groth16 Knowledge Soundness: Only proofs generated with knowledge of witnesses are accepted
4. Collision Resistance: SHA256 for Fiat-Shamir challenges

For detailed security analysis including attack vectors and mitigations, see TECHNICAL.md.

8. Current State

This is an experimental research implementation. Key features:

• Complete one-sided PVUGC construction with all verification checks
• End-to-end tests demonstrating proof-agnostic extraction
• Security property tests validating statement-dependence
• Simple commitment building from proof elements
• Lean CRS architecture (no Powers of Tau)

Known limitations and areas for future work:

• Extension to other SNARK schemes requires per-scheme PPE derivation
• Performance optimization of pairing operations

9. Testing

The test suite validates both functional correctness and security properties:

# End-to-end flow: Groth16 proof generation through key extraction
cargo test test_one_sided_pvugc_e2e

# Security properties: proof-agnosticism, statement-dependence
cargo test test_one_sided_security

10. References

See TECHNICAL.md for complete references and background on Groth-Sahai proofs, PVUGC, and related work.

Primary Sources

• Groth, J., & Sahai, A. (2008). "Efficient non-interactive proof systems for bilinear groups." EUROCRYPT 2008.
• Groth, J. (2016). "On the size of pairing-based non-interactive arguments." EUROCRYPT 2016.

Implementation Foundation

• arkworks: Elliptic curves, pairings, and zero-knowledge proof framework
• BLS12-381: Pairing-friendly elliptic curve

11. License

MIT or Apache 2.0

12. Citation

If you use this implementation in academic work, please cite:

@software{pvugc_2025,
  title={PVUGC: One-Sided Groth-Sahai Implementation},
  author={J Sidhu et al},
  year={2025},
  url={https://github.com/sidhujag/pvugc}
}