[Cryptography] Prime-based proof-of-work and Nashian cooperative mining (paper for comments)

[Christoph Gruber]

Critical Review: Prime Mining as Cooperative Proof-of-Work

Review of: “Prime Mining as Cooperative Proof-of-Work: A Nashian Blockchain Based on Deterministic Prime Discovery”
Authors: Ovanes Oganisian, Semion Oganisian, Yury Oganisian

The paper proposes a blockchain architecture where proof-of-work consists of discovering consecutive prime numbers rather than solving hash puzzles. While the fundamental idea of replacing wasteful computation with mathematically meaningful work is appealing, the proposal suffers from critical cryptographic weaknesses, scaling impossibilities, and fundamental misunderstandings of algebraic number theory. The economic model lacks intrinsic value proposition, and the game-theoretic analysis claiming “Nashian equilibrium” is superficial at best.
This review identifies the proposal as an interesting academic thought experiment that fails to meet the requirements for a viable cryptocurrency protocol.
1. Fundamental Scaling Problems

1.1 Prime Gap Growth
The average gap between consecutive primes near p grows as ln(p). While this seems manageable initially, the real problem lies elsewhere: the computational cost of proving primality grows superlinearly with the size of the prime.
1.2 Primality Certificate Complexity
The paper suggests using ECPP or Pratt certificates for deterministic primality proofs. Both approaches become prohibitively expensive at scale:
Pratt Certificates require the complete factorization of p-1. For large primes, factoring p-1 is itself a computationally hard problem. The certificate size grows as O(log2 p), but generating it requires solving multiple factorization subproblems.
ECPP (Elliptic Curve Primality Proving) runs in O(log6 p) under heuristic assumptions. For primes beyond 101000, this becomes impractical. The largest ECPP-certified prime to date has approximately 50,000 digits. A blockchain that mints primes sequentially would exhaust practical certificate generation within years.
The paper’s claim that “verification is cheap while mining is expensive” breaks down as primes grow. Certificate verification complexity approaches certificate generation complexity for sufficiently large primes.
1.3 Storage Requirements
Each wallet must store a coefficient vector with dimension equal to the number of mined primes. After mining the first million primes (reaching approximately 15 million), every wallet requires storage for one million fractional coefficients. The “headline integer” optimization does not solve this: it merely provides membership encoding while the full vector remains necessary for transaction validation.
2. Cryptographic Weaknesses

2.1 Incomplete Protocol Specification
The paper mentions “previous_block_hash” in the block structure but never specifies:
Which hash function is used
What data is included in the hash preimage
How the hash chain provides tamper resistance
Without a cryptographic hash function binding blocks together, the ledger lacks integrity guarantees against historical manipulation.
2.2 Signature Scheme Omission
The paper references “digital signatures” for transactions and composite proofs but specifies no signature algorithm. Critical questions remain unanswered:
Which signature scheme (ECDSA, EdDSA, RSA)?
What curve parameters or key sizes?
How are addresses derived from public keys?
2.3 Quantum Vulnerability
Shor’s algorithm reduces integer factorization to polynomial time on a quantum computer. This renders the entire composite-proof infrastructure worthless: any quantum-capable adversary could generate all composite proofs for an interval instantly.
More critically, if the (unspecified) signature scheme uses ECDSA or RSA, wallet security collapses entirely under quantum attack. The paper does not address post-quantum considerations.
2.4 No Formal Security Proofs
The security analysis in Section 8 consists of informal arguments rather than cryptographic proofs. Claims such as “finality is immediate” and “forks cannot be sustained” lack formal treatment. A rigorous security model would require:
Formal adversary definitions
Computational hardness assumptions
Reduction proofs to established problems
3. Game-Theoretic Deficiencies

3.1 Misuse of “Nashian” Terminology
The paper repeatedly invokes Nash equilibrium without providing formal game-theoretic analysis. No utility functions are defined, no strategy spaces are specified, and no equilibrium proofs are given.
The claim that “honest participation strictly dominates strategic deviation” is asserted but never proven. In fact, several profitable deviation strategies exist:
3.2 Composite Proof Withholding
A miner who discovers the next prime has strong incentive to:
Withhold composite proofs found during the search
Submit them under multiple pseudonymous addresses
Claim both the prime reward (50%) and a significant share of composite rewards
The paper’s Sybil resistance argument (“rewards are per integer, not per identity”) misses this attack vector entirely.
3.3 Volatile Incentive Structure
The 50/50 split between prime finder and composite provers creates highly volatile reward distributions:
For twin primes (gap = 2), composite rewards are minimal
For large gaps (Cramér gaps can reach (ln p)^2), composite rewards dominate
This volatility discourages consistent participation and may lead to mining pool centralization around prime discovery rather than the claimed decentralization.
3.4 Front-Running Composite Proofs
The gossip network design allows nodes to observe incoming composite proofs and potentially front-run them by broadcasting the same proof with their own address. The paper acknowledges “only the first valid proof” is accepted but provides no mechanism to establish temporal ordering in an asynchronous network.
4. Number-Theoretic Errors

4.1 Extension Chain Misconception
The paper proposes “extension chains in algebraic number rings such as Z[sqrt(d)] or O_K” for advanced proof-of-work. This reveals a fundamental misunderstanding of algebraic number theory.
Most algebraic integer rings do not have unique factorization.
Only rings with class number h = 1 are unique factorization domains. The concept of “the next irreducible element ordered by increasing absolute norm” is not well-defined in rings where factorization is non-unique.
Example: In Z[sqrt(-5)]:
6 = 2 * 3 = (1 + sqrt(-5)) * (1 - sqrt(-5))
Both factorizations are valid and irreducible. Which “comes next”? The question is meaningless.
The paper cannot simply “define mining over O_K” without addressing:
How to handle non-principal ideals
How to order elements with equal norm
How to define “primality” when unique factorization fails
4.2 Norm Ordering Ambiguity
Even in rings with unique factorization (e.g., Gaussian integers Z[i]), ordering by norm is ambiguous. Multiple irreducible elements share the same norm. The paper provides no tie-breaking mechanism.
5. Economic Model Failures

5.1 Absence of Intrinsic Value
The paper constructs an elaborate ownership model without establishing why anyone would want to own fractional shares of prime numbers. Bitcoin’s value proposition connects to network security and computational commitment. Here, “0.1 of prime 29” represents nothing beyond itself.
The paper states that prime assets are “mathematically grounded” but mathematical existence does not create economic value. The digits of pi are mathematically grounded; they are not valuable as currency.
5.2 Deflationary Collapse
Asset creation rate decreases over time as primes become sparser. The prime number theorem gives approximately n/ln(n) primes below n. New asset creation becomes vanishingly rare, creating extreme deflationary pressure incompatible with use as a medium of exchange.
5.3 Transaction Fee Absurdity
The fee model requires payment “in fractions of primes the sender owns.” This creates bizarre scenarios:
A wallet holding only large primes must pay fees in those primes
Fee amounts are not fungible across users
Market-making becomes impossible without holding many different primes
6. Missing Specifications

A viable cryptocurrency whitepaper requires concrete specifications. This paper omits:
Component    Status
Hash function    Unspecified
Signature algorithm    Unspecified
Address derivation    Unspecified
Fractional precision    Unspecified
Network message encoding    Unspecified
Reward formula constants    Arbitrary (50/50)
Minimum factor threshold    “Configurable”
Primality certificate format    Named but not specified
Gossip protocol details    Sketched only
7. Comparison with Existing Work

The paper does not cite or compare against existing “useful proof-of-work” proposals:
Primecoin (2013): Actually implemented prime-finding PoW, discovered its limitations
Proof of Useful Work literature: Extensive academic work on this problem
Verifiable Delay Functions: Modern approach to deterministic computational puzzles
The claim of novelty is undermined by failure to engage with prior art.
8. Conclusion

The paper presents an intellectually interesting but practically unviable proposal. The core issues are:
Cryptographic incompleteness: Missing hash functions, signature schemes, and security proofs
Scaling impossibility: Primality certificates become prohibitively expensive
Quantum vulnerability: No post-quantum considerations
Number-theoretic errors: Extension chains fundamentally misconceived
Economic vacuity: No intrinsic value proposition
Game-theoretic superficiality: “Nashian” claims without formal analysis
The proposal is unsuitable for implementation as a cryptocurrency protocol. It may have value as an academic discussion of alternative proof-of-work mechanisms, but would require substantial revision to address the identified deficiencies.
References

The following references would strengthen a revised version of this paper:
Agrawal, M., Kayal, N., & Saxena, N. (2004). PRIMES is in P. Annals of Mathematics, 160(2), 781–793.
King, S. (2013). Primecoin: Cryptocurrency with Prime Number Proof-of-Work. primecoin.io.
Lenstra, A. K., & Lenstra, H. W. (1993). The Development of the Number Field Sieve. Lecture Notes in Mathematics, 1554.
Nash, J. F. (1951). Non-Cooperative Games. Annals of Mathematics, 54(2), 286–295.
Shor, P. W. (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing, 26(5), 1484–1509.
This review represents the professional opinion of the author and is provided for informational purposes.

—
Christoph Gruber

—
Christoph Gruber