Bitcoin Forum

The task which is performed during block signing is very special.
Why not try to deep into the signing process in order to reduce number of required attempts?
May be to prepare some precomputed tables or so.
Can you point to topics about this?

http://en.wikipedia.org/wiki/SHA-2

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

that article describes all possible use cases, but we have a special one.

Where? :)

SHA256(SHA256(x))

All miners just brutforce one hash for current block.

Hashes are by design irreversible. In practice, they are simply very hard to reverse. The only effective way to "crack" a hash is to try trillions of hashes per second (the entire bitcoin network currently tests fewer than 600 billion hashes per second), and it would still take you on average longer than the age of the universe to find a key with a hash that matches. Bitcoin uses an "easier" hash to increase the rate of Bitcoin creation. This has been described elsewhere better, but my understanding is that blocks are created when:

hash(hash(hash(data that changes relatively infrequently) + nonce)) < some number inversely proportional to difficulty

If you were to construct a number line and place the values of hashes of random keys on it, you would find that the hashes are approximately uniformly distributed across the line. Difficulty represents the "smallness" of a range at the beginning of the line that hashes must fall into to be validated.

As for precomputed tables, even discounting the variability of the Merkle root, it would take far more time to precompute a hash table for the SHA hash than to generate thousands of bitcoins through legitimate mining. Precomputing a hash table doesn't save you any time in the long run, rather it allows you to invest (a tremendous amount of) time now so you can spend far less time on each block. You might as well generate blocks legitimately now while the difficulty is low.

I personally wonder about the difficulty of discovering someone's private key in their wallet.dat by brute force attack. I think this would require 2²⁵⁶ hashes to guarantee finding the private key with an average crack time of 2²⁵⁵ hashes. Can anybody familiar with cryptography answer that question and/or elaborate?

If that is true, and we assume that in 2011 a very wealthy attacker can bring 1 THash/second to bear on the problem, and the attacker works constantly on the problem starting now, purchasing new hardware which keeps up with Moore's law over the following years (processing power doubling every two years), his descendants will steal your private key and all your descendants bitcoins somewhere around 2390 (unless they get unbelievably lucky before then). A hundred years later in 2490, anyone with the equivalent of a PC will be able to crack a wallet.dat private key in about a second. Can anyone check my math on that?

If that is true, then bitcoins won't ever truly be "lost" because in a few hundred years, they will turn up again when in becomes feasible to crack a wallet.dat private key. Hopefully whoever manages to dig up those lost coins will be able to exchange them into whatever the equivalent form of bitcoins is at that time (with much stronger cryptography).

Wouldn't Moore's Law, if it still holds by then, make the Bitcoin network that much more computationally powerful and increase the difficulty accordingly?

But there isn't a changing difficulty for finding the private key as there is only ever 1 answer.

I see. To defend against this attack, people could just regularly transfer their savings between different wallets. If the target private key doesn't stand a good chance of containing enough bitcoins, the attack is kind of pointless, no?

The encryption of one's private keys is entirely different from the hashing algorithm used in generating blocks.

SHA-256 hashing, ECDSA encryption.

I might have gotten you wrong but aren't we talking about asymmetric encryption? So for Bitcoin's 160-bit ECDSA addresses, you would need 2⁸⁰ (~ 1.2 septillion, i.e. 25 digits) generations. Far easier than cracking symmetric encryption, you don't have to wait for the next century to reclaim lost coins.

it's ECDSA using secp256k1 curve, so 2¹²⁸ not 2⁸⁰.

If you're trying to break the private key, forget the hashes. A Bitcoin address is a hash of the public key, which you already know, so there's no point in trying to break that hash. I'm sure there's plenty of literature on the web about how long it would take to find a private key by brute force.