論文の概要: Proofs of Useful Work from Arbitrary Matrix Multiplication
- arxiv url: http://arxiv.org/abs/2504.09971v1
- Date: Mon, 14 Apr 2025 08:22:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-15 16:48:21.174348
- Title: Proofs of Useful Work from Arbitrary Matrix Multiplication
- Title（参考訳）: 任意行列乗算による有用作業の証明
- Authors: Ilan Komargodski, Itamar Schen, Omri Weinstein,
- Abstract要約: 我々は,実世界の計算課題に基づいて,中本のPoWコンセンサスを実装するという,長年にわたるオープンな問題を再考する。
所定の硬度と無視可能な計算オーバーヘッドを有するPoW証明書を生成する。
我々のプロトコルは、悪意のある証明者が正直な証明者に対して大きな優位性を得ることができないという意味で、最適なセキュリティを持っていると推測する。
- 参考スコア（独自算出の注目度）: 10.61664303118825
- License:
- Abstract: We revisit the longstanding open problem of implementing Nakamoto's proof-of-work (PoW) consensus based on a real-world computational task $T(x)$ (as opposed to artificial random hashing), in a truly permissionless setting where the miner itself chooses the input $x$. The challenge in designing such a Proof-of-Useful-Work (PoUW) protocol, is using the native computation of $T(x)$ to produce a PoW certificate with prescribed hardness and with negligible computational overhead over the worst-case complexity of $T(\cdot)$ -- This ensures malicious miners cannot ``game the system" by fooling the verifier to accept with higher probability compared to honest miners (while using similar computational resources). Indeed, obtaining a PoUW with $O(1)$-factor overhead is trivial for any task $T$, but also useless. Our main result is a PoUW for the task of Matrix Multiplication $MatMul(A,B)$ of arbitrary matrices with $1+o(1)$ multiplicative overhead compared to naive $MatMul$ (even in the presence of Fast Matrix Multiplication-style algorithms, which are currently impractical). We conjecture that our protocol has optimal security in the sense that a malicious prover cannot obtain any significant advantage over an honest prover. This conjecture is based on reducing hardness of our protocol to the task of solving a batch of low-rank random linear equations which is of independent interest. Since $MatMul$s are the bottleneck of AI compute as well as countless industry-scale applications, this primitive suggests a concrete design of a new L1 base-layer protocol, which nearly eliminates the energy-waste of Bitcoin mining -- allowing GPU consumers to reduce their AI training and inference costs by ``re-using" it for blockchain consensus, in exchange for block rewards (2-for-1). This blockchain is currently under construction.
- Abstract（参考訳）: 我々は、実世界の計算タスクである$T(x)$(人工ランダムハッシュとは対照的に)に基づいて、中本氏のPoWコンセンサスを実装するという長年にわたるオープンな問題を再考する。
このようなProof-of-Useful-Work(PoUW)プロトコルを設計する上での課題は、所定の硬さと無視可能な計算オーバーヘッドを持つPoW証明書を生成するために、T(x)$のネイティブ計算を使用することである。これは悪質なマイニング業者が、(類似の計算リソースを使用して)正直なマイニング業者よりも高い確率で認証者を騙すことで、"システム」をプレイできないことを保証している。実際、$O(1)$-factorのオーバーヘッドは、どんなタスクでも簡単だが、役に立たないPoUWの取得は、Matrix Multiplication$MatMul(A,B)$のタスクのためのPoUWである。MatMul(A,B)$の任意の行列の$1+$1+$の乗算オーバーヘッドを持つ任意の行列の$MatMul(A,B)$は、$T(\cdot)$ -- Matrix Multiplicationの$Mul(Mul(Mul.Mul.Mul.Mul.Mul.Mul.Mul.Mul.Mul.Mul.Mul.Mul.Mul.Mul.Mr.Mr.Mul.Mr.Mr.Mr.Mr.Mr.Mr.Mr.Mr.M r.Mr.Mr.Mr.Mr.Mr.Mr.Mr.Mr.Mr.Mr.Mr.Mr.Mr.Mr.Mr.Mr.Mr.Mr.Mr.Mr.Mr.M.D.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M .M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.D.M.M.M.M.M.M.M.M.M.M.M .M.D.D.M.M.M.M.M.M.M.M.M.D.M.M.M.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D .D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D .D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D .D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D .D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D .D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D.D
このブロックチェーンは現在建設中です。
関連論文リスト
- Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Fully Automated Selfish Mining Analysis in Efficient Proof Systems Blockchains [5.864854777864723]
私たちは、Bitcoinのような長鎖ブロックチェーンにおける自己中心的なマイニング攻撃について研究していますが、そこでは、作業の証明が効率的な証明システムに置き換えられます。
本稿では,敵の相対収益を最大化することを目的とした,新たな自尊心のあるマイニング攻撃を提案する。
本稿では,MDP の最適相対収益を$epsilon$-tight で計算する形式解析手法を提案する。
論文 参考訳（メタデータ） (2024-05-07T15:44:39Z) - Lossy Cryptography from Code-Based Assumptions [7.880958076366762]
高度な暗号プリミティブの拡散は、複雑性クラス$SZK$の難しい問題を暗示している。
これは、コードベースの仮定から高度なプリミティブを構築するための障壁となる。
我々は、Dense-Sparseという、複雑性クラス$BPPSZK$に該当する新しいコードベースの仮定を提案する。
論文 参考訳（メタデータ） (2024-02-06T02:17:08Z) - DAG-Sword: A Simulator of Large-Scale Network Topologies for DAG-Oriented Proof-of-Work Blockchains [2.0124254762298794]
本稿では,DAGに基づくコンセンサスプロトコルに着目し,離散イベントシミュレータを提案する。
我々のシミュレーターは、Bitcoinネットワークのデータから生成された現実的なブロックチェーンネットワークをシミュレートすることができる。
7000ノードの大規模ネットワーク上で得られた結果により,10ノードの小規模ネットワークを含む関連作業の結果を拡張した。
論文 参考訳（メタデータ） (2023-11-08T12:31:11Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Solving the sampling problem of the Sycamore quantum circuits [6.0604034858265345]
本研究では,GoogleのSycamore量子回路の出力分布から,目的の忠実度を持つ独立サンプルを生成する問題について検討する。
本稿では,対応するテンソルネットワークを1回だけ契約することで,この問題を古典的に解決する手法を提案する。
530ドルキュービットと20ドルサイクルのSycamore量子超越回路では、無相関なビットストリングが100万個発生しました。
論文 参考訳（メタデータ） (2021-11-04T17:13:09Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial
Rewards [59.559028338399855]
我々は,行動セットと敵意の報酬を伴って睡眠中の盗賊の問題を考察する。
本稿では,EXP3にインスパイアされた新しい計算効率のよいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-14T00:41:26Z) - A Proof of Useful Work for Artificial Intelligence on the Blockchain [0.3599866690398789]
本稿では,ブロックチェーン上での機械学習モデルのトレーニングに基づく,新たな"有用な作業の保護"(PoUW)プロトコルについて述べる。
マイナーは、正直なMLトレーニングをした後、新しいコインを作る機会を得る。
我々は、有用な仕事を報い、悪意ある俳優を罰する仕組みを概説する。
論文 参考訳（メタデータ） (2020-01-25T01:10:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。