Bitcoin Forum

There isn't enough data storage on earth, maybe not in the entire universe, to remember all primes, so finding new ones surely has to involve forgetting old ones at some point.

Primecoin though isn't looking for primes, it is looking some some fancy pattern/sequence of primes, I dunno though whether they too are so numerous we won't be able to remember them all.

Though if we only need remember on the blockchain those we found for the blockchain that isn't a problem for us; and maybe only bothering to remember same rare sequences is going to let science actually remember what is found instead of trying to find stuff it is only going to have to forget at some point when it runs out of memory/storage...

-MarkM-

The 1 minute confirmation time makes it a winner(I prefer to use XPM than those "cheap" scrypt cloneCoins) for those who do lots of arbitrage, it's currently in 3 or 4 exchanges, so moving funds between them with primeCoin is the best option so far. Wait until it hits BTC-e, it's price is gonna explode!  :D

didn't BTC-e say no for now?

It would be good to hear a mathematician's view on the usefulness of these prime chains. Seems dubious to me.

I'm curious of the efects of the network once difficulty gets really high and prime numbers to be found are insanely difficult to compute let alone verify by nodes to be efficient in any meaningful way.

There isn't enough data storage on earth, maybe not in the entire universe, to remember all primes

I didn't know there is a finite amount of primes.

There is some use to the data gathered for pure mathematicians (disproving conjectures, possibly discovering new patterns). In the same way you get programs online that allow people to search for higher and higher prime numbers (often Mersenne primes). It's usefulness is in a similar vein to those. The coin in itself will also strongly motivate people to write efficient algorithms that crunch through prime numbers, so a by product of the coin could be a breakthrough in that direction. A lot of 'pure maths' doesn't (yet) have any real world applications. Over the last hundred years though time and again pure maths that was thought to not be useful was later found to be ideal for solving a problem.

At the end of the day it's still primarily a currency, with 1 minute confirmation times. That's it's main purpose. But as a bonus, at least the proof of work contributes to society in some way rather than meaningless forgotten hashes.

I'm curious of the efects of the network once difficulty gets really high and prime numbers to be found are insanely difficult to compute let alone verify by nodes to be efficient in any meaningful way.

That's the 1,000 XPM question.... as you go from a chain of length N to a chain of length N+1, how much does the difficulty actually change?

That's the 1,000 XPM question.... as you go from a chain of length N to a chain of length N+1, how much does the difficulty actually change?

I'm curious of the efects of the network once difficulty gets really high and prime numbers to be found are insanely difficult to compute let alone verify by nodes to be efficient in any meaningful way.

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.

I think I saw an estimate that difficulty 8 was 30x harder to find chains for than difficulty 7. (But verifying just means checking one more prime, so it's only 1/7 harder in that case.)

I'm curious of the efects of the network once difficulty gets really high and prime numbers to be found are insanely difficult to compute let alone verify by nodes to be efficient in any meaningful way.

There isn't enough data storage on earth, maybe not in the entire universe, to remember all primes, so finding new ones surely has to involve forgetting old ones at some point.

Primecoin though isn't looking for primes, it is looking some some fancy pattern/sequence of primes, I dunno though whether they too are so numerous we won't be able to remember them all.

Though if we only need remember on the blockchain those we found for the blockchain that isn't a problem for us; and maybe only bothering to remember same rare sequences is going to let science actually remember what is found instead of trying to find stuff it is only going to have to forget at some point when it runs out of memory/storage...

-MarkM-

That's indeed what's implied but i think he was only betrayed by the choice of words

OnT: I think Primecoin is a step in the right direction, i am bugged by the general pointlessness and waistness of mining cryptos. I am patiently waiting for a coin which can be actually useful and sets the miners in a cooperative spending of resources, currently this cooperativeness can only be achieved by mining in pools, which Primecoin lacks. But what i would like to see is this cooperation structuraly implemented, otherwise the waist in resources is crasy.

This.

If we're not finding new (bigger) primes then isn't it possible to exploit the network?  But if indeed we're finding new primes, I don't see how the diff retarget algo can properly correlate with network hash rate growth eventually.  I even brought this up to Sunny King and I guess I worded my question in a way that Sunny misunderstood.  Nevertheless, this isn't innovative in the sense of finding new primes because it's not exhaustive.  For example, the sieve in ypool's jhPrimeMiner loads the primes in the first million positive integers.  That's only about 78k primes.  The more I look at it the more it just seems like XPM is using primes kind of like public keys for hashing new blocks to the block chain.