Zk-SNARK Marketplace with Proof of Useful Work

Basic Information

• Paper ID: 2510.09729
• Title: Zk-SNARK Marketplace with Proof of Useful Work
• Authors: Samuel Oleksak, Richard Gazdik, Martin Peresini, Ivan Homoliak (Brno University of Technology, Czech Republic)
• Classification: cs.CR (Cryptography and Security)
• Publication Date: October 10, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.09729

Abstract

Traditional Proof of Work (PoW) is widely recognized as the most secure permissionless blockchain consensus protocol, yet it relies on computationally intensive puzzles that are externally useless, resulting in enormous energy waste. To mitigate this issue, Proof of Useful Work (PoUW) has been proposed as an alternative that both protects blockchain platforms and generates real-world value. However, existing PoUW proposals often fail to embed blockchain integrity and miner identity into puzzle solutions, failing to satisfy the necessary requirements of PoW and thus being vulnerable to attacks. This paper proposes a PoUW consensus protocol that leverages client-outsourced zk-SNARK proof computation as a byproduct while simultaneously securing the consensus protocol. Furthermore, this mechanism enables the design of a decentralized zk-SNARK proof generation outsourcing marketplace, which is, to the authors' knowledge, the first such marketplace operating at the consensus layer while satisfying all necessary properties of PoW.

Research Background and Motivation

Core Problems

1. Energy Waste Issue: Traditional PoW protocols (such as Bitcoin) consume vast amounts of electricity for computations with no practical utility. Bitcoin mining may generate 65.4 megatons of CO2 emissions annually, equivalent to Greece's national emission levels.
2. zk-SNARK Computation Bottleneck: zk-SNARK proof generation is computationally and memory-intensive, typically requiring tens of gigabytes of RAM and spending tens of minutes on high-end hardware, making it impractical on resource-constrained devices.
3. Security Defects in Existing PoUW Schemes: Existing PoUW proposals fail to satisfy the core security requirements of PoW, particularly lacking the freshness property, making them vulnerable to replay attacks.

Research Motivation

• Combine the dual demands of PoUW and zk-SNARK generation to design a consensus protocol that ensures blockchain security while generating useful cryptographic proofs
• Create the first universal zk-SNARK computation marketplace operating at the consensus layer
• Address security deficiencies in existing PoUW schemes

Core Contributions

1. Novel PoUW-zk-SNARK Fusion Protocol: Proposes a new PoUW consensus protocol that leverages zk-SNARK proof generation as useful work, creating the first decentralized SNARK computation marketplace that provides security for the consensus protocol.
2. Extended Scheme Supporting Private Inputs: Addresses the challenge of delegating zk-SNARK proof computation involving private inputs in open permissionless blockchain environments, proposing the Witness Obfuscation Outsourcing (WOO) technique.
3. Comprehensive Security Analysis: Provides thorough analysis and proof of the security properties of the proposed consensus protocol and its extensions, satisfying all necessary conditions of PoW.
4. Innovative Block Proposer Selection Mechanism: Designs a weighted lottery-based block proposer selection algorithm combined with bucketing mechanisms to reduce wasted work.

Methodology Details

Task Definition

Design a PoUW consensus protocol where:

• Input: Arithmetic circuits and proof parameters submitted by clients
• Output: Valid zk-SNARK proofs and secure blockchain consensus
• Constraints: Satisfy all necessary properties of PoW (asymmetry, granularity, amortization resistance, etc.)

System Architecture

Network Participants

1. Clients: Do not participate in consensus; create coin transfer transactions and proof request transactions
2. Miners/Full nodes: Participate in consensus; select transactions; generate SNARK proofs; publish and validate blocks
3. Circuit registry nodes: Maintain SNARK circuit registry; participate in SMPC for trusted setup

Block Structure

Each block contains two types of transactions:

• Coin transactions: Native currency operations
• Proof transactions: Encapsulate SNARK generation requests

Core Technical Mechanisms

1. Block Proposer Selection Algorithm

Evolution Process:

• (A) Basic Approach: Miners must generate sufficient proofs to reach minimum difficulty threshold κ
• (B) Adding Lottery Mechanism: Lottery triggered each time a new proof is added, with winning probability: $P_{win}(i) = \frac{C_i}{\kappa}$ where $C_i$ is the complexity of the i-th proof
• (C) Reducing Wasted Work: Introduce parameter ψ considering accumulated work: $P_{win}(i) = \frac{C_i}{\kappa} + \psi \cdot \frac{\sum_{j<i} C_j}{\kappa}$
• (D) Parallel Block Production: Relax linear chain constraints to allow parallel mining
• (E) Bucketing Mechanism: Distribute transactions into different buckets based on transaction hash prefixes to reduce conflicts

2. Blockchain Integrity Assurance

Integrity Parameter η:

• Computed by hashing the current block header (containing previous block hash and coin transactions)
• Injected as a public parameter into the arithmetic circuit
• If lottery fails, η is recomputed to include newly generated proofs
• Forms a cryptographically linked proof chain, preventing proof theft

3. Circuit Registry Subnetwork

Functions:

• Decentralized registration and retrieval of arithmetic circuits
• Trusted setup via SMPC
• Storage of proving keys and verification keys
• Requires nodes to stake native currency; improper behavior results in slashing

Technical Innovations

1. Integrity Embedding: Binds proofs to specific blocks through integrity parameters, satisfying PoW's freshness requirement
2. Bucketing Parallelization: Borrows dynamic sharding concepts from Sycomore, dynamically adjusting bucket count based on network demand
3. Witness Obfuscation Outsourcing (WOO): Uses additive masking to protect private input privacy
4. Lottery Weight Mechanism: Adjusts winning probability based on circuit complexity, ensuring fairness

Experimental Setup

Modeling Approach

Models the consensus protocol using Stochastic Time-Colored Petri Nets (STCPN), implemented via Python's simpn library.

Experimental Hypotheses

• H1: Reward distribution is proportional to node mining power
• H2: Complexity of selected proofs does not affect rewards
• H3: Introducing parameter ψ to reduce wasted work increases centralization
• H4: Bucketing mechanism reduces wasted work

Experimental Configuration

• Focuses on proof generation process and miner interactions
• Ignores coin transaction confirmation time (relatively instantaneous)
• Assumes miners have cached circuit registry data

Experimental Results

Main Findings

1. Fairness Verification (H1)

• Block reward ratio exhibits linear relationship with computational power ratio (y=x)
• Key Issue: Proof reward ratio shows quadratic relationship (y=x²); stronger miners not only produce more blocks but also higher average block intensity
• Impact: May incentivize mining pool formation; requires minimizing proof reward proportion in total rewards

2. Complexity Independence (H2)

• Miners with different proof size preferences receive similar reward ratios with equal computational power
• Verifies system fairness regarding proof complexity selection

3. ψ Parameter Impact (H3)

• As ψ increases, wasted work decreases from approximately 78% to 70%
• However, strongest miner's reward share increases from approximately 37.5% to 47.5%
• Confirms trade-off between reducing wasted work and increasing centralization

4. Bucketing Effect (H4)

• Increasing bucket count significantly reduces wasted work
• With 16 buckets and 16 miners configuration, wasted work can be reduced to approximately 20%
• Bucket count is limited by available proofs in the mempool

Performance Analysis

Groth16 Proof Time

• Proof time exhibits linear relationship with constraint count: T(n) = a·n + b
• Supports predictable performance and efficient resource allocation
• Verification time is millisecond-scale and independent of circuit complexity

WOO Performance Overhead

• Obfuscated circuit time overhead compared to original circuit consistently below 0.1 seconds
• Overhead does not grow significantly with circuit scale
• Suitable for real-time, privacy-preserving proof generation

Related Work

PoUW Protocols

• Primecoin (2013): Searches prime chains, contributes to number theory
• Ofelimos: Uses combinatorial optimization problems
• Coin.AI: Distributed deep learning
• Limitations: Existing schemes universally lack freshness property, vulnerable to replay attacks

Proof Generation Markets

• Consensus-Integrated: Mina protocol's Snarketplace (application layer)
• Independent Network: =nil; Foundation Proof Market, RISC Zero's Bonsai
• This Paper's Advantage: First universal zk-SNARK marketplace operating at consensus layer

Conclusions and Discussion

Main Conclusions

1. Successfully designed a PoUW protocol satisfying all necessary PoW properties
2. Created the first consensus-layer zk-SNARK computation marketplace
3. Addressed private input protection through WOO technology
4. Experimental validation of system fairness and efficiency

Limitations

1. Quadratic Effect of Proof Rewards: May lead to mining centralization
2. Circuit Reusability Constraints: WOO technology requires circuit generation for each client
3. Trusted Setup Dependency: Still requires SMPC for trusted setup
4. Groth16 Limitations: Depends on specific proof scheme

Future Directions

1. Explore applicability of alternative proof schemes (e.g., STARK)
2. Optimize reward mechanisms to reduce centralization risks
3. Improve circuit reuse mechanisms for enhanced efficiency
4. Extend to more types of useful computation

In-Depth Evaluation

Strengths

1. Strong Innovation: First combination of zk-SNARK generation with PoUW consensus
2. Theoretical Completeness: Comprehensively satisfies all PoW security requirements
3. High Practical Value: Addresses two important practical problems
4. In-Depth Analysis: Systematic evaluation through Petri net modeling
5. Privacy Protection: WOO technology provides elegant private input solution

Weaknesses

1. High Complexity: System design is relatively complex with significant implementation difficulty
2. Centralization Risks: Quadratic effect of proof rewards may lead to unfairness
3. Scalability Limitations: Circuit registry and trusted setup may become bottlenecks
4. Insufficient Real-World Validation: Lacks large-scale testing in production environments

Impact

1. Academic Contribution: Provides new research direction for PoUW field
2. Practical Significance: May promote development of more environmentally friendly blockchain technology
3. Technical Inspiration: WOO technology applicable to other privacy-preserving computation scenarios

Applicable Scenarios

1. Blockchain applications requiring large quantities of zk-SNARK proofs
2. Computation outsourcing scenarios with high privacy protection requirements
3. New blockchain projects pursuing environmental sustainability
4. Decentralized applications requiring general-purpose computation capabilities

References

The paper cites 48 relevant references covering multiple domains including PoW/PoUW protocols, zk-SNARK technology, and blockchain consensus mechanisms, providing a solid theoretical foundation for the research.