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

[oovanes at midlincoln.com]

Dear Christoph, Peter, and members of the list,
Thank you for the detailed and thoughtful feedback.
The draft I shared is an early conceptual exploration, and several of 
your critiques correctly highlight areas where clarification or revision 
is needed. Posting here was intentional: to obtain exactly this kind of 
scrutiny from people with strong backgrounds in number theory and 
cryptographic protocol design.
Below I address the main technical points raised and outline changes for 
the next revision.

1. Scope of the paper
The current version is not intended as a complete cryptocurrency 
specification.
Its purpose is to explore:
     • deterministic prime discovery as a proof-of-work,
     • cooperative composite submissions,
     • a mathematically indexed asset structure, and
     • incentive mechanisms inspired loosely by Nash’s principles.
A fully cryptographic specification (hash formats, signatures, block 
encodings, adversary models) was not included because the architecture 
itself is what I hoped to evaluate first. The next draft will clearly 
separate:
     • conceptual architecture, and
     • protocol specification components (with concrete cryptographic 
primitives).

2. Scaling of prime sizes and feasibility of primality proofs
Christoph raised concerns about the feasibility of primality 
certificates for very large primes (beyond 10¹⁰⁰⁰ digits). Some of the 
numbers cited in the review reflect older benchmarks. Modern ECPP 
implementations have certified primes significantly larger than 50,000 
digits; recent records exceed 100,000 digits, and certificates above 
200,000 digits have been constructed in practice. Verification remains 
extremely fast compared to certificate generation.

It is also important to emphasize that the blockchain will never reach 
primes anywhere near those sizes.
The index of the first 1024-bit prime is approximately:
π(2^1024)≈10^306.
Even assuming an unrealistically fast rate of one prime per microsecond, 
the chain would still require:10^291 years to reach 1024-bit primes — 
vastly exceeding the age of the universe. At more realistic block rates 
(seconds or minutes), the gap becomes even more extreme.
Therefore the chain remains permanently in a range where modern 
primality certificates (ECPP, APR-CL) are fast and practical.
Verification remains cheap relative to mining.
This will be spelled out more clearly in the next revision.


3. Wallet representation — sparse model, not global vectors
Both Christoph and Peter interpreted the wallet state as an ever-growing 
vector of dimension equal to the number of mined primes. That was an 
error in the way the draft presented the model. Section 4.3 included a 
brief note, but I should have emphasized:
Wallets store only coefficients for primes they actually own.
The headline integer H encodes which primes appear.
Example:
     • If H=2⋅3⋅7,
     • The wallet stores coefficients only for (2,3,7), e.g. 
(0.4,0.1,1.0).
Wallets do not hold vectors with entries for all mined primes; they hold 
a sparse vector aligned to the factorization of their own H.
This makes storage compact and scalable.
The next draft will make the sparse model the canonical one.

4. Composite proof front-running and gossip timing
Christoph correctly notes that in an asynchronous gossip network, “first 
seen” does not reliably define ordering. The paper’s treatment of this 
was incomplete.
The intended mechanism is a commit–reveal protocol:
     1. Miner submits
commit=H(m∥t∥address).
     2. Commitments are timestamped upon receipt.
     3. Later, the miner reveals m,t.
     4. Only reveals matching prior commitments are valid.
     5. The earliest commitment wins.
This prevents front-running and does not require global synchronization.
Commit–reveal is widely used in decentralized protocols and adapts 
cleanly here.
The next draft will specify this protocol in detail.

5. Number-theoretic domain extensions
Christoph’s criticism about non-UFD rings is valid. Rings like Z[−5] do 
not support unique factorization, and therefore cannot sustain a 
divisibility-based ownership model.
Clarification:
     • Mining irreducibles in ANY ring is possible as a PoW puzzle.
     • Ownership accounting based on divisibility requires a UFD or 
Euclidean domain.
     • Therefore, extension chains must be restricted to such rings.
     • The main chain is always over Z, the canonical UFD.
The earlier version did not sufficiently separate “mining puzzles” from 
“ledger semantics.”
This will be corrected.

6. Quantum considerations
A few points are worth distinguishing:
6.1 Signatures
Yes—ECDSA or RSA fail under Shor. The protocol will adopt NIST-standard 
post-quantum signatures (e.g., Dilithium).
6.2 Composite proofs
Quantum algorithms accelerate factoring, but the protocol does not rely 
on factoring hardness. Composite proofs only require miners to exhibit 
one divisor, not to hide factorization.
Quantum ability to find divisors faster simply alters mining difficulty, 
much like ASICs affect Bitcoin.
6.3 Prime search
Shor does not accelerate prime search.
Grover provides at most a quadratic speedup, which can be offset through 
difficulty adjustment.
Conclusion:
The mining layer is far more quantum-resilient than Bitcoin PoW.
Only the signature layer needs a PQ upgrade.
This distinction will be clearer in the next draft.

7. Incentive model and Nash terminology
The current text uses “Nashian” in an informal sense (cooperative 
stability), not as a formal definition of Nash equilibrium. Christoph is 
right that an actual equilibrium analysis requires:
     • utility functions,
     • strategy spaces,
     • deviation analysis, and
     • explicit proofs.
I will replace “Nashian” with “cooperative incentive structure” unless a 
formal game-theoretic appendix is added.
On proof withholding: with commit–reveal the incentive to withhold 
vanishes because:
     • withholding commits delays reward collection,
     • simultaneous reveals cannot displace earlier commitments.
I agree that the current incentive description needs a formal treatment, 
which I will work on.

8. Economic framing
The current paper does not argue that fractional prime ownership is a 
superior currency.
Its intent is to explore:
     • deterministic mathematical issuance,
     • provable scarcity,
     • cooperative computation,
     • and a novel ledger structure.
Value attribution (or non-value) is orthogonal to the construction.
The revised draft will make this clearer.

9. On Peter’s comments
Peter, thank you for taking the time to review the draft. Several of the 
concerns you raise appear to come from assumptions that do not match how 
the system is actually defined, so I appreciate the opportunity to 
clarify these points and revise the exposition in the next version.

(1) On fungibility and currency value

The draft did not make this sufficiently explicit:
all prime-indexed units have equal monetary value.

A wallet holding 0.1 of prime 3 and another holding 0.1 of prime 5 
possess the same currency amount.

Thus: There is no conversion problem between Px and Py
“Swapping” fractional ownership of different primes has no effect on 
value;
A user sending 0.1 of 3 and receiving 0.1 of 5 has simply exchanged 
denominations, not changed wealth.

The fungibility is intentional: the protocol treats all 0.1-denomination 
units as interchangeable, regardless of prime label. This also means 
that ownership vectors need not grow unbounded; they only include 
entries for primes a wallet actually holds.

(2) On wallet size and factorization storage

The critique assumes that:

wallets must store factorizations for all integers up to 2^N
balances must be full-length vectors listing fractional ownership of 
every mined prime.

Neither is part of the protocol.

A wallet stores only:

its headline integer H, encoding which primes it holds;
its nonzero fractional coefficients.

A wallet that owns only fractions of primes
{p3,p5,p7} stores only those three entries. There is no global dense 
vector per wallet, and no storage of factorization tables for arbitrary 
integers.

All factorization work is performed during mining, on candidate 
composite proofs. Wallets and nodes do not retain factorizations after 
validation.

(3) On “Nash-stability” and Sybil behavior

Your concern about withholding composite proofs or submitting under 
multiple pseudonyms is valid. The intention is not to claim that the 
current mechanism is fully Sybil-resistant, but rather that the reward 
function can be constructed so that honest participation is at least 
competitive with strategic deviation.

I will rewrite this section to avoid the impression of a completed 
game-theoretic treatment. A more formal analysis (utility functions, 
adversary models, etc.) will appear in the next draft.

(4) On transparency and privacy

You correctly point out that a public ledger is traceable, as in 
Bitcoin. That is by design: the base system is pseudonymous and 
transparent, not anonymous.

However, the fungibility of prime fractions does introduce a mild form 
of obfuscation: balances change prime composition over time, breaking a 
simple “linear” asset history. This is not presented as a privacy 
feature, but it does make heuristic chain analysis less direct than in 
UTXO-based ledgers.

That said, the design can absolutely incorporate stronger, 
well-established privacy mechanisms
I will add a short section discussing possible privacy extensions and 
their implications.

(5) On scalability

Many of the scaling issues mentioned (global vectors, storing 
factorizations, etc.) stem from assumptions that do not match the 
described data structures. With the sparse representation actually used, 
wallet size grows only with the number of assets a wallet holds, not 
with the total number of mined primes.

The chain itself does not rely on storing composite proofs long-term; 
they are verified and discarded.

The economic model does not require exploding ledger state.

(6) On the tone of the critique

Although I disagree with several assumptions underlying your technical 
objections, I appreciate the candid feedback. I will improve the clarity 
of the specification to avoid similar misunderstandings, and I will make 
the system's intended transparency, fungibility, and design goals more 
explicit.

Next steps
I am preparing a significantly revised draft that will:
     • clearly separate architecture from protocol specification;
     • introduce commit–reveal for composite ordering;
     • adopt PQ-safe signature schemes;
     • restrict extension rings to UFDs;
     • formalize sparse wallet semantics;
     • add an explicit adversary model;
     • include a more developed incentive theory or remove Nash 
terminology;
I have also appended a new Section 9 to the draft that compares this 
proposal with Primecoin and with Factor blockchain designs, clarifying 
both similarities and substantive differences in proof-of-work 
philosophy, scalability, and verification cost.
https://midlincoln.com/pdfs/primenumberblockchain.pdf

Thank you again for the thoughtful critiques. They have been extremely 
valuable, and I welcome further comments as the next revision becomes 
available.
Best regards,

Ovanes Oganisian
oovanes at midlincoln.com