Exploring The Infinite With Primecoin

This article was originally published on The Daily Chain, 6th January 2021.

What do numbers look like? Courtesy of johnhw.github.io

Bitcoin’s Proof-of-Work, based on Hashcash, is wasteful of energy. In fact, that’s entirely the point of Hashcash; to consume an attacker’s resources. So although in Bitcoin the issuance of virtual coins psycho-magically offsets the relentless burning of electricity to solve arbitrary and otherwise useless equations, no one should ever be surprised that Bitcoin is profligate with energy. That was the intent, and is the nature of the beast.

Couldn’t miners use the energy they expend in other, more useful ways? That is the inspiration behind Primecoin, and its network has been running continuously since its genesis in 2013.work

Paul Erdős (1913–1996), renowned Hungarian mathematician

Explorers Of The Infinite

Madras, India, 1919 — A 31 year old mathematician writes an infinite series on loose-leaf paper. His mind is filled with number theory, continued fractions, prime numbers; and theorems on infinity.

Even with no formal training in pure mathematics before he was 26, this man has solved problems once considered unsolvable.

Srinivasa Ramanujan attributes his gift to divinity, and says the mathematical knowledge he displays is revealed to him.

In 1918, only months before, he had become the first Indian to be elected a Fellow of Trinity College, Cambridge. Illness hastened a return to his home of Madras, and in 1 year, age 32, he will pass away.

In an obituary written for Nature in 1920, famous English mathematician G. H. Hardy, who’d invited Ramanujan to England in 1913 after receiving a 120-page letter of equations from the former clerk, observed:

His insight into formulae was quite amazing, and altogether beyond anything I have met with in any European mathematician. It is perhaps useless to speculate as to his history had he been introduced to modern ideas and methods at sixteen instead of at twenty-six. It is not extravagant to suppose that he might have become the greatest mathematician of his time. What he actually did is wonderful enough… when the researches which his work has suggested have been completed, it will probably seem a good deal more wonderful than it does to-day

When asked how Ramanujan arrived at his solutions, Hardy commented:

By a process of mingled argument, intuition, and induction, of which he was entirely unable to give any coherent account.

A 2016 movie, The Man Who Knew Infinity, tells Ramanujan’s story and documents his relationship with Hardy. In 2011 the Indian government declared that 22 December would be celebrated every year as National Mathematics Day.

Srinivasa Ramanujan

Primer

Present Day — Exactly 100 years after his death, the research into Ramanujan’s work continues to unravel its mysteries.

As late as 2011 and again in 2012, researchers continued to discover that mere comments in his writings about “simple properties” and “similar outputs” for certain findings were themselves profound and subtle number theory results that remained unsuspected until nearly a century after his death.

Wikipedia

Sunny King, the inventor of Primecoin, is moved by Ramanujan’s work, and and spoke of it recently.

Very few people can understand some of his ideas. Nobody knows the value of each of these equations but now we are in an age of knowledge explosion. Some of these equations now begin to reveal its importance especially to physicists. Amazing isn’t it?

King is fascinated by prime numbers and infinite series, just as Ramanujan was. Minds similarly held captive by the subject date back to Ancient Greece and Euclid.

Around 300BC Euclid proved his theory that there are infinitely many prime numbers when he wrote the Proof of the Infinitude of Primes. Yet there exist other conjectures in prime number theory which remain unproven:

This is discussed in the paper Primecoin: Cryptocurrency with Prime Number Proof-of-Work (2013):

Prime numbers, a simple yet profound construct in arithmetic, have perplexed generations of brilliant mathematicians. Its infinite existence was known as early as Euclid over 2000 years ago, yet the prime number theorem, regarding the distribution of prime numbers, was only proven in 1896, following Bernhard Riemann’s study of its connection to the Riemann zeta function. There remain still numerous unsolved conjectures to this day.

Twins

There are 2 unsolved conjectures, or theories, at the heart of Primecoin. As Sunny explained:

The things in number theory that are only appreciated by mathematician as ‘beautiful’ may lie at the core of the mystery of our universe. Twin prime chains, is among one of these mysterious beauties to mathematicians.

Twin primes are prime pairs that differs by 2.

For example:

(3, 5), (5,7), (11, 13), (17,19)

King describes the first conjecture as follows:

The famous conjecture states that twin primes existence is infinite, just as prime number existence is infinite. But still no one can prove it.

He then discusses finding finer structures in these twin primes, and gave an example.

(5,7) (11,13)

The numbers between each twin, 6 and 12 respectively, are referred to as the center, or origin. In the example one origin is exactly twice as large as the other origin (6 x 2 = 12).

This “finer structure” Sunny King observes, gives rise to a second conjecture of particular interest to him: that twin prime chains can go arbitrarily long.

You can also find a chain of these twin primes. Each is twice the value of the previous one, although longer ones are much harder to come by. Now these chains of twin primes, they seem can go arbitrarily long as well.

I call this the twin prime chain conjecture, that these chains can go to unbounded length

Primecoin gives support to the Twin Prime Conjecture, and the stronger Twin Prime Chain Conjecture.

Looking for prime chains is what Primecoin does in place of solving arbitrary cryptographic puzzles. It was the first non-hashcash Proof-of-Work coin.

Vitalik Buterin wrote a 2013 Bitcoin Magazine article called “Primecoin: The Cryptocurrency Whose Mining is Actually Useful”:

All in all, Primecoin presents itself as an extremely interesting experiment; for the first time, we have a currency whose mining algorithm has a secondary value, and at the same time Primecoin, unlike so many other coins before it, actually makes serious attempts to improve on Bitcoin in unrelated aspects. Not taking into account Bitcoin’s massive headstart, Primecoin may well be the first alternative coin to actually be better than Bitcoin, giving the currency the potential for a bright future ahead.

Vitalik Buterin, Bitcoin Magazine, 2013

At the time of Buterin’s article, Primecoin was getting a lot of interest, and for a brief time it seemed possible that an Ethereum-style project would be built on top of Primecoin. Chat logs from a conversation between Buterin and Yanislav Malahov (who later founded Aeternity), and published by the latter, discuss the unrealized concept.

PoW

Long prime numbers would not serve as a good proof-of-work. Even though long primes meet the PoW requirement of being computationally difficult, they fail to meet another main requisite for PoW; simple and fast verification. The numbers are just too large.

However prime chains are easier to verify, and this thought struck Sunny King, as he explains in his paper.

In March 2013, I realized that searching for prime chains could potentially be such an alternative proof-of-work system. With some effort a pure prime number based proof-of- work has been designed, providing both minting and security for cryptocurrency networks similar to hashcash type of proof-of-work. The project is named primecoin.

Specifically, Primecoin miners search for three types of prime chains: Cunningham chains of the first kind; Cunningham chains of the second kind; and Bi-twin chains.

Cunningham chains are useful in cryptographic systems as they provide two concurrent suitable settings for the ElGamal cryptosystem, and other asymmetric key encryption algorithms for public-key cryptography based on Diffie–Hellman key exchange.

“Infinite Cunningham Chains and Infinite Arithmetic Primes”, a 2016 paper published in the International Journal of Innovation in Science and Mathematics, elaborates on their utility in cryptosystems.

Cunningham chain has a number of interesting properties “it is always a complete finite set”, however the number of finite length Cunningham chains is infinite.…The higher the chain’s value, the harder to reverse engineering it. As such, we can use it to fulfill the tasks of the public or private authentication key generation and distribution, with the variations of Elgamal signature algorithms for the agricultural application.

In a Cunningham chain of the first kind, the prime numbers in the series are double that of the predecessor plus one. The chains are of different lengths.

Examples are:

2, 5, 11, 23, 47 (The next number would be 95, but that is not prime.)
3, 7 (The next number would be 15, but that is not prime.)

In a Cunningham chain of the second kind, the prime numbers are double that of the predecessor minus one, so:

2, 3, 5 (The next number would be 9, but that is not prime.)
7, 13 (The next number would be 25, but that is not prime.)

In the examples above, the first forms a chain of 5 prime numbers (2, 5, 11, 23, 47).

Gems

Primecoin finds chains of 10 or more primes every single minute. Miners have even found chains of 15 prime numbers, and that’s a world record. This is what a Primecoin record-breaking chain of 15 prime numbers looks like:

10675051868243041144166338821390281421550066007482453221241219105692907824915754459907705017466879, 10675051868243041144166338821390281421550066007482453221241219105692907824915754459907705017466881, 21350103736486082288332677642780562843100132014964906442482438211385815649831508919815410034933759, 21350103736486082288332677642780562843100132014964906442482438211385815649831508919815410034933761, 42700207472972164576665355285561125686200264029929812884964876422771631299663017839630820069867519, 42700207472972164576665355285561125686200264029929812884964876422771631299663017839630820069867521, 85400414945944329153330710571122251372400528059859625769929752845543262599326035679261640139735039, 85400414945944329153330710571122251372400528059859625769929752845543262599326035679261640139735041, 170800829891888658306661421142244502744801056119719251539859505691086525198652071358523280279470079, 170800829891888658306661421142244502744801056119719251539859505691086525198652071358523280279470081, 341601659783777316613322842284489005489602112239438503079719011382173050397304142717046560558940159, 341601659783777316613322842284489005489602112239438503079719011382173050397304142717046560558940161, 683203319567554633226645684568978010979204224478877006159438022764346100794608285434093121117880319, 683203319567554633226645684568978010979204224478877006159438022764346100794608285434093121117880321, 1366406639135109266453291369137956021958408448957754012318876045528692201589216570868186242235760639

And this is the origin:

10675051868243041144166338821390281421550066007482453221241219105692907824915754459907705017466880

All of Primecoin’s records are stored immutably in its blockchain, and also presented in Primes.Zone, an online database and visualizations of Primecoin’s record breaking prime chains. At the time of writing a total of 38,512,121 prime numbers in 3,731,741 chains have been found since July 2013.

Prime.Zone visualization

Difficulty adjustment in Primecoin is explained in the paper, and uses the remainder of the previous block’s primality verification test.

Of course, hashcash’s linear difficulty model made it easy. For prime proof-of-work, it is not apparent how this could be achieved. Initially I thought about using prime size as an indicator of difficulty. However, a non-linear difficulty curve would negatively impact block chain security. Also, using prime size as difficulty indicator would interfere with efficiency of verification. Eventually I discovered that the remainder of Fermat test could be used to construct a relatively linear continuous difficulty curve for a given prime chain length. This allows primecoin to largely keep the security property of bitcoin.

Mining Primecoin PoW is efficient on CPU’s, but has largely been dominated by GPU’s since 2014. Possibly FPGA’s exist too, although Sunny wasn’t sure, and doesn’t regard it a problem.

The failure of manufacturers to commodify Primecoin mining hardware is likely one of the reasons Primecoin has been pushed out of the limelight over the years. Other reasons include the rise of Ethereum, ICO’s and DeFi projects with big marketing budgets to grab investor’s attention and money.

The future looked gloomy for Primecoin, and very finite indeed, until Sunny King returned to the project earlier this year to bring it back from the precipice. And certainly he should. After all, Primecoin breaks records and Cunningham chains have a practical as well as theoretical utility these days.

There can be little doubt that Primecoin is Sunny King’s most cherished work, and the gem in his crown. That’s what he calls the long chains the network discovers. Gems.

Primecoin is mining coins, but coins are only a bi-product of discovering primes and exploring the infinite.

The Immutable Network (DARA), founder. Immutable builds free blockchain products and platforms to fight censorship and stop data loss. Also a journalist/writer.