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 マーケットプレイスと有用仕事量証明

基本情報

論文ID: 2510.09729
タイトル: Zk-SNARK Marketplace with Proof of Useful Work
著者: Samuel Oleksak、Richard Gazdik、Martin Peresini、Ivan Homoliak（ブルノ工科大学、チェコ共和国）
分類: cs.CR（暗号化とセキュリティ）
発表日時: 2025年10月10日（arXiv プレプリント）
論文リンク: https://arxiv.org/abs/2510.09729

概要

従来の仕事量証明（PoW）は、許可不要なブロックチェーン合意プロトコルの中で最も安全であると広く認識されていますが、計算集約的で外部に無用なパズルに依存しており、膨大な電力エネルギーの浪費をもたらしています。この問題を緩和するため、有用仕事量証明（PoUW）が代替案として提案されており、ブロックチェーンプラットフォームのセキュリティを保護しながら現実世界の価値を生成することができます。しかし、既存のPoUW提案は、チェーンの完全性とマイナーのアイデンティティをパズル解決方案に埋め込むことに失敗することが多く、PoWの必要要件を満たさないため、攻撃に対して脆弱です。本論文は、クライアント外注のzk-SNARK証明計算を副産物として活用しながら同時に合意プロトコルを保護するPoUW合意プロトコルを提案しています。さらにこのメカニズムを利用して、分散型の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信頼設定に参加

ブロック構造

各ブロックには2つのトランザクションタイプが含まれます：

コイントランザクション（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) バケット分割メカニズム：トランザクションハッシュプレフィックスに基づいてトランザクションを異なるバケットに割り当て、競合を削減