Bitcoin Magazine

Everyone can see what you download - Private Internet Access
Show Menu
primes

Primecoin: The Cryptocurrency Whose Mining is Actually Useful


Read the exclusive interview with Primecoin’s creator Sunny King in the issue 13 of Bitcoin Magazine.


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:

2, 5, 11, 23, 47

 

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 confitmations 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.

Read the exclusive interview with Primecoin’s creator Sunny King in the issue 13 of Bitcoin Magazine.

BTC: 1FxkfJQLJTXpW6QmxGT6oF43ZH959ns8Cq

LTC: LaBhvWiAP7msku6w8QSQ5G7omVWMF3uxJC

By

Vitalik Buterin is a co-founder of Bitcoin Magazine who has been involved in the Bitcoin community since 2011, and has contributed to Bitcoin both as a writer and the developer of a fork of bitcoinjs-lib, pybitcointools and multisig.info, as well as one of the developers behind Egora. Now, Vitalik's primary job is as the main developer of Ethereum, a project which intends to create a next-generation smart contract and decentralized application platform that allows people to create any kind of decentralized application on top of a blockchain that can be imagined.

Get Top Stories Weekly

We respect your email privacy

  • http://suso.suso.org/ Deltaray

    Bitcoin mining isn’t useless. The work you are doing is to prove for the rest
    of time that a Bitcoin can be used and trusted by others in the system and that has real world value because you’re creating a digital currency system that can be used.
    To say the algorithm is useless is kinda like saying “the process of mining gold is useless because you didn’t discover a cure for cancer while doing it”. Well no, but you discovered gold, which was the point.

    • Vitalik Buterin

      No, gold mining is indeed close to useless (well, not quite since it has industrial and jewellery applications, but those are minor compared to speculation these days). The problem is that you’re conflating individual value with social value. If something happens, then of course it has individual value; that’s almost a definition. But in terms of social value, to see why it’s wasteful consider the following thought experiment.

      Suppose some non-profit group manages to create a new kind of gold, X-gold. X-gold has all the monetary properties of gold, but significantly better. The group then hands out this X-gold to everyone who has gold and everyone who would have mined it in the future. X-gold is superior money, so it outcompetes gold and the value of gold drops back to $200. However, the value of X-gold goes up to $1400. How is the world different? In monetary terms, everyone’s just as well off; they’re exactly as wealthy as they would be, as they have as much X-gold as they had gold. However, most gold miners are not going to be mining anymore, so instead they’ll be free to spend all that time with their families or working on other interesting projects. Hence, the effort that is going into gold creation now is an economic waste.

      It may be a necessary waste given current technological and political circumstances, as it would not actually be possible for such a corporation to distribute the money (they would in reality keep a lot for themselves, like the Ripple developers), but it is still a waste, and a waste that is, at least theoretically, fixable.

      • Richard Boase

        I really liked this article, and I really like the idea of Primecoin. It’s a winner already, and this is a great explanation. It reading the white paper made me instantly jump to the idea of ‘e’, ‘i’ and ‘pi’ coins as the next logical step in the story of crypto-currencies. Sound like a plan?

  • Richard Boase

    “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.”…

    …You lost me at ‘The…’

  • Michael Toomim

    I’m a Computer Scientist, and the author is totally wrong here! Primecoin is far LESS secure than bitcoin!

    “Primecoin blocks … 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 confitmations is no less secure.”

    The underlying mathematics are COMPLETELY dependent on the block confirmation time—it’s only as secure as the amount of CPU time that’s gone into block. More time means more security!

    A 1-minute primecoin block is less than 1/10th secure as a 10-minute bitcoin block! In reality, it’s far less secure, because there are far fewer computers on the primecoin network seeking that block.

    • Richard Boase

      I really want to read what you said now. The primecoin chain is less secure? Can you elaborate please, I’m hungry for information on XPM.

      • Michael Toomim

        I was wrong. I had a conversation with Vitalik (the author) in which he convinced me that a faster block time actually DOES improve security, so I deleted my post. I suggest asking him to post his extended analysis, it was quite good!

  • Espen

    “an attacker had the processing power such that she had a 20% chance of outrunning the bitcoin blockchain for 2 blocks (20 minutes). Assuming an equal sized network on primecoin, the attacker would have a 20% chance of outrunning the blockchain for 20 blocks (20 minutes)”

    Nope. False.

    To have 20% chance to outrace the network for 2 blocks, you need 30.9% of the network hash rate. This percentage doesn’t change with faster blocks.

    Assuming you have 30.9% of the hash rate:
    To outrace the network for 6 blocks your chance is not 6.67%. It is 0.8%.
    To outrace the network for 20 blocks your chance is not 1%. It is 0.00001%.
    To outrace the network for 60 blocks your chance is not 0.33%. It is 0.0000000000000000001%.

    The only factor that works in your favor when the blocks are faster is that you can make attempts more frequently. This is a linear factor, but higher difficulty is an exponential factor.

    Conclusion: Faster blocks improves security if the number of required confirmations is also adjusted upwards.

  • Diego Martinez

    Then you have NameCoin, a decentralized DNS system.

  • Bitcoin Expert

    interesting article

  • http://zapataozid.wordpress.com/ True North

    I chose QuarkCoin for it’s speed, it’s philosophy and the fact that it would continue to be issued at a small percentagerate in perpetuity to make up for the fact that we will be producing more goods and services in perpetuity (hopefully – unless capitalism pollutes us to death first, as seems the most likely still unfortunately), So to all the squabble about security, it does not seem like a “real” issue. Until Quantum computers become commercially available of course… but when that happens we have yet another shift in pardigm so something new will take its place or be used to update the e-currencies anyway… I was very happy to se that it was possible for me to mine around 10 quark’s in a few days too, which was fun, but at the current prices I think buying Quarks in the market is a way better option. Just thought I’d share these thoughts and calm anyone who thinks that there is any serious “problem” or “issue” with Quark. I’m in for the long haul. at least 3-5 years or more, so I have no worries. I only invest what I can stand to loose or dont need have increase anyway.
    So that’s my two cents so far. Hope it helps :) Cheers.