2025-11-18T21:40:12.686968

Zk-SNARK Marketplace with Proof of Useful Work

Oleksak, Gazdik, Peresini et al.

Proof of Work (PoW) is widely regarded as the most secure permissionless blockchain consensus protocol. However, its reliance on computationally intensive yet externally useless puzzles results in excessive electric energy wasting. To alleviate this, Proof of Useful Work (PoUW) has been explored as an alternative to secure blockchain platforms while also producing real-world value. Despite this promise, existing PoUW proposals often fail to embed the integrity of the chain and identity of the miner into the puzzle solutions, not meeting necessary requirements for PoW and thus rendering them vulnerable. In this work, we propose a PoUW consensus protocol that computes client-outsourced zk-SNARKs proofs as a byproduct, which are at the same time used to secure the consensus protocol. We further leverage this mechanism to design a decentralized marketplace for outsourcing zk-SNARK proof generation, which is, to the best of our knowledge, the first such marketplace operating at the consensus layer, while meeting all necessary properties of PoW.

academic

Zk-SNARK Marketplace with Proof of Useful Work

基本信息

论文ID: 2510.09729
标题: Zk-SNARK Marketplace with Proof of Useful Work
作者: Samuel Oleksak, Richard Gazdik, Martin Peresini, Ivan Homoliak (Brno University of Technology, Czech Republic)
分类: cs.CR (Cryptography and Security)
发表时间: 2025年10月10日 (arXiv预印本)
论文链接: https://arxiv.org/abs/2510.09729

摘要

传统的工作量证明(PoW)被广泛认为是最安全的无许可区块链共识协议，但其依赖计算密集型且对外部无用的谜题，导致了巨大的电力能源浪费。为缓解这一问题，有用工作量证明(PoUW)作为一种替代方案被提出，既能保护区块链平台安全又能产生现实世界价值。然而，现有的PoUW提案往往未能将链的完整性和矿工身份嵌入到谜题解决方案中，不满足PoW的必要要求，从而容易受到攻击。本文提出了一种PoUW共识协议，将客户外包的zk-SNARKs证明计算作为副产品，同时用于保护共识协议。进一步利用此机制设计了一个去中心化的zk-SNARK证明生成外包市场，据作者所知，这是第一个在共识层运行且满足PoW所有必要属性的此类市场。

研究背景与动机

核心问题

能源浪费问题：传统PoW协议（如比特币）消耗大量电力进行无实际用途的计算，比特币挖矿每年可能产生65.4兆吨CO2排放，相当于希腊的国家级排放量。
zk-SNARK计算瓶颈：zk-SNARK证明生成在计算和内存方面都非常密集，通常需要数十GB的RAM和在高端硬件上花费数十分钟，使其在资源受限设备上不实用。
现有PoUW方案的安全缺陷：现有PoUW提案未能满足PoW的核心安全要求，特别是缺乏新鲜性(freshness)属性，容易受到重放攻击。

研究动机

结合PoUW和zk-SNARK生成的双重需求，设计既能保证区块链安全又能产生有用密码学证明的共识协议
创建第一个在共识层运行的通用zk-SNARK计算市场
解决现有PoUW方案在安全性方面的不足

核心贡献

首创性PoUW-zk-SNARK融合协议：提出了将zk-SNARK证明生成作为有用工作的新型PoUW共识协议，创建了第一个为共识协议提供安全性的去中心化SNARK计算市场。
支持私有输入的扩展方案：解决了在公开无许可区块链环境中委托涉及私有输入的zk-SNARK证明计算的挑战，提出了见证混淆外包(WOO)技术。
完整的安全性分析：全面分析并证明了所提议共识协议及其扩展的安全属性，满足PoW的所有必要条件。
创新的区块提议者选择机制：设计了基于加权彩票的区块提议者选择算法，结合分桶机制减少浪费工作。

方法详解

任务定义

设计一个PoUW共识协议，其中：

输入：客户提交的算术电路和证明参数
输出：有效的zk-SNARK证明和安全的区块链共识
约束条件：满足PoW的所有必要属性（不对称性、粒度性、防摊销等）

系统架构

网络参与者

客户(Clients)：不参与共识，创建币转移交易和证明请求交易
矿工(Miners/Full nodes)：参与共识，选择交易，生成SNARK证明，发布和验证区块
电路注册节点(Circuit registry nodes)：维护SNARK电路注册表，参与可信设置的SMPC

区块结构

每个区块包含两种交易类型：

币交易(Coin transactions)：原生货币操作
证明交易(Proof transactions)：封装SNARK生成请求

核心技术机制

1. 区块提议者选择算法

演进过程：

(A) 基础方法：矿工必须生成足够证明达到最小难度阈值κ
(B) 添加彩票机制：每次添加新证明时触发彩票，获胜概率为： $P_{win}(i) = \frac{C_i}{\kappa}$ 其中 $C_i$ 是第i个证明的复杂度
(C) 减少浪费工作：引入参数ψ考虑累积工作： $P_{win}(i) = \frac{C_i}{\kappa} + \psi \cdot \frac{\sum_{j<i} C_j}{\kappa}$
(D) 并行区块生产：放松线性链约束，允许并行挖矿
(E) 分桶机制：根据交易哈希前缀将交易分配到不同桶中，减少冲突