Bitcoin Forum

I'm trying to understand why cryptocurrency private keys are safe. Maybe it's a n00b question, but here I go.

I understand that if you know someone's private key, this is means you can transfer the coins. I tried this with my CGA wallet, I used dumpprivkey to get my private key, deleted my wallet file, restarted the client, and all I needed to to to get my balance back was entering "importprivkey <privatekey>". You don't need anything else than the private key.

What if someone ran a powerful computer which runs a program that does nothing else than:

1) generate random key
2) importprivkey <randomlygeneratedkey>
3) return to 1

Wouldn't that mean that this program could randomly pick up users balances, like some lottery?

Here is why

https://i.imgur.com/fYFBsqp.jpg
https://i.imgur.com/fYFBsqp.jpg

I'm no cryptography expert myself, but I believe what you describe is known as 'rainbow 'tables'.
In short, there's no use in trying to generate rainbow tables for SHA-256 (the hash algorithm Bitcoin uses) as it would take way too much computing power and storage space.

nice one.

Yes. But...
The probability that you hit an existing private key is so small that the time and energy invested into finding one key would cost more than the total market cap of bitcoin (in fact, as Gabi has pointed out, more than the available energy output of our sun over its entire lifetime).
This is pretty similar to a lottery where you buy all the tickets - of course you will win the lottery, but it's not really cost-effective, and in the case of bitcoin, you can't buy enough tickets to even get a chance of winning a little bit...

Onkel Paul

Actually, there's a small exception to this rule: If you look at deterministic keys generated from a passphrase instead of random keys, and the passphrase can be guessed, it's much easier of course.
Example: There's a private key generated from "correct horse battery staple" (corresponding public key is 1JwSSubhmg6iPtRjtyqhUYYH7bZg3Lfy1T) which is a passphrase that wasn't too hard to guess (actually, if xkcd had kept its mouth shut, it would be pretty hard to guess...). Everybody can spend contents of this address, which is why its balance is almost always zero...

This is asked every two days. Please search before you ask

OK, I get that. Chances you hit a private key are too small. And if people are smart enough to store their balances in small amounts over multiple private keys its even less effective for hackers.

But I have another question.

If I use my private key to make a transaction, the network needs to match this private key to the public key (which is derived from the private key). Doesn't this mean that all the private keys are stored on the network? And how safe is this? Why can the network easily verify the private keys but can't someone else look into them? And can't someone simply "listen" to the network and pick up those private keys?

And if I make a wallet address with the QT client, does the cliënt generate a private key? And is I encrypt my wallet, what does that mean? Does that mean my passphrase is the new private key?

You should have stopped at the first question, the answer to that answer the other too :P The transaction is SIGNED by using the private key, this means that anyone can prove it is valid but no one can get the private key. So, no problem!  :D

So the private key you use to sign the transaction isn't compared to some list of private keys which are on the network to verify if it is an existing private key?

If there were a list of private keys they would not be private keys.
It's really easier to learn crypto basics by reading some introductory texts on the net.
Do you know how to google? Enter "private key signature" into the search bar. Don't come back before you've read and understood at least 5 of the pages that come up :)

Onkel Paul

mvdheuvel,

You can find the answers to your questions much more quickly by doing some research rather than waiting for people to answer them. Try this site: https://en.bitcoin.it/wiki/

There is no need for that. Also there is no "list of existing private key".
The network just uses the public key and match it against the signed transaction, that confirms that yes, the transaction was signed with that private key. "signing" a transaction=get the transaction and make some operations on it with the private key, the output is the "signed" transaction. From a signed output you CANNOT get the private key so it is secure.

Thanks everyone!

I promise I will do more research myself  :)

Bitcoin uses ECDSA (http://en.wikipedia.org/wiki/ECDSA) to cryptographically sign transactions.

This is also the reason why you can keep your private keys offline, and sign transaction on a dedicated offline system, to keep them completely off the internet and have exactly ZERO risk of your keys being stolen (even if that machine would be infect with malware). For example Electrum and Armory offer this feature.

Works like this:
1. setup the transaction (you need internet access for this, it involves getting the history for the involved addresses from the blockchain)
2. sign the transction (this can be done entirely offline, it only requires the data from step 1 + your private key, no blockchain or internet or connection involved) and save it on a USB flash drive or something
3. push the signed transaction from step 2 on the network (this requires a connection of course)

Note that creating the data in step 2 requires the private key, but the result does NOT include the key in any way.

Even if ALL machines would be infected by malware, there is still no risk: the offline system which contains your private keys can't send or leak the keys, and the online system (which you use to setup and push the transaction) can't modify the transaction without the signature becoming invalid.

It's because you stored a backup of your blockchain wallet in your email or dropbox, or you entered your info into one of the fake blockchain websites.

This.

A private key is only private if only you know it.  There is no such thing as a private key that everyone knows (but promises not to use because it doesn't belong to them).

The super simplified version is that there is a mathematical relationship between private key and public key such that a message signed with a private key can be verified with the public key.

http://www.ghacks.net/files/screens/2007/04/digitalsignature.jpg

Just replace email with bitcoin transaction and the process (at a high level) is similar.

You aren't.

Of course it is very easy to prove.

Supply the tx id and YOUR public key (PubKey) for the address in question.  If there is a PubKeyHash collision the tx will be signed by a pubkey which is different than yours (i.e spending tx signed with PubKey A and you provide PubKey B and both of them hash to the same PubKeyHash.

Since a 160 bit hash collision would be incredible news (beyond just bitcoin) and you have all the information to prove it publicly you of course will do so promptly right?

Hint: here is the part where you makeup reasons as to why you can't do that.

Please take cryptography 101
https://www.khanacademy.org/search?page_search_query=cryptography

thanks

No.  a cryptographic hash is a one-way function. 

A simplified example of how this works is a password for a website.

The website's database has a HASH of your password..when you enter
the password, it hashes your input, compares it to the stored hash,
and if its correct, it lets you in.

It can never determine the original password from the hash itself.

If you forgot your password, you'll get a password reset (Not a password reminder).

Now I'm confused.  Are you saying that someone else has created a new address inside your blockchain.info online web wallet and it's being used by someone else?  Are you sure it's just not a change address of some sort?

a private key is only private until you tell someone it..

blockchain.info is a third party.

as someone else said

if you do not have sole possession of the private key's bitcoin......... you have no bitcoin

have a private key for your wealth that is not on any third party server based wallet. have it as either paper wallet or bitcoin QT.
only trust pocket money / daily amounts to be used on server based wallets.

hotwallet and cold wallet concepts are not just for businesses, bt for individuals

imagine it this way. paper wallet is your bank. server wallet is the banknotes that you only withdraw a daily limit of, then you wont get robbed of your life savings.

bitcoin economy is the inverse of government economy.
government bank notes are safer in third party services, compared to hanging out of your back pocket
bitcoins are safer in your control, compared to hanging around non insured webservers

It sounds more like blockchain.info fucked up your account more than you had some 1 / 10^160 chance collision

i always thought blockchain.info stored wallet data as a hash of your identifier/password.

and that password is not saved on any blockchain.info database

the only way to get into you wallet is using your identifier to locate which hashed wallet belongs to you.. and then using the password to unhash the wallet..

so if a hacker got in.. he "should" only see identifiers and hashed wallets. still requiring him to then use password cracking tools to crack wallets open.

also needing 2 factor authentication.

if i was blockchain info and they didnt have this. then i would hope to change their user database have 2 columns.
1. identifier
2. hashed wallet(of all imported privkeys)
and have 2 factor authentication enabled as default

then the only way a hacker would get to coins is through using key loggers in some of those dodgy altcoins (i know it may be a coincidence due to popularity, but most thefts, people admit to having a DOGEcoin client) roslinpl, did you have DOGEcoin client software?

Can you just post both public keys here, instead of spreading rumours?

But let me guess...

Since Blockchain.info does not have your private key, that makes it somewhat less likely that your private key was stolen from Blockchain.info. 
It would be truly amazing if they could.

Key logger? Virus? Trojan? Another user on your PC? Zero day vulnerability? You have eliminated all of these, and must therefore lose confidence in the technology of private key encryption? 

Actually, they do, but it is encrypted.  If you happen to choose a very weak password, and someone gains access to the encrypted private key from blockchain.info, they could brute-force the decryption.

This problem is a generalization of the birthday problem.

What is the chance that you and I were born on the same day of the year??  1 in 365.  Seems small, yet if you have 23 people in a room there is a 50% chance that two of them will share a birthday.

If we extend this to larger numbers, there is a 50% chance of a collision occurring when the sqrt root (roughly) of the space is filled.  Since we care about addresses, rather than private keys, the space is 2^160.  So when 2^80 addresses have been used we can expect a collision, or when roughly 10^24 addresses have been made.

According to this thread: https://bitcointalk.org/index.php?topic=441336.0;all

The current rate of address increases is x10 every three years, and we're at about 10^7

which means that 63 years from now there is a 50% chance that a collision will have happened.  The rate of collision will continue to creep up after that.

Half a dozen collisions in the 21st century does not mean that bitcoin has suddenly become insecure.  It just means that - worst case scenario - half a dozen addresses are compromised.  Right now more than 90% of addresses in the blockchain are empty, and this percentage is almost certain to increase.  So if you create a colliding address you probably won't get any free money.

What about the person who had the address before?  You fund the address and now it shows up in his wallet... or does it?  I imagine that the wallet software of the future won't check the balance of addresses that have been emptied.  The old owner might never know that you are now using an address that he has a key to.

At some point the rate of collisions will climb to unacceptable levels.  That's more than a century away, probably several centuries.  People will have time to come up with solutions.

You mean 3*63 years.  If there were to be 1e24 addresses in use there would be a much bigger problem:  blockchain storage, transaction volume, and the aliens who have come and generated 1e16 address each.

There's an elephant in the room and it's in a state of superposition.

I don't know if I'm off topic, but I read somewhere (can't remember the article) that approximately the number of possible private keys is similar to the numer of atoms in the universe, and running a computer capable of cracking a private key would require the energy produced by a star...obviously there is always luck, but seems unlikely

I believe you're referring to the image posted at the beginning of this thread.

Yeah it might be it, was on mobile so couldn't visualize images when I wrote before, sorry for repeating :)

As another poster has already noted, searching for the private key to a given address is different from encountering a collision between two random addresses which is much more likely due to the birthday paradox. However, the probability that such a collision happens, is being noticed, and leads to undesired transfer of bitcoins is extremely small.

Onkel Paul

I see, but I was directly answering op's question, which was about private keys  :)

Address 17G7VMdNvAMc6fyvB1C2PxtVVvWgsJ9Mp7 was in the signature lines of user "jongameson" at one time, too.

Suspicious - looks like the address was somehow not generated in a truly random way.

Onkel Paul

Nay, if such computer or device exists for that reason (which do, check for websites that gives you addresses that have words of your choice to be in front of the address) they'll just be generating new wallets

Yes, if something like the Android RNG bug was used (e.g. if blockchain.info generated this and they have/had a RNG bug) then something similar could occur.  I am not sure if that portion of blockchain.info is on github yet.  Of course it could be something else, but if the private key wasn't compromised somehow, it could be a RNG bug.

Totally agree. Private key is important.

Ahh yes, so that's about 189 years before we can expect a collision.  Of course I'm making a big assumption about the rate of address creation, so that number will probably be very different.  Good points about the other hurdles to such a huge number of addresses.

Current world population is approximately 7.152 X 10⁹

Average global population growth rate is 1.14%

If I've got the math correct, that means that in 189 years, there will be approximately 6.1 X 10¹⁰ people on earth.

If address use were to continue increasing X10 every 3 years, that means that 9.99 X 10²³ addresses would have to be generated in the final 3 years of this calculation.  That's 1.63 X 10¹³ addresses per person for every man, woman, and child on the face of the earth.

172,132 addresses per second per human being every second continuously for three years straight.

That's assuming I've got my math correct and assuming that your calculation that 10^24 addresses results in a 50% chance of address collision.


Of course, since there are only 2.1 X 10¹⁵ discrete units of currency, the odds of either of those 2 addresses actually having anything in them at all are also exceedingly small.

It sounds more like you stole his private key than the other way around.

On which software/operating system did you generate your private key?

It is much more likely there was a weakness in how your key was generated, rather than a true random collision.

https://blockchain.info/address/17G7VMdNvAMc6fyvB1C2PxtVVvWgsJ9Mp7

36 transactions
Current value 0 BTC

First transacation:  2014-01-28 18:41:00
Most recent transaction:  2014-03-21 22:13:48

Was it you or the "other guy(s)" that played Satoshi dice with this address?

Which transactions are yours?  How many out of the 36 transactions are yours?

Do you (or anyone) recognize this address:  https://blockchain.info/address/1Gy2DTd7sXQNLSTrsJE8BYTuoLZdgsVV6D

A pretty good chunk of related BTC dust was collected to this address.

blockchain.info does not create the public addresses and assign them from their servers.

The private key is randomly generated locally in your own wallet.  Then your wallet calculates the public address from that private key.  Finally your wallet encrypts the private key with your password and sends the encrypted private key to blockchain.info for them to store on their servers.

What device were you using when you created that address and how long ago did you create it?

There was a known problem in the Android operating system a few months ago.  Android was not properly generating random numbers.  Perhaps you used an android device long enough ago to generate the address and therefore ended up with a non-random private key?  If so, and if other users used a similar device long enough ago, then it is possible that due to a faulty operating system multiple people generated the same address.

You didn't import that address from a brainwallet or any other address generating program (such as vanitygen), right?

OK! I am so sorry Blockchain.info and all users!
Look at this!

+100 to blokchain.info

I totally forgot about that I DID import private key into my blockchain!

I forgot about it because there was 0 btc on it and it was some kind of joke I was thinking!
I totally forgot! Because I do not use my blockchain.info wallet to revieve or send money, and I import that key over there because I though as for experiment I can do it there, as I do not keep any money there!

look:
https://bitcointalk.org/index.php?topic=516987.0

I am so sorry .... but at least we prove that Blockchain.info is SECURE! :)

So, you imported someone else's private key, and then became concerned that someone else had the same private key as you?

Can you please go through all of your recent posts and delete all this alarmist trash before you scare some newbie that thinks this might be a real problem?

Sure I can I just edited my thread about this and in this thread I did deleted those posts.

I am so sorry for that rumor :)

Eh... but tell me how stupid is to put your private key in public...

and tell me how stupid is to import it  and forgot about? :)
So sorry! :)

You do realize that this is a scam attempt.  If someone imports a formerly private key into their wallet, and the wallet starts using it for a change address, the scammer simply sweeps the address and steals your money.

Someone really needs to compile a list of all the ways you can get your coins stolen

Here's my private key 5KMWWy2d3Mjc8LojNoj8Lcz9B1aWu8bRofUgGwQk959Dw5h2iyw

I've never seen a private key that started with a 9, what type is that?

SHA256 Rainbow table does exist!! But lucky, it is only in 6 - 7 characters.
http://www.cryptohaze.com/gpurainbowtables.php#sha256

I am sure a lot of Unethical Hackers already have a list.  ;D

Also Ethical Hacker like myself knows a lot of ways, but I am not going to list them out.  8)

Also lucky, it is not enough to just use SHA256 to find address.

You would need a rainbow table that is generated with ECDSA, followed by SHA256, and then RIPEMD-160.

Well I am glad we got that all figured out.

Just want to say I told you so :)

I must admit investing 0.22019748 BTC in a long term scam attempt is not a small amount. These scammers are getting serious.

How long until scammer can seriously except that amount of change lands on that address? Even if he gets lucky and gets some change, he has to be the fastest to collect it.

Wrapping my had around the fact that someone is really attempting this kind of scams.

The scammer would be using software to continually monitor transactions on the address, and sweep it as soon as the transaction appeared (send out the spend transaction).

The gullible would import the "private" key into their wallets, thinking they might find some free money on the address eventually, and then forget about it.

I know, amspir, how that works, but isn't it that by default in Bitcoin-QT wallet new address is used for a change? My question was how realistic is that change ends up on an imported address?

That depends on what wallet you import the address into.

I'm pretty sure that, blockchain.info, and MultiBit use an existing address in the wallet for change.

Furthermore, if the victim forgets that they imported the address, and is receiving bitcoins from someone, there is a chance that they will give out the imported address as a receiving address.

In QT client the chance is exactly 0%.  Change addresses (and requests for new address) are always pulled from the keypool not active keys.

I use blockchain as my hot wallet, but I keep most of my BTC on paper wallets.   Usually, when I buy a large amount of BTC, it goes into a paper wallet.

On my blockchain wallet, when I need some BTC, I import a paper wallet, and write "Exposed" on it, then put it in a separate envelope.

So, in my blockchain wallet, I several addresses that came from exposed paper wallets.

When I send some BTC, I believe it works (not 100% on this) by using the oldest address with a balance on it then using newer addresses until the transaction amount is equaled or exceeded as the input to the transaction.   The entire amount from all the source addresses are used as input to the transaction, then an output from the transaction is sent back as change to the newest address (rather than a new address)

If the newest address gets a change transaction, the scammer would watch for this, then sweep it -- if I had imported a scam private key.

Side note, when sending a shared transaction from a blockchain.info wallet the change always goes to a band new freshly created change address and I don't see a way to specify any other address.  As stated above for a non shared transaction the blockchain.info wallet sends the change back to the address the unspent output(s) came from.

I'd too would like an answer to this question.

Because the quantum computer has not yet been invented. Give it a few more decades.

We've got a quantum computer store here called D-Wave. They've got quantum computers in stock and for sale.

http://arxiv.org/pdf/1403.4228v1.pdf

Or it could just be really expensive snake oil.

http://en.wikipedia.org/wiki/Dwave_1


http://arxiv.org/abs/1401.7087


http://www.scottaaronson.com/blog/?p=1400

Wikipedia quotes penned by a competing manufacturer (IBM). lol

Quotes from the same competitor (IBM). lol

A quote from Scott Aaronson (uh, who the hell is this guy? lemme guess...works for IBM). He points to a simulation running on a classical machine optimized to exploit quirks in the "d-wave problem" to gain an advantage and says "look d-wave's slower", ridiculous. lol

Superconducting hardware walks the walk and theory-crafting talks the talk. Keep on talking IBM... and hurry up with that Bitcoin wallet, it's going to be a full implementation of the bitcoin protocol right?

A guy that I talk to on IRC (friend of a friend) does quantum computing research at Caltech.  He says that the "mood" in the community is that D-Wave is actually quantum.  It wasn't so early on and they needed a lot of convincing.  I've seen similar statements online (but don't have any references handy).

But people need to keep in mind that D-wave does quantum annealing (http://en.wikipedia.org/wiki/Quantum_annealing), which is different from "general" quantum computing (http://en.wikipedia.org/wiki/Quantum_computer).

And, while it may actually be quantum, it quite possibly offers no significant speed improvement over carefully designed software on a classical computer for the types of problems that it's specifically designed to handle.

This.

On edit:In hindsight it might looks like I am trying to educate you kjj.  That wasn't my intention just expanding on what I believe is a similar view on the threat of quantum computing which may be useful to others reading the thread.  Then again I haven't had caffeine yet so no promises.

To expand upon what kjj said and to put it in simplified terms, Quantum Annealing is some pretty "interesting" stuff, but it isn't particularly well suited to breaking most forms of cryptography.  Even if it was repurposed it can't be used to implement Shor's algorithm.  Quantum Computing isn't the magical kill all crypto in the world instantly nonsense that the media makes it out to be.  Quantum Computers can implement Quantum Algorithms.  For the purpose of breaking public key cryptography the interesting one is Shor's algorithm because it provides a massive reduction in the complexity of the problem bring what otherwise would be an impossible to brute force scenario to one which can be completed in polynomial time.  However using Shor's algorithm requires three things.  The first is a general purpose quantum computer (which DWave isn't and never will be).  The second is a public key to be attacked (and until spent the PubKey in bitcoin is unknown, you actually "send coins" to the PubKeyHash), and the third is the ability to construct said QC using a large enough number of qubits to implement the algorithm against keys of that size (and we are nowhere near the material science necessary to build a computer with tens of thousands of qubits).

So if an articles talks about "quantum computing being a threat to public key cryptography (and thus Bitcoin among thousands of other systems including TLS/SSL) it is paraphrased for a general purpose quantum computer with a sufficient number of qubits capable of implementing Shor's algorithm to break a particularly sized public key.  DWAVE's processors may end up being used for solving a lot of unique and interest problems and I am sure they will get larger and cheaper but it will never implement Shor's algorithm anymore than making an internal combustion engine more efficient will allow you to go faster than the speed of light.  Quantum Annealing and general purpose Quantum Computing are two divergent areas of study that sadly are very "nerdy" and share similar names so the media won't ever be accurate enough in their articles.  They use "Quantum Computing" to vaguely cover both fields.

So what about those fabled general purpose quantum computers?  Do they exist?  
Well we have two very public and very reviewed milestones in general purpose quantum computers.  General purpose means a design that is programmable or one which could someday lead to a programmable design.  Much like your PC is an example of a general purpose classical computer.  It can run various classical computing algorithms.  A general purpose (or programmable) quantum computer would be one that could implement Shor's algorithm (a quantum algorithm which requires a quantum computer to execute in real time).

The first major milestone was in 2001 a general purpose quantum computer with 4 qubits was able to factor the number 15 (into 5 & 3).  The next breakthrough came a decade later in 2011.  Keep in mind this is a decade later.  During that timeframe Moore's law improved the transistor density of "classical" computers by a factor of 32x.  That means generally speaking computing power per watt and computing power per dollar also increased by roughly the same magnitude.  So weaker encryption became even more weak by a factor of 32x.  Quantum computer is in its infancy so the rate of improvement should be much higher right?   So 4 bit number factored in 2001, for those playing along at home, how large of a number do you think was broken after a decade of improvement?  18 bits? 40 bits? 64 bits?  Even 64 bit would be decades away from factoring 3,076 bit numbers.  Don't use google or wikipedia just try to guestimate how much progress was made.  From 4 bit to ____ bit after a decade.

Got your guess?  Highlight the blue to reveal the answer.


Both 4,096 bit RSA and 256 bit ECDSA provide 128 bit security.  128 bit security is considered beyond brute force when using classical computers (although keys can be weakened through cryptanalysis).  Key strength is a way to roughly measure the time/energy required to break various different cryptographic systems by providing the equivalent symmetric key security.  4,096 bit RSA (public key - integer factorization), 256 bit ECDSA (public key - elliptical curve), 256 bit SHA-2 (cryptographic hash), and 128 bit AES (symmetric key) all have 128 bit key strength.  Since 128 bit is beyond brute force for any convceivable amount of time the only way these systems will be broken is through cryptanalysis which weakens the key not just using brute force.  So if that quantum computer had factored a 4,096 bit number it would have done something that no classical computing system could do.  In reality it did something, which millions of children have to do each year using pen and paper.


I have said it in other threads, wake me up when a general purpose quantum computer of sufficient size is able to factor 32 bit (or larger) number using Shor's algorithm faster and cheaper than a classical computer. To put it into perspective

For the record in hexadecimal this is a 5 bit number (what was actually broken):

This is a 32 bit number (my "wake me up milestone"):

This is a 128 bit number (a random symmetric key this size is considered beyond brute force for producing a collision):

This is a 4096 bit number (a QC would need to be able factor numbers this large to break 4,096 bit RSA which is the equivalent strength of 256 bit ECDSA):


Quantum Computing is a possible attack vector, it isn't an instant Bitcoin killer.  There is no evidence that anyone is anywhere close to building a general purpose quantum computer of the size needed to be anywhere close to breaking 256 bit ECDSA.  Even if/when that happens there are mitigating factors to consider.

The first is that if the PubKey is unknown Shor's algorithm can't be used, so don't reuse keys.  It gives you options to transistion safely to stronger addresses/keys.
The second is that Bitcoin can as an interim step use larger/stronger keys.  512 bit or even 1,024 bit ECDSA.  If quantum computing can break smaller keys it would provide a cushion of time/cost.
The third is that there are Post Quantum (http://en.wikipedia.org/wiki/Post-quantum_cryptography) Cryptography (PQC).  Bitcoin in theory could be extended to use addresses based on PQC.

Note despite the similar names Post Quantum Cryptography (PQC) shouldn't be confused with Quantum Computing or Quantum Cryptography.  They are three distinct fields.  Quantum Computing is the study of implementing quantum algorithms to solve problems (like breaking Bitcoin public keys).  Quantum Cryptography is a system is key exchange which uses photons to ensure a key can not be intercepted by an eavesdropper (observing the photon will alter the photon).   PQC are classical computing algorithms for which there is no known polynomial time solution even when using quantum computing.  To date the major concerns with PQC are the need for much larger key and signatures sizes (easily 100x that of ECDSA), a lack of extensive testing, and in some cases weaker strength against classical computing.

That is true however in DWAVE defense what is more interesting is scalability.  Simulated annealing has been an area of study to solve large complex problems long before DWAVE.  With simulated annealing the barrier isn't that you can't solve small problems it is that solution complexity grows exponentially which puts larger problems out of reach.

As an example in one paper I read they showed relative complexity (the computing power/time) for simulated annealing increased about 100x when the number of variables was tripled.  The DWAVE system showed a ~3x increase in complexity or runtime under the same conditions.   So 3x vs 100x increase in computing requirements as the problem scales out.  Another way to look at it is for each magnitude increase in the number of variables to keep the runtime the same the DWAVE would need a one magnitude increase in the number of qubits but the simulated annealing would need four magnitudes (10,000x) increase in computing power.

The major problem with simulated annealing is a couple hundred variables doesn't allow you to solve very "interesting" problems.  So today simulated annealing is faster for problems which aren't very useful and larger problems are uneconomical while the DWAVE is slower but in theory could be faster on larger problems but they are impossible (due to quantum decoherence).  Neither is particularly useful but the quantum approach at least in theory would allow larger problems in the future.


IIRC using a high end card like a NVidia Tesla the average solution time for a problem with a couple hundred variables in measured in hours.  That scales out as 10^4 increase for every 10x in problem size. 
A thousand variable scale problem would be about ten GPU years.  Maybe a rack of high end GPU servers running for a year.   Not too great but possible. 
A ten thousand variable scale problem would be about a hundred thousand GPU years.  The top super computer is roughly 10,000 GPUs so it would need to run ten years.  Feasible but not really realistic.
A hundred thousand variable scale problem would be about a billion GPU years.  Even assume a 32x performance gain from Moore's law for a decade and a hundred thousand future GPU super computer in 2024 you would be looking at a solution time measured in centuries.  Ok we just hit infeasible.

On the other hand due to quantum decoherence, a quantum annealing will either find a solution in a fraction of a second or it may never find one.
A thousand variable problem would require a chip with thousand of qubits.
A ten thousand variable problem would require a chip with tens of thousands of qubits.
A hundred thousand variable problem would require a chip with hundreds of thousands of qubits.

People buying DWAVE computers know simulated annealing doesn't work at the variable scale they are interested in.  Today DWAVE simply can't solve those problems even given an infinite amount of time.  That will require much larger chips but DWAVE went from 128 qubits to 512 qubits in two years.  That is roughly double Moore's law.  Now nobody knows if DWAVE can continue to scale the chips larger at the same rate, and even if they do nobody knows if the solution time will also scale linearly.  Still it is interesting to just imagine both will happen.  A ten thousand variable scale problem would be solvable in 2-3 years.  A hundred thousand variable scale problem would be solvable around the end of the decade.  If you are a major corporation it is worth paying millions of dollars to get up to speed on a potential breakthrough like that.

They are only safe if you checksumed your wallet as well as verifying via PGP.

Fantastic write, this should be on the blog post somewhere or Wiki, not only to be buried in this thread.

It's a base58 encoded (without the checksum) 32 byte elliptic curve hex private key.  It corresponds to the WIF private key 5Jno1aCaRaBWS3DKf5DDB96A5xSTqCJC4GbjQXPBWr8edhWX3Cg

Here's a private key of the same format as the one starting with 9:
4ujvNgAQsPYyGYRes6FCTVXR5zhvotRnZGH2KF8BBov3

See if you can get it.  It's for the address 1ErkEFoAQYYNkP9GKk6MW9VyPMXe7EosQs

Not what is absolutely safe.

Thanks, I didn't know that it was common to just convert the secret to base58 like that.  I got: 5JFsHfdCqMXmYAoQczHpg1eTCXNRsGjW7tSi3bauUmhTdqUY15z

Thank you for your share.

The chances that someone could randomly generate your private key is so low, that its just not going to happen, at least with any kind of technology we can think of or comprehend at this point in time.

Somewhat of a dumb question here, but if you have a private key but not a QR code or way to scan it how can you access the wallet? I am finding that different wallets only import certain formats, and I think Armory offline only gave me a private key and some file I cannot import to other wallets. I generally kinda suck with using wallets, so any input on this would be helpful...

It depends on the format of the private key that you have, but generally most of the commonly used wallets provide some method to import private keys.

Most wallets treat it as advanced functionality, so importing the private key will take some effort and a bit of technical know-how.

Let us know what wallet are you trying to import the private key into, and we can describe the process for you.

It's been a while since I looked at it... I'll try to revisit soon and will check back with questions. Thanks.