A new type of proof-of-work based on searching for prime numbers is introduced
in peer-to-peer cryptocurrency designs. Three types of prime chains known as
Cunningham chain of first kind, Cunningham chain of second kind and bi-twin
chain are qualified as proof-of-work. Prime chain is linked to block hash to
preserve the security property of Nakamoto’s Bitcoin, while a continuous
difficulty evaluation scheme is designed to allow prime chain to act as
adjustable-difficulty proof-of-work in a Bitcoin like cryptocurrency.
Since the creation of Bitcoin [Nakamoto 2008], hashcash [Back 2002] type of proof-ofwork
has been the only type of proof-of-work design for peer-to-peer cryptocurrency.
Bitcoin’s proof-of-work is a hashcash type based on SHA-256 hash function. In 2011,
ArtForz implemented scrypt hash function for cryptocurrency Tenebrix. Even though
there have been some design attempts at different types of proof-of-work involving
popular distributed computing workloads and other scientific computations, so far it
remains elusive for a different proof-of-work system to provide minting and security for
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-ofwork
has been designed, providing both minting and security for cryptocurrency
networks similar to hashcash type of proof-of-work. The project is named primecoin.