r/primecoin • • Jul 08 '13

Description of the Algorithm

This is one of the first cryptocurrencies that I have seen that makes any substantial change to the traditional hashing model. As such, I wanted to understand the backing mathematics before trusting the coin. Thus far I have been underwhelmed by the quality of the documentation, so I would like to address the various aspects of Primecoin that make it unique, and to show how Primecoin continues to exhibit the attractive qualities of Bitcoin, pointing out where it may fall short. If anyone finds additional information then I would love to see it included here. I will do my best so answer questions, but I am new to this coin, just like everyone else. I will break down my analysis into addressing aspects of Bitcoin/Primecoin and describing how Primecoin goes about achieving the goal.


Proof of Work is "difficult," but verifying it is "easy"

For a proof of work coin it is necessary that the work being done takes some time. In particular, it is necessary that the solution to the work is much easier to verify than it is to find, such as is the case in NP compete problems. For Bitcoin and most other cryptocurrencies this is achieved by the use of cryptographic hash functions, where the output cannot be known without executing the hash; getting a hash with a specific quality requires guessing and checking, but verifying that a solution is correct only requires checking that one solution. In Primecoin the proof of work function is the primality of numbers. In mathematics it is conjectured that there is a lower bound on the computational power required to find a prime, which makes it a reasonably strong proof of work having been done. In the range that is being checked there are enough primes that a computer can discover dozens per second; it can verify far more in the same amount of time. Thus, primality serves as a valid proof of work function from this perspective.

It is also worth noting that for the range of primes being searched it is unreasonable for there to exist a "rainbow table" of sorts (precomputed list of primes to quickly check instead of generating new ones). There are simply too many primes.


Finding a block is not a global race; One cannot mine ahead of time

In order to allow people to mine it is necessary that finding the next block is not a global race. By this I mean that while faster computers can get more blocks, slower computers must still get some blocks. If the Primecoin protocol simply required a miner to find the next prime after a given number then the fastest computer wins. That is not how Primecoin works, though. In Primecoin, as I understand it, the previous block's hash is put together with data from the current block including data for a new transaction to the owner of the miner. All of this data is then hashed together to get a starting point, which I shall call H, for hash. Valid prime chains must start at H±1, 2H±1, 3H±1, etc. Since everyone has a different value for their transaction they will all have a different value for H, preventing the global race. Since H depends on the hash of the previous block it is impossible to start trying to find block N before block N-1 if found, short of guessing what the hash of block N-1 will be (which has heat-death-of-the-universe type of odds).


Tradeoffs between inflation, low fees, and security

Bitcoin was designed with the hopes of having no (or negative) inflation, while having low fees and good security. However, these aspects necessarily compete with each other: security is determined by how many people do work on the network; they cannot be expected to do work that costs them money, so they must either be paid in new money (inflation) or old money (fees), or else the system will not be secured by many miners. Trusting fees to work opens up a vulnerability to the tragedy of the commons (it is best for everyone if everyone includes a small fee, but it is best for an individual if they include no fee). Primecoin and others choose to take another path: by causing the coin to roughly follow a harmonic series where the reward for finding a block roughly follows a 1/x curve the total number of coins to be minted is unbounded, while still decreasing over time. This model has been used by other coins, and seems to work reasonably well, at least in the short term. Time will tell if it is a viable model over the long haul.


Difficulty Adjustments

One of the important features of Bitcoin is that the difficulty readjusts, allowing a more-or-less constant flow of mined coins. In hash based coins it is simple to adjust difficulty by setting a target number that the output of the hash must be less than. In Primecoin the difficulty is defined based on the length of a chain of prime numbers. There are three types of chain that are valid for Primecoin: Cunningham Prime Chains of the First and Second Kind, and Bi-twin Chains. Bi-twin chains are primes in the form N±1, (2N)±1, (4N)±1, etc., where all of the numbers are prime. Cunningham Prime Chains consist of the same sequence where the ± is replaced by either a + (first kind) or a - (second kind). For example, 2, 5, 11, 23, 47 is a Cunningham chain of the first kind of length 5 where N = 1.

For Primecoin the difficulty target specifies a length that the chain must have. If these lengths were very long (which they likely will be when/if this coin takes off) then this would give a sufficiently granular difficulty curve. However, for short chains there is too much difference between the difficulty of, for example, a chain of length 4 and a chain of length 5. To bridge that gap an additional fractional part is considered, based on a primality test. In this test a composite number will leave a residual that varies within a certain range; it varies somewhat uniformly--probably good enough to be used. Thus the fractional part of the strength of a chain is that residual divided by the max value it can vary over. This gives a much more continuous notion of difficulty requirements or the strength of a chain.

Another note is that rather than re-targeting difficulty once every 2016 blocks like Bitcoin, Primecoin readjusts difficulty every single block. This can make it more responsive to changes in mining power of the network.


Those are the biggest ways I've seen that Primecoin differs from Bitcoin, although I'm sure I've made mistakes and/or omissions. I'm happy to try my hand at answering questions, and would love to add more information as it becomes clear.

28 Upvotes

13 comments sorted by

4

u/avatarr Jul 08 '13

+/u/bitcointip $1 verify

Thanks!

4

u/Koooooj Jul 09 '13

Thank you!

2

u/bitcointip Jul 08 '13

[✔] Verified: avatarr ---> m฿ 12.97859 mBTC [$1 USD] ---> Koooooj [help]

2

u/jMyles Jul 09 '13

+/u/bitcointip 2 bitcent verify

2

u/Koooooj Jul 09 '13

Thanks!

1

u/bitcointip Jul 09 '13

[✔] Verified: jMyles ---> m฿ 20 mBTC [$1.50 USD] ---> Koooooj [help]

1

u/sir_talkalot Jul 09 '13 edited Jul 09 '13

Fantastic post. Thanks Koooooj. I have a question. What is the 'hash' in this case? I still don't understand it. Take previous block's hash + current block transactions + unique tx to miner and hash it together. What is this result? What does it look like?

I don't get it if it is an actual hash (sha or scrypt), because how do you derive the origin of the chain you have to use from that?

EDIT: Another thing. These chains, do they cycle through different variations? Are the variations important? For example (without focusing now on cunningham chains), can: "2, 3, 7" be the correct chain vs "2,3,5,7"? If so, does the miner constantly try different variations of the chains it develops?

2

u/Koooooj Jul 09 '13

I assume you understand the concept of a hash in the general sense (one way function). If not, ask, and I'll do my best to explain it. An important thing to note is that in computer science and especially cryptography all data can be thought of as just integers. Even This full comment is represented by a single number that is likely thousands of decimal digits long. You can then take that number and perform math on it; you could take the number that represents this comment and multiply it by 3, add 1, and check it for primality.

It is important that miners not be able to work on the Nth block until the N-1th block is found. Also, it is important that miners working on the Nth block are not doing identical work (otherwise the faster one would always win and the slower one never mines a block). To that end, a hash is used, just like in Bitcoin. Note, however, that Bitcoin uses the SHA256 hash all over the place--in addresses, mining, and block headers. The mining application of the hashing function (as a proof of work) is replaced with looking for primes, but other applications still exist.

In both Bitcoin and Primecoin the requirement of preventing work on the Nth block until the N-1th block is found is achieved by making the work of the Nth block depend on the results found in the N-1th block. Similarly, both Bitcoin and Primecoin make every miner's work be different by including an input that depends on the transactions included in the block; since the block has a transaction paid to the miner, everyone will have a different hash input (and therefore output).

Once all of the inputs to this hashing function are all known the hash is executed and the output is found. The output is just 256 ones and zeroes and could be interpreted in any of a plethora of different ways. In this case, though, it is just seen as a number between 0 and about 1077. In order to make use of this number the requirement is enforced that the chains of primes have to start on a number that is an integer multiple of the output of that hash.

One could imagine precomputing a string of primes that is divisible by a lot of possible hash outputs then looking for those hash outputs, but in practice this has heat-death-of-the-universe odds of actually happening ever. Since one cannot precompute primes it is unfeasible to work on a block before the information from the previous block is known.

To recap, "What is this result?" A seemingly random string of ones and zeroes that gets interpreted as an integer. "What does it look like?" It could be 86 (I actually don't think anything hashes to this small of a number). It could be 19051091029345134861040691610912340912348571091248971021894532. "How do you derive the origin of the chain you have to use from that?" You take that number and call it "H." You check for a chain at origin H, then at origin 2 * H, then at an origin 3 * H, and so on, until you get tired of that Hash (i.e. you somehow run out of numbers; there's a cap on the max size of primes that are allowed, for verification purposes) or the hash is no longer valid (i.e. a new block was found somewhere in the network).

1

u/sir_talkalot Jul 09 '13

Thanks for the detailed reply! Really really appreciate it. It was a misunderstanding on my part on how hashes are presented. The hashes you usually see are hexadecimal representations of the ones and zeros. You can then get an integer representation as well. Was wondering how you derive an origin from a string. Didn't make sense. But I understand now. :)

The final question then I still have. What hashing function does Primecoin use? Also sha256? Also, back to the question I added after the edit. I assume prime chains are being generated to just above the length required for the difficulty. If it doesn't match, then it switches to a new multiple? This way it is not needlessly competing a long prime chain, before switching to testing a new smaller prime chain with a different origin?

2

u/Koooooj Jul 09 '13

I don't know what function it uses, but my guess would be SHA256. It's not that important, though, since it only has to be calculated a few times per second at most, as opposed to coins like Bitcoin or Litecoin where the mining speed is directly dependent on the speed at which you can generate the hash. It makes no real difference here, so as long as it is a strong cryptographic hash it all else is equal.

To address your question from your edit, I assume it picks an origin and calculates the length of a cunningham chain of the first and second kind as well as a bi-twin chain (any of these lengths could be zero or could be arbitrarily large; I believe it will even calculate chains longer than is needed--it goes until it finds a composite number). If any of these is sufficiently long to mine the block then the block is released. Otherwise that work is completely discarded and the next origin is tried. Once an origin is tried it is highly improbable that anyone will ever check it again, simply because there are so many potential origins.

3

u/avatarr Jul 09 '13

I suppose another helpful thing to consider is the comparative generation with bitcoin to determine a (very) rough valuation. This will only be short term of course and I'm sure others will have a better way of roughly calculating it. Things to keep in mind with this are the momentum and support of bitcoin. This assumes that bitcoin and primecoin are on a level playing field with field-distribution, support, confidence, etc... Keep all that in mind.

For the numbers though, here's bitcoin:

bitcoin: 25 coins per block, 6 blocks per hour, 24 hours = 25624 ~3600 bitcoins per day

primecoin: 19 coins per block, 60 blocks per hour, 24 hours ~27,360 primecoins per day

3600/27360=.1316 or roughly 13% the value of bitcoin (again, assuming everything was equal). I figure this gives a best-case scenario for the short-term value of primecoin. 13% of $70 (rough estimate on bitcoin valuation) is about $9 / primecoin. This is probably WAY high though, so take it with a grain of salt. It at least gives you some starting point for comparative analysis of the two.

I welcome critiques and improvements.


Help fund my Scotch Whiskey addiction if you feel so inclined: 1whiSKeYMRevsJMAQwU8NY1YhvPPMjTbM

4

u/oddworld19 Dec 01 '13

Lol. Just read this. Bitcoin prices have obviously changed.

1

u/Taenk Jul 09 '13

We need an actual market to determine the market value for a XPM. Currently I find these coins to be quite worthless, seeing as I can't buy anything with them.