I don't have a deep understanding at all here. But this is particularly interesting because so far we've all, as far as I know, only been using modified internal miners (like mikaelh's). No one has really even solved the problem of parceling out work to two separate CPU's using external miners. But at a basic level, I would think that if there someday exists code allowing 2+ CPUs (or 2+ GPUs) graphics cards in the same system to interface with the same primecoind and mine via external miner, there would have be a way to insert as an intermediary some pool management code to consolidate work and distribute rewards fairly.
It's not like that. A process can start 2 threads that run on 2 CPUs and it can trust it's threads. A pool cannot trust its miners: some will try to steal/take advantage. So it's a different problem, it's not as simple as subdividing the work |
|
|
|
|
I don't know how much detail do you require in the explanation... let's try this:
the chain origin is at hash * something
the more primes the origin has in it's factorization, the higher the probability of it having a long chain
that's why it looks for primorials: we want hash*something to be a multiple of the higher primorial possible, but we also want it to be a small number in order to make math faster
the "something" part is divided into a fixed part and a variable part. So the chain origin is hash * fixed * varMultiplier, where fixed*varMultiplier is the proof of work, and once the fixed part is selected, then the sieve to look for "varMultiplier" is generated
if hash is already multiple of some primorial, that fixed part could be smaller and the origin is still guarranteed to be part of a primorial. The varMultiplier part will be searched for starting from 1 and up to whatever the sieveSize.
The origin needs to be multiple of the primorial up to 7 to meet the minimum diff (this can be mathematically proven) otherwise it cannot generate the prime chain. That primorial is stored in bnHashFactor.
So we change the nonce until the hash is a multiple of bnHashFactor.
the origin (or the first prime of the chain, which is origin +/- 1) needs to be larger than bnPrimeMin, I guess this is to guarrantee that a minimum effort is required.
Now, we want a fixed part so origin is multiple of a primorial, we want it to be small because small numbers mean less RAM and faster math, but we want it to be large so that we meet the minimum value requirement (that minimum value is bnPrimeMin). Also, since the hash is already a multiple of bnHashFactor, we don't need to include that in the fixed part. So the fixed part is not actually a primorial, but a priomrial divided by bnHashFactor. Let's write this as
fixed = somePrimorial / bnHashFactor
What is the minimum possible value for that somePrimorial?
hash * somePrimorial / bnHashFactor > bnPrimeMin
so we get
somePrimorial > bnPrimeMin * bnPrimeMin / hash
so it's minimum possible value is
somePrimorialMin = bnPrimeMin * bnPrimeMin / hash + 1
and that's your first line of code
Then when we start with varMultiplier = 1, then origin is "origin = hash * fixed". If hash is multiple of primorial(7) then we don't need primorial(7) to be part of fixed. So instead of fixed being a primorial, it can be a somePrimorial / bnHashFactor, so it has a lower value.
This is done with the second line:
CBigNum bnFixedMultiplier = (bnPrimorial > bnHashFactor)? (bnPrimorial / bnHashFactor) : 1;
if our selected primorial "bnPrimorial" is larger than bnHashFactor, (since both bnPrimorial and bnHashFactor are primorials, it means bnPrimorial is a multiple of bnHashFactor) we can remove the factors of bnHashFactor from bnPrimorial and don't worry because hash * bnFixedMultiplier will still be a multiple of the desired primorial.
Now the else part: If bnPrimorial <= bnHashFactor, our selected primorial is less that the primorial factor needed to find a chain, which is already a divisor of hash, so our fixed part can be 1.
In practice, I never saw bnFixedMultiplier to be less than 11, so bnPrimorial was 2*3*5*7*11 and bnHashFactor was the constant 2*3*5*7. At least in the few cases I debugged I never saw it to be 1.
mmmm this post looks disorganized, I hope this is not a mess and you can understand something of it, sorry but it's late here
I believe it's sad that Sunny didn't explain any of this in the paper or the comments in the cod,e and we have to resort to deciphering what he's trying to do...
let me know if something is not clear
cheers
|
|
|
|
|
The ANN puts "it is using proof-of-stake not proof-of-work"... but how do you mine it if there's no proof of work?
proof of stake cannot work if nobody has any stake... how would you bootstrap the currency, ie how would the initial coins be created?
|
|
|
|
Pool share can be implemented as lower difficulty prime chains, similar to hashcash proof-of-work I think.
I'm not sure this is the case, or at least it is not as simple. With hashcash proof-of-work it is impossible to look for lower difficulty shares without also looking for higher difficulty shares. In Primecoin, on the other hand, as I understand it, one could look for chains of length 7 and find them with much greater frequency than they would find chains of length 7 while looking for chains of length 8 (i.e. pool miners would maximize their share submission by hurting the pool; the tragedy of the commons ensues). I assume that when the mining algorithm executes it first executes the Sieve of Eratosthenes to build a list of possible primes. If one finds that there is a list of 7 numbers that passed the sieve and form a chain then they could be checked to see if they form a valid share, even if the sieve eliminated the next value, proving that a block of difficulty 8 or higher is impossible from that start (I am assuming a share difficulty of 7 and a network difficulty of 8 or more). A miner optimized for finding valid blocks as fast as possible would save computational time by ignoring the chain of length 7 when the difficulty is 8 or higher, while a miner optimized for finding valid shares would check every chain of primes that passes the sieve that is at least (share length) long. This could be circumvented by requiring the numbers after the share's chain up to the integral network difficulty to all pass a sieve, but I believe that that would break the requirement that shares be fast to verify by the pool host. Additionally, it would set stringent requirements on how the numbers would have to be sieved which would limit improvements to be made in that area (which seems to be where most of the improvements are being made). You've made a really innovative coin, Sunny, and I trust you to come up with an innovative solution to this, but it isn't as simple as it may appear at first glance. My p2pclient will beat this problem. By making a sub blockchain with difficulty one less than the main chain's, payment is based on all the blocks you have submitted during the round. The P2P chain will end up producing many many more primes than the main chain does, maybe somebody will take it upon themselves to create a listening node and just store them, since I won't be making a site for the pool it won't be me, which also means I can make it a no-fee pool. How does it beat the problem? I think having difficulty one less does not solve it: a miner optimized for the sub blockchain could generate valid blocks which would not pass the sieve if they were working on the main chain. This means they get payed for work easier that what they should be doing, "stealing" from honest miners in the same pool. I guess that if all miners did this "cheat" the problem wouldn't be that serious, however lot's of hardware would be doing "useless" work, something that we were trying to avoid. this gets worse as the difference between the main chain's difficulty and the pool's difficulty gets higher. |
|
|
|
Hi gatra,
with those few blocks/day and primes/s being quite imprecise...
I left optimizations in when they didn't appear to cause an immediately visible (~10min) deterioration in primes/s.
Hi I didn't try it for primecoin, but for other coin I used this: https://github.com/freewil/bitcoin-testnet-boxIt's just a script that allows you to run 2 instances against each other, so it works like a small network of 2 nodes. If you run the optimized against the standard wallet and have them mine for some time, the faster one should have mined more blocks. Also, using ints for the bool arrays adds only a couple of fast instructions: for example instead of doing vfCompositeBiTwin[nVariableMultiplier] = true; you would do vfCompositeBiTwin[nVariableMultiplier >> 5] |= 1 << (nVariableMultiplier & 0x1f ) for testing it's if( vfCompositeBiTwin[nVariableMultiplier >> 5] & (1 << (nVariableMultiplier & 0x1f ))) |
|
|
|
Ok, so I'm probably hurting my income, but sharing some hints for optimizations:
A quick'n'dirty profiling run showed that we spend very much time in memory allocations, so I am trying to eliminate some of them.
-did the headerhash mod outlined earlier
-did the time limit on Weave() from Sunny King
-removed some printf's , especially
printf("MineProbablePrimeChain() : new sieve (%u/%u) ready in %uus\n", psieve->GetCandidateCount(), nMaxSieveSize, (unsigned int) (GetTimeMicros() - nStart));
from prime.cpp since it's the only call to the rather expensive GetCandidateCount
-after creating vPrimes array in prime.cpp, store vPrimes.size() in a static variably and replace all calls to it with the variable
-in prime.cpp, PrimeTableGetNextPrime and PrimeTableGetPreviousPrime: Use upper_bound/lower_bound instead of linear search:
// Get next prime number of p
bool PrimeTableGetNextPrime(unsigned int& p)
{
std::vector<unsigned int>::iterator foundelement=upper_bound(vPrimes.begin(), vPrimes.end(),p);
if (foundelement!=vPrimes.end()){
p=*foundelement;
return true;
}
return false;
}
// Get previous prime number of p
bool PrimeTableGetPreviousPrime(unsigned int& p)
{
std::vector<unsigned int>::iterator foundelement=lower_bound(vPrimes.begin(), vPrimes.end(),p);
if (foundelement!=vPrimes.end()){
p=*--foundelement;
return true;
}
return false;
}
- in prime.cpp, CSieveOfEratosthenes::Weave() :
Split the for loop into two for loops, one going up to nChainLength, the other one going up to 2*nChainLength
Thus, you can safe the first first if+for clause in the first loop and leave away the if, and leave the if+for completely away in the second loop.
Also,
if (((nBiTwinSeq & 1u) == 0))
...
if (((nBiTwinSeq & 1u) == 1u))
can be substituted by
if (((nBiTwinSeq & 1u) == 0))
....
else
.....
-prime.h: Removed nSieveSize and replaced all occurrences with nMaxSieveSize. Removed nSieveSize from the initializer as it's become obsolete.
-prime.h: Changed
< std::vector<bool> vfCompositeCunningham1;
< std::vector<bool> vfCompositeCunningham2;
< std::vector<bool> vfCompositeBiTwin;
---
> bool vfCompositeCunningham1[1000000];
> bool vfCompositeCunningham2[1000000];
> bool vfCompositeBiTwin[1000000];
Thus, we should save on quite a few mallocs.
did you measure the speedup of every change? the first rule of optimization is: measure! otherwise you may be making it worse without knowing... just a few comments: those bool arrays are probably no much better than the vectors. Each bool takes 1 byte of RAM. If you want to make that faster you have use an array of ints that is 1/32 of the size, and encode each bool in a single bit of the 32 bits. That will make arrays shorter, speeding up mallocs and making more bools fit in the cache. Also, probably changing the call to size() by a variable, and splitting the loop look like not worth it. However the upper and lower_bound are definitly better |
|
|
|
Ok!!... I think I got it... I think I have to sacrifice a virgin in a pyre meanwhile I performance a tribal dance in order to get more blocks... ok... so... I'll tell you the results in a while (when I can find a f***ing virgin... of course)  jeje, finding a f***ing virgin may be somewhat difficult... |
|
|
|
Does anyone know where in the code (or can translate to layman English) which hardware can actually mine or is restricted from mining? What I mean is: Some people having issues with EC2 nodes. My old/free CR-48 will not get any primespersec at all. My two desktops work fine. Etc, etc. Is there some prerequisite to have >0 primespersec within the code that could be referenced so I don't waste time compiling on old hardware only to not have it mine? I'm almost sure that there is no such thing as hardware black (or white) list. You may be getting 0 primespersec becuase your hard is too slow. |
|
|
|
I'll put up one Bitcoin in bounty for a CPU-miner (standalone) that will run on both windows and linux and outperform the built-in miner.
How much does it need to outperform it? I'm looking into possibly adding support to BFGMiner. since primespersec doesn't seem to have comparable meaning, it would be difficult to compare performance. Maybe primespersec could be normalized to the size of the primes and to the length of the chain? |
|
|
|
Correct me if I am wrong but isn't there already an existing set of prime numbers that are known?
Would this not be applicable to the proof of work function here?
There are infinitely many primes. However, the table of known primes is rather big and increasing all the time. New primes are huge and it takes weeks/months of computing power to find them, so I don't think this project can actually find any new ones. So in a way, I believe you could use the list of known primes, but then it becomes a memory-bound problem, and it's probably faster to use other tests than search through the list. you could not use any list. It's the same thing with SHA/scrypt mining: you could have a table with the nonce for every possible midstate. However it's not possible to store such table. If you could store one bit of information on every particle of the universe (imagine the whole universe is your hard disk), then you would need many universes to store that data. With prime numbers it's even worst: SHA/scrypt possibilities are huge but finite. Prime numbers and Cunningham chains are infinite. Genesis block has a starting prime in the order of hundreds of bits. If all his primes are this size then it's safe from tables. |
|
|
|
|
interesting...
can you prove that there will always exist a chain for any hash and any difficulty?
I guess a "proof" that relies on widely accepted conjectures (like the Rihemann Hypothesis) should suffice.
|
|
|
|
|
B506CDC2768418A0E7ECBECB88A4BEEF0712010F7D4E4984E64BEC113BEF0A5928FCCD8F8DA4720 377A7D579C87D08F7206B8097ECF90DB0E443CC0DA8A03EDB
|
|
|
|
Finally something that will actually have real value.
I wouldn't go that far. I know not yet. But I would like to see a proof of work linked to something like finding new primes and this project is the closest I've seen. but we haven't seen anything yet! please give more details on what this project is about |
|
|
|
- Pure proof-of-work, no proof-of-stake (unlike ppcoin), not energy efficient, but with additional potential scientific value derived from proof-of-work energy consumption (energy multiuse)
What kind of scientific value? I believe he is referring to finding high number prime numbers. Which actually can be quite difficult. Since the spacing of each prime number increases exponentially. I believe he is referring to finding high number prime numbers. Which actually can be quite difficult. Since the spacing of each prime number increases logarithmically. FTFY |
|
|
|
|
damn!
I've been working in a prime-finding proof of work and I'm currently testing my difficulty adjustment algorithm.
Also, I have plans for pool software too. How did you solve that?
I wonder if your ideas are similiar, and I'm looking forward to seeing you paper.
PM if you're interested in sharing ideas.
|
|
|
|
|
cool, but it's too centralized.
and since there seems to be no difficulty adjustment, the value will collapse when the ASICs come...
|
|
|
|
nature haha I'm free! |
|
|
|
|
why 10min? the announcement says it depends on the hash of the last block, and it has 32 Second block time
so as soon as you see a block you would have to decide if you mine or not depending on that block.
|
|
|
|
|
so it has to be automated, still, Difficulty hoping is being done automatically too.
|
|
|
|
|
Show Posts
