Topic: What lies beyond ASICs? (Read 2246 times)

Thank you for the insightful comment.  The analogy helps a lot.

Ha Ha, I see what you did there 

They aren't inefficient at mining they are completely incapable of mining.  A quantum computer of insufficient size (in terms of qubits) to "model" the problem can't solve the problem even given an infinite amount of time.   Even if a quantum computer of sufficient size (# of qubits) was built collision resistant hashing algorithms (like SHA) can't be solved using Shor's algorithm.  The only known quantum algorithm is Grover's algorithm which doesn't provide the exponential reduction that Shor's algorithm does.

To brute force a symetric key or hash function requires 2^n operations (attempts) in classical computing.  Grover's algorithm reduces that to 2^(n/2).  There has been little work done in quantum resistant hashes because despite how great n/2 vs n looks one can compensate by simply doubling the hash size. For example if someday a quantum computer could break a 2^256 hash in reasonable amount of time one could go to 2^512 hash (which would require 2^256 operations or 2^128 times as long as that "reasonable amount of time").  We routinely extend hashes beyond what is necessary.  Brute force of SHA-128 isn't even possible using classical computing and probably won't be in our lifetimes (barring some cryptographic break) but we hedge that by using 256 bit (or 512 bit) hashes instead.

For bitcoin mining the issue becomes more complex.  The Grover's algorithm looks for a specific value (which is very difficult in a 2^256 keyspace) but Bitcoin mining isn't that hard.  In Bitcoin mining where the miner is looking for ANY value that is less than the difficulty based on the target.  In other words a miner's job is easier than a simple brute force attack because any hash meeting the difficulty target is "good".  For current difficulty, the target is 0x0000000000000113370000000000000000000000000000000000000000000000 in hexadecimal and there are 1,797,329,777,810,040,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 potential hashes below that target.  

For SHA-256 a QC running Grover's algorithm would require 2^128 attempts to break a specific hash.  However a Bitcoin miner using classical computing can find (at current difficulty) one (of many) hash which is small enough in "only" ~2^56 attempts.  2^56 is still a smaller number of operations than 2^128 even if 2^128 is much smaller than 2^256.  

A common misconception is that QC are "faster" in the sense that a single operation is completed faster which is incorrect.  In actuality they are many many magnitudes slower due to need for retesting to compensate for quantum noise (errors).  They are "faster" because they need to perform less operations. It would be more accurate to say they operate more efficiently.  An analogy might help.  Imagine you have a task which requires 1 second per attempt and on average takes 3,600 attempts to find a solution.  It would take you on average 1 hour to complete.  On the other hand if you could complete the task in such a way that it took 10 seconds per attempt but on average only took six attempts the time to a solution is now only a minute.  Although the individual attempt takes 10x as long the fact that the new algorithm is so much more efficient means the solution is found faster.  This is how quantum computers gain significant "speed" increases.  They are "fast" because they exploit quantum properties to reduce the number of attempts not because each attempt is any faster.

2^128 quantum operations is still greater than 2^56 classical operations even if both systems could complete a single operation in the same amount of time.  At the current time quantum computers are much slower per operation but that will likely decrease with time.  Satoshi did well using a 256 bit hash although SHA-128 for example is essentially unbreakable even with classical computing.  Had he done so 2^64 is pretty close to 2^56 and when difficulty is 20 billion a quantum computer would require less operations than a classical one.  Even then it is unclear if quantum mining would be faster.

Could you repeat that please.

No
+
Go troll elsewhere
+
This is why we have newbie limitations

I think that any further and the bitcoin market will collapse.

This is the key to all high performance computing. Just look at the current top supercomputer ... 17 PetaFlops consuming 8MW.
Compare to human brain consuming 20 Watts. Estimates vary between 1 PetaFlop and 1000000 Petaflops to emulate (once we've got the software development cracked). So there is clearly some great scope for improvement, possibly using "WetWare" (real neurons genetically engineered), all the way to the "Computronium" beloved of the Singulantarians.

Not so sure about renewable/free energy though. Miners need to run 24*7 to stand any hope of ROI before they are outpaced by the difficulty spiral. Energy storage is expensive for intermittent renewable sources. Perhaps hydro or geothermal? Or for the space-cadets, put your rigs in orbit closer to the sun (latency may be a problem though, too many orphaned blocks).

The one area that few people in this particular debate topic focus on is the "left hand" of mining...

In mining, you need processing/calculating power, of course.  But that's not the full equation.  It's "how much power do we have" for "how much energy we put out."  The only reason ASICs are superior to GPU or even CPU mining is because of their speed PER kilowatt-hour.  You could theoretically have millions of CPUs still mining, but the power requirements make no financial sense.

The next step isn't about faster-than-ASIC, it's about less-power-than-ASIC.

I think instead of counting on faster and faster hashrates, you'll find more ASIC miners who switch to solar or wind energy for "free" energy.

To me, that will be where bitcoin mining finds its most profitable path -- no energy costs, high output.

You might need to arrange another 10e70 universes to store it all in at one atom per bit.

Or a huge rainbow table with all hash values in it. It should have capacity of 2^511 bits and some very fast search function.

Printed on the window organic transistors powered by sun light. Not very powerful, but cheap to produce and no electricity is needed.

I could imagine, one day there might occur a demand to create Coin-Algorithms which do not depend so much on hardware-power.

For example: some sort of smart algorithm-switching could perhaps be an approach to prevent any motivation to design, build and deal cost-intensive dedicated hardware.
It might be especially optimized for usual mainstream-hardware in order to get distributed to greatest possible extent.

Bitcoin like most other Cryptos promotes an idea of "Indendancy" - but as we now see with ASICs all current systems are vulnerable via the hardware-side.
(For the scrypt-fans - look here: https://bitcointalksearch.org/topic/scrypt-litecoin-asic-prototype-231185 )

It should not be forgotten: Big Money could afford almost any material equipment which allows for technical prevalence. 

A Quantum computer is very specialized. It only "works" for very specific types of problems and I do not believe bitmining is included in that list. It also has to compete with the cost efficiency of ASIC's. Basically it all depends on how the next generations of quantum computers will work. I cant say with certainty that they wont be able to bit mine but I am 80% sure they essentially cant and 99% sure that if they could they would cost more to run then the bitcoins you would earn.

After creating the thread I read what a lot of other bitcoiners have been recently mulling over.  Here is a brief summary: proto-quantum computers exist (D-Wave based in Canada) and have sold for $10-$15 M to Lockheed Martin and Google/NASA Ames.  It is generally thought that these adiabatic devices are not capable of high-level cryptography and pose little threat to the bitcoin ecosystem.  Additionally, some believe that the device will also be inefficient at mining -- although I am inclined to think otherwise.  Needless to say, the challenges to the bitcoin protocol posed by QC will be met as affordable devices reach the market.  I am confident that the bitcoin community will adapt, but I do think that QC will be used to mine someday.

Please read this for a detailed explanation above quantum computing and SHA256 hashes.

http://en.wikipedia.org/wiki/Key_size#Effect_of_quantum_computing_attacks_on_key_strength

Basically iterations go from 2^n to 2^(n/2) where n is the key length so it implies that if / when quantum computers become available implementing SHA512 would give the same amount of security as SHA256 does today.

You just described mask-programmed gate arrays (uncommitted logic arrays), technology from the 1980's (I know, because I worked on them). They were superceded by field-programmed gate arrays FPGA (which did away with the final metallzation mask, changing them from a custom Application Specifc Integratd Circuit (ASIC) to commodity devices). They still exist to some degree (I think the Altera Hardcopy FPGA conversions use similar technology ... [edit] yes, its called "Structured ASIC", much more sophisticated than the original ULA's  with up to 6 layers of customizable metal and via, but essentially the same sort of beast, and exactly fitting your description).

AFAIK all the current mining ASICs are full custom designs (using standard cell libraries), not that that helped BFL who made a right dog's dinner of their design flow.

Moores law man, something with double the power will probably come out.

I believe that the current generation of ASICs will be further refined at smaller nm which results in more efficient mining that runs cooler. The small size of each chip would allow more to be fit on boards, resulting in even greater hash rates.

Here's the analogy that I'm familiar with.  A CPU runs like a bunch of CEOs in the boardroom.  They are a few highly intelligent employees of a corporation who exhibit cognitive flexibility, and supreme decision-making skills.  Although CPUs serve a vital role in computation, they are ineffectual miners.  GPUs are like factory workers who routinely perform the same monotonous operation.  GPUs are extremely well-suited to perform mining tasks (e.g., proofs of work).  FGPAs compound the benefit of GPUs by sheer numerosity.  ASICs are substantially better than CPU for the same reason but they were specifically designed perform the same mundane task over and over.

Your comment above indicates that you'd lump quantum processors in the same group as classical CPUs.  What support is there for this contention? 

One of the most well-known properties of quantum computers is their ability to concurrently maintain multiple states due to quantum superposition.  A qubit can take on the classical values of 0 and 1, but it can also take a third value that conveys a sense of indeterminacy -- both/neither 0 and 1 simultaneously.  The way I see it, the speed-up comes in the way the data are processed as a result of prepared inputs.  Thus, if the inputs to the hashing algorithm were sufficiently prepared to take advantage of the quantum speed-up, then we'd have a system that could hash exponentially faster than a classical CPU.     

Mainly because the process is already so fast that the change would be neglectable and probably cost more then you would earn in the end. The only reasonable way to evolve bit coin miners is quantity. Not quality, not efficiency and not cost. Not saying it would not be beneficial to do it just that dollar for dollar you get more hashes by getting more transistors/gates (or whatever they use to calculate). Like it or not we will probably be stuck on Asics for a while.

I would also like to add that another thing that is most likely going to be a problem for quantum computers and that is how fast they can repeat the process. From Graphics cards to Asics the system is designed to do one thing and that is to run one type of calculations as fast as possible. Processors and Quantum computers might be scary fast but (this is just speculations on the quantum computer part) they will be very slow in comparison with running the same calculation over and over again.