How can we know the first bytes of a hash for a given input format string?

Question

In the bitcoin developer wallet guide, when talking about Mini Private Key Format, when they explain how the format works, they describe some steps:

1. The first character of mini keys is ‘S’.

2. In order to determine if a mini private key is well-formatted, a question mark is added to the private key.

3. The SHA256 hash is calculated. If the first byte produced is a `00’, it is well-formatted. This key restriction acts as a typo-checking mechanism. A user brute forces the process using random numbers until a well-formatted mini private key is produced.

4. In order to derive the full private key, the user simply takes a single SHA256 hash of the original mini private key. This process is one-way: it is intractable to compute the mini private key format from the derived key.

What I do not understand is step 1 and 2 combined with step 3, if a hash function such as sha256 is irreversible, this is, given its output we cannot guess its input, how is it possible that we can know that a private key that starts with 'S' and which we added a question mark will result in a hash that starts with '00' byte?

Can people extract input formats knowing that it will output certain characters in certain positions?

Is it not one of the pros of hashes that a minimum change in the input will transform the whole output?

How can someone assure that with step 1 and 2, you will get '00' byte, when if a change is made over the left hash input characters, it will completely change?

Answer 1

how is it possible that we can know that a private key that starts with 'S' and which we added a question mark will result in a hash that starts with '00' byte?

The text you quoted includes this:

A user brute forces the process using random numbers until a well-formatted mini private key is produced.

So I guess the initial mini-private-key is the result of a lot of attempts to produce a value with that characteristic.

I think that if you take "S", append 29 random characters (from the base58 character set) and append "?" then take the hash, there is a 1 in 256 chance the resulting hash will have 0x00 as its first byte. So you probably only have to try around 256 attempts on average to create a valid private mini key.

In pseudo-code

func create_minikey() string {
  repeat
     attempt := "s" + random(29, base58)
  until (hash(attempt + "?"))[0] == 0
  return attempt
}