Bitcoin Magazine
Original author: Vitalik Buterin
One of the disadvantages of Bitcoin that its proponents often gloss over is the fact that its mining algorithm has little real-world value. The underlying issue is this: in order to add a new block to the Bitcoin blockchain, a Bitcoin miner must include a “proof of work”, a number which has a property that is hard to find numbers that satisfy, but is efficient to verify. Essentially, a proof of work is a way of proving to the world that the miner spent a certain amount of computational effort generating the block, and is in fact a vital component of Bitcoin’s security – without proof of work, an attacker could easily pretend to be a million Bitcoin nodes at the same time, and in that way seriously compromise Bitcoin’s transaction ordering mechanisms. The canonical attack, the so-called “double spending” fraud, involves sending a payment to a merchant, later sending the same coins back to yourself and then creating a false consensus that the second transaction happened first, thereby depriving the merchant of their money. Proof of work solves the problem by making “pretending to be a million Bitcoin nodes” prohibitively expensive. However, what makes people uncomfortable is that in Bitcoin’s case the work (SHA256 computations) has no underlying value; rather, Bitcoin’s proof of work is literally nothing more than burning electricity for its own sake.
It has always been thought that we could do better. Many newbies to Bitcoin immediately suggest that the mining algorithm should have involved SETI@home or folding@home, so that the computations would also help bring humanity closer to curing protein misfolding diseases or finding aliens. The problem is, however, that Bitcoin mining requires one key property that SHA256 does have but SETI@home and folding@home do not: it is efficiently verifiable. Right now, all participants in the SETI and folding networks are volunteers, meaning that they (probably) have no intentions other than the desire to actually help the project’s underlying goal. If these networks become tied to Bitcoin mining, however, participants will be motivated by profit, so there would be an overwhelming incentive for miners not to bother with the actual computations and instead provide fake data that has no value to the networks’ underlying goals but is indistinguishable from a genuine computational output.
Primecoin is the first proof-of-work based cryptocurrency that has come up with any kind of workable solution. The central premise of Primecoin is that, instead of useless SHA256 hashes, the proof of work protocol would require miners to find long chains of prime numbers. There are three specific types of chains that are of interest: Cunningham chains of the first kind, Cunningham chains of the second kind, and “bi-twin” chains. The rule behind a Cunningham chain of the first kind is that each prime in the chain must be one less than twice the previous. The first Cunningham chain of length 5, for example, consists of the following six primes:
1531, 3061, 6121, 12241, 24481
In Cunningham chains of the second kind, each prime must be one more than twice the previous. Here, the first length-5 chain appears much sooner:
Finally, bi-twin chains are chains of pairs of twin primes, or primes that are 2 units apart from each other, with the average of each pair being twice the average of the previous pair. Each bi-twin chain must obviously have even length; the first chain six primes long is:
211049, 211051, 422099, 422101, 844199, 844201
Note that a bi-twin chain is essentially a Cunningham chain of the first kind and a Cunningham chain of the second kind rolled into one; the first numbers of each pair follow the recurrence that each one is one more than twice the previous (211049 * 2 + 1 = 422099, etc), and the second numbers of each pair are similarly one less than twice the previous.
What is the practical utility of finding primes? Well, if the effort that we put into the topic today for its own sake is any indication, there is definitely at least something to it. The Electronic Frontier Foundation is offering $550,000 worth of prizes to the first groups to discover a prime number more than 1 million, 10 million, 100 million and 1 billion digits long. The first two awards have already been claimed. The Great Internet Mersenne Prime Search has been looking for large prime numbers since 1996, and mathematicians in universities around the world are involved. The University of Tennessee at Martin provides a list of reasons why looking for primes is useful; aside from “for the glory!”, searching for primes leads to useful byproducts in other areas of number theory, provides an incentive for computational hardware development and leads to insights in the underlying workings of prime numbers themselves; the prime number theorem, for example, a theorem stating with high precision how often prime numbers are likely to occur at a given size, was first conjectured by looking at the distribution of actual prime numbers. Here, the hope is that if Primecoin takes off people will start looking for much more efficient ways of finding Cunningham and bi-twin chains, potentially leading to mathematical breakthroughs in how these chains work.
Further Refinements
In order to be a viable cryptocurrency, Primecoin needs a way to finely tune the difficulty of the proof of work; otherwise, new developments in technology or increased popularity may lead to new blocks being created too quickly for the blockchain to be stable or so slowly that transactions take hours to confirm. By themselves, prime chains do not provide enough granularity; a chain eight primes long may be a hundred times harder to find than a chain seven primes long. One option is to reward length, but that would make verification more difficult. The solution that Primecoin settled for is one based on the Fermat test. The Fermat test is a quick way of telling if a number is (very probably) a prime: raise any number (typically 2) to the power of a prime, subtract out the prime as many times as possible and see if you get the original number back. For example:
217 – 17 * 7710 = 2
223 – 23 * 364722 = 2
But:
221 – 21 * 99864 = 8
An alternative, and slightly better, formulation is to raise the number to the power of the prime minus one and see if you get one; this being true clearly implies the number passing the other test, and the other direction holds most of the time (one exception is that 3560 = 375 but 3561 = 3 (561 is not prime), but these become extremely rare as primes get bigger). Primecoin uses the p-1 test in combination with the Euler-Lagrange-Lifchitz test, which uses similar principles, to establish primality. So, the question is, how can one use this test to create granularity? That is, how can one distinguish between a chain 7.2 primes long and a chain 7.5 primes long? The answer is simple: look at the resulting value of the Fermat test of the first value in the chain not to be a prime; the lower it is, the larger the “fractional length”. For example, our chain of 2, 5, 11, 23, 47 has the next value 95, 294 modulo 95 (modulo being the mathematical term for the process of repeated subtraction used above) is 54, so the chain would have a length of 5 + (95 – 54) / 95 ~= 5.43. However, the chain 1531…24481 has the next value 48961 with a relatively low Fermat remainder of 1024, so the length would be 5 + (48961 – 1024) / 48961 ~= 5.97. In order for a prime chain to count as a valid proof of work, it must have a fractional length at least equal to the difficulty; as of the time of this writing, this parameter is floating around 7.1.
Since we do not want proofs of work to be reusable, Primecoin also adds another restriction. For the purposes of Primecoin, the “origin” of a bi-twin chain is defined as the average of the first pair, and for single Cunningham chains the origin is what the average of the first pair would be if the Cunningham chain’s twin also existed; for example, the origins of the two single Cunningham chains given above are 1530 and 3, respectively. The restriction is that the origin of a prime chain must be divisible by the hash of the block that the proof of work is for. Hash functions have the property that the only way to look for a value that has a particular hash is the computationally infeasible strategy of simply trying new values until you get a result that works; thus, the only way to generate valid proofs of work is to look for prime chains targeted to one block of which you already know the hash, and these chains would only ever be useful for that specific block.
Primecoin also adds a number of other innovations on the side:
Smooth difficulty adjustment – unlike Bitcoin, which adjusts its difficulty to exactly match the target rate of 1 block per 10 minutes every 2016 blocks (roughly two weeks), Primecoin adjusts its difficulty slightly every block, nudging it toward the target rate in an exponential decay pattern. For example, if network hash power (or rather, prime generation power) suddenly doubles, the next block would be 0.02% harder than the previous, increasing the amount of work required per block to 186.5% of the original after one week and 198.2% after two weeks, assuming no further mining power increases take place.Very fast confirmations – unlike Bitcoin, where transactions take an average of ten minutes to confirm (eight minutes in practice since the difficulty must constantly catch up to increasing mining power), Primecoin blocks come at a rate of one per minute. This allows secure transactions to be made much more quickly; six confirmations may take fifty minutes in Bitcoin, but they take only six minutes in Primecoin. The underlying mathematics behind why six confirmations is a fairly safe threshold is independent of block confirmation time, so the Primecoin transaction at six confirmations is no less secure (it can be argued that attackers can make double-spending attempts ten times more frequently, but going up to just seven or eight confirmations more than makes up for this). Self-adjusting block reward – Bitcoin is known for its
controlled currency supply algorithm, which guarantees that only 21 million Bitcoins will ever be generated, as well as specifying the rate at which these Bitcoins will come out. Primecoin follows a different path. The number of Primecoins (XPM) released per block is always equal to 999 divided by the square of the difficulty, a formula which
should converge to some maximum if the difficulty increases linearly. Given that Moore’s Law states that computing power increases exponentially, and the effort it takes to find a prime chain is exponential in its length, that is quite likely to hold true.
There are some places where Primecoin missed some serious opportunities for improvement. First of all, the self-adjusting block reward was intended to be a “more natural simulation of gold’s scarcity”. However, in practice it does the exact opposite. The desirable property that gold has is that its supply at least somewhat increases with its value; if the gold price shoots past $5,000, mining opportunities will become profitable that were not profitable before, increasing the rate at which new gold is mined and eventually making the supply go up, partially counteracting the price shock. Here, if the price goes up by a factor of ten, the difficulty will shoot up significantly as well as more miners move in, leading to… a reduction in the Primecoin generation rate. Thus, instead of adding the negative feedback mechanism inherent in gold, Primecoin instead creates a positive feedback mechanism that exacerbates the problem of volatility. Also, Primecoin could have set up its exponential adjustment algorithm to have a much longer period – reaching 86.5% adjustment after two months, for example, instead of a week. This is one innovation that would also at least somewhat stabilize the value of the currency by generating more coins when interest goes up, but unfortunately so far no currency has tried this; Primecoin, despite all of its other improvements, missed the chance to be the first.
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.
