There's a fork of Bitcoin called Tenebrix that is claiming to be CPU-friendly and GPU-resistant (with regard to mining). They say that this is because they're using scrypt instead of SHA256. From what I'm reading, scrypt seems similar to bcrypt or PBKDF2 in that it's just a multi-round scheme. If it's simply more rounds of something that's already faster on GPU than CPU then wouldn't N rounds still be faster on GPU than CPU or am I missing something inherent to scrypt that ruins GPU efficiency?
asked Sep 30, 2011 at 18:59
-
4Keep in mind that Tenebrix is GPU-resistant, not custom-hardware-resistant. A custom PCB covered with lots of cheap pipelined DRAM chips and memory buses will still give vastly more hashes-per-dollar than a normal computer. I still don't understand why the Tenebrix creators think it's so important to hobble GPU miners.– eldentyrellCommented Sep 30, 2011 at 20:03
-
1I poked through the PDF on scrypt and while I didn't understand ALL of what was written, there was a section where the author combined the CPU & memory requirements for custom hardware to break a bunch of algorithms in terms of "die space" and compared the costs that way and scrypt still came out on top. I'm assuming these requirements also hobble FPGAs and at the very least would make ASICs much more expensive than for Bitcoin?– David PerryCommented Sep 30, 2011 at 20:32
-
1Oh, I see what you're saying. Building the memory into an ASIC would be expensive, but building the ASIC and buying already-cheap RAM on the side wouldn't be. How much RAM does Tenebrix's implementation of scrypt actually require?– David PerryCommented Sep 30, 2011 at 20:35
-
2David, the maximum size of the table (see my answer below) is a pseudorandom function of the message being hashed. There is no "required" amount of memory, although if you don't haven enough to hold the table you'll end up repeating a lot of expensive computation.– eldentyrellCommented Sep 30, 2011 at 21:48
-
1These two questions might interest you: Are there algorithms that could have been chosen for mining that balance CPU/GPU? and Are there algorithms that could be used for mining that resist acceleration with ASICs?– nmatCommented Sep 30, 2011 at 23:20
|
Show 5 more comments
5 Answers
The scrypt() algorithm has at its core a routine called ROMmix. Basically, it defines
V(1) = hash(message)
V(2) = hash(hash(message))
V(3) = hash(hash(hash(message)))
...
and it calculates
V(V(V(V(...(message))))
Since computing V(n+1) requires computing V(n) first, the most efficient way to do this is to cache all of the previously-computed values. Once you've generated a large enough table, the V(V(V(...))) is just a bunch of lookups.
Caching all the previously computed values requires lots of memory, and since each lookup depends on the previous one it's sensitive to memory latency (although if you're mining you can work on several blocks in parallel and pipeline the requests to get around this).
GPUs can perform far more integer operations per second than a normal CPU, but have roughly the same memory bandwidth/latency as a CPU. So an algorithm that is memory-dominated should "level the playing field" between CPUs and GPUs.
I still don't understand why the Tenebrix folks consider this to be an important goal. It just "equalizes" GPUs and CPUs, but you can still build custom hardware that does scrypt() much faster and cheaper than a CPU. So it's just going from "GPUs are best" to "custom printed circuit boards covered in memory buses are best". Nobody's been able to explain why this change is worth all the trouble.
-
I don't think it's that they're GPU hostile so much as they want to be CPU friendly. The current state of Bitcoin is that semi-specialized hardware is required just to participate. You can CPU mine Bitcoins but you're likely to never see a bitcent from it. It may be possible to bring in custom hardware, but I don't think it's cheap or likely and so CPU mining has someplace to flourish now. Commented Sep 30, 2011 at 23:26
-
1@DavidSchwartz, you're confusing latency with bandwidth. PCs are optimized for memory latency, but since mining is inherently parallel (just work on several blocks in parallel) you can always compensate for that by pipelining. It is not hard to build a machine with way, way, way more memory bandwidth than a PC: just devote all of the motherboard space to DIMM slots and memory bus traces instead of stuff like PCI slots and southbridge chips. Sun's Niagra machines were a midpoint along this continuum, and they had obscene memory bandwidth compared to then-top-of-the-line PCs. Commented Oct 1, 2011 at 21:59
-
2@David Perry writes I don't think it's cheap or likely and so CPU mining has someplace to flourish now. -- trust me, it is likely. If Tenebrix currency ever becomes valuable somebody (probably even me) will build the machine described above and start selling them. The situation will rapidly become worse than is for bitcoin: not only won't you be able to mine with CPUs, you won't be able to mine profitably with any device sold at a retail electronics store. Commented Oct 1, 2011 at 22:01
-
1@eldentyrell - you have it exactly backwards LATENCY not BANDWIDTH is what is important in scrypt. It doesn't require much bandwidth but it is nearly constantly either fetching or writing data to memory. This creates a bottleneck as the CPU has to idle until the operaiton is complete. Pipelining is useless because the net operation is based on inputs in memory. Latency is what kills scrypt performance. L2 cache has roughly a 2-5 cycle latency (depending on CPU design) while main memory has 240+ cycle latency. Commented Oct 10, 2011 at 13:16
-
2@this_site_is_a_cesspool it's quite easy: Tenebrix creators are silly kids who wanted to play mining and were angry they couldn't do it with Bitcoin, so created a custom currency which allowed them to do it with CPUs. Of course this is a very short-sighted and misguided operation, doomed to fail horribly.– o0'.Commented Feb 1, 2013 at 17:17
This might interest you https://bitcointalk.org/index.php?topic=45849.0 FPGA implementation was investigated, too, and it appears somewhat lacking in performance compared to a CPU about 1/7th the price, thus being quite non cost-effective
Tenebrix uses Scrypt as the proof of work algorithm. Scrypt was said to be GPU resistant due to the in memory look up tables the algorithm uses. Most people no longer mine tenebrix with CPUs and use GPUs instead. Mining tenebrix with a GPU you can expect to hash at approximately 1/1000th the rate you would get on the same card mining bitcoins. For example, if you had a 5970 mining bitcoin at ~700Mhash/s you could expect to get ~700khash/s mining tenebrix. There is by no means a direct correlation as in the example and in reality the tenebrix has rate will probably be less but it is true enough to do rough hardware comparisons where litecoin mining data is lacking.
I think I may have located my own answer (on a different StackExchange beta even!)
The answer to question "Why can't one implement bcrypt in Cuda?" seems similar enough to apply to scrypt/OpenCL as well (since they're basically the same technologies with different names) but I'd like verification from someone with a hair more crypto knowledge than myself. Here's the accepted answer from the other question:
It is not impossible, only harder. This is because of RAM. In a GPU, you have a number of cores which can do 32-bit operations. They will run at one operation per cycle and per core, as long as they operate on their respective registers. RAM access, however, is more troublesome. Each group of cores has access to a small amount of shared RAM, and all cores can read and write the GPU main RAM, but there are access restrictions: not all cores can read from or write to RAM simultaneously (constraints are stricter for main RAM).
Now bcrypt is a variant of the Blowfish key scheduling, which is defined over a table (a few kilobytes) which is constantly accessed and modified throughout the algorithm. Due to the size of the table, each core will have to store it in the GPU main RAM, and they will compete for usage of the memory bus. So bcrypt will run -- but not with full parallelism. At any time, most cores will be stalled, waiting for the memory bus to become free. This comes from the type of elementary operation bcrypt consists in, not from the fact that bcrypt is derived from the key schedule of a block cipher.
For SHA-1 or SHA-256, computation entirely consists in 32-bit operations on a handful of registers, so a password cracker will run without doing any memory access at all, and full parallelism is easily achieved (I did it on my GeForce 9800 GTX+, and I got about 98% of the theoretical maximum speed with a straightforward unrolled SHA-1 implementation).
For details on the programming model in CUDA, have a look at the CUDA C Programming Guide. Also, the author of bcrypt now proposes scrypt, which is even heavier on the memory accesses, exactly so that implementation is hard on GPU and FPGA.
answered Sep 30, 2011 at 19:13
I know I am late to the party, but what is the incentive to use custom hardware when economies of scale make CPUs cheap ?
A sane Rich Attacker would just buy hundreds of 4-cpu servers with, say, Bulldozer CPUs (In case of bitcoin a Rich Attacker could buy a screaming ton of GPUs or whichever equipment gives him best bang per buck)
You can't defend yourself against a Rich Attacker by technological means because no matter whether you use CPUs, GPUs, or Babage engines, he will just buy more tech than you can afford, end of line.
