Interview | That "怼" Algorand's paper says? Come listen to the author

There are too many disputes in the market, and even the teacher came out to send me a melon.

On June 24th, well-known bitcoin investor Li Xiaolai posted on Weibo "I really don't know what Algorand is, and I don't understand what they are saying… Who told me?"

Li Xiaolai also has a few screenshots of WeChat chat. The content of the screenshot is probably just auctioned in the Netherlands. The star public chain Algorand founded by the Turing Award winner was questioned by a professor from a US university. Algorand has serious and fundamental errors. .

People are not much. On June 18th, Algorand just finished the first round of Dutch auctions, but after the second-tier market went up, the price of the currency plummeted, and many people dissed it as the “Turing Award-level fund disk”. There are too many disputes in the market, and even the teacher came out to send me a melon.

• Four major regulators in the US have launched Facebook, requesting suspension of Libra development
• ECB Executive Director calls for financial regulators to act quickly on Libra
• Digital currency payment tax exemption How far are we from the blockchain payment?

The author of the paper questioning Algorand is Professor Wang Yongge from the School of Computer and Information Science at the University of North Carolina at UC Charlotte. He is also the co-founder and chief scientist of the public chain project SperaX, and the post-render of RLCE by Professor Wang Yongge. The algorithm became a candidate for the NIST of the American Institute of Standards and Technology.

Recently, the Odaily Planet Daily interviewed Wang Yongge exclusively on his published paper. Wang Yongge gave us a detailed analysis of the doubts about Algorand mentioned in the paper.

Wang Yongge said that as early as May of this year, he had published the paper titled "Another Look at ALGORAND". Wang Yongge told the Odaily Planet Daily that he never thought that his paper would be taken out for malicious interpretation. Completely misinterpreted his positive views and improvements to Algorand.

On June 26, Wang Yongge made a statement through the media. "The so-called "a paper written by Professor Wang Yongge on the Internet has raised the serious and fundamental mistakes of the Algorand project" on the Internet. Misreading and hype of the paper."

Wang Yongge said that he officially published a paper entitled "Another Look at ALGORAND" in May 2019, and made several comments on the Algorand project from an academic perspective, including the theoretical possibility of bifurcation and the Byzantine agreement in Algorand. Too complicated, there is room for optimization, etc. However, "the content of the paper is widely misunderstood."

Wang Yongge reiterated to the Odaily Planet Daily that he did not comment on the Algorand project. On the contrary, he appreciated Algorand and considered Algorand to be one of the best public chain projects. The reason why the article was published was also because of the curiosity of the resistance bifurcation mechanism proposed by Algorand and the possibility of further optimization, so the article was published purely for the academic discussion.

Wang Yongge explained that the Algorand proposed in his paper has the possibility of bifurcation in theory, which is actually a problem of costless simulation attack that is common in PoS consensus. Any public chain adopting the PoS consensus has such a risk in theory; as for the overly complex Byzantine agreement in Algorand, it has been noticed that the Algorand team has made many improvements and optimizations from the initial design to the final implementation. . Professor Wang Yongge said that the paper "proposed a serious and fundamental error in the Algorand project", "obviously misunderstood and hyped the paper" and was very angry with such behavior.

Wang Yongge said that he had already sent this paper to the founder of Algorand, the Turing Award winner Silvio Micali and the chief scientist of Algorand, Ms. Chen Yu, before the publication of this paper on Twitter, obeying the rules of the academic community, but later Did not get the other party's response.

Later in our interview, Wang Yongge stated that he never said that the Algorand system was completely wrong, and his paper also discussed Algorand's article published in arXiv in 2017.

Wang Yongge’s paper on Algorand’s question is mainly divided into three points:

Algorand theoretically has the possibility of bifurcation

First of all, Wang Yongge believes that the zero-fork proposed by Algorand is impossible. Wang Yongge said that all PoS consensus has a problem of "costless simulation attack" or "nothing at stake attack". Andrew Poelstra has noticed this in his 2014 article "A Treatise on Altcoins". Wang Yongge said that Algorand, like other public chains that use the PoS consensus, has a theoretical risk of bifurcation.

Algorand claims to have solved the fork problem in the blockchain, making it a public chain that can continue to "evolve." Due to the decentralized design of the blockchain, each node must be consistent, which makes it difficult to simply upgrade the system in the blockchain. Whenever the rules are changed, it is easy to cause the system to fork. But Algorand is a distributed ledger with almost no forks, because the probability of its fork is as low as 1/10^18, which is equivalent to if there is a block every second, then from the big bang to the now Algorand will only Fork once. The transaction can be confirmed in a few seconds and the funds transferred through Algorand are immediately available.

For the case where the network is not in strong synchronization (ie two blocks are proposed due to network latency issues in both areas), the Algorand network will have a fork. As mentioned in the white paper, this does not affect the security of Algorand, but it will affect the activity within the Algorand network. For a given S time, because the committee members on different forked blocks will have different block information, it means that they will not calculate the number of votes for each block when they are notarized, so there will not be enough votes. By reaching the threshold, BA* will not be able to reach consensus on more forked blocks. At this point, Algorand will propose a branch that is unified for all users, and use the BA* consensus to let the user confirm whether it should switch to this branch. In the case of weak synchronization across the network, if the time exceeds S, the Algorand network completes the irreversible fork and cannot be recovered. The S here is just a coefficient, and the specific parameters are not mentioned.

Algorand's consensus mechanism works under both licensed environments and permission-free environments. In a licensed environment, only 2/3 of the nodes in the network are required to be honest nodes, which are required in a non-licensed environment. Ensure that 2/3 of the entire network's assets are in the hands of honest nodes. In both cases, the probability of the Algorand network's forking will be reduced to less than 1/10^9 (Algorand's article in 2017) It is 1/10^12 – 1/10^18).

In the paper, Wang Yongge believes that these two assumptions of Algorand cannot guarantee the bifurcation of this small probability. According to Algorand's article, as long as the number of nodes controlled by a malicious node does not exceed 1/3 of the number of summary points, the malicious node cannot be maliciously forked. But Wang Yongge cites a counterexample: a malicious node can easily fork by controlling certain nodes that are no more than 1/3.

"Algorand's 2017 article has a theorem: If the total number of malicious nodes (or total gross property) is less than 1/3 of the total number of nodes (or total assets) at any time, then a malicious node cannot initiate a fork attack on Algorand. This theorem is wrong," said Wang Yongge.

Wang Yongge further explained that if the blockchain height is 100, all the assets in the Algorand chain are concentrated in the hands of two hundred users. These users can be represented as P1, P2, …, P200. As the chain grows, new users will join, and two hundred users may sell all of their Algorand properties.

Also assume that there are already 700 users on the chain at a block height of 300. At this time, the number of users P1, P2, …, P200 is already less than 1/3 of the total number of users (the total value of the property they hold is also much less than 1/10 of the total property of Algorand). According to the mathematical model and theorem of Algorand's 2017 article, if these users P1, P2, …, P200 become malicious at a block height of 300, they cannot initiate a fork attack on Algorand's main chain. But the truth is: if these users have almost sold out their Algorand property before the block height of 300, they are no longer interested in Algorand's main chain.

So they can start with a block height of 100 and generate a new chain. Because these users make up all users with a block height of 100. So they can generate a fake chain very quickly. Their fake chain can be generated very quickly and quickly exceeds the length of the main chain. By this time, the newly added users can't tell which chain is the main chain. In other words, at a block height of 300, a malicious node that does not exceed 1/3 of the total number of nodes (or a malicious property with a total property value of no more than 1/3) P1, P2, …, P20 can fork the Algorand main chain . This contradicts the theorem of Algorand's 2017 article.

Wang Yongge specifically pointed out that his above attack is a special case of the Algorand attack with no cost to simulate the attack. All PoS consensus-based blockchains cannot prevent this type of attack. To prevent costless simulation attacks, we must introduce other mechanisms. For example, SperaX uses trusted hardware to defeat this attack.

"Most nodes are honest nodes,"

This assumption is unrealistic

In the Algorand network, all users who participated in the consensus voting were secretly aware of their identity. After voting, their identity was exposed. Although the adversary could corrupt them immediately, the messages they sent could not be withdrawn. After the message is generated, the temporary key used for signing will be destroyed immediately, so that the adversary cannot generate any legitimate messages again in the round.

Algorand assumes that more than two-thirds of the nodes in the network are honest, and that they assume that all honest nodes will destroy the temporary key after completing the task.

Wang Yongge believes that this assumption is not feasible. He believes that it is unrealistic to assume that a node is sufficiently honest in a distributed network, especially in a license-free environment. If a node is given enough benefits, he can be "bribe". An original honest node may eventually "rebel", which is the "bribery attack."

Wang Yongge analyzed that although a malicious attacker has no way of knowing which user to corrupt in advance, it can publicly advertise a block proposer and a verifiers agreement. He would encourage block proposers and verifiers to contact his malicious attacker before proposing their block proposal or before voting. In this way, these malicious nodes can identify the target users to be corroded. In this case, the block proponent and the block certifier will become fans of these malicious nodes.

Wang Yongge believes that Algorand's assumption that most users are honest nodes is unrealistic in the real world. Every node in the blockchain network wants to maximize its own benefits (nearly no one will reject this), and the selected block proponents and block verifiers are getting enough "bribery". The next one can be "rebellious". Moreover, for users who participate in consensus voting, the system does not give them enough economic incentives to ensure that they destroy the temporary key, they are more inclined to sell the temporary key than to directly destroy the temporary key. .

There is room for optimization in the Byzantine agreement in Algorand

Algorand formed a consensus through "Immediate Propose and Agree." This is a "Byzantine Agreement (BA*)". The Byzantine protocol is a communication protocol model that is commonly used in blockchains. Algorand's consensus mechanism is divided into two steps, a proposal and a consensus.

Practical Byzantine Fault Tolerance (PBFT) is the first practical consensus algorithm for implementing Byzantine fault tolerance in asynchronous distributed networks. The algorithm is applied to a distributed file copy system. There are 3f+1 copy nodes in the system, of which up to f Byzantine error nodes. Each replicated node in the system runs a copy of a finite state machine and supports several operations.

The PBFT algorithm consists of a three-phase protocol, which is pre-preparation, preparation, and confirmation. The pre-preparation and preparation phase ensures that all normal nodes perform all valid user requests in the same order, while BA* can complete immediate offers and confirmations.

Wang Yongge believes that the Byzantine agreement in Algorand is too complicated, the implementation cost is too high, and there is room for optimization.

Wang Yongge believes that the corresponding effect can be achieved by a simple method. It is assumed that in the same network environment, the same effect can be achieved by "majority vote".

Wang Yongge said that the Algorand team seems to have realized that Algorand did not follow the Byzantine agreement proposed in their 2017 article during the course of the project. Wang Yongge said that this has nothing to do with the safety of Algorand, but his advice to Algorand.

Reference materials:

"Read the Algorand algorithm in a single article, completely eliminate the blockchain "impossible triangle"

Another Look at ALGORAND

Text | Wang Ye

Produced | Odaily Planet Daily (ID: o-daily)

Original article; unauthorized reprinting is strictly prohibited, and violation of the law will be investigated.

We will continue to update Blocking; if you have any questions or suggestions, please contact us!