CPU friendly Altcoin in development

[Seth Otterstad]

You wouldn't need 6GB.  The latency on main memory for a GPU is horribly bad so bad that any process which needs random access to GPU main memory will be annihilated by a CPU in terms of performance.  GPU memory is designed to stream textures and as such it couples massive bandwidth with extreme latency.  Scrypt was designed to fill the L3 cache of a CPU.  The developers of alt-coins had to intentionally lower the memory requirements by 99% to make GPU competitive.  Yes Litecoin and clones use about 128KB of cache.  The MINIMUM memory requirement for Scrypt is 12MB.  It doesn't take 16GB.  Try it out yourself or check out various hacking forums the OpenCL performance for Scrypt (2^14, 8, 1) is beyond pathetic.  A cheap CPU will run circles around it.

This begs the question: Was this known to the devs of Litecoin and/or Tenebrix? I mean, why else did they intentionally lower the memory requirements? Big scam after all (hurr durr gpu resistant)?

I have never got a satisfactory answer.  I will point out that it is intentional though.  The default parameters for Scrypt are (N=2^14, r=8, p=1), the parameters used by Litecoin are N=2^10, r=1, p=1).

I am not sure if was a scam but the end result is the same, Litecoin is 99% less memory hard then the default Scrypt and about 1/7000th as memory hard as the parameters recommended by the author for high security (not realtime) applications.

Why not use Scrypt as intended.  Scrypt with default variables has beyond horrible performance on GPUs.  Litecoin developers modified it to make it roughly 128x less memory resistant (using only 128KB total).

I'm working on this too and the problem I'm anticipating is that it will take time to verify the hash. The performance I'm seeing running scrypt to require 256MB of memory is a hash time of at least 0.5 seconds . . . . time increasing linearly with memory required . . that's not so bad for mining where you can just have a low difficulty, but creates a problem for clients verifying the block chain - it makes it a slower process, and could start to bite as the block chain gets longer.

Artforz said in one of his last posts on this forum that the verification time is the reason you can't jack up the n values.

So, the algorithm is fine as it is.  If you increase the amount of memory required, you end up with a GPU-favoured implementation of scrypt.

I don't understand this line but the rest of your post is a welcomed commentary that I do intend to provide counter-arguments for.

I would assume that the more memory required the *less* feasible GPU mining became. For instance you could (if artforz released the code) mine scrypt coins with a GPU but it would be so inefficient that you might as well just mine them with the CPU. My understanding is that increasing the amount of memory required further would make GPUs even more pitiful. If you kept increasing the memory required CPU's would decrease in hash power. Some CPU's with smaller and or slower amounts of cache (or inefficient cache usage) would fail to keep up. This would push innovation to improve memory management in CPU's as people try to design ways to make CPU's address large cache sizes faster or make more efficient use of L2 and L3 cache.

We would first see more efficient mining software just as people keep improving the existing scrypt miners but ultimately we would be pushing for CPU's that are continuously improving at memory hard math.  
Although you argue it is difficult to make large amounts of cache easy to address there is room for competition and innovation in this area as people push the boundaries on what is possible with the CPU.

Yes it sounds like a lot of very difficult work I agree but that's the whole idea. It is a speculation market for emerging CPU technology.

Short version: compared to (1024,1,1) increasing N and r actually helps GPUs and hurts CPUs.
Longer version:
While things are small enough to fit in L2, each CPU core can act mostly independently and has pretty large read/write BW, make it big enough to hit external memory and you've got ~15GB/s shared between all cores.
Meanwhile, GPU caches are too small to be of much use, so... with random reads at 128B/item a 256 bit GDDR5 bus ends up well < 20% peak BW, at 1024B/item that % increases very significantly.
end result, a 5870 ends up about 6 times as fast as a PhenomII for scrypt(8192,8,1). (without really trying to optimize either side, so ymmv).
The only way to make scrypt win on CPU-vs-GPU again would be to go WAAAY bigger, think > 128MB V array so you don't have enough RAM on GPUs to run enough parallel instances to mask latencies... but that also means it's REALLY slow (hash/sec? sec/hash!) and you need the same amount of memory to check results... Now who wants a *coin where a normal node needs several seconds and 100s of megs to gigs of ram just to check a block PoW for validity?

The guys who maintain YACoin disagree with artforz and tacotime's position.  They claim that verification time is not a problem based on their testing.

Sorry if this has been answered before, but I just found out about YACoin and I don't want to read all 170 pages.

Is YACoin just continually raising the N value?  Does this mean it will eventually take a huge amount of time to check a block PoW for validity?  How could this possibly be a good idea?

Probably the YACoin ongoing development thread will give you a better idea while reading much less than 170 pages:
https://bitcointalk.org/index.php?topic=206577.0

My post with my benchmarks for hash rates at various values of N, and when YACoin will switch to those values of N, is in the 15th post:
https://bitcointalk.org/index.php?topic=206577.msg2162620#msg2162620

I benchmarked with a 4 year old dual Xeon E5450 server (almost stone age technology, but similar combined performance to today's i7-2600k's).  It appears it'll be a few decades before even today's hardware (or hardware from 4 years ago) would have a problem with the time needed to validate a block PoW.

As time goes on, doubling of N becomes further and further apart in time.  Advances in computing power will rapidly outpace the rising N over the long term.

So I am to understand that when coblee asked for suggestions on how to prevent GPUs from taking over litecoin, all he had to do was change the N value to higher than 8192 and litecoin would have become way more GPU resistant?

Coblee's thread about GPU-mining and Litecoin:
https://bitcointalk.org/index.php?topic=64239.0

Thanks for the reply!  So am I to understand that artforz's analysis is wrong?  I guess that wouldn't be the first time....

The other thread has the majority of the GPU discussion, including benchmarks from mtrlt, the developer of Reaper (the first GPU kernel released for Litecoin in response to ArtForz's claim Litecoin was GPU resistant).  I disagree with ArtForz's claim that increasing N helps GPU's once both CPU's and GPU's are computing hashes large enough that they're pushed to external RAM.  I would say ArtForz's analysis was cherry-picked based on the specific value of N (8192) where computation gets pushed out of the L2 cache on the AMD Phenom II he was testing with.

Indications, including from mtrlt's benchmarks, are that the performance spread between CPU's and GPU's narrows as N rises.  As long as we don't cherry-pick a specific result from a certain value of N on an AMD Phenom II CPU..

Also note that YACoin doesn't use the same scrypt variant as Litecoin.  The mixing algorithm is switched from salsa20/8 to chacha20/8, and the hashing algorithm is switched from SHA-256 to Keccak-512.  Direct comparisons between hash rates of the two aren't quite going to be an apples-vs-oranges comparison for a given value of N.

Well, the N factor increases memory requirements for computing a single hash (thus it's using more memory and memory bandwidth). Current GPUs will quickly run out-of-memory (or there's other GPU-specific constraint that prevents the code from running at higher N, dunno). However, it also affects CPUs really hard (around 40% hashrate decrease if I remember correctly).

Nah, all you have to do is increase the lookup gap (via the previously published TMTO solution for scrypt from cgminer/reaper) and then you can compute the same hashes with less memory.

There's a probably bug in mtrlt's current code that doesn't allow calculation above N=4096, but it's possible that this particular TMTO implementation is not really optimized well for the GPU and that in the future with some hacking we'll see the gap further widen.

The further up the N value you get, the greater dependence on memory access speeds you typically observe (or at least, I observed using scrypt-jane on a CPU).  I wouldn't be surprised if eventually an implementation for GPUs came along that was optimized and destroyed CPUs for efficiency and speed.

BLAKE is used as an entropy source to randomize memory access too, I wouldn't be surprised if you looked at accesses to the lookup table and found that they end up being less than random as well due to consistent ordering of some types of data in the block header (thus also diminishing the amount of memory required).  I think pooler observed this when he was writing his CPU miner.

The whole point of trying to make a GPU-hard coin is to get a more even initial coin distribution than bitcoin/litecoin did.  The number of people with CPUs is way higher than the number with good GPUs.  There is no point to making a new alt-coin to change the mining algorithm if it doesn't promote a wider distribution by cutting out the GPU farmers.  The algorithm doesn't have to last forever; it only has to last a few years until ASICs are developed.  Litecoin lost its whole purpose when it was taken over by GPUs.  If we knew a way to assign an equal amount of coins to everyone on the planet in a decentralized way, we would do that, but that technology is decades away.  Distributing it to everyone with a CPU is way less fair, but it is still vastly superior to giving it to everyone with a GPU.

Here are the benchmarks from mtrlt, who was the first to write a GPU miner for litecoin.  He switched to mining YACoin because it was more profitable for him.  Now he is writing a GPU primecoin miner apparently, but I haven't paid attention for a several months.

Here are all my GPU benchmarking results, and also the speed ratio of GPUs and CPUs, for good measure.

GPU: HD6990 underclocked 830/1250 -> 738/1250, undervolted 1.12V -> 0.96V. assuming 320W power usage
CPU: WindMaster's 4 year old dual Xeon, assuming 80W power usage. In reality it's probably more, but newer processors achieve the same performance with less power usage.

Code:

N      GPUspeed    CPUspeed     GPU/CPU power-efficiency ratio
32     10.02 MH/s  358.8 kH/s   6.98
64     6.985 MH/s  279.2 kH/s   6.25
128    3.949 MH/s  194.0 kH/s   5.1
256    2.004 MH/s  119.2 kH/s   4.2
512    1.060 MH/s  66.96 kH/s   3.95
1024   544.2 kH/s  34.80 kH/s   3.9
2048   278.7 kH/s  18.01 kH/s   3.88
4096   98.5 kH/s   9.077 kH/s   2.72
8192+  0 H/s       4.595 kH/s   0

GPUs are getting comparatively slower bit by bit, until (as I've stated in an earlier post) at N=8192, GPU mining seems to break altogether.

EDIT: Replaced GPU/CPU ratio with a more useful power-efficiency ratio.

TacoTime asked if he had played with the lookup gap, and he said he had played with it quite a bit and couldn't get it to mine faster.  You can see here that jacking up the N value DOES make GPU mining substantially less effective relative to the CPU, and apparently they are not having problems with verification times.  YAcoin switches to N=8192 on August 13th.  You should probably get WindMaster in here to comment.

[Seth Otterstad]

Regardless of what innovation you develop or how cool this "CPU Friendly" coin will be, until you solve the Botnet issue, there will never be a successful cpu only crypto coin.

That should be the first priority.


Just an opinion.

~BCX~

Both Litecoin and Bitcoin have had large botnets mining them early in their histories, and it hasn't been any huge security issue as far as I remember.  The legitimate miners eventually outnumber the botnets.  I will agree that if anything can reasonably done to prevent them from mining, it should be done because the whole point of a CPU coin is to get a better initial distribution of the currency, and having tons of CPUs all linking to one person is bad for that.

[Flashman]

Just a driveby thought.

I am under the impression that the vast majority of botnet machines are windows XP 32 bit.

Therefore, make it 64 bit only, or make minimum memory requirement 3.5 GB or wherever the cutoff is for what XP handles.

[FreeTrade]

Seth - thanks for compiling all that history and summarizing the position on this with the different altcoins. Here's my take . .

>Artforz said in one of his last posts on this forum that the verification time is the reason you can't jack up the n values.

This is true to an extent . . . but Litecoin's N values could have been a lot higher before that became an issue.

If you look at the following chart -
http://yacexplorer.tk/graphs.htm

Litecoin has an Nfactor of around 8 . . . you could go right up to 17/18 before you see a problem with verification times. Most CPU users can verify those blocks faster than they can download them.

>The guys who maintain YACoin disagree with artforz and tacotime's position.  They claim that verification time is not a problem based on their testing.

It may not be a problem, but that will be based on their timeframe rather than their testing. They're expecting faster CPUs and memory to reduce the time as the NFactor increases. NFactor 20 takes 0.5 seconds now, who knows what that will be in 2020. But Yacoin was handed to the GPU miners, so I don't see it even tried to be GPU resistant. It would have been interesting if it had started with an NFactor of 15 or 16. As it is, it'll take a year to get to that point.

[Lauda]

I like CPU friendy coins 

[Seth Otterstad]

In case anyone is curious, here is the thread with the speculation that Coblee and Artforz knew litecoin was not GPU hard and were mining it with GPUs from the start.

https://bitcointalk.org/index.php?topic=63365.0

I think it is funny that now ignorant litecoiners are the ones saying "cpu coins will get ruined by botnets", when the whole point of litecoin was to be a cpu coin in the first place.

Here is another thread where Coblee suggests changing litecoin's proof-of-work to something more GPU hard after a GPU miner was proven to exist.  TacoTime suggests a radix sort at the end of the thread, and then nothing was done to change it.

https://bitcointalk.org/index.php?topic=64239.0

Most litecoiners have no idea this happened and continue to promote a coin that already has 19 million coins mined in a way that is most likely a massive deception.

There is definitely some room for a CPU coin.  I would recommend signing up a few merchants and coming up with a method to pay for stuff like electrum support, phone wallet support, and exchange support before launching it.

I recall seeing a coin launched within the last two weeks that claimed to use 6 different hashing functions.  What was the problem with that one?

[FreeTrade]

I recall seeing a coin launched within the last two weeks that claimed to use 6 different hashing functions.  What was the problem with that one?

That was Quarkcoin, and I quite like that one. There's also Primecoin which I think might turn out to be more GPU resistant than some had imagined.

[markm]

I have followed the whole CPU vs GPU debate since it started, and nowadays it has been looking more and more clear to me that we really should try to keep securing the network separate in our minds from initial distribution of coins.

Is there any big reason to force the ongoing securing of the network to have to be done by inefficient hardware?

Or would it be fine to leave that to the most secure and efficient method a given point in history allows?

(History of a coin itself not just the field in general; for example even if methods different from bitcoin's are more efficient changing bitcoin to use a different method at this point in its history is more than just a technical problem of upgrading to the latest technology.)

Suppose for example that Ripple's consensus method turns out to be both effective and efficient and its source code is released or a free open source implementation is built to circumvent its failure to release its source code.

Would it not be ideal to use such an approach to securing the network, leaving us with only the question of how to initially distribute its built-in ("native") currency?

Or would that make the problem of who even gets to be a node that actually matters too political or something?

Another possibly useful thought-experiment is to imagine we already have a fine and dandy initial distribution of the currency ready to go and are only worrying now about how nodes get to be nodes that actually matter. For this thought experiment how the initial distribution happens can be a black box, magic, how it works need not be part of our concern. Although I expect man people have various ideas how it might work. Some ideas I have i do not even want to mention before using them, since most such ideas can be gamed so part of coming up with them is thinking of something there was hotherto no good motive to game thus that are unlikely to have already been gamed in anticipation of being used.

(Forum accounts and email addresses and IP addresses for example people already have motive to have gamed / sockpuppeted, same for facebook accounts and such. But blockchain based things based on blockchain activities that cost fees would have cost people to have gamed ahead of time for years, would anyone have bothered if they weren't sure their expensive gaming was going to be rewarded someday by the launch of a coin that issues its new coins to people who had done those precise actions on that particular already-existing blockchain?)

Initial distribution of coins aside then however that gets accomplished... is there any big reason for all this anti-GPU, anti-FPGA, anti-ASIC stuff purely for the ongoing securing of a network / blockchain / ledger / transaction-set ?

-MarkM-

[FreeTrade]

Initial distribution of coins aside then however that gets accomplished... is there any big reason for all this anti-GPU, anti-FPGA, anti-ASIC stuff purely for the ongoing securing of a network / blockchain / ledger / transaction-set ?

Ongoing distribution is a feature too . . in 5 years time will a user be able to get some of your altcoin by joining a pool and converting electricity into altcoin, or will he need to buy it from a third party. By ensuring CPU generation is efficient, we'll be able to ensure both the user can generate altcoin for himself, or have a local thirdparty who can.

[DeathAndTaxes]

Initial distribution of coins aside then however that gets accomplished... is there any big reason for all this anti-GPU, anti-FPGA, anti-ASIC stuff purely for the ongoing securing of a network / blockchain / ledger / transaction-set ?

Sure because it works.  POW has been proven to work.  POS is more efficient and is "close" to working but requires significant centralized control (checkpointing) something which may be improved upon in future versions.  You keep talking about Ripple as if it works. It doesn't or at least it hasn't been shown/proven to work in an open network where some nodes are malicious.   

If it works then great but why not cross that bridge when (never) you get to it.  My belief is that Ripple will never work in an open psuedo-anonymous network.  So anyone planning to go that route is planning to build a closed source, central authority coin.  The good new is it will be very efficient.

[markm]

Initial distribution of coins aside then however that gets accomplished... is there any big reason for all this anti-GPU, anti-FPGA, anti-ASIC stuff purely for the ongoing securing of a network / blockchain / ledger / transaction-set ?

Ongoing distribution is a feature too . . in 5 years time will a user be able to get some of your altcoin by joining a pool and converting electricity into altcoin, or will he need to buy it from a third party. By ensuring CPU generation is efficient, we'll be able to ensure both the user can generate altcoin for himself, or have a local thirdparty who can.

Okay but what about in 25 years time, 100 years, 100,000 years, etc?

Do we have to keep minting forever? it seems like part of the appeal of Bitcoin has always been that after the relatively brief initial 140 years or whatever during which initial distribution takes place we do eventually reach a point where that is all, we have reached the cap, the only way to get some now is to go into business earning them (including going into the transaction-processing business which is just one of many possible financial-services businesses one could choose to get into) or just outright buy some.

Transaction fees presumably do ensure that there will always be some for sale, even if they are being sold only for the specific service of processing transactions; but can a currency be a success, even only as a store of value, if that is the only product or service they ever get used to buy? If not then there will be other products or services one can buy the coins with, so transaction processing surely should have no special desirability it should become merely yet another product or service people can choose to go into business as a provider of.

So really unless your model is that a cap is bad, minting forever is needed, then this whole get the coins minted thing should probably be done rapidly, so that as soon as possible the world can reach the presumable long term equilibrium stage in which minting is long over, part of prehistory, and we get to see the real thing really running not just yet another "get in early to get rich" pyramid / ponzi / tulip-mania / IPO type project?

It does not seem unreasonable to question the division of motives, as in how much if any of the motivation is actually the goal of the long term stable state versus how much is the desire to launch yet another "get rich in 150 years or less" scheme...

-MarkM-

[Seth Otterstad]

Markm, of course we could MASSIVELY improve upon bitcoin and get everyone to switch to a new coin if we designed one that was:
a) more efficient while still providing the same level of security
b) equally distributed to everyone on the planet in a decentralized way

The thing is, we don't know how to do either of those things yet.  If ripple is proven to work (unlikely), that could solve A.  B is virtually guaranteed to be solved within a few decades, but is impossible now.  Governments are reasonably well equipped to do an initial distribution to a population with minimal gaming of the giveaway mechanism, but it would never be decentralized.

By the time these things are solved, bitcoin's network effect is likely to be so large that even a more efficient and fair coin will not be able to displace it.

Btw, you cannot use events in the block chain to distribute an alt-coin because that would result in an even narrower initial distribution than bitcoin had.

[markm]

I do not think it is practical, given the number of CPUs in existence and the projected numbers of things-that-can-do-a-CPU's-job going forward, to expect, aim for or hope for one person with one CPU, or even one person with one normal everyday everyone has one billion-trillion-CPU-equipped-handheld-device, to be able to earn any really useful fraction of the common weal / common wealth in any reasonable span of time by mere application of that device to well known familiar task(s) everyone knows full well can be done by such a device and has access to the program/app for doing.

There are many examples in history, even merely in the history of the internet.

Every fully automatic method of raking in money over the internet from home using your PC died a horrible death once someone made available a Windows binary GUI app for doing it.

Every single one, I am pretty sure?

Can anyone come up with one that didn't?

Even CPU-mining Bitcoin, which is one of the latest such things, died a horrible death once compiled GUIs for Windows became available to do it.

This whole thread is motivated by the same quest that motivated the spam ten million email address apps for Windows, the spam the newsgroups apps for Windows, the build a pyramid of marketers marketing for you apps for online marketers and so on and so on.

There are too many people, with too many PCs, dividing up pies that like ponzis and pyramids can only grow so large before the piece of pie each PC gets is too trivial to be worth doing.

Such things always (any counterexamples, anyone?) seem to get to a point where even just trying to keep up with trying all kinds of new twists on the same old ideas, join new launches of the same thing renamed/rebranded and so on and so on ends up making you less money per hour that you'd make simply solving captchas for pay or other "mechanical turk" type tasks.

I strongly suspect that even the time put into these discussions only seems potentially likely to pay off if you plan on being an "early adopter", one of the top of the pyramid / early entrant to the ponzi people who runs around making money off the suckers who buy into the scheme or buy the Windows app not realising the very fact that anyone with Windows can run it already means the thing the app does is obsolete. Selling the Windows app is pretty much the last resort, the last way to try to eke out a few last bucks from a wonderfully lucrative exploit that unfortunately too many people are exploiting for it to be worthwhile anymore for any one of them.

I realise I seem to be arguing that no one would sell shovels unless the shovels would dig them less gold using them directly or by means of employees than they make just selling the damn shovels. You sell the shovels once using them is no longer lucrative. Hmm. So I can see that I still need more insight.

-MarkM-

[FreeTrade]

So really unless your model is that a cap is bad, minting forever is needed, then this whole get the coins minted thing should probably be done rapidly, so that as soon as possible the world can reach the presumable long term equilibrium stage in which minting is long over, part of prehistory,

The model I favor is rapid distribution followed by a 2% inflation. I'll have more about this soon.

[eule]

The model I favor is rapid distribution followed by a 2% inflation. I'll have more about this soon.

I thought about making my own clone, where all coins are given out after 1 year or so, calling it Finitecoin. 

[FreeTrade]

I thought about making my own clone, where all coins are given out after 1 year or so, calling it Finitecoin. 

No need for a clone. Take a closer look at Infinitecoin. The name is a con to make people think it is inflationary . . but everything will be distributed within 6 months.

[Impaler]

I've speculated about a protocol that might use the Peer-2-Peer network itself as a place of 'work'.  Block solving is done by daisy chaining together a number of signatures, the resulting hash then determines (randomly) what public keys are eligible to sign again.  The chain of signatures just grows as it bounces from node too node until it legally can be signed by its original creator to complete a chain-link, this makes the total number of signatures random.  The obvious weakness it that private keys are free so a huge number can be created to churn through, so an additional PoS signature might be needed with the chain-link requiring a cumulative total.  Also a small nominal coin cost to keep an address active would also be a good idea as it may make the mass address attack unaffordable, and it would likely have a stabilizing effect on valuation too.

I've also begun wondering if a more distributed chain is also something we want.  Rather then one monolithic chain, ever account is its own chain with each transaction being it's own block that requires both parties to sign, thus each transaction is a point were two chains share a block.  The only way to double spend is thus to create two forks of your private chain with two different people and preventing them from learning of each other.  By doing this daisy-chain proof you force the disclosure of all transactions to the network at large and eliminate mining-in-secret which is the object of any double spend.

[eule]

I thought about making my own clone, where all coins are given out after 1 year or so, calling it Finitecoin. 

No need for a clone. Take a closer look at Infinitecoin. The name is a con to make people think it is inflationary . . but everything will be distributed within 6 months.

Oh, didn't know that, that's quite an interesting experiment then.

[Flashman]

Howabout reverse difficulty with reward doubling, time limited and proof of stake (So it's not last minute gazumped) gold at the end of the rainbow coin or something

[Seth Otterstad]

Mark I agree that bitcoin's distribution mechanism is incredibly terrible.  I mean 99.99% of the world's population does not own any bitcoins and the distribution is halfway done!  Unfortunately, no one has been able to think of a better decentralized solution, and Satoshi was a genius to even be able to think of the one we have now.

Giving coins to everyone with a forum account or email address, while open to manipulation, still gives a WAY better initial distribution than mining does.  Ripple does this.  Unfortunately this method sabotages the ability to use proof-of-work to secure the network since the miners won't have any incentive to mine on a new network with few transactions if they don't get a block reward, so proof-of-work must be abandoned in favor of a centralized solution.