Bitcoin Forum
July 14, 2020, 11:59:21 AM *
News: Latest Bitcoin Core release: 0.20.0 [Torrent]
 
   Home   Help Search Login Register More  
Warning: One or more bitcointalk.org users have reported that they believe that the creator of this topic displays some red flags which make them high-risk. (Login to see the detailed trust ratings.) While the bitcointalk.org administration does not verify such claims, you should proceed with extreme caution.
Pages: « 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 [33] 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 ... 758 »
  Print  
Author Topic: IOTA  (Read 1463416 times)
This is a self-moderated topic. If you do not want to be moderated by the person who started this topic, create a new topic.
Tobo
Hero Member
*****
Offline Offline

Activity: 763
Merit: 500


View Profile
November 16, 2015, 12:40:31 PM
 #641


If quantum computers become popular, what impact will it bring to Bitcoin and other existing cryptocoins?
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
patmast3r
Hero Member
*****
Offline Offline

Activity: 980
Merit: 1001


View Profile
November 16, 2015, 12:48:08 PM
 #642


If quantum computers become popular, what impact will it bring to Bitcoin and other existing cryptocoins?

Pretty much all current public-key cryptography is done for.

iotatoken
Hero Member
*****
Offline Offline

Activity: 714
Merit: 500


View Profile
November 16, 2015, 01:18:36 PM
 #643


If quantum computers become popular, what impact will it bring to Bitcoin and other existing cryptocoins?


https://bitscan.com/articles/all-about-iota-ii-the-tangle-and-quantum-resistant-cryptography This explains some of it

Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2128
Merit: 1009

Newbie


View Profile
November 16, 2015, 02:06:06 PM
 #644

Pretty much all current public-key cryptography is done for.

PoW blockchain mining too. PoS/PoI/DPoS blockchains unaffected.
Tobo
Hero Member
*****
Offline Offline

Activity: 763
Merit: 500


View Profile
November 16, 2015, 02:25:14 PM
 #645

Pretty much all current public-key cryptography is done for.
PoW blockchain mining too. PoS/PoI/DPoS blockchains unaffected.

How difficult is it for Bitcoin and Ethereum to switch their current algorithms to quantum resistant cryptographic algorithms?
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2128
Merit: 1009

Newbie


View Profile
November 16, 2015, 02:26:22 PM
 #646

How difficult is it for Bitcoin and Ethereum to switch their current algorithms to quantum resistant cryptographic algorithms?

Ethereum is migrating to PoS. Bitcoin will be dead.
patmast3r
Hero Member
*****
Offline Offline

Activity: 980
Merit: 1001


View Profile
November 16, 2015, 02:30:19 PM
 #647

Pretty much all current public-key cryptography is done for.

PoW blockchain mining too. PoS/PoI/DPoS blockchains unaffected.

I guess those would be unaffected but those projects would still need to swtich from ecdsa to something else that is "quantum secure" for all their signing right ?

Tobo
Hero Member
*****
Offline Offline

Activity: 763
Merit: 500


View Profile
November 16, 2015, 02:30:39 PM
 #648

How difficult is it for Bitcoin and Ethereum to switch their current algorithms to quantum resistant cryptographic algorithms?
Ethereum is migrating to PoS. Bitcoin will be dead.

But Ethereum still needs to take care their public key attack issues. Is it easy for Etheruem or POS to switch to a new algorithms to protect the public keys?
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2128
Merit: 1009

Newbie


View Profile
November 16, 2015, 02:33:23 PM
 #649

I guess those would be unaffected but those projects would still need to swtich from ecdsa to something else that is "quantum secure" for all their signing right ?

Don't know about the others, but Nxt Account Control feature includes QC-resistance.
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2128
Merit: 1009

Newbie


View Profile
November 16, 2015, 02:36:20 PM
 #650

Is it easy for Etheruem or POS to switch to a new algorithms to protect the public keys?

Existing schemes of QC-proof signing require pretty big signatures. In Iota, for example, ~433 bytes are occupied by the signature, it's exactly 50% of the transaction size.
tromp
Hero Member
*****
Offline Offline

Activity: 647
Merit: 566


View Profile
November 16, 2015, 02:39:29 PM
 #651

Pretty much all current public-key cryptography is done for.

PoW blockchain mining too.

Hashcash PoW (like Bitcoin's and most altcoin's) is amenable to Grover search which can search a space of n nonces in time O(sqrt(n)).

But Hashcash with large memory requirements will likely not be affected as long as scaling quantum computers up to millions of bits remains elusive.

Non-hashcash PoWs like Cuckoo Cycle are even less affected, as they are immune to Grover search.
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2128
Merit: 1009

Newbie


View Profile
November 16, 2015, 02:49:54 PM
 #652

Hashcash PoW (like Bitcoin's and most altcoin's) is amenable to Grover search which can search a space of n nonces in time O(sqrt(n)).

But Hashcash with large memory requirements will likely not be affected as long as scaling quantum computers up to millions of bits remains elusive.

Non-hashcash PoWs like Cuckoo Cycle are even less affected, as they are immune to Grover search.

"Improvements" like Scrypt make nodes more vulnerable to spam. Also, a quantum computer doesn't need to evaluate a whole hash value, it can verify first bits and throw away nonces that don't suit with high probability. BTW, why is Cuckoo Cycle less affected, birthday paradox problems are solved with N^(1/3) effort VS N^(1/2).
tromp
Hero Member
*****
Offline Offline

Activity: 647
Merit: 566


View Profile
November 16, 2015, 03:39:36 PM
Last edit: November 16, 2015, 03:50:56 PM by tromp
 #653

Hashcash PoW (like Bitcoin's and most altcoin's) is amenable to Grover search which can search a space of n nonces in time O(sqrt(n)).

But Hashcash with large memory requirements will likely not be affected as long as scaling quantum computers up to millions of bits remains elusive.

Non-hashcash PoWs like Cuckoo Cycle are even less affected, as they are immune to Grover search.

 Also, a quantum computer doesn't need to evaluate a whole hash value, it can verify first bits and throw away nonces that don't suit with high probability.

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.

Quote
BTW, why is Cuckoo Cycle less affected, birthday paradox problems are solved with N^(1/3) effort VS N^(1/2).

Because, unlike Birthday collision problems, Cuckoo Cycle is a more structured search problem; you must find a 42 cycle in an arbitrary graph.
There are no known quantum speedups for such graph problems.
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2128
Merit: 1009

Newbie


View Profile
November 16, 2015, 03:51:03 PM
 #654

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? http://jheusser.github.io/2013/02/03/satcoin.html claims the opposite.
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2128
Merit: 1009

Newbie


View Profile
November 16, 2015, 04:28:53 PM
 #655

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 time-memory trade-off of quantum computers, but if we assume that the trade-off is not worse than the trade-off 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.
tromp
Hero Member
*****
Offline Offline

Activity: 647
Merit: 566


View Profile
November 16, 2015, 04:33:59 PM
 #656

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.

Quote

That is a long document to read. Where exactly does it claim that?
tromp
Hero Member
*****
Offline Offline

Activity: 647
Merit: 566


View Profile
November 16, 2015, 04:37:39 PM
 #657

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 time-memory trade-off of quantum computers, but if we assume that the trade-off is not worse than the trade-off 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 hash-functions that don't allow for time-memory trade-offs.
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2128
Merit: 1009

Newbie


View Profile
November 16, 2015, 05:21:04 PM
 #658

Of course I was talking about hash-functions that don't allow for time-memory trade-offs.

Give me the name of one of such functions, please. The trade-off is a pretty universal thing, the best a function can do is to keep time*memory*advice constant, if I'm not mistaken.
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2128
Merit: 1009

Newbie


View Profile
November 16, 2015, 05:27:47 PM
 #659

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?

Quote
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 non-deterministic 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
Hero Member
*****
Offline Offline

Activity: 647
Merit: 566


View Profile
November 16, 2015, 06:25:11 PM
 #660

Of course I was talking about hash-functions that don't allow for time-memory trade-offs.

Give me the name of one of such functions, please. The trade-off 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 time-memory-trade-off resistance was one of the design goals.
Pages: « 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 [33] 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 ... 758 »
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!