Proofs of Useful Work from Arbitrary Matrix Multiplication

• URL: http://arxiv.org/abs/2504.09971v3
• Date: Sat, 19 Apr 2025 09:56:28 GMT
• Title: Proofs of Useful Work from Arbitrary Matrix Multiplication
• Authors: Ilan Komargodski, Itamar Schen, Omri Weinstein,
• Abstract summary: We revisit the longstanding open problem of implementing Nakamoto's proof-of-work (PoW) consensus based on a real-world computational task.<n>We produce a PoW certificate with prescribed hardness and with negligible computational overhead.<n>We conjecture that our protocol has optimal security in the sense that a malicious prover cannot obtain any significant advantage over an honest prover.
• Score: 10.61664303118825
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Lite-PoT: Practical Powers-of-Tau Setup Ceremony [11.689131565202945]
  Zk-SNARKs rely on a one-time trusted setup to generate a public parameter, often known as the Powers of Tau" (PoT) string.<n>The leakage of the secret parameter, $tau$, in the string would allow attackers to generate false proofs, compromising the soundness of all zk-SNARK systems built on it.<n>We present Lite-PoT, which includes two key protocols designed to reduce participation costs.
  arXiv  Detail & Related papers  (2025-03-06T15:34:50Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  We propose two principled algorithms for the test-time compute of large language models.<n>We prove theoretically that the failure probability of one algorithm decays to zero exponentially as its test-time compute grows.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• Unified Breakdown Analysis for Byzantine Robust Gossip [15.69624587054777]
  In decentralized machine learning, different devices communicate in a peer-to-peer manner to collaboratively learn from each other's data.<n>We introduce $mathrmFtext-rm RG$, a general framework for building robust decentralized algorithms.<n>We show an upper bound on the number of adversaries that decentralized algorithms can tolerate.
  arXiv  Detail & Related papers  (2024-10-14T12:10:52Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• Fully Automated Selfish Mining Analysis in Efficient Proof Systems Blockchains [5.864854777864723]
  We study selfish mining attacks in longest-chain blockchains like Bitcoin, but where the proof of work is replaced with efficient proof systems. We propose a novel selfish mining attack that aims to maximize expected relative revenue of the adversary. We present a formal analysis procedure which computes an $epsilon$-tight lower bound on the optimal expected relative revenue in the MDP.
  arXiv  Detail & Related papers  (2024-05-07T15:44:39Z)
• Lossy Cryptography from Code-Based Assumptions [7.880958076366762]
  A proliferation of advanced cryptographic primitives imply hard problems in the complexity class $SZK$. This poses a barrier for building advanced primitives from code-based assumptions. We propose a new code-based assumption: Dense-Sparse, that falls in the complexity class $BPPSZK$ and is conjectured to be secure against subexponential time adversaries.
  arXiv  Detail & Related papers  (2024-02-06T02:17:08Z)
• DAG-Sword: A Simulator of Large-Scale Network Topologies for DAG-Oriented Proof-of-Work Blockchains [2.0124254762298794]
  We focus on DAG-based consensus protocols and present a discrete-event simulator for them. Our simulator can simulate realistic blockchain networks created from data of a Bitcoin network. We extend the results of the related work that contains a small-scale network of 10 nodes by the results obtained on a large-scale network with 7000 nodes.
  arXiv  Detail & Related papers  (2023-11-08T12:31:11Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Solving the sampling problem of the Sycamore quantum circuits [6.0604034858265345]
  We study the problem of generating independent samples from the output distribution of Google's Sycamore quantum circuits with a target fidelity. We propose a new method to classically solve this problem by contracting the corresponding tensor network just once. For the Sycamore quantum supremacy circuit with $53$ qubits and $20$ cycles, we have generated one million uncorrelated bitstrings.
  arXiv  Detail & Related papers  (2021-11-04T17:13:09Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  We study the fundamental task of list-decodable mean estimation in high dimensions. Our algorithm runs in time $widetildeO(ndk)$ for all $k = O(sqrtd) cup Omega(d)$, where $n$ is the size of the dataset. A variant of our algorithm has runtime $widetildeO(ndk)$ for all $k$, at the expense of an $O(sqrtlog k)$ factor in the recovery guarantee
  arXiv  Detail & Related papers  (2020-11-19T17:21:37Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  We study a constrained contextual linear bandit setting, where the goal of the agent is to produce a sequence of policies. We propose an upper-confidence bound algorithm for this problem, called optimistic pessimistic linear bandit (OPLB)
  arXiv  Detail & Related papers  (2020-06-17T22:32:19Z)
• Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewards [59.559028338399855]
  We consider the problem of sleeping bandits with action sets and adversarial rewards. In this paper, we provide a new computationally efficient algorithm inspired by EXP3 satisfying a regret of order $O(sqrtT)$.
  arXiv  Detail & Related papers  (2020-04-14T00:41:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.