user22: 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?

user22: 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.


user554: 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.

user2789: 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.

user525: 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

user405: 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.

22: <p>There's a fork of Bitcoin called <a href="https://bitcointalk.org/index.php?topic=45667.0">Tenebrix</a> 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 <em>still</em> be faster on GPU than CPU or am I missing something inherent to scrypt that ruins GPU efficiency?</p>
 22: <p>I think I may have <a href="https://crypto.stackexchange.com/questions/400/why-cant-one-implement-bcrypt-in-cuda/401#401">located my own answer</a> (on a different StackExchange beta even!) </p>

<p>The answer to question "<a href="https://crypto.stackexchange.com/questions/400/why-cant-one-implement-bcrypt-in-cuda">Why can't one implement bcrypt in Cuda?</a>" 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:</p>

<blockquote>
  <p>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).</p>
  
  <p>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.</p>
  
  <p>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).</p>
  
  <p>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.</p>
</blockquote>
 554: <p>I know I am late to the party, but what is the incentive to use custom hardware when economies of scale make CPUs cheap ?</p>

<p>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)</p>

<p>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.</p>
 2789: <p>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.</p>
 525: <p>This might interest you
<a href="https://bitcointalk.org/index.php?topic=45849.0" rel="nofollow">https://bitcointalk.org/index.php?topic=45849.0</a>
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</p>
 405: <p>The scrypt() algorithm has at its core a routine called ROMmix.  Basically, it defines</p>

<pre><code>  V(1) = hash(message)
  V(2) = hash(hash(message))
  V(3) = hash(hash(hash(message)))
  ...
</code></pre>

<p>and it calculates</p>

<pre><code>  V(V(V(V(...(message))))
</code></pre>

<p>Since computing V(n+1) requires computing V(n) first, <strong>the most efficient way to do this is to cache all of the previously-computed values</strong>.  Once you've generated a large enough table, the V(V(V(...))) is just a bunch of lookups.</p>

<p>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).</p>

<p>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 <strong>an algorithm that is memory-dominated should "level the playing field" between CPUs and GPUs.</strong></p>

<p>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.</p>
