On the Feasibility of Proof-of-Useful-Work via Number Theoretic Transform Micro-Tasks
A preliminary exploration of whether the computational waste inherent in proof-of-work consensus might be partially redirected towards precomputations useful to zero-knowledge proving systems. We wish to stress that what follows is speculative. We have no settled answers, only what we hope is an interesting set of questions.
1. The Problem
Proof-of-work, for all its virtues — and they are considerable, as anyone who has studied the history of distributed consensus will attest — has one property that has long troubled its proponents: the work itself is, from an external perspective, entirely useless. The hash function is evaluated trillions of times per second across the Bitcoin network, and the result of each evaluation is discarded the moment it is found not to satisfy the difficulty target. The thermodynamic cost is real; the useful output is nil.
This state of affairs has motivated a long and largely unsuccessful search for “proof-of-useful-work” schemes. The difficulty, as we shall discuss, is not in finding useful computations — the world is full of those — but in finding useful computations that can be embedded into a consensus mechanism without degrading its security or fairness properties.
We explore one narrow corner of this design space: whether micro-scale Number Theoretic Transform (NTT) computations, which are core primitives in modern zero-knowledge proving systems, can be attached to proof-of-work block production in a way that produces a cumulative, publicly useful dataset.
We emphasise at the outset that we are not proposing a change to Bitcoin, nor to any existing production system. This is a research note, and a fairly tentative one at that.
2. Why Number Theoretic Transforms?
The NTT is a finite-field analogue of the Fast Fourier Transform. It reduces the cost of polynomial multiplication from O(n^2) to O(n log n), and it is ubiquitous in the arithmetic of zero-knowledge proof systems. Every zk-SNARK, STARK, Halo2, and Plonky2 proof involves, at some level, a great many NTT evaluations over carefully chosen prime fields.
Two properties make NTTs potentially suitable for our purposes.
First, there is no shared global dataset. Each proving system computes its own parameters from scratch. There is no analogue of the folding@home protein database or the SETI signal archive. Every NTT result is recomputed, identically, by every participant in the system, and then discarded. If these results could be precomputed and stored, they would constitute a genuinely novel public resource — or so the argument goes.
Second, individual NTT evaluations are small and fast. An NTT-64 or NTT-128 computation completes in under a millisecond on commodity hardware. Verification — checking that the claimed output is the correct transform of the claimed input — is even cheaper. This makes it plausible, at least in principle, to treat each evaluation as an atomic “micro-task” that can be embedded into block production without materially affecting block times.
Whether this plausibility survives contact with reality is, of course, another matter entirely.
3. The Design Principle: PoW First, Useful Work Second
The most important constraint in any proof-of-useful-work design is that the useful work must not compromise the security of the underlying consensus. We state this principle in its strongest form: the block producer must solve the proof-of-work puzzle first. Only then are useful-work tasks attached, as secondary commitments, to the block.
The useful work is, in effect, a sidecar. It rides along with the block but does not influence block eligibility. This means that consensus security remains entirely dependent on the hash puzzle, which we understand well and which has withstood over fifteen years of adversarial scrutiny.
We recognise that this is a somewhat deflationary approach. A more ambitious design would intertwine the useful computation with the proof-of-work itself, so that the hash puzzle could not be solved without also producing useful output. Such designs exist in the literature. They are, in our judgement, considerably more fragile, and we prefer to begin with something more conservative even if it yields less useful work per block.
4. Preventing Hardware Centralisation
If useful work is rewarded — whether through protocol incentives, royalties, or mere reputation — there is a natural incentive to build specialised hardware for it. This would be counterproductive. One of the virtues of proof-of-work is that, while ASICs exist, the hash function itself is simple enough that the barrier to entry is reasonably well-understood. If we introduced a useful-work component that favoured narrow, fixed-function hardware, we would risk creating a new axis of centralisation.
We propose four mitigations, though we are not fully confident that any of them is sufficient.
Cross-parameter binding. Each block requires not a single NTT computation, but a bundle of K tasks drawn from different domains: distinct prime fields (e.g., the Mersenne-like primes near 2^64 and 2^128), different transform lengths (64, 128, 256), and mixed task types (forward NTT, inverse NTT, polynomial multiplication). The intent is to force flexibility — a chip that accelerates NTT-64 over one specific modulus would gain no advantage on the remaining K-1 tasks.
Pseudorandom parameter rotation. The precise parameters for each block’s task bundle are derived deterministically from the parent block hash. Since miners cannot predict the block hash before finding the proof-of-work solution, they cannot precompute the tasks. This eliminates the advantage of large-scale offline computation.
Bounded verification cost. Each micro-task must be verifiable in well under a millisecond. This ensures that full nodes — which are not expected to possess specialised hardware — can verify the useful-work commitments without their resource requirements increasing materially. If verification were expensive, the useful work would effectively be unverified, which would rather defeat the purpose.
Commit-and-challenge model. Results are committed as Merkle roots in the block header. Verifiers can challenge and sample-check individual leaves without re-executing the entire bundle. This is a standard technique, but it is worth noting that it provides only probabilistic guarantees: a dishonest miner who falsifies a small fraction of results is unlikely to be caught by random sampling.
5. Task Structure and Data Model
The question of how to partition useful work into atomic units is deceptively subtle. The unit must be small enough to fit within block production timescales, large enough to be meaningful, and structured enough to be indexable and retrievable after the fact.
We define the atomic unit as a single NTT evaluation of a specific length over a specific prime field. A block’s useful-work payload is a bundle of K such units, with their parameters determined by the block hash as described above. The raw results are stored off-chain — on IPFS, Filecoin, or whatever distributed storage happens to be convenient — and indexed by their cryptographic commitment.
The hope is that, over time, these micro-results accumulate into a library of precomputed NTT evaluations that zero-knowledge proof systems can draw upon. Whether this library would actually be useful in practice is an empirical question that we cannot answer here. ZK proving systems tend to have highly specific parameter requirements, and there is no guarantee that the parameters selected by our pseudorandom rotation would coincide with those needed by any particular prover. We mention this caveat because it is the sort of thing that is easy to overlook in the enthusiasm of a new proposal.
6. On the Question of Incentives
We are unsure about the incentive model, and we wish to say so plainly.
The simplest approach is to offer no direct protocol incentive for useful work at all. Miners produce it as a best-effort contribution, and the resulting dataset is a public good. This is clean but, we suspect, insufficient: without incentive, compliance would be low and data quality unreliable.
A more complex approach involves royalties: when an external user — say, a rollup operator — retrieves and uses a batch of precomputed NTT results, a micropayment is routed back to the original miner. This is appealing in theory but raises formidable engineering questions. How are usage events tracked? How is the royalty rate determined? How are disputes resolved? We have no answers to these questions, and we suspect that the incentive design may prove harder than the cryptographic design.
7. Open Questions
We collect here the questions that we have not been able to resolve to our own satisfaction.
How should K (tasks per block) be calibrated? Too few tasks produce negligible useful output; too many impose an unacceptable verification burden on full nodes. The optimal value likely depends on the specific chain’s block time and validator hardware profile, which makes it difficult to generalise.
Could specialised but non-dominant hardware — GPU libraries optimised for small NTTs, for instance — tilt the fairness landscape? Our mitigations target fixed-function ASICs, but a sufficiently well-optimised GPU implementation might still command an outsized advantage without being an ASIC in the traditional sense.
Is there a way to align the pseudorandomly generated task parameters with the actual needs of existing ZK proving systems? Without such alignment, the dataset risks being voluminous but useless — a library of answers to questions nobody asked.
What happens to the dataset if the chain ceases to exist? The off-chain storage assumption introduces a durability dependency that is not present in pure proof-of-work systems.
Concluding Remarks
We have outlined a speculative design for embedding useful NTT computations into proof-of-work block production. The design is conservative in the sense that it does not modify the consensus mechanism itself; useful work is strictly secondary. It is ambitious in the sense that it aims to produce a durable, publicly accessible cryptographic dataset as a byproduct of mining.
We are not confident that the idea works as described. The centralisation mitigations may be insufficient, the incentive model is underspecified, and the utility of the resulting dataset remains unproven. But we think the question is worth asking, and we offer these notes in the hope that others with more experience in ZK system design and mining economics might point out what we have missed.