[Abstract] Bitcoin mining in the past 10 years has been an arms race of computing power: solving the reverse SHA256 hash function problem is an easy goal to optimize, and the game quickly develops from running on the CPU to running on the GPU. It runs on a specially designed ASIC, and even adopts the technology of a mining pool. Because mining consumes a lot of electricity, miners are looking for places with cheap electricity to carry out mining operations. These are obviously challenging Satoshi's basic principle of "one CPU, one vote". That said, the arms race to use specialized hardware and cheap electricity eventually overturned the egalitarian principles of mining, favoring Bitcoin mining towards centralization.
Speaker: Dr. Zhu Jiang
Moderator: Claire Wu
Claire: Hello everyone! I am the host tonight, Claire, and tonight's guest speaker, Dr. Zhu Jiang, will share with you a very hard-core topic: one of fair mining: the battle between computing and storage.
On the topic of fair mining, a heated discussion was initiated in the [Magic Piper Technology Development Community]. I will summarize everyone’s views here for the speaker’s reference:
Martian Fox: Let me explain first, how is the distribution fair?
Evan Liu : We need to define "fairness" first. "Fairness" is a subjective value judgment, and subjective value judgments vary from person to person. Therefore, there is no consistent definition in the sense of universal value. Therefore, I personally think that it is impossible to achieve a global "fair" mining, and any so-called "fair mining" should be able to borrow the metaphor from "1984": All animals are equal, but there are Some animals are more equal than others.
Yunhai: The rules ensure fairness. There is no priority for mining machines. They are all equal. Because the total computing power and difficulty are extremely high, there is no so-called super mining machine, which ensures fairness.
SHAN: I agree with Evan Liu. For farmers in the west who can't afford mining machines for a lifetime, it doesn't matter if POW is fair or not.
Oita: Fairness, the rules are the same for all participants, that is fairness. Rarely is justice.
Gadfly: I feel that things like mining should be difficult to be fair. Whether it is POW or POS, first of all, there must be hard power. It can only be said to be fair to miners with a certain basic strength.
Justin: Mining was originally something that individuals could keep accounts, but now they are all large mining farms and mining pools, which have become centralized, and some oligopolies have deviated from Satoshi Nakamoto's original intention of decentralization. I feel that it needs to be improved. Moreover, although there are cloud mining and mining machine hosting, but it still has to let mines and pools pick up the skin, they set the management fee, and the price of selling computing power is also set by them, and the mining income is calculated clearly . . . Hahaha, I have learned about some mining things before, but I don’t know if there is any improvement mode for over-centralization. Please tell me if you understand it. In fact, mining has developed to the present, and it is no longer the case that everyone can mine as originally imagined. I don't know if I thought of this result in the first place. Moreover, although BTC is POW, there are always more than a dozen mining pools that explode blocks, but it is DPOS like EOS.
Early explorers of PiNetwork: Everyone has to dig coins to get the projects from the project party, and there is no airdrop! No algebra no hierarchy! And they all contribute value to each other.
Wang Chengwei: There is no airdrop coin, do you think some people are willing to do such a project without reward?
Gadfly: It is impossible for everyone to be equal. Everyone has different abilities and strengths. The level of investment in the project is also different.
Early explorers of PiNetwork: There is no airdrop, that is the relationship between invitation and invitation, and mutual contribution of value! As long as one party does not mine each other's mining will be reduced!
Guanmuhu: I think the fairness of mining is more inclusive, more people will participate, and the value of the network will be more valuable and safer.
Xiaomi Pigeon: What should I do if the mining machine is stolen in the hosting center?
Wei Honggui: Regarding fairness, this cartoon has been quoted in different fields and has also been controversial.
Claire: Many thanks to the Pied Pipers for participating in discussions and asking questions. Now let me introduce tonight's guest speaker, Dr. Zhu Jiang.
In the profile of Dr. Zhu Jiang, I can faintly feel the shining halo on him. From home to abroad, he has studied in famous schools with a long history, and the industry he was engaged in before is also the most popular at present. I have read Dr. Zhu's previous articles, and they are written in a simple way, very close to the people, and Xiaobai can roughly understand what he wants to explain, and then inspire thinking and ask questions.
Back to today's topic: equal mining. There is no doubt that Bitcoin mining has achieved great success and provides a guarantee for the security of the Bitcoin network. On the latest Hurun Report, there are 5 new entrants from the mining industry. However, today, ordinary people can no longer squeeze into this thorny but profitable industry. How can ordinary people join this race to get more opportunities? Tonight, with all the questions raised by the members of the Pied Piper group, we invite Dr. Zhu Jiang to explain a question that we are all very concerned about:
"Equal Mining One: Computing and Storage Competing"
Dr. Zhu Jiang please...
Zhu Jiang: Thank you host Claire for your invitation and introduction.
Hello everyone, I am Zhu Jiang, the founder of Soteria. Thank you for coming to our online sharing today. Today I will talk to you about mining. I am a technical nerd, but I will try to use easy-to-understand language and examples to discuss with you. I promise not to use mathematical formulas. Even if it appears, it is within the scope of the syllabus of the entrance examination for junior high school students. You can rest assured.
Let's start with the principle of mining, and then I will discuss how to achieve fairness. Finally, if time permits, we will combine SoteriaDAG's inclusive features to introduce how we solve the problem of equal mining. Of course, time always passes quickly. If it is too late, please look forward to the articles we will publish on the same topic later or pay attention to ourhttps://github.com/soteria-dag/soterd
Let us briefly review the mechanism of PoW mining in the blockchain system. The essence of PoW mining is actually a computationally difficult game with the following four important features:
1. The solution process is very difficult
2. The verification process is very simple
3. The topic itself needs to be bound to some text messages
4. The questions are randomly generated and the difficulty can be adjusted as needed
In the Bitcoin network, this digital problem is designed to "solve the reverse SHA256 hash function": During the mining process, miners perform two SHA256 operations on the 80-byte block header data of Bitcoin, and the result of the operation is A string of 256 bits (32 bytes) in length. Judging whether the current block is legal by comparing it with the current difficulty value. That is, the following conditions are met:
SHA256(SHA256(block_header))< difficulty
Look at the formula, it's very simple. [Yeah!] This is the only formula for today~
If the above conditions are not met, you need to change the random value in the block header, so that the data in the block header can be changed to find a block that meets the conditions. This is the essence of the PoW mechanism: using a one-way function, and with the help of a reward mechanism, miners are encouraged to continuously try random numbers to find eligible blocks to complete a certain amount of calculations, so as to continuously ensure the security and stability of the system.
Next, let’s discuss the issues of consensus and network transmission: According to the PoW mining method mentioned above, assuming you have found the solution that satisfies the conditions, how can you be sure that the block you dug out is valid? This is another basic point of blockchain: asynchronous consensus. Everyone has carefully studied the specific agreement, so I won't repeat it here. But I can give you a very perceptual understanding, which will help you understand what we are going to discuss later.
The specifics are as follows: The security of POW is based on the fact that the personal computing power does not exceed 50% of the entire network computing power. The underlying necessary condition is that any node should compete fairly with other nodes in the network. It's like running a race, everyone has to start together. The blockchain system is an asynchronous system, and the security of POW can only be guaranteed when the system state is nearly synchronized.
In fact, an important principle of POW mining rewards is to reward miners to broadcast the blocks they have dug out as soon as possible and be received by the network; at the same time, they are actively receiving other blocks transmitted from the network instead of wasting computing power on The chain that cannot be climated (the longest chain principle). The essence of this in and out (TX/RX) is to use the natural behavior of miners under the system framework to ensure the synchronization of the network.
When you were young and went to school, you often took exams. At that time, the teacher would give the papers to the children's shoes in the first row, and pass them from front to back one by one. The children’s shoes sitting in the last row always get the papers very late (I used to be short and did not have this problem in the first row). Well, if you start to make the children's shoes when you get the test paper, then when the students in the last row get the test papers, the students in the first row have already started to do it for a long time, and they might finish it, which is unfair.
Therefore, the teacher asked each student to buckle the papers on the desk when they got them. After everyone got the papers, the teacher said, "Start timekeeping now", and then everyone can start to do it. This is the synchronicity brought about by fair competition. Come on, let's take a look at what the examination room looks like:
There are two variables here: the first is the time to pass the papers, and the second is the time to do the questions. The scroll can be a sheet of paper, or it can be a thick stack. Suppose we have to pass the papers one by one, because when the teacher prints the papers, he prints the amount of the whole class on each page. Therefore, the test paper can be passed in half a minute, or it can be passed in 10 minutes without all being sent out. Similarly, the topic is also difficult and easy. A smart child can finish it in ten minutes with a calculator, and a rigorous child can do it completely by mouth, and it may take two hours to finish.
Now you probably understand why I said that the examination papers will be issued. The test paper corresponds to our block size, and the difficulty of the question corresponds to our block generation time. Or the difficulty of hashing. The small difference is: in the block system, there is no teacher to tell everyone "start counting the time now"; instead, children's shoes start to do it as soon as they get the test paper.
Specifically, there is such a rhythm: for each newly generated block, the network propagation time is half a minute (network broadcast radius). Each miner starts mining on it after receiving the new block and verifying that it is correct. A new block is like a new test paper, and network dissemination is the issuance of the test paper. And it takes at least half a minute for this paper to be distributed to all the students. However, in each round of mining, someone will always get the paper half a minute earlier than others. But the miners think it doesn’t matter. First of all, the questions are quite difficult. The test time is ten minutes, and getting the test paper half a minute late will not have much impact; second, unlike the test in the classroom, everyone’s seat is random and often In the exchange, the person who gets the test paper first is different every time, so there is no problem.
Some unlucky miners have produced new blocks on the other side of the network for half a minute when TA digs out a new block, and the new block has not yet been propagated to him. So his new block was ruthlessly dropped, that is, it became an orphan block. TA's work was ruthlessly wasted. But there is no way around this, the design is the winner takes all, but TA has actually contributed to the security of the entire network objectively (500 words of game theory analysis are omitted here).
Originally speaking here, I will generally continue to expand to the issue of capacity expansion, but in view of today's time, we are still focusing on the matter of mining. For capacity expansion and SoteriaDAG’s expansion plan, you can refer to some technical articles we wrote before:
Ok, let's continue to study the task of mining. Just now I briefly mentioned that in the examination room, each child's shoes are done at different speeds: some children's shoes are completely counted by mouth, some children's shoes bring calculators into the arena, and even more exaggerated students bring mobile phones to talk to parents outside the test room. Real-time communication, and the parents bring a calculator for each person in the family to calculate N calculation problems at the same time. Even the family members do not have a calculator in their hands, but a quantum computer connected by cloud computing.
So here comes the problem, children's shoes with calculators must be faster than children's shoes with oral calculations (not necessarily, for example, my oral calculations are faster than calculators, this is another topic), and there are ten calculators or even quantum computers with a mobile phone. For children's shoes whose computer can perform parallel calculations, it is simply against the sky: the exam papers have just been issued, and he finished the exam papers before the students in the back row saw them.
According to our analysis above, there must be a lot of chicken feathers in the classroom at that time (no, there should be a lot of test papers, some are completely blank, and some are half-finished), the direct impact is the huge waste of energy, and the entire network caused by waste. A drastic drop in security. Even if there is no security attack, all transaction fees and mining salaries are taken away by these "defying" students because of the "winner takes all" game rule. Do you think it is fair?
Of course it's not fair, and it's very unfair. In fact, Bitcoin and other PoW blockchain projects are facing such an unfair problem. Bitcoin mining over the past 10 years has been a computing power arms race: solving the reverse SHA256 hash function puzzle is an easy optimization goal, and the game quickly progresses from running on the CPU to running on the GPU operation, and then transferred to run on a specially designed ASIC, and even adopt the technology of the mining pool.
The operation of mining operations also consumes a lot of electricity, which has prompted miners to look for places with cheap electricity to conduct mining operations, such as near hydroelectric power stations. These are obviously challenging Satoshi's basic principle of "one CPU, one vote". That said, the arms race to use specialized hardware and cheap electricity eventually overturned the egalitarian principles of mining, favoring Bitcoin mining towards centralization.
The direct result of concentration is monopoly, which may seriously damage the security of the entire system. First send a GPU image to warm up:
Then we go back to the basics of PoW mining that we talked about at the beginning.
The problem with the reverse SHA256 hash function of PoW mining is actually a computationally intensive algorithm. Let's first take a look at the situation of this algorithm in the CPU and GPU environment. This algorithm does not require a particularly large amount of memory. Therefore, for the CPU, we assume that there are 4 cores, and all data is placed in the cache or SRAM, and the space is negligible, but because there are only four cores, only four processes can be started. For a GPU, there are generally 1000 to 3000 computing units, so we can start thousands of processes. Of course, the efficiency of each process may not be as good as that of the CPU, but there is no problem at all if the total efficiency is increased by hundreds to thousands of times.
Of course, but and but. . . For ASIC, there are thousands of gate circuits in one core, which can complete the work that CPU and GPU need to complete in thousands of clock cycles in one clock cycle. Almost the core of a mining machine is on top of a graphics card. Therefore, the mining efficiency of ASIC is easily a million times that of CPU or GPU, and there is basically no possibility of victory without ASIC.
Let me stop here for a while, let's digest these figures and see how helpless the comparison of these scenarios is. How speechless I will be to the western farmers who can't afford mining machines all their lives~ Well, it happens that we still have feelings, and we can't be content with this kind of injustice, right? Then let's imagine, if there is a magical algorithm that needs to use 1G memory during the entire calculation process, what will happen?
For the CPU, with 4 cores, if you install 4G memory conservatively, you can run up to four processes at the same time for calculation. Here we don't consider virtual memory, because it is too slow, and the process of scheduling and swapping is not enough to toss. As far as the GPU is concerned, no matter how high-end the graphics card is, it only has a few gigabytes of memory. Assuming 4G, then we are running four processes to calculate at the same time. If we want to use all the computing units, we have to install 4TB to 12TB of SRAM, which is already a bit unrealistic. The situation of ASIC is even more terrifying: the requirement for memory is doubled thousands or even tens of thousands of times. I pause again, and everyone digests this batch of numbers again. As a farmer in the west, seeing the enemy spend so much money just to dig a mine, don't I feel a little better?
In view of this analysis, let's take a look at the development trend of processor technology and memory technology. The main purpose is to see if this type of mining machine can return to the standard that left us speechless in the foreseeable future:
This graph is very clear: Since the 1980s, the innovation of computing technology has completely followed Moore's Law, and the annual performance improvement has basically stabilized at about 60%. But did you see that storage technology is only crawling at a slow rate of 7% per year. Moreover, this is only the improvement rate of DRAM. So a calculation-intensive algorithm will run fast on mobile phones in a few years, and it will be cheap. Memory-intensive ones are obviously not good enough, and it is said that this is the trend of DRAM. Due to the refresh problem of DRAM, the delay and bandwidth of DRAM are not suitable for applications with strong computing power. This issue should have been covered in the course Computer Composition and Structure. Interested children's shoes can read this textbook.
Mining is not ok if you don't understand computer architecture. But when I took this class at Stanford, I almost failed it. But it’s not that I’m stupid, it’s that my English is not very good, oh no, it’s that my Greek is not very good. Teacher Da Niu Christos has a Greek accent in class, and I basically don’t understand it. Back to the memory problem of mining, in order to ensure storage access bandwidth and latency, we can only use SRAM. But the progress of SRAM performance and price is even more limited. This may not be a good thing for game enthusiasts, because the price of the top game console will not drop much. But will this situation be an opportunity for fair mining?
Let's deduce it: the performance-price ratio of SRAM is so outrageous, so is there a mining algorithm, TA must use a really large enough memory to calculate? In other words, the new mining algorithm is no longer more than CPU, GPU, or ASIC, but the size and bandwidth of memory. Because of the speed of progress in memory technology mentioned above, in the process of the mining arms race, even if large-scale resources can be mobilized, it is impossible to dominate mining with an advantage of tens of thousands or hundreds of thousands of times . Well, no matter how rich you are, you can't completely block the diaosi mining machine. Although it cannot be absolutely fair, it objectively improves the fairness of mining. This is exactly the original intention of our mining and asynchronous consensus, right.
So let's study this type of algorithm. In addition to the four necessary characteristics we mentioned earlier, this type of algorithm must also meet the following additional conditions:
1. The algorithm requires a huge memory space: if it is too small, it will be done directly on the GPU or ASIC, and finally it will become a combined calculation, which is unfair.
2. Unpredictable access to memory: Even if the entire algorithm requires a large memory, if the memory access is predictable, multi-level caching technology can greatly reduce the capacity requirements of the system for high-performance and high-bandwidth memory. Satisfied.
3. Algorithms cannot have conversions between time complexity and space complexity: If you can use high-performance computing to exchange for large memory, that is, reduce the requirements for high-performance and high-bandwidth memory capacity, then return to GPU It's an arms race with ASICs.
An algorithm that satisfies the above conditions is called"Memory-Hard/memory-intensive algorithm". The Cuckoo Cycle PoW algorithm based on Cuckoo Hash is a good Memory-Hard algorithm. This algorithm has been successfully adopted in the Grin project, and Soteria's equal mining technology is also based on this algorithm.
Let's briefly introduce the working principle of this algorithm. If there is still time, I will give you a preview of the design and implementation of fair mining in the SoteriaDAG project.
Let's take a look at the required courses of Cuckoo Cycle Pow. Today we will talk about the data structure of Hash Table and Cuckoo Hash. Everyone must be familiar with Hash Table. We have a hash function Hash, TA can map a Key to a certain position in a linear table, so that a put operation can store a Key Value Pair in the table, as shown in the figure Show:
What to do when there is a collision? That is, both keys are mapped to the same location. It doesn't matter, the newcomer will just check to see if the next position is empty, if it is empty, there will be that position. as the picture shows:
and this one
When querying, use the hash function to find the corresponding position. If the Key is the key we want to query, it will be ok if the return value is found. If the key is different, then we have to look at the next position, if the key is the same, we have found it. If it does not match, continue until it encounters an empty position or traverses all positions, that is, it encounters a boundary condition.
This is the principle of the hash table, also known as the hash table. Cuckoo hash is a leap forward based on hash table. The difference is that TA introduces two sets of hash functions and two linear tables, each function corresponds to a linear table. The same key can correspond to a position in each of the two tables. as the picture shows:
See, two functions correspond to two linear tables.
The addition operation is similar to the hash table, mapping the key to a position in the linear table, because there are two tables, we can choose a table to put it, for example, use the first hash function to map to the first table A location, as shown in the figure:
In this way, we can load many records into the linear table. If there is someone in the mapping position of one of the tables, then use another set of hash functions to map to another table, and then load it in the corresponding position of the second table. However, assuming that the next record to be loaded is very unfortunate, the positions on the two tables mapped by the two hash functions happen to already be occupied, what should we do at this time?
At this time, our new record will kick the existing person to the corresponding position in another table, and that position is determined by the hash function of the corresponding table. As shown in the picture:
If unfortunately there is another person in the place where you were kicked, then continue to kick the person in that position to another table position. By analogy, until the kicked record is settled, or the record that kicked someone else is encountered before, a loop is formed. as the picture shows:
Now everyone knows why this algorithm is called Cuckoo Hash. Cuckoo is actually a cuckoo, they like to lay their eggs in other people's nests, and then kick other people's eggs out. It is really similar to the cuckoo hash loading algorithm we just described. Take a look at this classic diagram:
I pause for the third time, and everyone digests the process of this algorithm, which is a very important algorithm. It’s a little brain-burning later, but there is absolutely no formula. We express the loading and kicking routes on the graph and we can see the directed bipartite graph below:
This is the road map for the cuckoo to kick out other people's eggs. There may actually be a subgraph in this bipartite graph, and this subgraph happens to be a ring. As we said before, kicking and kicking actually kicked the seat where I stayed. As shown below:
The algorithm we mentioned earlier is actually to find a ring structure of a specific length in a randomly generated bipartite graph. In fact, this process is basically access and access to memory, which fully meets the necessary characteristics we mentioned before:
1. The algorithm requires a huge memory space: this bipartite graph is very large;
2. Unpredictable access to memory: the graph itself is randomly generated;
3. Algorithms cannot have conversions between time complexity and space complexity: the problem of finding loops really cannot be changed.
This algorithm makes it possible for us to take a step closer to the goal of "fair mining". There are many design and implementation details that we will discuss in detail in the next sharing.
The city where I live in Northern California has caused widespread power outages due to severe weather in the past two days. Let me show you the map of the power outage.
We will focus on the working principle of this PoW algorithm in the next sharing, and give you a preview of the design and implementation of fair mining in the SoteriaDAG project. Let's stop here for today's sharing first, my side will be dark every minute, sorry that I don't have enough time to answer everyone's questions online. But it doesn't matter, all your questions will be summarized, and when we call, we will answer them separately in the form of articles. In addition, there will be more text sharing later. We'll be back soon in ourhttps://github.com/soteria-dag/soterdPublish mining updates on . Stay tuned, thank you all!
Claire: Thank you Dr. Zhu for bringing us such a wealth of information. Time flies, and it is the end of today's theme sharing. I believe that you still have many questions or opinions. You are welcome to continue to leave messages and discussions in the community. We will collect them for Dr. Zhu and the Soteria team, and they will discuss them with you in due course. Thanks again to Dr. Zhu Jiang for preparing such a wealth of hardcore information for us in spite of his busy schedule! See you next time.
Zhu Jiang: Thank you everyone! Thank you host Claire.
(full text)
