Polymath

Project

In the Pearl protocol, the MatMul A ⋅ B is computed as (A+E) ⋅ (B+F) where E,F are rank-r matrices. The miner hashes (r ⋅ r) @ (r ⋅ r) intermediate tiles, and peels the noise E(B+F)+A·F to recover A⋅B. For n × n matrices, hashing costs O(n³/r) and peeling is O(n²r), yielding a total of O(n²⋅⁵) additive overhead when r=√n.

Can you devise an alternative secure protocol with lower asymptotic overhead?

One idea (proposed in Appendix A of the paper) suggests a different "random rotation" encoding of A,B, which doesn't require any "noise peeling" at all: Sample a random orthogonal matrix S, ask the miner to compute (A·S) ⋅ (S⁻¹·B) while hashing (lg(n) × n/lg(n)) @ (n/lg(n) × lg(n)) intermediate tiles. To make the multiplication by S cheap (o(n³)), we propose sampling S as a "pseudorandom" rotation, i.e., a randomized Hadamard matrix so that computing AS and S⁻¹B and the entire overhead is O(n² lg(n)). Our conjecture is that for large enough r, the (FFT) structure of S cannot be exploited on intermediate tiles.

Is this PoW rotation-scheme secure?

The protocol described below (which we call "Pearl-GEMM"), is our future candidate for an ultra-low overhead MatMul-PoW algorithm, that works with floating-point (FP8) as well as INT8 datatypes. This protocol no longer preserves exact MatMul, and only outputs an approximate MatMul. Nevertheless, since weight and activation matrices in AI training and inference are typically quantized–a lossy operation by definition–small approximation error is already incurred in the vanilla AI pipeline, provided that the approximation error is sufficiently small. As such, a natural idea is to leverage native quantization noise as the perturbation encoding of A,B for PoW, forcing the miner to commit to the weight+activation matrices pre-quantization (in higher precision). Let us make this more formal.

The idea is simple: Assume A, B are matrices given in some arbitrary datatype, say FP16, and we need to multiply them using a tensorcore of a certain datatype, say FP8. This requires to quantize them to Q(A), Q(B) in FP8 format, and then compute Q(A)·Q(B). As described above, this is not good enough for PoW, as the non-useful miner can submit A = B = 0, and we must apply an encoder incurring enough randomness.

In Pearl-GEMM, we add independent identically distributed (iid) noise matrices E, F to A, B prior to quantization, and use A'·B' = Q(A + E) · Q(B + F) as the approximation to A·B, without applying a decoder. There is a tradeoff between accuracy and security here: If the noise distribution is not "rich enough", it might be possible to come up with cheap schemes for computing Q(A + E) · Q(B + F) for tailored A, B. On the other hand, the approximation error A'·B' − A·B is proportional to the variance of the noise.

Problem: Find a noise distribution that is both secure and results in negligible end-to-end accuracy loss in LLM inference (e.g., in MMLU).

Remark: Ideally, we want Q(A + E) to be an unbiased estimator of A (and same for B), to ensure unbiased gradients in LLM training (as in stochastic rounding).

FP4 is a 4-bit per entry datatype, that can represent the numbers 𝓕 = {0, ±0.5, ±1, ±1.5, ±2, ±3, ±4, ±6}. In order to attain reasonable accuracy using such a small constellation, a common scale γ ∈ R is given to every k entries, where k is typically small. For example, in NVFP4, k = 32 and γ is represented in FP8 E4M3 datatype. To simplify the discussion that follows, we ignore the finite precision of γ and think of it as a real-valued number of infinite precision. Thus, NVFP4 encoding is a mapping f : 𝓕¹⁶ × ℝ → ℝ¹⁶ and the decoding is a mapping g : 𝓕¹⁶ × ℝ → ℝ¹⁶. Because NVFP4 quantization is already quite noisy, adding iid noise matrices E, F prior to quantization (as above) seems to lose too much accuracy. However, it seems plausible that the choice of scales γ opens another dimension for optimization, and may allow to incur enough randomness in A', B' without significant loss of accuracy.

Problem: design an encoder f(A, B, σ) that returns NVFP4 matrices A', B' such that the approximation error A·B − A'·B' is small (so that the end-to-end accuracy is not compromised), and computing A'·B' is "as hard" as multiplying two random NVFP4 matrices of the same shapes.

So far, we have implemented cuPOW only for inference use cases on vLLM (due to its obvious reduced complexity compared to training, which involves more complex dynamics and algorithmic components, and since the commitment hashing can be done in preprocessing time, lowering overhead). On the bright side, one could hope that the training and finetuning processes will be less susceptible to small (unbiased) noise (perturbations of weights and activation matrices). The intuition is the robustness of SGD, which is already a very noisy estimator of the true gradient, yet works fantastically well in practice (enabling minibatch training, arguably the most dominant feature in the scalability of Deep Learning). If true, this could mean that no "denoising" is required in cuPOW (alternatively, that the "no-peeling" Pearl-GEMM scheme will not lose accuracy)

Despite recent success on INT8 training, training is in fact very sensitive to numerical precision (likely due to enormous curvature of the loss function (Hessian condition number). This begs the question:

How does Numerical precision affect training (e.g. LoRA)? Is the price only a few extra epochs?

Note that, for example, in the simpler setting of linear regression or minibatch-PCA, online gradient descent is known to be extremely robust to noise. It would be very interesting to develop numerical scaling laws for finetuning of SoTA LLMs.

The cryptographic commitment hash on the multiplied matrices possesses an inherent overhead in the Pearl protocol, hence it is desirable to minimize its computational fingerprint.

Propose a GPU-compatible cryptographic hash function that is 128-bit collision-resistant, that is not a SoTA hash on CPUs (Blake3, 13.1 int32 ops/input byte)?

Is it possible to base it on matrix multiplications and harness TensorCores?

What about TPU-compatible options?

A notorious feature of Bitcoin's PoW (random hashing) is the emergence of ASIC hardware (produced solely for BTC mining and otherwise useless), which is order-of-magnitudes more efficient in SHA256 hashing than any other commodity hardware, This feature completely eliminated the incentive to mine using GPUs (let alone CPUs), and is the main reason there's no private mining of Bitcoin anymore.

A unique aspect of the Pearl protocol (cuPOW) is that it might, for the first time, create an ASIC-resistant PoW network, where commodity hardware (GPUs, TPUs) is as competitive as any other hardware. This is not a technical statement, but rather an economic one: While designing specialized hardware for multiplying (noisy) all-zero matrices A,B= 0 of size (say) 4096x4096 is viable (IO and silicon savings due to specific dim, etc.), it is very unlikely that such hardware will be able to run real AI workloads (training or inference). Therefore, the economic incentive for developing such ASIC hardware is diminished: The cost-of-production of Pearl tokens via such hypothetical hardware would have to outweigh the external rewards earned by (slower) commodity hardware (i.e., LLM price-per-token, which by free market value already justifies purchasing GPUs).

Question: Is cuPOW ASIC-resistant? How about Pearl-GEMM, Is 1-bit hardware enough to implement Pearl-GEMM(A=0, B=0)? How much speedup (measured in speed-of-light) would such hardware provide, compared to GEMM on H100?

Our team thought of the following candidate alternative protocol for PoW for end-to-end inference tasks, inspired by Pearl-GEMM (problem (2)), yet aims for literally zero computational overhead. The caveat is that this scheme only seems to be applicable to "white-listed" (open-source) models:

This scheme may be vulnerable to backdoors of computing the model faster (e.g. on malicious prompts). Can one base the security of this scheme, or variants thereof, on some simpler concrete assumption.

Another critical problem is that this scheme doesn't have an efficient SNARK (unlike individual linear-layers = MatMul), let alone for FP computation, so an additional challenge is providing an efficient SNARK for the whole LLM computation.

Challenge: As an initial challenge, break the simplified scheme where we do not add noise to the input x. That is, find x for which M'(x) can be computed faster than naively running M'(x). Next, break the actual scheme when also adding noise to the input, or present simpler assumptions under which it is secure.

(I.e., marginal mining cost is 0!).

A basic price attribution to Bitcoins is the cost of mining (i.e, electricity and amortized ASIC costs). in that sense, PoW must "waste" energy in order to attribute value to the coin (Ofc this is merely a lower bound, since actual price is based on network-effects which are hard to model). Indeed, a common criticism of (0-overhead) PoUW is that the marginal cost of mining is ~0 and hence also the cost of attacking the network.

However, the last statement is only true if one has an infinite stream of useful work—i.e., the ability to collect AI workloads for which an external consumer is willing to pay. This observation highlights the difference between Pearl and Bitcoin— the key "scarce" resource in PoUW mining is the ability to collect useful data (matrices). At ~0 overhead, every AI workload on earth should in theory opt-in to mine Pearl (free option call) in which case the hashrate (and hence distribution/entropy) are also maximized.

What should be the value/price of the Pearl coin at 0 mining overhead? Is it 0? infinity?

While the Pearl coin was created to serve as AI-native money (i.e., a Store-of-Value (SoV) digital asset for intelligence), the Pearl blockchain also provides a trustless verifiable historical record of intelligent computing – It will record (encrypted) execution traces of general AI training and inference (from LLMs to AI agents, humanoid robots and self-driving cars). This feature of the blockchain facilitates unique applications. Some examples we thought of are: