Algorand, may be, somewhat broken.

Reposting my post from Medium (https://medium.com/@rajeshbhaskar/algorand-may-be-broken-d1d2c2542064)

Algorand is one of the most interesting projects in the blockchain space, with a lot of promise. I really like the maths and cryptography behind it, but I think the overall blockchain schema is theoretically broken, however — you decide. I am also working on a solution, inspired by Algorand itself.

In the blockchain space, Algorand is quite well known as the one “without incentives”.

Quoting from Coindesk report from Apr 4, 2017:

“Can you say anything about incentives in Algorand?”
That question was directed to Silvio Micali, an MIT professor who had just delivered a keynote on his theoretical proof-of-stake (PoS) system at the Financial Cryptography and Data Security conference in Malta, yesterday. And the Turing-award winner’s answer set a few back on their heels.
“Incentives are the hardest thing to do,” Micali said.
As he explained, when you put incentives out there, people learn how to use those incentives for making money in ways that are nearly impossible to predict.>

I agree. I also submit that the Algorand “theoretical proof of stake” is also flawed for the same reason. Even without Algorand incentives.

Supposing, for example:

1. Total money in the Algorand system is about 1B USD. Total wallets about 1 Million. Total verifiers ~ 10000. Committee size ~ 1000 (can vary — see below).
2. Wallets A1 to A200 hold 25% of the wealth in big quantities each (Between 0.5 — 1 Million USD each. Total 250M USD). They are registered as verifiers and have full nodes. Let us label the verifiers as V1-V200.
3. Some Big and Small Whales, with Wallets A201-A10000 hold 70% of the wealth in the system (700M USD). They are NOT registered as verifiers. They do NOT have any nodes for verification, ONLY wallets.
   Wallets A10001-A10000001 hold 5% of the wealth in the system (average of 50 USD). Some of them (10000) are registered as verifiers. (Do you see the problem already?). Note also that these folks must maintain nodes so that they can verify transactions.
4. The voting power of A1–200 is now about ≤25% of the total votes or ≤250 out of 1000. (Why? “Algorand’s committee election mechanism is weighted, and a user with high stake is likely to get more than 1 vote. Intuitively, each coin is mapped to a user. The algorithm elects, say, 1000 coins out of the total stake, and then the owner of each elected coin gets one vote. If K coins that belong to a user are selected, that user gets K votes.” — Private email correspondence with member of Algorand, reproduced without permission.)
5. A10001 to A1000000 hold their 5% in “small” quantities (about 50-100 USD each on average). About 10000 of them have registered as verifiers, so they should get the remaining 750 votes. Let us call them V1–10000 (This population will get the remaining 750 votes, although each wallet V(x) has quite a small probability in itself.)
6. 50% of V1-V10000 can be corrupt without violating any assumptions of Algorand. (in fact, even more can be corrupted without violating the assumption of Algorand that majority of money is honest.)
7. Assume 50% of the potential verifiers are corrupted by the Adversary. (Two possibilities: 1. Mr Adversary uses a botnet/malware to infect multiple Algorand verifiers — this will become possible if mobile phones etc can also be made as verifiers 2. One single Mr Adversary actively raises funds worth 50M USD to create 5000 wallets with 10000 USD each. 8. So, the corrupt Adversary holds about 5% of the total money in the system distributed among 5000 wallets.). Each corrupt wallet holder has a 100-200x voting power and probability of committee selection compared to the rest of the population (the rest of the population has an average holding of 50–100 USD only.)
8. The parameter h (weighted fraction of honest users — check whitepaper) is higher than 90. So the ideal committee size will be between 500 to 1000 (as per the Algorand whitepaper). Let us assume a committee size of 1000.

Clearly, (750 of) the 5000 corrupt accounts of one single (in possibility 2 above) Adversary, together have a high probability (much greater than 5*10^-9 expected in the whitepaper) of being chosen to form the committee. They can even get 2/3rds majority with at least 670 votes and override the remaining committee members.

All that is remaining is to transfer out money from A201–10000 (≤ 700M USD) and also the 50M used to fund the attack.

The cost of funding this attack using a single Adversary, however, is quite high at 50M USD (although only 5% of the total money [1B USD] in the system).

I reached out to the Algorand team, including Dr Micali, who responded quite graciously. He assured me that while it is plausible, the probability of this scenario (slightly modified and made more precise from the version sent to him) is negligibly low. Hopefully I did not miss out something very simple!!

There are some ways of working around this problem in current Algorand with its PoS. Keeping a minimum staking amount, restricting validators to a small set etc may be a few ideas here. Such solutions will impact decentralization and scalability and probably make Algorand somewhat as good as Tendermint with its PoS.

I really am impressed with the Algorand BA* self-selection method for choosing proposers and verifiers and would really like it to work. But, as mentioned by Dr Micali himself, even a theoretical proof of stake is “all about the money” and that remains a potential problem, especially in Algorand.

My team and I are working on a (theoretical) solution for Algorand without the PoS element and hopefully that will resolve the matter. It is upto Algorand to be open to adopt it and defeat the Adversary!

— Cheers! (Rajesh Bhaskar)

(*) The purpose of publishing this article is to educate, clarify and thwart any loopholes in Algorand and also to study alternatives.

(-) Please read the Algorand White Paper to know who/what is the Adversary and how it works.

(+) If you liked this article and would consider donating to my independent blockchain research efforts to build a better blockchain, please do so to the wallets below:

ETH: 0x058503afffd50303e1e49623c67e8760f50d304d

BTC: 3PrR945zHeTPh7kmUiftUUwmxUV2jkuy4M

@dan