The domestic online sharing of the chief scientist of Algorand
On March 15, 2019, CryptoGeek was very honored to invite a mysterious founding team member of Algorand—Chief Scientist Dr. Chen Jing, to the community to chat with you about the progress of Algorand and important technical advantages and characteristics , this event can be described as a collision between knowledge and professionalism, and has been widely praised by blockchain technology enthusiasts in the industry. More than 100,000 people across the network participated in this online sharing. After this event, the members of the password geek community can be said to have gained a lot.
secondary title
Sharing guest introduction:
Chen Jing, chief scientist of Algorand, co-author of Algorand theoretical white paper.
Bachelor and Master of Computer Science from Tsinghua University, Ph.D. in Computer Science from MIT, Postdoctoral Fellow of the Institute for Advanced Study in Princeton. In 2016, he won the Early Career Development Award of the National Natural Science Foundation of China.
secondary title
Topics shared this time:
1. Current status of the blockchain field
2. The breakthrough of the consensus agreement of the main body of Algorand, the core technical advantages and technical characteristics
secondary title
The following is the full text of Dr. Chen Jing's sharing.
Algorand is a blockchain project that is different from many current projects. First of all, our biggest feature is that our technology is based on the First Principle (first principle) and uses a very strict mathematical method to prove its feasibility. The feasibility of the technical system has also been realized through prototype verification. In addition, our Protocol has considered long-term development and evolution when it was originally designed, because there is no way for any blockchain design to foresee all possible future situations clearly at the beginning, so it should be in the initial design. We are also very concerned about leaving enough space and possibility for future evolution when designing.
Current state of the blockchain space
First of all, what is the starting point of Algorand? I think it should be an open secret in the blockchain field, that is, in the blockchain field, there is still a big gap between everyone's vision and expectations and the technology that the current blockchain can provide. We can hear many exciting prospects and ideas, but when these ideas are implemented, they may encounter various problems in terms of scalability, security, etc. In particular, for example, the so-called impossible triangle mentioned before, that is, many people believe that decentralization, scalability, and security in the blockchain field cannot be achieved at the same time, and only three can be achieved at most. Whichever is the second. But such an idea is unacceptable in our opinion, because these three are very important for many blockchain applications, especially in a public chain, which requires large-scale distributed The user group needs easy access for everyone, and it also needs to provide users with high security. But the good thing is that Algorand has implemented these three aspects at the same time, which means we don't think they are incompatible.
Speaking of Algorand, let’s first say that it is a distributed public ledger. Let’s first talk about some basic requirements for the public ledger: First, as a truly decentralized public ledger, it needs to be accessible to everyone , the information on it should be directly readable for all users. Second, it can be modified by everyone, that is to say, no matter what kind of participant it is, it is possible for him to participate in this system, and the final consensus of this system will all be retained on this block. The third requirement is that its security is highly guaranteed, that is to say, the data on the block cannot be tampered with arbitrarily, and the order and content of the data are not ambiguous. However, if you only care about these three points, if you just want to be readable, writable, and unmodifiable, in fact, a centralized database system can also be implemented in this way, but why is the centralized database system not for many people now? Not a very satisfactory solution? That's because centralized management usually becomes the performance or security bottleneck of the entire system. For example, it can be attacked or congested. All permissions must be generated by the central administrator of the system, which leaves A space that is influenced in various ways. Then a decentralized public ledger, the fourth point it requires is that there is no centralized management method. Its consensus generation, data modification, block generation and other transactions are all completed by all users on the blockchain.
Regarding the benefits of distributed ledgers, I believe you have already discussed a lot. I just list them briefly here. A centralized and trusted third party can, in a distributed situation, sign a contract, reach an agreement, pay, and so on. People will not need to meet each other, and they will be able to reach more complex transactions without any trust relationship. With the development of the blockchain, many people have an idea that this is a very good underlying architecture. On this architecture, we have the possibility to create countless application scenarios and very convenient applications. But the most critical question is, how do we implement such an underlying architecture? At present, we have seen many existing methods, such as proof of work, such as proof of equity custody in proof of equity, proof of equity mortgage, and so on.
Let’s talk about proof of work first. Although it was not originally proposed by Bitcoin, Bitcoin has raised the application of proof of work to an unprecedented level and height. Its basic assumption is that the computing power in this system is in the hands of the majority. Although Proof of Work has a good application in Bitcoin, it has also reflected some problems, for example, it has a very high cost. In addition, the balance between this very high cost and the decreasing mining revenue has led to the gradual concentration of computing power to different mining pools. At the same time, this also brings some scalability problems, because the computing power is constantly increasing at a rapid rate. In order to continue to ensure the security of the system, it is necessary to continuously increase the difficulty of mining, entering a vicious circle . At the same time, this continuous forking and continuous selection of the longest chain method also brings a problem to the finality of transactions in the system, that is to say, everyone has to wait for a transaction, which not only has to appear on the chain, but also And there must be enough time on the chain to be able to finally confirm. This is especially important for large transactions, because there may be problems such as transaction rollbacks.
Of course, there is another one that everyone feels more personally. In the workload proof, it may bring a relatively long transaction delay. For example, if you have to wait 10 minutes for a block, if you need six blocks to confirm a transaction If not, then it will take more than an hour to wait, and a large transaction may need to wait longer. So, when looking back at Bitcoin and Proof of Work, we should say that Proof of Work was the first really good idea in the entire blockchain space. It can be said that Bitcoin has made everyone, including myself and many people in our team, re-understand how to reach consensus in a large-scale distributed system. It has given everyone a lot of inspiration, but at the same time, it is necessary to realize that proof of work is not what everyone really needs in a large-scale and fast decentralized system. We have to find another more scalable solution. So at this time, many people's eyes turned to POS, proof of rights and interests.
In terms of proof of stake, there are basically two types that we often see now. One is called Delegated Proof of Stake (DPOS), which is to entrust certain users with the rights to vote or generate blocks. . The other is Bounded Proof of Stake (BPOS). Users need to deposit coins to have voting rights in the system, and the so-called mortgaged stake will not be available for a long time. And if the user cheats in the system, these stakes will also be confiscated by the system. It should be said that such a solution is not a truly distributed method. Algorand believes that the POS implemented in our system is a very pure proof of rights and interests. Why do you say that?
First of all, our system will not confiscate users' coins, nor will they impose so-called penalties on users. We will set up the security mechanism in the system to ensure that even malicious users cannot cause damage in the system, instead of punishing and confiscating stake to achieve this. In our system, there is no need for everyone to deposit coins or lock their stake in the system. Your stake is always your own and can be used at any time. The basic assumption of this matter is also very simple, just like POW believes that the amount of calculation it mines is in the hands of most honest people. The basic assumption of POS is that most of the stakes in this system are in the hands of honest users. There is a very critical point here, that is to say, every token in this system has the same decision-making power and is equivalent. It doesn’t matter which user the token is in, and it doesn’t matter whether the user has any other accounts, or has any stake in other accounts. So the original intention of our design is to always make it a truly distributed and decentralized system. But to solve it in a technical way, to achieve this, we have to face many, many problems in the middle.
The breakthrough of the consensus agreement of the main body of Algorand, the core technical advantages and technical characteristics
I just introduced the general situation of the blockchain. Although I believe that everyone is already familiar with it, the brief introduction is for everyone to have a general understanding, and also for the next technical introduction. background foundation. Next, we will enter into a comparative technical discussion, which is some of the core technical advantages and technical features of the consensus protocol of the main body of Algorand. Mainly, I will introduce three aspects to you. One is our Byzantine agreement, and the other is what we use when we choose users to participate in the consensus agreement. We call it the secret self-selection process. The third is that our consensus agreement is very A unique feature we call user substitutability. And this is why our system can allow an attacker to dynamically attack users at any time, and we can still resist this kind of attack. After introducing these three points, I will introduce our new algorithm, that is, Algorand 2.0, and tell you some of its advantages and technical features in resisting network segmentation attacks.
1) Byzantine agreement
The Byzantine agreement is actually a very classic concept in computer science, and there have been many studies in this area in the 1970s and 1980s. Of course, the research on the traditional Byzantine agreement is in a relatively closed environment. The number of computers and the identities of all users are known in advance, so the working method and working environment of the Byzantine agreement at that time were relatively simple. Before extending it to the blockchain, we can briefly introduce the two most basic characteristics that the Byzantine agreement can achieve. It is because of these two characteristics that the blockchain can guarantee that our consensus agreement has no ambiguity.
First of all, the nature that can be achieved by the Byzantine agreement is of course identity. That is to say, after many users interact through the Byzantine agreement, no matter what their own understanding of the state of the system is at the beginning, everyone can think that each person at the beginning Every now and then, everyone will see some transactions sent to themselves, and then everyone will combine a block based on the transactions they have received. It can be considered that the system state that everyone sees is the value of the block itself, or the hash value of the block. After the communication in the Byzantine agreement is completed, all honest users will eventually output the same system state, which is the hash value of the same block. Then it is the result that a blockchain needs to achieve. Based on the previous block, there is no doubt that the content of the next block is unanimously accepted by everyone.
Another very interesting feature of the Byzantine agreement may not be known to many people, and this feature is precisely why we can quickly reach a consensus later. That is, the consensus that can be reached by Byzantine agreement. The so-called consistency means that in the process of reaching consensus in the system, if the system is in a relatively good state, then it will not waste the interaction in the system for unnecessary information transmission. In other words, that is to say, if all the good users in this system, at the very beginning, the transactions you see or the blocks you form yourself have already reached a consensus state, then the Byzantine agreement We will not force everyone to agree to something different. This is why the system using the Byzantine agreement will be faster when the network condition is relatively good and under normal circumstances.
Why can't we directly use the existing Byzantine agreement and use it directly on the blockchain? Everyone participates in a Byzantine system, and its output is the content of the next block, which is exactly what a blockchain wants to achieve, so why can't it be done directly? There are two main reasons. The first reason is that the existing Byzantine agreement is still relatively slow in general, although we can say that this agreement is a polynomial time in theory, such as the running time and the total number of participants. The square or cube is proportional, there is no problem in theoretical validity, but it is not feasible to apply a so-called polynomial time Byzantine agreement to this, because even if it is a square or cubic time agreement, if To run it in a system with millions of users, you can imagine for yourself that the amount of communication and calculation is millions of square or cubic, and the required consumption is beyond the capacity of the system. And another very key reason, why the Byzantine agreement cannot be used directly in the blockchain, because the original design of the Byzantine agreement is in a relatively closed and relatively good network environment, that is, the number and identity of all users in it are already It is determined in advance and known to everyone. Both of these points are impossible on an open Internet. Because everyone can easily generate many identities on the Internet, and no one knows whether the two identities on the Internet will be controlled by the same person. Account, where is the user corresponding to each public key. This is the Sybil Attack that many of us are familiar with. It is an attack that controls many permissions on the Internet by generating multiple identities. This attack is completely feasible for the original Byzantine agreement. Therefore, if the Byzantine agreement is to be used on the blockchain, the above two problems must be solved, which is what the Algorand consensus system does.
First, the new Byzantine agreement protocol we designed is a very fast and efficient protocol. First of all, the participants in the protocol only need to send a very short message for each step, and even Even in a very bad network environment, this protocol only needs a few steps to complete a consensus in the expected state. It should be said that such an agreement is already very fast in theory. But even with such a protocol, it is impossible to directly use it in a system with, say, 10 million users. Why? Because there are 10 million users, even if everyone sends a very short message, the network in this system has been completely blocked. For this solution involving a large number of users, I believe many people can easily think that since there are so many users, then we just randomly select a small group of users to participate in this protocol. One of the simplest ways is that we can open the selection, so that everyone knows who is selected, and the selected users only need to communicate among themselves. In this way, the Byzantine agreement protocol can be limited to a small range. How can this be achieved? In fact, it is very simple. For example, for each user's identity, ID or his public key, or other identity information, make a hash (hash value) to map it to a random character of, for example, 256 bits. string, and then sort the strings of all these users from small to large, and at this time change all the users randomly. So if we need a thousand users in this system to participate in the Byzantine agreement protocol, we only need to take the first thousand users of this random transformation, which is completely fine. This is a very efficient way, very transparent, and very easy to implement. So what's the problem with this approach? Why wouldn't it work if we publicly and randomly elect a small group of users? Many people may have thought of this question.
In other words, not only good users can easily know at this time, who will be responsible for generating the next block, and who will be responsible for generating the next ten blocks, but also malicious users can easily find this out. And it can be discovered a long time in advance, then a malicious organization can attack these selected users in advance at this time, so that these users cannot go online when they need to participate in the Byzantine agreement agreement, or send the wrong information and more. We have seen that in the current blockchain field, there are such protocols. The most basic assumptions of these protocols are that any malicious individual or organization will take a long time to attack a user. For example, it takes a day to attack a certain user, which is much longer than the time required to generate a block. Such an assumption is completely unacceptable in our opinion, and we hope that Algorand's system can resist very powerful network attacks, or other attacks. So in our system, when we design, the imaginary attacker can take down any user immediately and at any time, whether it is DDOS or other methods, these attackers can completely control all The attacked users, no matter what messages they send, when they send messages, or even when their messages will be sent to good users, can be completely controlled by the attacker. Our only assumption about the attacker is that it cannot crack the most basic elements in the password, such as hash functions, such as digital signatures or encryption, etc. These are also some basic assumptions required by all digital systems. Therefore, for such attackers, it is not realistic to openly choose users who participate in the Byzantine agreement. The innovation of Algorand is that we use a secret method to allow users to choose whether they should participate in the Byzantine agreement, or even which step in the Byzantine agreement they should participate in.
2) Secret self-selection
The so-called secret self-selection sounds abstract. When I usually imagine it, I like to use a lottery system as an analogy, that is to say, each user will generate his own lottery. It is the lottery itself that has decided. When there is no winning, the user cannot deceive the system, and cannot deceive other people to say that they have won the prize. And in the case that the user has won a prize, it can easily tell everyone, just show this lottery ticket. And another point of this is that when the user knows that he has won the prize, but before he publicly redeems the prize, an attacker has no idea who will win the prize, and he has no idea who to attack. So if there is such a lottery system, we can enable users to secretly determine who will participate in the following system and who will participate in the following consensus through this lottery, and then they can be completely like other users Prove that you do have this authority. Of course, another problem is involved here. The lottery system we see in reality is completely centralized. It is a certain issuer who prints out all the lottery tickets and then distributes them to everyone. This approach is contrary to the decentralized system we mentioned earlier. What we need is actually a distributed lottery generation system. Each user can use his own private key to generate his own lottery ticket, so that he can neither cheat nor prove that he has won the lottery.
If you first think about it, these two points may sound contradictory. Why? Because if a user can generate his own lottery tickets, then he can secretly generate many. He can generate one, and then find that he has not won a prize, and then generate another one, and can continue to generate until a winning lottery ticket is generated. Then use this lottery ticket to tell everyone that he should participate in this system. In this case, a malicious user can generate many lottery tickets by himself, and then only show the winning one to everyone. Of course, such a system cannot work at all, because at that time, malicious users will always tell everyone that I have won the lottery, and then I should participate in this system. This is a very important point when we do this kind of secret self-selection, that is to say, in our system, each user can only generate a unique and certain lottery ticket, even in the stage of lottery ticket generation, it is There is no way to cheat. This requires some knowledge of cryptography. The structure of this cipher is called VRF (Verifiable Random Functions), which can verify random functions. Although it is impossible for us to describe a VRF from beginning to end in today's sharing, it will take too much time, but we can tell you what is the most basic structure of VRF. Its basic structure, if you figure it out, is actually pretty simple. You can think of a VRF as having two basic structures, one is a digital signature and the other is a hash function.
When a user wants to generate his own lottery ticket, he uses his own key to sign, for example, the current system state, and generates his own signature. Of course, this signature can only be generated by himself, while others People don't know what it is at all. If he wants to prove the signature to everyone, as long as he uses his public key, everyone can verify that the signature is correct. With this signature, it is very easy to generate a random lottery ticket. You only need to use this signature as the input of a hash function. For example, you can output a 256-bit random number, then this random number becomes this The value of the user's lottery ticket. If we want to select 1,000 users in a system with 1 million users, then the probability of each person being selected should be 1‰. At this time, you can define that when the output of this hash function is less than 0.001 , then the user is selected, and if it is greater than, then he is not selected. The output of the hash function is a string, which is usually considered an integer, but you can easily interpret it as a real number by adding a decimal point in front.
So it seems that this is a very simple operation, just let the user sign the name, and then hash (hash encryption) the signature, then the final result can be a random number. Because it is impossible for an attacker to forge the user's signature, there is no way for him to predict what value a certain user will eventually output through the Hatch function, whether he is selected, and so on. But in the description I just made, there is actually a hidden problem that is not easy to be discovered. People who are familiar with ciphers, VRF or digital signatures may have realized it. What is the problem? That is, many digital signature systems have random numbers in them. It is usually necessary to generate a random string, and then this string will be used as part of the input of the digital signature protocol, and then a signature will be generated through it. That is to say, the signature process is random. For the same system state, if different random numbers are used as auxiliary inputs, different signatures can be generated, and these signatures are all valid. This goes back to the issue we just said about lottery printing, which is equivalent to giving a user the possibility to print countless lottery tickets by himself. Because it can completely use a signature method with random numbers, you can keep changing different random numbers until you change a random number, and the signature it generates gets a very small hash value after being hashed, like What I just said is less than 0.001. I just mentioned that this way of allowing users to print countless lottery tickets at will is of course unacceptable.
Then this will mention another very good innovation in cryptography, that is, unique signature, unique signature. The so-called unique signature, as the name suggests, is easy to understand. That is to say, for the same document that needs to be signed, or the state of the system, the same user can only generate a unique signature with his own key. At this time, the user has no way to cheat, because the system state is certain, his own public key and secret key have been generated in advance, all he can do is to give these two things to the signature function, and the signature function A unique signature value will be output, and this unique signature value will correspond to a unique hash (hash encryption) output. This unique hash (hash encryption) output is also the only value that may be accepted in this system. So the two basic structures of a VRF are actually very simple, one is a unique signature, and the other is a hash function. Basically, it can be seen that many VRF structures can be decomposed into similar two parts.
3) User replaceability.
This is some of the more interesting technologies in secret self-selection, so even after using the secret self-selection method, there is another problem, that is, when a user is selected, he does not issue any Byzantine agreement. Before information or voting, a malicious user certainly does not know who this person is, nor does he know whether this person has been selected. But as long as the user sends a message in the system, he needs to tell everyone the signature, then at this time the malicious user will immediately know who is selected and who will be responsible next, then at this time the malicious Users can also immediately block or attack these people in the next steps. We are still back to the previous state, that is to say, all participants are malicious, so to solve this problem, we must mention another very interesting innovation of Algorand, that is, user replaceability. In Algorand's consensus protocol, it has several steps, such as the first step, the second step, the third step, etc., but there is no need to store internal state between each step. The content of the next step can be determined based on the current public information. So it is completely possible to select a group of users in the first step and let them send the information in the first step. In the second step, a completely different group of users is selected, so they don’t need to know the first group of users. What kind of internal structure you have, it can completely decide what the second-step information should be through the public information sent out on the Internet, and then decide to finish sending your own second-step information. By analogy, even if the user in the second step is attacked immediately after sending the information, a new user group will be selected in the third step of the protocol, and this user group is still based on the public information on the Internet. Information to decide what your message is. So the attacker never knows who will be responsible next and who will be selected from them. This also ensures the security of the entire system. Even if the attacker can take down a user at any time, it will not affect the execution of the next protocol of the system. And this method of re-selecting users at each step ensures that the entire system is really a decentralized system, and no user will be in charge for a long time. All users, in fact, every user of the user A token has the same probability of being selected. This is a truly distributed, truly proof-of-stake based system.
Therefore, in the Algorand system, it does not have a proof-of-work method, and does not require users to solve difficult password puzzles. Its calculation amount can be said to be very small, and its user selection method is also a real decentralization. And the Byzantine agreement itself, because there will be no disagreement or fork, so any transaction, as long as it enters the block on the blockchain, it can be considered to be finalized, and not It needs to wait for it to have a lot of blocks generated behind it in this system before it can be confirmed. So this system can provide high scalability and security.
Algorand's technical development, Algorand 2.0
Let's briefly explain Algorand 2.0, which is the system that will be used in our mainnet. In addition to inheriting the characteristics of Algorand's original consensus protocol, this system is still user-replaceable, and still selects users who participate in the Byzantine agreement through secret self-selection, and it is still a very efficient protocol. But in addition, 2.0 has a very strong property, which is currently not achievable by any blockchain system, that is, it can completely resist attacks on network segmentation and recover quickly. What's the meaning? That is to say, in a blockchain consensus system, we usually have to assume that a transaction or a block will be propagated to the entire network. Because if the transaction cannot be spread to the whole network, or the consensus information or block cannot be spread to the whole network, then obviously there must be at least two parts of users, the blocks they see are different, and the blocks they see are different. The status of the transaction is also different. This means that there is a Double spent, that is, the possibility of double spending. This kind of network attack is usually not considered when analyzing the Byzantine agreement, and the reason why we consider this is because to make the whole system more realistic, we need to consider all possibilities. Now there are, There are also attacks that may be encountered in the future.
The cost of an attack that divides the network is indeed very high. But if Algorand becomes very successful, for example, when there are many assets on it and the value of the entire system is very high, some people may be willing to spend a lot of investment, such as investing millions of dollars, and then transfer a large number of users to other users. A large number of users are completely separated and completely control the communication between them, making it impossible for them to reach a consensus. Under this network attack, it can be said that no blockchain can remain secure and continue to generate blocks. Because of a very simple reason, any system needs to finally confirm the block time, for example, one minute or one hour or one day, then in the case of the system being split, if the split time is longer than one minute or One hour or one day, then the system has no way to generate an effective consensus. However, in the system protocol of Algorand 2.0, even if the network is attacked, it can still guarantee that the system is safe and will not fork, that is to say, there will be no two confirmations at the same height. blocks. And once the network attack in the system is over and the network restores its previous connectivity, the consensus protocol can be easily restored and new blocks can be regenerated.
And these two features, one is in the case of network segmentation, that is to say, even when the network enters a completely asynchronous state, the attacker can completely control the transmission of messages in it, and any message may be delayed arbitrarily. Algorand 2.0 The protocol will still not fork. Another, that is to say, when the network returns to a well-connected state from this completely divided state, the system can easily recover and can then generate blocks. The realization of these two properties is achieved through a new Byzantine agreement. Due to time constraints, it is impossible to introduce the details of the system here.
This new system has now been implemented in our test network. The test network is by invitation so far, and everyone needs to submit an application for approval by our developers. It has been running relatively stably for a long time, because it was joined through an application, and the number of nodes in it is not many, but the distribution of nodes is very wide, from the United States to Australia to Asia to Europe, etc. There will be nodes distributed, and there are also It clearly verifies the stability and scalability of the entire system. We will open the entire testnet to everyone soon, and everyone is welcome to pay attention.
