1
$\begingroup$

This question comes to mind after seeing "custom" Bitcoin addresses with some special string at the beginning of the address. They are generated in the same way Bitcoins are "mined", continually hashing with a nonce + password to get some desired output.

My question is, is it just as hard to find [HLOWRLD]M9VveeBLcY4UC4vjpPs6rZtFBQE as it is to find 1FpUYCpM9V[HLOWRLD]4UC4vjpPs6rZtFBQE as it is to find 1FpUYCpM9VveeBLcY4UC4vjpPs6[HLOWRLD]? *Note the values in the digest not in brackets can be any value

The reverse to the question, given you have some insane computer, would it be easier to try to find the input for [HLOWRLD]M9VveeBLcY4UC4vjpPs6rZtFBQE versus 1FpUYCpM9V[HLOWRLD]4UC4vjpPs6rZtFBQE versus 1FpUYCpM9VveeBLcY4UC4vjpPs6[HLOWRLD]?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

With an ideal hash function each bit of the output is 1 independently with 50% probability. So to find a hash with $n$ bits chosen you have a $2^{-n}$ chance per guess. That's regardless of which bits you chose, so whether they are in the beginning or the end doesn't matter. If you accept either, you can have about twice the chance, though, and more if you also accept it in the middle.

A Bitcoin address is a hash of an elliptic curve public key, so searching for them is just like searching for hashes – you cycle through private keys in some way, generate corresponding public keys which you then hash. The actual process is rather complicated, but the address is a concatenation of two truncated hashes, which you can treat as another hash function.

However, for Bitcoin it's slightly faster to search for a match in the beginning, because that saves you two SHA-256 computations which you would need to calculate the final 32 bits of the address.

Improve this answer
$\endgroup$
2
$\begingroup$

As the other answers point out, output bits of a good hash function are uniformly distributed, so your substring has equal chance to appear in any part of the hash digest.

However, in the case of Bitcoin, the address is not a random string. Not only it starts with a predefined number (1 or 3), but the string is the result of the Base58-conversion, which may (I did not check) produce biased outputs. The addresses may even be of different lengths.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The first byte after the 1 is extremely biased. Character Characters 2 to P occur with about 4.3% probability, characters R to z with 0.07% probability. 1 and Q are somewhere in the middle. I believe this results from the rare characters being impossible if the address has the usual length, only occurring in the rare case where the number is small enough to have a shorter encoding. The bias quickly disappears as you get to less significant digits. $\endgroup$
    – CodesInChaos
    Commented Oct 22, 2014 at 8:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.