tromp


November 16, 2015, 04:33:59 PM 

Computing a single bit of a hash is almost as much effort as computing the whole hash; you might be saving a percent or two at most.
Could you provide a proof of this statement? Thus follows directly from how SHA256 is defined. It is many rounds of confusion and dispersion; so that each single bits in one round depends on pretty much all bits of previous rounds. That is a long document to read. Where exactly does it claim that?





Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.




tromp


November 16, 2015, 04:37:39 PM 

But Hashcash with large memory requirements will likely not be affected as long as scaling quantum computers up to millions of bits remains elusive.
I didn't find information on timememory tradeoff of quantum computers, but if we assume that the tradeoff is not worse than the tradeoff of classical computers then we get that memory increase of the hashing function can be counteracted by increasing time we run the computations. So Hashcash with large memory won't save us. Of course I was talking about hashfunctions that don't allow for timememory tradeoffs.




ComefromBeyond
Legendary
Offline
Activity: 1526
Newbie


November 16, 2015, 05:21:04 PM 

Of course I was talking about hashfunctions that don't allow for timememory tradeoffs.
Give me the name of one of such functions, please. The tradeoff is a pretty universal thing, the best a function can do is to keep time*memory*advice constant, if I'm not mistaken.




ComefromBeyond
Legendary
Offline
Activity: 1526
Newbie


November 16, 2015, 05:27:47 PM 

so that each single bits in one round depends on pretty much all bits of previous rounds.
This means that after some number of rounds SHA256 doesn't give a better mixing, hence it's possible to do a shortcut by finding a polynomial with fewer number of operators. That is a long document to read. Where exactly does it claim that?
I introduced a novel algorithm to solve the bitcoin mining problem without using (explicit) brute force. Instead, the nonce search is encoded as a decision problem and solved by a SAT solver in such a way that a satisfiable instance contains a valid nonce. The key ingredients in the algorithm are a nondeterministic nonce and the ability to take advantage of the known structure of a valid hash using assume statements.
A couple of benchmarks demonstrated that already with simple parameter tuning dramatic speed ups can be achieved. Additionally, I explored the contentious claim that the algorithm might get more efficient with increasing bitcoin difficulty. Initial tests showed that block 218430 with considerably higher difficulty is solved more efficiently than the genesis block 0 for a given nonce range. This means that in average computation of a single bit takes less time than computation of the whole hash.




tromp


November 16, 2015, 06:25:11 PM 

Of course I was talking about hashfunctions that don't allow for timememory tradeoffs.
Give me the name of one of such functions, please. The tradeoff is a pretty universal thing, the best a function can do is to keep time*memory*advice constant, if I'm not mistaken. You are quite mistaken. This is a recognized weakness in scypt's design. Here's one: Argon2, winner of the Password Hashing Competition. Most of the PHC candidates qualify, since timememorytradeoff resistance was one of the design goals.




tromp


November 16, 2015, 06:41:47 PM 

This means that in average computation of a single bit takes less time than computation of the whole hash.
Like I said it takes a about a percent less. All that article does is propose an extremely inefficient way of evaluating SHA256, as some of the comments there already point out. You should find more reputable sources to support your questionable claims.




ComefromBeyond
Legendary
Offline
Activity: 1526
Newbie


November 16, 2015, 06:47:36 PM 

Here's one: Argon2, winner of the Password Hashing Competition.
Argon2 whitepaper says that timememory tradeoff still can be used. At some point the tradeoff stops working because computational units will occupy more space than the removed memory but this protection won't work for a quantum computer with its perfect parallelism of computations. Looks like Argon2 fails to deliver protection against quantum computers.





tromp


November 16, 2015, 07:07:40 PM 

Here's one: Argon2, winner of the Password Hashing Competition.
Argon2 whitepaper says that timememory tradeoff still can be used. At some point the tradeoff stops working because computational units will occupy more space than the removed memory but this protection won't work for a quantum computer with its perfect parallelism of computations. Looks like Argon2 fails to deliver protection against quantum computers. The whitepaper (Table 1) says that reducing memory for Argon2d by a mere factor of 7 requires increasing the amount of computation by 2^18, and it only gets much worse beyond that. Best of luck with your perfect quantum computer.




ComefromBeyond
Legendary
Offline
Activity: 1526
Newbie


November 16, 2015, 07:14:51 PM 

The whitepaper (Table 1) says that reducing memory for Argon2d by a mere factor of 7 requires increasing the amount of computation by 2^18, and it only gets much worse beyond that.
Best of luck with your perfect quantum computer.
So it requires to add 18 qubits to that perfect quantum computer, it seems? Have you seen this pic:




WorldCoiner


November 16, 2015, 08:51:02 PM 

Two years ago I was the first German blogger that took notice of Nxt. I hope for IOTA I can also play an important role to create attention in the German speaking communities (what includes Switzerland and Austria as well). This first post includes a lot of information from this thread also some parts of the cointelegraph interview and other sources from the web. In addition I brought attention to Jinn and how IOTA is related to this semiconductor start up: https://altcoinspekulant.wordpress.com/2015/11/15/iotakryptowaehrungsrevolutionzuminternetofthings/Have a good start in the week! Thanks a lot ! Of course David. It would be great if I could contact you as well for an interview, not right now but begin of December, when we get closer to the ICO date. Just 45 questions. Many thanks in advance!

Altcoinspekulant: Deutscher Altcoinblog.



tromp


November 16, 2015, 09:01:57 PM 

The whitepaper (Table 1) says that reducing memory for Argon2d by a mere factor of 7 requires increasing the amount of computation by 2^18, and it only gets much worse beyond that.
Best of luck with your perfect quantum computer.
So it requires to add 18 qubits to that perfect quantum computer, it seems? You are rather confused about the abilities of quantum computers. A 2^18 increase in sequential computation is also a 2^18 increase in quantum runtime. Please read http://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdfto understand what quantum computers can and cannot do. Scott also writes regularly about DWave and their snakeoil version of quantum computer that your pictures alludes to. See http://www.scottaaronson.com/blog/?p=2448




ComefromBeyond
Legendary
Offline
Activity: 1526
Newbie


November 16, 2015, 09:11:47 PM 

DWave is not a quantum computer, that's true. Regarding that 2^18 issue, your paper says: A small number of particles in superposition states can carry an enormous amount of information: a mere 1,000 particles can be in a superposition that represents every number from 1 to 2^1,000 (about 10^300), and a quantum computer would manipulate all those numbers in parallel, for instance, by hitting the particles with laser pulses. While it's obvious that 1 number is not enough for Argon2 computation, if we assume that 10 numbers is enough then 18*10 extra qubits should solve the problem. Right?





ComefromBeyond
Legendary
Offline
Activity: 1526
Newbie


November 16, 2015, 09:42:05 PM 

An idea has come to my mind. We could use a quantum computer to check SHA256 digests for different patterns by using Kuperberg's quantum sieve algorithm, this would let us to assess how secure SHA256 is. No patterns = hash function is close to random oracle. We could do the same for any algorithm even if it requires petabytes of RAM, we need only digests.




tobeaj2mer01


November 17, 2015, 04:20:16 AM 

What algorithm will IOTA use, can I mine it?




ComefromBeyond
Legendary
Offline
Activity: 1526
Newbie


November 17, 2015, 08:29:52 AM 

What algorithm will IOTA use, can I mine it?
Iota is not mineable.






iotatoken


November 17, 2015, 02:31:14 PM 

Could you rephrase the question? Are you wondering why we did the Tangle instead of Blockchain?




