On Pearl Blockchain's Proof of Useful Work: Systematization and Flexibility

On Pearl Blockchain’s Proof of Useful Work: Systematization and Flexibility

arXiv:2610.25347v1 [cs.CR] 18 Oct 2026

Youlong Ding†

Abstract We revisit the proof-of-useful-work (PoUW) scheme in Pearl blockchain’s white paper (Pearl Research Team), giving a systematic sensitivity characterization as an alternative to its Jackpot policy, along with efficient algorithm for verifying the sensitivity condition. Beyond its independent interest, our characterization yields a more flexible PoUW scheme that eenables miner autonomy: each miner can independently choose its noise magnitude to tailor the trade-off between computational accuracy and mining efficiency to its own needs.

†

The Hebrew University of Jerusalem, Israel. Email: youlong.ding@mail.huji.ac.il.

1

Contents 1 Introduction

3

2 Preliminaries

4

3 Systematic Characterization: Sensitivity Condition

5

4 Efficient Verification of Sensitivity Condition 4.1 Inverting a monotone map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Backward propagation on the evaluation tree . . . . . . . . . . . . . . . . . . . . 4.3 Verification algorithm and analysis . . . . . . . . . . . . . . . . . . . . . . . . . .

5 5 5 6

5 PoUW Scheme Made Flexible

7

2

1

Introduction

We assume that the reader is familiar with Pearl blockchain’s proof-of-useful-work (PoUW) protocol, as described in its white paper [Pea26] (also see [KW25]). In this paper, we focus on the Jackpot policy in [Pea26, Section 5], which aims to prevent miners from exploiting adversarially chosen inputs to perform the prescribed matrix multiplication substantially faster than a generic computation. At a high level, the Jackpot policy consists of four checks: 1. Entry liveness. Limits the fraction of input entries whose magnitudes overwhelm the injected noise, making their quantized values largely predictable. 2. Noise floor. Requires every input row to contain a sufficient amount of noise in quantized units. 3. Tamed products. Limits the fraction of output entries whose accumulation magnitudes are unusually large relative to the noise. 4. Unpredictable summands. Requires most summands to have sufficient variability relative to the accumulator’s numerical precision. While these checks address plausible attack vectors, we identify two limitations: • First, the policy is rather ad hoc: it consists of several separate numerical conditions with carefully chosen thresholds, rather than a unified principle. This makes the policy difficult to understand and its completeness difficult to assess. • Second, the policy prescribes a fixed relative noise magnitude, leaving miners little freedom to tailor the noise to their individual needs. In particular, different miners may prefer different trade-offs between computational accuracy and mining efficiency. Our contributions. We propose a simple and systematic sensitivity condition as an alternative way to characterize the effect of injected noise. Informally, the condition requires that removing any single entry of either noise matrix, while keeping all other entries unchanged, must change the resulting matrix product. We formalize this condition over general finite types, allowing non-associative arithmetic such as floating-point accumulation. We then give an efficient algorithm for verifying the sensitivity condition. For locally monotone operations, our algorithm runs in O(n3 log |S|) time, nearly matching the cost of a single matrix multiplication. The key idea is to propagate intervals backward through the evaluation tree, allowing the effect of every noise entry to be tested without recomputing the matrix product. Beyond its independent theoretical interest, our characterization also enables a more flexible PoUW design through miner autonomy. Rather than imposing a uniform noise magnitude, miners can independently choose their noise levels according to their own priorities. Smaller noise improves computational accuracy but may reduce the likelihood of satisfying the sensitivity condition, whereas larger noise may improve this likelihood at the cost of greater computational error.

3

2

Preliminaries

Definition 2.1 (Chain). A chain is a finite totally ordered set S = {s1 , . . . , sq },

s1 < · · · < sq ,

q ≥ 1.

For L, U ∈ S, L ≤ U , define its interval [L, U ] := {s ∈ S : L ≤ s ≤ U }. Definition 2.2 (Type). A type is a triple (S, ⊕, ⊗), where S is a finite chain and ⊕, ⊗ : S ×S → S are binary operations satisfying the following properties: 1. Commutativity: For all a, b ∈ S, a ⊕ b = b ⊕ a,

a ⊗ b = b ⊗ a.

2. Zero element: There exists a zero element 0 ∈ S such that, for every a ∈ S, a ⊕ 0 = a,

a ⊗ 0 = 0.

Example 2.3. Floating-point arithmetic, e.g., (FP8, +, ×), (FP16, +, ×) is a type. Definition 2.4 (Tree evaluation). Let ⊕ : S × S → S be a binary operation on a chain S. Let T be a binary tree with n leaves. Given a = (a1 , . . . , an ) ∈ S n , we assign the value ai to the i-th leaf. We recursively define the value val(v) of each node v: ( ai , if v is the i-th leaf, val(v) := val(vL ) ⊕ val(vR ), if v has left child vL and right child vR . The tree evaluation is the value at the root: TreeEvalT (a, ⊕) := val(root(T )). Definition 2.5 (n-ary extension of a binary operation). Let (S, ⊕, ⊗) be a type, and let T be a binary tree with n leaves. We define the n-ary extension of ⊕ induced by T as M a := TreeEvalT (a, ⊕), a ∈ S n. T

Definition 2.6 (Local monotonicity). Let S be a chain, f : S n → S. We say that f is locally monotone if, for every i ∈ [n] and every fixed choice of xj ∈ S for j ̸= i, the unary map fi : S → S,

t 7→ f (x1 , . . . , xi−1 , t, xi+1 , . . . , xn )

is either nondecreasing or nonincreasing. Definition 2.7 (Matrix multiplication). Let (S, ⊕, ⊗) be a type, and let T be a binary tree with n leaves. For A, B ∈ S n×n , we define their matrix product A ·T B ∈ S n×n by M
(A ·T B)i,j := Ai,1 ⊗ B1,j , . . . , Ai,n ⊗ Bn,j T

for all i, j ∈ [n]. When T is understood, we simply write A · B. 4

3

Systematic Characterization: Sensitivity Condition

Definition 3.1 (Sensitivity condition). Let (S, ⊕, ⊗) be a type. For A, B, E1 , E2 ∈ S n×n , let C := (A ⊕ E1 ) · (B ⊕ E2 ), where ⊕ is naturally extended by applying it entrywise. We say that the sensitivity condition holds for (A, B, E1 , E2 ) with respect to T if, for every (i, j) ∈ [n]2 , \(i,j)

(A + E1

\(i,j)

) · (B + E2 ) ̸= C,

(A + E1 ) · (B + E2

) ̸= C,

where E\(i,j) denote the matrix obtained from E by replacing its (i, j)-th entry with 0S .

4

Efficient Verification of Sensitivity Condition

There are 2n2 possible noise-entry removals. Recomputing a full matrix product for each takes O(n5 ) time; even recomputing only the affected row or column takes O(n4 ) time. We show that local monotonicity of ⊕ allows all tests to be performed in O(n3 (1 + log |S|)) time. Theorem 4.1 (Efficient verification). Let (S, ⊕, ⊗) be a type, and let T be a binary tree with n leaves. If ⊕ is locally monotone, then the sensitivity condition for any A, B, E1 , E2 ∈ S n×n with respect to T can be verified in O(n3 (1 + log |S|)) time, assuming constant-time operations on S and indexed access to its ordered elements.

4.1

Inverting a monotone map

Our basic tool is an interval inversion procedure that does not need to know the direction of monotonicity. Lemma 4.2 (Interval inversion). Let f : S → S be either nondecreasing or nonincreasing, and let I ⊆ S be an interval. Suppose that x0 ∈ S satisfies f (x0 ) ∈ I. Then f −1 (I) is an interval containing x0 , and its endpoints can be found using O(1 + log |S|) evaluations of f . Proof. For x ≤ y ≤ z, monotonicity implies that f (y) lies between f (x) and f (z). Thus f (x), f (z) ∈ I implies f (y) ∈ I, so f −1 (I) is an interval. Since x0 ∈ f −1 (I), the predicate f (x) ∈ I is false and then true to the left of x0 , and true and then false to its right. Two binary searches on the ordered elements of S therefore find the endpoints, regardless of the monotonicity direction.

4.2

Backward propagation on the evaluation tree

Write X := A ⊕ E1 ,

Y := B ⊕ E2 ,

C := X ·T Y,

where matrix addition is entrywise. Fix an output entry (i, j). Its evaluation tree T has leaf values pk := Xi,k ⊗ Yk,j , k ∈ [n], and root value Ci,j . Evaluate the tree once and store val(v) for every node v.

5

For each node v, let Iv ⊆ S be the set of values that can replace val(v) without changing the root value, while all other parts of the computation remain fixed. In particular, Iroot(T ) = {Ci,j }. If v has left child u and right child w, then Iu = {t ∈ S : t ⊕ val(w) ∈ Iv }, Iw = {t ∈ S : val(u) ⊕ t ∈ Iv }.

(1)

Because ⊕ is locally monotone, each set is the inverse image of an interval under a monotone unary map. Moreover, val(u) ∈ Iu and val(w) ∈ Iw . By Lemma 4.2, both child intervals can therefore be computed in O(1 + log |S|) time. Propagating these intervals from the root to the leaves gives, for each k ∈ [n], the interval Ik of leaf values that preserve Ci,j . Now consider removing one noise entry. Replacing (E1 )i,k by 0 changes only the k-th leaf of this output computation, whose new value is (1)

pi,j,k := Ai,k ⊗ Yk,j . Similarly, replacing (E2 )k,j by 0 gives (2)

pi,j,k := Xi,k ⊗ Bk,j . Consequently, the output entry (i, j) changes under the first or second removal exactly when, respectively, (1) (2) pi,j,k ∈ / Ik or pi,j,k ∈ / Ik . (2) No monotonicity assumption on ⊗ is needed: each candidate leaf value is computed directly.

4.3

Verification algorithm and analysis

Initialize two n × n arrays of counters, d(1) and d(2) , to zero. For each (i, j) ∈ [n]2 , evaluate (1) the corresponding tree and propagate the intervals as in (1). For every leaf k, increment di,k if (1)

(2)

(2)

pi,j,k ∈ / Ik , and increment dk,j if pi,j,k ∈ / Ik . The algorithm accepts if and only if every counter is positive. Proof of Theorem 4.1. The intervals computed by backward propagation have exactly the stated meaning. This holds at the root, and (1) preserves it when passing from a parent to either child while fixing the other child’s value. Thus (2) correctly determines whether removing a noise entry changes the output (i, j). (1) Removing (E1 )i,k can affect only row i of the matrix product. Hence di,k > 0 exactly when this removal changes the output matrix. Likewise, removing (E2 )k,j can affect only column j, (2) and it changes the output matrix exactly when dk,j > 0. Therefore all counters are positive precisely when the sensitivity condition holds. Each output entry requires a forward evaluation of O(n) nodes, a backward traversal with O(1+log |S|) work per node, and O(n) leaf tests. Over all n2 output entries, this takes O(n3 (1+ log |S|)) time. The matrices and counters use O(n2 ) space, and the values and intervals for one tree use O(n) additional space. 6

5

PoUW Scheme Made Flexible

Beyond its independent interest, our systematic characterization enables a desirable feature of the resulting PoUW scheme: miner autonomy. Namely, rather than imposing a uniform noise magnitude rule as in [Pea26], the resulting PoUW scheme allows each miner to choose its own noise level, tailoring the trade-off between computational accuracy and mining efficiency to its individual needs: 1. Smaller noise. A miner prioritizing accuracy may choose smaller noise, reducing the deviation from the original matrix product, but potentially lowering the probability that the sensitivity condition holds. 2. Larger noise. A miner prioritizing mining efficiency may choose larger noise, potentially increasing the probability of satisfying the sensitivity condition at the cost of greater computational error.

Acknowledgements Ding was supported in part by a grant from the Israel Science Foundation (ISF Grant No. 1774/20), and by the European Union (ERC, SCALE,101162665). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.

References [KW25] Ilan Komargodski and Omri Weinstein. Proofs of useful work from arbitrary matrix multiplication. arXiv preprint arXiv:2504.09971, 2025. [Pea26] Pearl Research Team. Pearl floating point scheme specification. Technical report, Pearl Research Labs, September 2026.

7

Related documents

• Study on Blockchain-Based Certificate Verification and Validation#86197
• Proofs and Fundamentals#1331619
• A review of Blockchain Technology applications for financial services#421599
• Decentralized by Design, Centralized by Necessity: The Blockchain-Surveillance Dilemma.#678494
• On the Convergence of Internet of Things and Decentralized Finance: Security Challenges and Future Directions.#847