Bitcoin Mechanism Research

1. Origin

The electronic payment system in today's world has become very developed, and our daily consumption can basically be easily solved on Alipay and WeChat. However, both Alipay and WeChat essentially rely on a centralized financial system. Even if this system works well in most cases, arbitration disputes will still arise due to the trust model. If there is an arbitration dispute, it means that there is no irrevocable transaction, so for irrevocable services, a certain proportion of fraud is inevitable. Before Bitcoin, there was no solution that could address payments on communication channels without introducing a centralized trusted party.

The power of Bitcoin is that it is an electronic payment system based on cryptographic principles rather than relying on centralized institutions. It allows any two parties willing to trade to transact directly without the need for a trusted third party. The mathematical irreversibility of transactions will protect merchants providing irrevocable services from fraud, and programmatic contract mechanisms to protect buyers will be easier to implement.

2. Transaction

Suppose there are three people A, B, and C in the network.

A pays B 1 Bitcoin, B pays C 2 Bitcoins, and C pays A 3 Bitcoins.

As follows:

Transaction Record

They have such transactions in reality, so on the network, such transaction records will be packaged by one person (this process is called accounting) and then broadcast to the other party. What it looks like after encapsulation is what is called a block:

clogged

A block is like this, with transaction records between three parties written on it.The benefits of accounting

In order to stimulate users in the Bitcoin system to keep accounts, there are rewards for keeping accounts. There are two main sources of rewards:

1. Handling fee

Every transaction in Bitcoin will generate a handling fee, which will be paid to the bookkeeper

2. Gift pack rewards

There will be rewards for packaging blocks in accounting. The plan designed by Satoshi Nakamoto in 2008 was: one package every 10 minutes, each package was rewarded with 50 Bitcoins, and the reward for a single package was halved every four years. That is, after four years, each package will be awarded 25 Bitcoins, and after another four years, 12.5 Bitcoins will be awarded... In this way, we can actually calculate the total amount of Bitcoins:

Bitcoin total amount calculation

These 21 million Bitcoins are distributed through bookkeepers who collect packaging rewards.

Because of these two reward mechanisms, users in the Bitcoin system will rush to pack. Then there is the next question:

So who should determine the packaging records?

A, B, and C can all be packaged, but the order of transactions in the blocks they package may be different. What's more, if one of them modifies a certain transaction record and then packages it, how will the entire Bitcoin system work? 3.The Byzantine Generals Problem and Bitcoin

In order to explain the problem of who is the winner of the packed record, we need to introduce a famous Byzantine Generals Problem ( ). The Byzantine Generals Problem is a fundamental problem in point-to-point communications posed by Leslie Lambert. This means that it is impossible to achieve consistency by delivering messages over an unreliable channel where message loss exists.

During a war, all generals and lieutenants in the Byzantine army must reach a consensus and decide whether there is a chance of victory before attacking the enemy camp. However, there may be traitors and enemy spies in the army, which may affect the generals' decisions and disrupt the order of the entire army. When consensus occurs, the results do not represent the majority opinion. At this time, when it is learned that one of the members has rebelled, how can the remaining loyal generals reach a consensus without being affected by the traitor? This is how the Byzantine problem emerged.

In the context of the Internet, when value exchange activities need to be conducted with unfamiliar parties, how do people prevent themselves from being deceived and confused by malicious saboteurs and making wrong decisions. Extending the "Byzantine Generals Problem" further into the technical field, its connotation can be summarized as: how should various nodes distributed in the network reach consensus in the absence of a trusted central node and a trusted channel. In our example here, how do A, B, and C reach consensus without a centralized organization—who will keep the generally accepted correct ledger?

1.Solution to the Byzantine Generals Problem

Suppose there are 9 distant generals surrounding the Byzantine Empire. Unless 5 or more generals attack together, the Byzantine Empire can be defeated. These nine generals distrusted each other. They don't know if there is a traitor among them. So how can you win this battle through long-distance negotiation?

Option 1: Oral Agreement

Verbal agreements have 3 default rules:

1. Every message can be received accurately

2. The recipient knows who sent it to him

3. Everyone knows who hasn’t posted a message

4. The recipient does not know who the forwarder of the forwarded information is.

If the generals follow the verbal rule, here's what happens: General 1 sends a message to 8 other generals, and then Generals 2 through 9 relay (broadcast) the message. Every general is a receiver and forwarder of messages. There are a total of 9×8=72 transmissions in this round. This way, generals can choose actions based on the information they have and majority vote. Even if there are spies at this time, because of the principle of the minority obeying the majority, as long as the majority of generals agree to attack Byzantium, they will take action.

This solution has many disadvantages:

1. First of all, the sending volume is large, between 9 and 72 times. As the number of nodes increases, the workload grows exponentially.

2. In addition, it is impossible to find out who is the traitor because this is a verbal agreement and the recipient does not know who is the forwarder of the information. The data in the hands of each general is only a quantitative comparison:

Information in the hands of the general 1 (verbal agreement)

Here we assume there are three traitors. The most extreme case is that the traitor always changes "no attack" when forwarding information. Then our worst result is as shown in the picture above. General 1 can conclude that he will attack based on the information in his hand, but he has no way of knowing who among the generals is the traitor.

So we have option two: a written agreement.

Option 2: Written Agreement

A written agreement means the military receives the information and can sign it, and everyone can identify whether the signature is his or hers. In other words, if someone tampered with a signature, everyone can know. Compared to verbal agreements, written agreements add an authentication mechanism and all messages are recorded. Once you find someone providing inconsistent information, you are hunting a spy.

With the written agreement, the information in General 1’s hands is this:

General 1 information held (written agreement)

It can be clearly seen that in the worst case scenario - the traitor always forwards the "no attack" message, generals 7, 8, and 9 are the traitors in the team.

This solution solves the problem of non-traceability of historical information in verbal agreements, but does not achieve any improvement in sending volume.

2. Bitcoin solves the Byzantine Generals Problem (1) Asymmetric encryption In a written agreement, we assume that the general’s signature is unforgeable. In cryptography, there are also digital signatures. Digital signatures are generated through private key encryption, and the public key can decrypt the digital signature. The public key is generated from the private key, and it is very difficult to infer the private key from the public key (it is very difficult to calculate the private key through the public key with the current computing power of the computer). This is an existing concept in cryptography called asymmetric encryption. The private key is owned by the individual and the public key is public. Asymmetric encryption can solve the problem of signature forgery.

public key private key

In our example, each user in the Bitcoin system initiates a transaction and signs it with his or her private key. The mathematical formula is:

= symbol (, )

So the previous block looks like this:

signature block

In this way, every transaction is digitally signed by the transaction initiator through the private key. Since the private key is not public, transaction information cannot be forged.

(2)Proof of Work (PoW)

As stated at the end of a written agreement, a written agreement does not solve the problem of excessive information exchange. When there are tens of millions of nodes in the Bitcoin system, if they want to broadcast verification to each other, the number of request responses will be a very huge number, which will obviously cause network congestion and slow down node processing. To solve this problem, Satoshi simply allowed a block to be generated within 10 minutes. Who will package and send this block? The proof-of-work mechanism (PoW) is used here. Proof of work, to put it bluntly, is to solve a mathematical problem. Whoever solves the math problem first will have the right to package the block. Take the Byzantine generals as an example. Whoever solves a mathematical problem first becomes the commander-in-chief among the generals, and the other generals obey his orders.

We have said before that if you successfully package a block, you can get two rewards, one is the handling fee, and the other is the packaging reward.

complete block structure

A complete block structure is like this, and the algorithm mechanism of PoW is as follows:

First, the miner will evaluate the 128-byte string occupied by the block header twice, namely:

Hash = ((block header))

This results in a Hash of values ​​and compares it with the target value. If the conditions are met, the proof of work is considered successful.

The conditions for successful proof-of-work are written in the difficulty number field of the blockchain header, which requires that the Hash value of the last two operations must be less than the set target value; if not, change the random number in the block header. (nonce), tested by repeating the calculation again and again until the condition is met.

In addition, Bitcoin has its own set of difficulty control systems, which allows the Bitcoin system to maintain a speed of generating a block in 10 minutes under different computing power conditions across the entire network. This also means that the difficulty value must be adjusted according to changes in the computing power of the entire network. The difficulty adjustment strategy is calculated by comparing the time taken by the latest 2016 blocks to the expected time (expected time is 20160 minutes or two weeks, which is the total time calculated based on the generation rate of one block every 10 minutes ). It will be adjusted accordingly (either more difficult or easier) depending on the ratio of actual construction period to expected construction period. That is, if the block generation speed is faster than 10 minutes, the difficulty will increase, and if the block generation speed is slower than 10 minutes, the difficulty will decrease.

4. The role of workload proof

PoW actually does the following three things in Bitcoin.

1. Control node access mechanism

This prevents high-performance machines from running tens of thousands of nodes simultaneously, as sufficient computing power is required to complete each job.

2. Economic incentives

Economic rewards will accelerate the decentralization of the entire system and encourage everyone not to do evil, but to actively implement the protocol in accordance with its original implementation. (So, a currencyless blockchain is actually not feasible, and a currencyless blockchain will definitely lead to centralization.)

3. Ensure there is a minimum interval between the block generation times of each block

In other words, each node cannot control the speed according to its own hardware conditions. Today, Bitcoin generates a block every 10 minutes on average. No matter how good the machine is, this rule cannot be broken. This ensures that blockchains can converge on a common main chain, which is what we call consensus.

To sum up, consensus is only one of the three major functions of PoW. In fact, PoW design has at least three functions.

5. Zero-knowledge proof 1. Merkle tree

The concept of Merkel tree is actually very simple, as shown in the figure

Merkle tree

First, perform a hash operation on D0, D1, D2, and D3 in Data to obtain N0, N1, N2, and N3 respectively. Then divide and conquer the two hashes to obtain the parent node, until the root hash node is finally generated. This node is called the default node. Kergen.

Trees have three major characteristics:

(1) Any small change in a leaf node will cause earth-shaking changes in the Merkel root. This can be used to determine whether two encrypted data are exactly the same;

(2) The tree can quickly locate modifications. If the data of D1 is tampered with, it will affect N1, N4 and Root. Therefore, when it is discovered that the hash value of the Merkel root has changed, along Root->N4->N1, D1, the actual changed data can be quickly located in at most O(log n) time. In other words, if there are 16 transactions in a block, then only log 16=4 or 4 steps are needed to find any transaction in the block.

(3) Zero-knowledge proof means that the prover can convince the verifier that an assertion is correct without providing any useful information to the verifier. For example, if the owner of D0 wants to prove that he owns the data D0, he does not need to publish the real data of D0. He only needs to gradually calculate the Root hash based on the published N1 and N5, and then publish the Root hash together. Compare the Merkle roots, and if they match, it proves that you are the owner of D0. During this process, you did not disclose the contents of D0 to the outside world. Only through some known hash value calculations do the outside world believe that you are the owner of D0.

Zero knowledge proof

2. Generate the root of the block transaction. We hash each transaction in the block and generate the root as follows:

Introduction to trees

In this way, our block structure is roughly complete, divided into two parts: block header and block body.

6. Development of blockchain

Each node of the blockchain stores every block of the blockchain from its creation to the present, that is, every transaction is stored on this node, which currently contains hundreds of GB.

Whenever a new transaction is generated in the Bitcoin system, the new transaction is broadcast to all nodes. Each node collects new transactions and generates corresponding Merkle roots. After splicing the block header, it starts adjusting the random values ​​in the block header and then starts calculating the math problem.

=(())

Compare the calculated value to the target value in the network. If the result is less than this value, the answer is broadcast to the entire network. After other miners receive this information, they will immediately put down their calculations and start calculating the next block.

For example, Node A is currently mining 38936 blocks. Once mining node A completes the calculation, it immediately sends the block to all its neighbor nodes. After these nodes receive and verify the new block, they will continue to propagate the block. When this new block propagates through the network, each node adds it to its own node's copy of the blockchain as the 38936th block (the previous block was 38935). When the mining nodes receive and verify this new block, they abandon their previous calculations to build this block of the same height and immediately start calculating the next block in the blockchain.

The whole process is shown in the figure below:

Blockchain growth process

This process forms a growing blockchain:

Blockchain

7. The double-spending problem and Bitcoin

Simply put, the double-spend problem is money being spent twice. Specifically, the double-spend problem can be divided into two situations:

1. The same money is used multiple times;

2. A sum of money was used only once, but through hacking or forgery, the money was copied and used again.

In the digital system we live in, due to the replicability of data, the same digital assets may be reused in the system due to improper operations. In order to solve the double-spend problem, daily life relies on third-party trust institutions. . Such institutions centrally manage data and prevent double payments by modifying account balances in real time. As a decentralized peer-to-peer value transmission system, Bitcoin solves the double-spend problem through the integration of UTXO, timestamp and other technologies.

What is UTXO

The full English name of UTXO is, which means unused transaction output. UTXO is a new accounting model that is different from traditional accounting methods.

The traditional accounting method of banks is based on accounts, which mainly records the account balance of a certain user. The UTXO transaction method is based on the transaction itself and does not even have the concept of an account. In the UTXO accounting mechanism, in addition to currency issuance, all funding sources must come from one or more previous transactions. The total amount of any transaction must equal the total transaction output. The UTXO accounting mechanism allows every transfer in the Bitcoin network to be traceable to its previous transactions.

Bitcoin mining nodes receive mining rewards for new blocks, such as 12.5 Bitcoins. At this time, its wallet address obtains a UTXO, which is the output of the coinbase transaction (also known as the minting transaction) of this new block. . A transaction is a special transaction with no inputs and only outputs.

When A wants to transfer a Bitcoin to B, the process is to use the private key to sign the previous UTXO in A's wallet address and send it to B's address. This process is a new transaction, and what B gets is a new UTXO.

This is why some people say that there is no Bitcoin in this world, only UTXO. The Bitcoins in your address refer to unspent transaction outputs.

Take the process of Alice transferring money to Bob as an example:

Assume that Alice previously obtained 12.5 Bitcoins through mining. In her address, these Bitcoins are UTXOs for some kind of monetary base transaction. Alice initiates a transaction, the input is her last transaction, the output is Bob's address, the amount is 12.5 Bitcoins, Alice signs the transaction with her private key. When the transaction is confirmed by the blockchain, Alice's UTXO becomes 0. There is another UTXO in Bob's address, the number is 12.5.

The Three Stages of Bitcoin Transfers

Bitcoins stored in Bob's wallet address can only be signed and transferred to others using Bob's private key.

If Bob wants to transfer these Bitcoins to someone else, repeat the above process.

UTXO is very different from the account concept we are familiar with. Accounts are what we come into contact with most every day. For example, if I open an account at a bank, the balance in the account is my money.

But the concept of an account does not exist in the Bitcoin network. You can have multiple wallet addresses, and each wallet address has multiple UTXOs. Your money is the sum of UTXOs in all these addresses.

Satoshi Nakamoto's goal in inventing Bitcoin was to create a peer-to-peer electronic cash. The design of UTXO can be seen as borrowing the idea of ​​​​cash: we may put some cash in this pocket and some cash in the corner of that cabinet, and in this case, there is no account, and you everywhere The cash you put in adds up to all your money.

There is also a technical reason for adopting UTXO design. This special data structure can make double spends easier to verify. Compare:

How Bitcoin solves the double-spending problem

标签： #Block #Bit #Node #General #Pack