Cryptography in Bitcoin: Five characteristics of hash functions and mining principles

Bitcoin is the world's first successful cryptocurrency, and no previous attempt has solved various problems related to currency as effectively as Bitcoin.

Bitcoin itself is a product of the development of cryptography, and is constructed using two very important technologies in cryptography: "one-way hash function" and digital signature. Today we will focus on explaining the five important characteristics of one-way hash function and the technical principles related to Bitcoin mining.

Let's first talk about the characteristics of hash functions:

One-way hash function (one-way hash function ), also commonly known as hash function.

The first feature: the input can be of any length, and the output is of fixed length

Hash functions don't need to know what the input information represents, nor does it matter how long the information is. As long as the input to the hash function is a fixed-length bit value, it will output 256 bits of 0 and 1. For example, the famous SHA256 hash function will output any value as 256 bits of 0 and 1. Input a copy of "Romance of the Three Kingdoms" or just the letter a, and the output will be 256 bits of data.

The second feature: the hash value is calculated faster  

This point is often overlooked by everyone, and it seems that people don't pay attention to it because it seems to be something they are used to. In fact, this point is equally important, because the calculation of one-way hash is very fast, which can ensure the speed of encryption or verification.

The third feature is collision resistance .

X≠y, H(x)=H(y) The input space is much larger than the output space. For example, a 256-bit hash value means that the output space is 2^256. The input is infinitely possible, and the output is of fixed length.

However, there is currently no good way to find an x ​​such that H(x) equals the value on the right.

Iterating through all inputs to find this value is called brute-force cracking, which is the origin of the term " hash collision " in mining machines.

The purpose of hash anti-collision is to ensure that the uploaded and downloaded data are the same, that is, a slight change will result in a big difference in the result. For example, if the information you input is a Dream of Red Mansions (of course, the computer recognizes it as 0 and 1), and then you change a comma to a period in the fifth sentence of page 100 of Dream of Red Mansions, then the output hash value will be completely different. This is a very important feature of hash functions.

However, there is currently no mathematical proof that collision resistance will not occur. MD5 is the best example. It was very secure before, but a way to crack it was later found.

The fourth characteristic: Hiding or one - way

The calculation process of the hash function is one-way and irreversible. x deduces H(x), but there is no way to reverse it (one-way), that is, the hash value does not reveal the information of the input x. In other words, the information of x is hidden, which is the hidden property.

The input space must be large enough and the values ​​must be uniform, so that it is difficult to crack by brute force.

The third and fourth characteristics can be used to create very interesting application scenarios.

For example, predicting an event. In the real world, predictions and results often have a subtle relationship. For example, during the Three Kingdoms period, Cao Cao specifically went to Xu Shao, an expert in character appraisal, to ask him to see what kind of material he was. Xu Shao commented that Cao Cao was "a capable minister in a peaceful era, and a treacherous hero in a chaotic era." It is difficult to say whether his evaluation was accurate or not. Perhaps because of this comment, Cao Cao's psychology was affected, and he developed in this direction, which became a self-verified prophecy. Therefore, it is difficult to judge whether the prediction is really accurate.

A simpler example is that an influential stock analyst predicts today whether the stock price will increase tomorrow. Then, if he publicly announces the price of the currency, it may affect the price of the currency.

So how do you prove that he is really accurate? Ask him to write down the stock review information on paper or save it in a computer, but ask him not to secretly modify the content after the market opens the next day, so that there is no need to worry about the prediction affecting the stock price. Now all you need to do is make sure he has not tampered with the content he has already written.

Then, you can use a hash algorithm, the predicted result (information) is x, hash x, publish the hash value , and release x at the close of the next day. If you change yesterday's data, the hash will change. Everyone can use the hash to calculate this x and compare it with the hash value published yesterday.

In reality, the actual input space is not very large, and the input is not random enough. We are worried that someone will combine and arrange vocabulary sentences such as rising and falling to find this x. In order to ensure security, a nonce random number will be added. The formula is expressed as follows.

H（x丨丨nonce） nonce is a random number

This means adding a random number after the predicted result information x and getting the hash together.

Fifth point : puzzle friendly

That is to say, you don't know what H(x) is when you look at x? You can't tell what the output will be from the input data. That is to say, even if you know the input information, you can't tell at a glance what the output hash value is. The friendliness of the puzzle is that you can't get the desired output value H(x) by controlling the input value x.

Therefore, combining the two characteristics of concealment and puzzle friendliness, if you know the input information but don't know what the hash value is, you can calculate it quickly, but you can't judge it in advance; if you know the hash value, you can't know what the input value is, and reverse calculation is very, very difficult, and you can only crack it by brute force.

So if you want the output value to fall within a certain range, such as being less than a certain value, the computer can only try and guess the answers one by one to see which input will produce an output value that falls within the range you want.

You want to get a hash value with the first K bits being 0. You have no idea how to get an x ​​with so many 0s in the front.

Mining is about finding nonce, which is this random number.

H (block header + nonce ) ≤ target

This is the basic principle of Bitcoin mining, which is to find the nonce through hash collision, so that it is less than a target (such as 32 zeros, etc.). The information included in the block header (or block head) is all known to all miners (such as version, prehash, merkle root, ntimenbits, etc.), so everyone competes to guess the nonce first.

Note: In the binary world, because each bit is either 0 or 1, the comparison is the number of 0s in front. The first 32 bits are 0, which is naturally smaller than the first 31 bits are 0 (the 32nd bit is 1). The so-called comparison of the target is to limit the range. Because the numbers output by sha256 are all 256-bit binary numbers (the output value of the hash function is fixed in length), comparing who has more 0s in front is a very convenient way to define the area of ​​the result value. Many people ignore this point. In fact, it is a very basic mathematical knowledge and it is worth noting.

The basic idea of ​​mining comes from the above information. In the process of Bitcoin mining, it is actually to find the nonce, that is, after determining the output range, find the input value. H (block header + nonce) ≤ target

When the input value (various information + nonce) is hashed, the resulting value meets the target range. For example, the first 35 zeros are sufficient. If the first 40 of the hash value you guessed are all zeros after input, then it definitely meets the requirement. In fact, the first 35 zeros satisfy the condition.

Then you publish this information, and other miners see your nonce value and hash it, and quickly know that your nonce is appropriate and can meet the target requirements. This is where the fast calculation speed of the hash function (the second characteristic) is used.

This article summarizes the characteristics of singular hash functions, which are the basis of many blockchain applications and the basic principle of Bitcoin cryptographic mining. As mentioned at the beginning of the article, in addition to the function function, there is another very important content in the cryptography used in Bitcoin: digital signature. We will talk about this soon.

At present, the so-called blockchain applications in the world sometimes use the data structure of Bitcoin (Merkle tree, etc.), and sometimes use the UTXO model for settlement. Sometimes it is called traceability, and sometimes it is called a contract. Many applications, no matter what the concept is, most of them use hash functions and use some of the five characteristics of hash functions.

As the article goes on, more information about Bitcoin and the industry is revealed, and slowly everyone can understand why hash functions are the foundation of Bitcoin and the blockchain industry.

Author: Village Head Two Old