Broken Algorand fork-free property: Another Look at ALGORAND

Yongge Wang with his recetn paper “Another look at ALGORAND” (May 11, 2019) (arXiv) says it is possible to fork Algorand even with 1/3 malicious users and possibility to bribe validators easily is not unrealistic:

[…] our first attack in this paper shows that a malicious adversary who controls less than 1/3 of the users (or money units) could fork the ALGORAND chain very easily. Our second attack shows that a malicious adversary could use a bribery attack to fork the ALGORAND chain very easily also.

Is there any official response for Wang claims?

Hi @robert Thanks for the interest; you may find this post relevant: https://www.algorand.com/resources/blog/various-questions

Hmm. That’s a very interesting article.
At first the article claims

… could fork the ALGORAND chain very easily

And later on

… fork the ALGORAND chain very easily also

Yet, we both know very well that so far the Algorand network has not forked.
( even though, it’s “easy”; right ? )

I think that there are at least three aspects that are completely ignored by the article.
First, the implementation doesn’t use 1/3 and 2/3. In most cases, the actual implementation require higher committee thresholds. ( i.e. enforces higher security than required by the Algorand original design )
Second, the assumption of “having 1/3 corrupted” is meaningless if you can’t tell which 1/3 you’re truly referring to. The VRF is ensuring that a voter/proposer would figure it out only when it matter most, hence - removing the “target” from any potential participant. It cannot be realistically “predicted” any easier than breaking a cryptographic signature.
Last, almost half (48%) of the voting stake is maintained by the Algorand Foundation. The Algorand Foundation sole purpose is to support the Algorand network; hence, they cannot be “bribed”.

To sum this up, easy, it’s not going to be…

Hi @tsachi. Thanks for response.
I think this deserves a whole analysis and an official response to tell the “world” how easy it is.
I don’t make any claims, but I saw this criticism and also this page also cites the paper: https://golden.com/wiki/Algorand

I would expect that we qualify the attacks:

1. Today foundation has 48% of stake, it doesn’t mean that it’s impossible to bribe (although most of the world will trust the foundation). Moreover the foundation share is going to decrease.
2. Re VRF: malicious actors can collude and create a “gang”. An baker knows that he / she can produce a block immediately after the previous block got published. So he can quickly send a message that he is in and find out how many other bad actors are in. He can also anticipate the network state in order to evaluate a success rate of an attack.

Stake thresholds

Could you elaborate the 1/3 treshold? I know that everything is about probability here. Once 1/3 stake is at malicious hands then the probability of having a validator set of at least 1/3 malicious actors is significant and then the system will halt. Correct?

Various Questions about the Algorand Blockchain

I’ve read that article some time ago. I don’t understand the most important part of Q1:

Suppose that S1000 (the set of all users present at round 1000) collectively own less than 1/3 of the total stake in round 2 million. Can an adversary, who corrupts S1000 at round 2 million, have them produce a different block for round 1000?

What’s the relationship between users present at round 1000 (S1000) to users present at round 2 million? Also, going through the response for Q1: Algorand doesn’t have checkpoints. So even we forget the private key which signed block at round 1000 (R1000) we could keep a “secret” chain and perform long range attack which forked at R999. Correct?

I don’t think the article deserves much attention. It has several mistakes in the assumptions.
Runtime Verification is a company that is focus on formal verification, they build products, languages and won grants from NASA on this field.
They formally proof that Algorand can’t fork: