PaperlayerView exact revision on arXiv

Source-linked AI summary

Proofs of Useful Work from Arbitrary Matrix Multiplication

Ilan Komargodski, Omri Weinstein

arXiv:2504.09971v4cs.CR

TL;DR

Useful proof of work remains elusive when miners choose their own inputs, and conventional Bitcoin mining is criticized for its energy use. This paper proposes a PoUW protocol based on arbitrary matrix multiplication, with 1+o(1) overhead; its security analysis relies on a hardness conjecture, and adapting the protocol to Strassen-like algorithms is left outside the paper’s scope.

  • Problem

    A truly useful PoUW protocol for tasks whose instances are chosen by miners has remained elusive, against a backdrop of energy-intensive Bitcoin mining.

    Source: §1 · pp. 2–3

  • Method

    The protocol uses the transcript of a miner’s matrix multiplication, with unpredictable perturbations that can be removed to recover the original output.

    Source: §1.1 · p. 3, §2 · p. 6, §6.2 · p. 13

  • Results

    1+o(1) multiplicative overhead over the worst-case time for matrix multiplication is reported for producing a verifiable PoW certificate.

    Source: §1.1 · p. 3, §2 · p. 6

  • Takeaways & Limitations

    Matrix multiplication’s role as a bottleneck in AI training and inference makes it a potentially valuable workload for useful proof of work.

    Source: §1.1 · p. 3

    A cuPOW analogue for Strassen-like fast matrix multiplication is outside the paper’s focus, although the security analysis considers such algorithms as attacks.

    Source: §1.1 · p. 4

Abstract

from arXiv · show

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.

1 Introduction

The paper addresses the lack of a truly useful proof-of-work protocol in which miners choose their own task instances, and presents a matrix-multiplication protocol with near-optimal overhead. It also frames matrix multiplication as economically valuable work and contributes a framework for comparing proofs of work.

1 Introduction

  • A truly useful PoUW remained elusive because prior approaches did not provide a useful, efficient protocol for instances chosen by the miner.Ball et al.’s proposal required solving poly-logarithmically many instances for one proof, failed the stated efficiency property, and later retracted its usefulness claims.Source: §1 · p. 3

1.1 Our Contributions

  • The proposed PoUW uses miners’ arbitrary matrix multiplications to produce Nakamoto-style PoW certificates with 1+o(1) multiplicative overhead over the worst-case computation time.For square matrices with naïve multiplication as baseline, the stated cost is (1+o(1))n^3.Source: §1.1 · p. 3
  • Matrix multiplication is presented as economically valuable work because it is a bottleneck in AI training and inference and underlies other applications.The paper also identifies vector databases, quantum simulations, graphics rendering, and statistical physics as applications.Source: §1.1 · p. 3
  • The protocol’s security relies on a conjecture about solving batches of correlated low-rank random linear equations; under it, comparable-runtime adversaries gain no non-trivial advantage.The paper states that even multiplying zero matrices is as hard as any other product under the protocol.Source: §1.1 · p. 4
  • The paper contributes a non-trivial formal definition and framework for reasoning about and comparing computational-task proof-of-work schemes.It describes this as an independent contribution.Source: §1.1 · p. 4

1.2 Related Work

  • Proof-of-stake and proof-of-space avoid energy waste but shift waste to other resources and introduce new economic and cryptographic tradeoffs.Trapdoor-matrix speedups have a different goal: PoW seeks uniform hardness even for parties choosing inputs, with computation performed locally and no hidden trapdoors.Source: §1.2 · p. 4

2 Overview of our PoUW

The overview develops a matrix-multiplication PoUW that returns the useful product while using computation transcripts to make the work difficult to shortcut. Its near-optimal prover overhead is paired with a hardness conjecture about computing correlated random subproblems.

Proof and verification

  • Solve outputs the product and a proof, but naive verification repeats the prover’s work; SNARKs can delegate that check, with zkSNARKs available for input privacy.The proof is described as o(t(n)) in size.Source: §2 · pp. 5, 8

Why the initial construction fails

  • The uniform-noise baseline is not useful: recovering A·B adds two generic products, making honest work roughly three products while a malicious prover needs one.The baseline hashes a noisy product whose randomness gives the desired acceptance probability, but its noise is costly to remove.Source: §2 · pp. 5–6

Low-rank noise

  • Low-rank noise can be removed in O(n²·r) time, asymptotically less than standard matrix multiplication when r ≪ n.The noise matrices are formed as products of n × r and r × n matrices.Source: §2 · p. 6

Why low-rank noise alone fails

  • Low-rank noise alone permits a shortcut: with A = B = 0, an attacker can multiply E and F in roughly O(n²·r) time.This is much faster than the honest O(n³) computation, or n^ω with fast matrix multiplication.Source: §2 · p. 6

Transcript-based hardness

  • Hashing the computation transcript rather than the product output makes intermediate computations the source of proof-of-work hardness.The approach encodes noise in the inputs and enforces unpredictability in the transcript.Source: §2 · pp. 5–7

Prover efficiency and correctness

  • The prover returns C = A·B and accepts with probability ϵ, while its runtime is tr(n)·(1+o(1)), dominated by transcript computation.Steps 1 and 4 take O(n²·r); transcript computation is the dominant term.Source: §2 · p. 7

Hardness assumption

  • Hardness is conjectured to require essentially the full transcript computation, because exploiting correlations among random low-rank subproblems is conjectured as difficult as matrix multiplication.The security argument assumes no noticeable speedup in computing the transcript of a product of two random rank-r matrices.Source: §2 · p. 7

Memory complexity

  • Storing the whole transcript uses significant memory; hashing intermediates separately can reduce that need and make puzzle attempts scale with matrix size.The intermediate-matrix approach also supports systems handling varying matrix sizes.Source: §2 · pp. 7–8

3 Open Problems and Future Directions

The open problems ask how far efficient PoUW can extend beyond matrix multiplication, how its noise and security assumptions can improve, and whether more standard assumptions can support it.

Generalizing PoUW

  • The paper asks which tasks beyond matrix multiplication admit PoUW with 1+o(1) overhead, noting that some candidates lack a natural decomposition into subproblems.Examples include linear equations, graph search and routing, and database or string problems.Source: §3 · p. 8

Alternative noise schemes

  • Alternative noise schemes may improve overhead or security assumptions; a self-canceling candidate offers O(n² log n) overhead for certain dimensions but applies only to high-rank matrices.It relies on a more subtle security assumption than Algorithm 6.4.Source: §3 · p. 8

Provable security

  • The paper leaves open whether useful-operation PoUW can be proved secure under more standard or well-studied assumptions.General-purpose program obfuscation is given as one example of a possible assumption.Source: §3 · p. 9

4 Preliminaries

The preliminaries specify the paper’s notation, random-oracle model, and complexity accounting.

Notation

  • The notation defines [n] as {1, …, n}, ← as uniform or distributional sampling, and U_m as uniform over {0,1}^m.The meaning of ← depends on whether the subscript denotes a set or a distribution.Source: §4 · p. 9

Random-oracle model

  • The paper assumes the random-oracle model, where a query counts as one operation; it says the model can be heuristically replaced by a cryptographic hash function.SHA-256 and BLAKE3 are named as examples.Source: §4 · p. 9

Complexity

  • Complexity is counted separately by random-oracle queries and arithmetic operations over a field F_q supporting addition and multiplication.Source: §4 · p. 9

5 Definitional Framework for Proofs of Useful Work

A proof of useful work lets a prover certify effort on a task of its choice while keeping honest solving efficient and making faster forgery difficult. The section defines this goal and contrasts it with a trivial construction whose overhead or prover advantage makes it unsuitable for useful work.

5 Definitional Framework for Proofs of Useful Work

  • PoUW must support useful computation on arbitrary inputs, keep honest solving close to task-solving cost, and require comparable work to generate acceptable proofs.Classical PoW lacks the usefulness condition because its challenge instances are random and detached from a task someone wants solved.Source: §5 · p. 9
  • The framework models solving and verification as algorithms over a task instance and proof; a public seed makes the work fresh and prevents preprocessing.The protocol may be viewed as interactive or non-interactive; the paper assumes the random-oracle model and notes that Fiat–Shamir can remove interaction.Source: §5 · pp. 9–10
  • The definition parameterizes prover overhead and difficulty, while stronger security notions include parallel amortization and streaming challenges.The paper focuses on a simpler security definition in the main text and conjectures that the protocol satisfies the stronger properties associated with Bitcoin PoW.Source: §5 · pp. 10–11
  • Both instance size and success probability are tunable in the final protocol, and the intended overhead is sublinear in task-solving time.The paper identifies negligible overhead as the interesting regime, since a constant-multiplicative-overhead construction is trivial for any task.Source: §5 · p. 11

5.1 A (Trivial) PoUW for Any Function

  • The trivial construction solves the task independently, then searches random-oracle nonces; it achieves overhead α = c and difficulty ϵ = 1 − e^−c.Its verifier runs in ˜O(1) time.Source: §5.1 · pp. 11–12
  • The trivial construction is not useful: its honest prover has linear overhead, or a nonce-only adversary gains a linear runtime advantage.Increasing c can make the adversary’s advantage sublinear, but raises honest-prover complexity to a factor (1 + c) above task-solving complexity.Source: §5.1 · p. 12

6 A PoUW for Matrix Multiplication

This section develops a matrix-multiplication PoUW from transcript-unpredictable encodings, then gives a parameterized construction whose overhead is negligible under its stated hardness assumption. It also contrasts this construction with a less efficient first instantiation and analyzes the noise matrices.

6 A PoUW for Matrix Multiplication

  • The section presents protocols for multiplying matrices over Fq, with the second construction claimed to be optimal under a new algorithmic conjecture.The first protocol improves on the generic construction but is not optimal.Source: §6 · p. 12

6.1 The Canonical MatMul Algorithm

  • For n × n multiplication, the canonical algorithm computes tiled intermediate values; fast square or rectangular algorithms can improve asymptotic cost, though direct multiplication is often practically fastest.The section assumes r divides the matrix dimensions.Source: §6.1 · p. 13

6.2 A Transcript Unpredictable Encoding Scheme

  • The encoding injects noise so the perturbed computation's transcript has non-trivial entropy, while decoding removes that noise to recover the original product.The two required properties are correctness and transcript unpredictability: recovering the product must coexist with requiring direct computation to learn transcript pieces.Source: §6.2 · pp. 13–14

6.3 From Transcript Unpredictability to a PoUW

  • Computing the whole transcript requires essentially tMatMul(n), so transcript unpredictability yields hardness against provers running in less time, except with probability at most ϵ.The hardness argument follows directly from the encoding's transcript-unpredictability property.Source: §6.3 · p. 14, A PoUW for Matrix Multiplication with… · p. 15

6.4 A First Instantiation

  • The first instantiation uses r=1 and random self-reducibility, but a malicious solver can skip decoding, leaving honest-prover overhead at least 3.Completeness follows by subtracting the correction term C′′ from C′ to recover A · B.Source: §6.4 · p. 15

6.5 A Second Instantiation

  • The second instantiation uses parameterized random self-reducibility and assumes computing all intermediate values for random rank-r matrices takes Ω(n^ωr+1/r) time.The section argues that low-rank structure does not yield a faster way to compute all intermediates than the general-purpose algorithm.Source: §6.5 · pp. 15–16
  • α(n)=o(1) unless fast matrix multiplication is used; the second instantiation makes the honest solver perform exactly one n × n matrix product.Its other Encode and Decode products cost O(n² · r); the overhead claim relies on the assumption about computing intermediate values.Source: §6.5 · p. 16

6.5.1 Properties of our Noise Matrices

  • The noise-generation method yields matrices uniformly distributed among n × n matrices of rank r, with very small statistical error.With very high probability, every r × r submatrix is marginally uniform.Source: §6.5.1 · p. 17

7 Using Native AI Workloads for Blockchain Consensus

Matrix multiplications are central to neural-network training and inference, where they dominate computational work. The section discusses reusing native workloads and possible reductions in protocol overhead.

7 Using Native AI Workloads for Blockchain Consensus

  • Training and inference combine matrix multiplications with other operations, including activations, normalization, rounding, and weight updates.Training also uses matrix multiplications in gradient calculation and forward propagation.Source: §7 · pp. 17–18
  • For inference, public weight matrices may be hashed in advance; for training, commitments may be reused across layers by recomputing needed matrices.The authors present these as ideas for reducing cuPOW overhead in AI workloads.Source: §7 · p. 18
  • Matrix multiplication accounts for at least 50% and often 70–80% of total computational load in typical neural-network training scenarios.The estimate is based on the authors' experiments and benchmarks.Source: §7 · p. 18

A A Self-Canceling Noise Scheme

The appendix describes a self-canceling-noise PoUW scheme using pseudorandom rotations. Its prospects depend on hardness assumptions and constraints on the matrices and rotation parameters.

A A Self-Canceling Noise Scheme

  • Pseudorandom rotations allow the scheme to avoid decoding noise, because R R⊤ cancels at the output, though not locally on intermediate tile partial sums.The proposed rotations include a randomized Hadamard transform that can be applied in O(n² log n) time.Source: A A Self-Canceling Noise Scheme · p. 20
  • The scheme is useless for all-zero input matrices; the authors require high-rank inputs, which they say can be ensured by adding a random permutation of the identity matrix.Under this condition, they simplify the discussion to A = B = I_n and use the FastJL transform's tile-embedding property.Source: A A Self-Canceling Noise Scheme · p. 20
  • Choosing block size d=r ensures full marginal entropy for each r × r tile, but raises runtime to O(n²(r + log n)), no faster than the earlier scheme.The authors conjecture that constant block size remains computationally hard without massive preprocessing.Source: A A Self-Canceling Noise Scheme · p. 21
  • The authors conjecture that computing all partial sums remains costly for r=√n and constant block size, even with O(n³) preprocessing.The conjecture concerns full-rank matrices and the partial sums in the proposed scheme.Source: A A Self-Canceling Noise Scheme · p. 21

B Proof of Useful Work as a Poisson Process

This appendix defines PoUW mining in terms of Poisson-distributed accepted proofs and a bound on adversarial advantage. It explains the Poisson model through Bitcoin's independent hash trials.

B Proof of Useful Work as a Poisson Process

  • A Poisson process models independent events occurring at a constant average rate, with exponentially distributed inter-arrival times.The appendix cites Bitcoin's 10-minute block-generation rate as an example.Source: B Proof of Useful Work as a Poisson… · p. 21
  • A PoUW for blockchains requires honest accepted-proof events to form a Poisson process and adversarial mining to satisfy the definition's corresponding condition.The process samples a random σ_i and lets the miner choose x_i and data_i.Source: B Proof of Useful Work as a Poisson… · p. 22
  • Bitcoin's random-oracle model makes successful hash evaluations binomial over a finite interval, approximating a Poisson process with rate ρ = (R · T · κ)/2^λ.The difficulty parameter κ is adjusted so ρ = 1/600, corresponding to one block every 10 minutes in expectation.Source: B Proof of Useful Work as a Poisson… · p. 22

Bitcoin from our PoUW.

The authors argue that PoUW for blockchains, combined with standard cryptographic hash properties, can establish Bitcoin-backbone security. They instantiate Bitcoin’s public-ledger functionality by using PoUW in place of signatures of work.

Bitcoin from our PoUW.

  • PoUW combined with standard cryptographic hash properties can establish the security of the Bitcoin backbone protocol.The proof follows, instantiating signatures of work with PoUW.Source: Bitcoin from our PoUW · p. 22
  • The proposed instantiation provides the same functionality as Bitcoin: a public ledger.Source: Bitcoin from our PoUW · p. 22
  • The security proof follows by instantiating signatures of work with PoUW.Source: Bitcoin from our PoUW · p. 22

C Unpredictable Encodings

The section generalizes transcript-unpredictable encodings into unpredictable encoding schemes (UES), a form of instance-optimal randomized encoding with distinct properties. UES combines correctness, near-optimal running time, and fine-grained hardness.

C Unpredictable Encodings

  • Unpredictable encoding schemes (UES) generalize transcript-unpredictable encodings, which suffice for PoUW for matrix multiplication.The UES abstraction is proposed as potentially independently interesting.Source: C Unpredictable Encodings · p. 22
  • A UES is an instance-optimal randomized encoding with properties new and incomparable to classical randomized encodings.For function f, Encode probabilistically maps input x to an encoding, and Eval deterministically maps that encoding to output y.Source: C Unpredictable Encodings · p. 23
  • Correctness requires Eval(Encode(x)) = f(x) for every x.Source: C Unpredictable Encodings · p. 23
  • Encode plus Eval must run in t(n) · (1 + o(1)) time, where t(n) is the canonical algorithm’s worst-case running time.Source: C Unpredictable Encodings · p. 23
  • For every input and time-t′(n) algorithm, the probability of producing its random encoding is at most C · (t′(n)/t(n)).This is the scheme’s fine-grained hardness requirement.Source: C Unpredictable Encodings · p. 23
  • Classical randomized encodings provide privacy, while UES instead requires fine-grained hardness and optimal efficiency.Transcript unpredictability is the special case where the encoding is essentially the canonical matrix-multiplication transcript on encoded matrices.Source: C Unpredictable Encodings · p. 23
Loading 2504.09971v4…