Forking in algorand network - Indefinite stuck better then forking?

General
1

Hi, I am very happy that Algorand management seeks youtubers who do not ask bad questions and propagate the network because I believe there is huge potential in it.

However. I have some doubts in the basis of the algo protocol.

In this video Silivo has noted again that there are no forks and attempts to tell us that probability of fork is less then time of the universe.

However this applies only for stable internet and does not take into consideration internet to be spitted to several subnetworks…

I have asked this question before in the algo forum with no answer to it, so I am doing specific topic from it…

So what does happen if russia, china or some other ISP will cause of network not to communicate…

Lets say the example of 1000 people running nodes in russia, 10000 outside of russia… Protocol has been setup to create block each 4 seconds, so when nodes in russia will not communicate to outside world, I assume the russian group will create block, and outsiders will create different block… Depending on the location everyone accepts the block because they communicate to the nodes they are connected…

So the problem is that there is double spending opportunity. If someone could spend the block in both areas, lets say deposit algos to russian exchange, and deposit to the US exchange, he will have money deposited twice.

This issue is solved in bitcoin by taking over the longer branch. In algorand Silvio is trying to persuade us that there is no such issue.

I have suggestion for you:
Can you please stop talking about no forking of algorand blockchain, and invent the mechanism that will prevent double spending? This mechanism may be for example the decision that when the internet nodes will unite again and try to resolve the conflict, the accepted transaction will be the one that is older, and will be included in the blockchain with more transactions…

Silvio, please if you read this please be more participative in the forum/discord… It is your company. If you really believe that the algo governance should be democratized, please do real steps to prove it… Please make the algorand much more transparent… The 3B algos in the hands of people from circle of trust (runners of relay nodes) is quite the issue for the real price move…

Also it might be good to make a list of public appearences of algo management and Silvio… Because now it seems as they are trying to influence the market and only few people knows when these types of vides are going public… It is like if tesla would not make public announcement when the annual shareholder meeting will take place… Or that the event of battery day would be lived streamed without prior notice…

2

OK, I think there is a need for an AMA session with Prof. Micali. There are a lot of Algorand employees on this forum, we should ask them to forward our appeal for an AMA. E.g. @ryanRfox , would you be so kind to do so?

Back to the forking question: I think, Russia and China could be treated in the case of a network split like “bad people”. So, if less than 1/3 of the staking Algo power is in Russia, China,etc,. the network would go on. In Russia, China,etc.the network would grid to a halt – not enough voting power to create a block. But on the majority of the Internet life would go on.

So, yes, I think Algorand is vulnerable to network attacks Russia and China could make. But making so would be a kind of a financial suicide. It is the question of worldwide useage: how popular and how widespread Algorand will be in the next years? (If) When one day it will be so widespread like the smartphones today, and the Android OS, then Russia and China would become powerless against it, in a sense.

Technically, Bitcoin can fork even without a network split, because of the network delays, and the uncoordnated nature of the proof of work hash calculation, but the probability that Algorand will do so is negligable, 10^{-18}

The long run is a misleading guide to current affairs. In the long run we are all dead. Economists set themselves too easy, too useless a task if in tempestuous seasons they can only tell us that when the storm is past the ocean is flat again. (John Maynard Keynes)

3

Russia and china has power to set the firewalls so that no allowed communication goes out or in… Thus the algo nodes within the china would see the nodes outside of the world, so they would think they are the only nodes thus they will not die and create their own blocks…

Why do you have assumption that there is not enough voting power to create a block?

4

Because of the previous number of votes… and the sudden change of the numbers… but I have feelings only, Prof. Micali is the one who can answer your questions.

In the meantime, let’s try to read his paper, Byzantine Agreement, Made Trivial

5

are you sure something like this is implemented? what is the percentage of the sudden change? Can one entity put the network down by either stop being validator or by increasing number of validators and sudden stop? (Eg. binance or coinbase would stop it for whatever eg technical reason)

What will happen with the governance protocol and stopping the staking rewards?

6

I Googled this article:
A Technical Q&A on Network Partition Attacks, date 23-Jul-2020, by https://hackernoon.com/u/ricc

A quote to pick your interest:

A few weeks ago, after I started my path as an Algorand ambassador, I had an opportunity to interview the leaders of Algorand foundation, Silvio Micali and Massimo Morini.

I asked them different kinds of questions including some more technical ones about network partition attacks, which interest me. Then I decided to go deeper into this topic.

7

Have you read it @scholtz ? It is clear, the “Algorand prefers safety to liveliness”, i.e. the whole Algo network would grid to a halt.

But after the network split, recovery would be VERY quick – with recovery messages.

No double spending possible – that’s true, because no spending is possible.

8

Yes, I believe that @Maugli is correct here.

In the case that there isn’t enough stake online ( i.e. or that the votes generated by that stake are missing due to firewalling / shutdown computers or others), then the network would stall.

This would ensure that once a new block does get accepted, it’s being done with no less than the committee threshold votes. ( i.e. weighted votes, of course ).

But please don’t take my word for it. You can spin your own private Algorand network, and test it for yourself. You’ll be able to see that the network not only get “stuck” when the committee threshold are not met, but also that the network knows how to recover from these situations pretty fast.

9

Thanks for sharing this resources… i have not seen them before, but i am very happy that I am not the only one concering this…

How is Algorand secured against possible attacks on relay nodes that secure communication? Is it even possible to attack the relay nodes to paralyze the communication between participating nodes?

M. Morini: Any decentralized system is susceptible to a network attack in which an adversary targets the communication links between users, making it difficult or impossible for users to interact. But during a network partition in Algorand, the adversary is never able to convince two honest users to accept two different blocks for the same round. Algorand remains secure.

How would Algorand react to splitting the network if the Great Firewall of China and potentially Russia would stop all the application protocols of the internet?

M. Morini: In case of such a dramatic event, Algorand is best poised than any other blockchain, as I explained in the previous answers.

I dont understand the answer that “adversary is never able to convince two honest users to accept two different blocks for the same round” … In the real world if network would be split, there would be two honest people in each area and two adversaries… Do I get that right?

I assume everyone is honest, and the event is that the china blocks the internet… So some network reminds in the china and some outside.

I was not been able to find answer for what percentage is required for network to be halted… Is this hardcoded in the protocol?

I am trying to brainstorm this, and I believe it has the solution… If we allow these network subparts to be disconnected and create blocks separatly (in the case of chine lets say for month), then the solution would be to combine these blockchain… I assume most people are honest, so if they were doing some transactions within china area they will not do it in other area…

So most of the transactions are safe… the thing is that if some actor has access to both china and nonchina area and do the transactions, he might do it as doublespending… so if we make rules that the doblespending is decided by the earlier transaction, and we use the blockchain with more transactions, the issue is solved… Am I wrong in my opinion?

It is better solution then to halt algorand spending in whole chine for month… or?

10

This is a very good question. I’ve written a detailed answer there: Network partitioning - #2 by fabrice Let me know if something is unclear.

The short answer is: there is no risk of forking on Algorand even in case of network partitioning as long as something like 80% of the (online) stake is honest.
The very high-level reason is that all nodes know how much stake is supposed to be “online”, aka participating, as this information is written in the blockchain.

2 Likes
11

I still do not understand…

If there is split on the network…

The first group does the key registration transaction and everyone is aware of it…
The second group does the key registration transactions and everyone in the network is aware of it…

Both groups has more then 1000 participants.

If network is stalled for the 320 rounds, will it create two different blockchains?

320 rounds = 24 minutes…

How long can the network be in stalled phase?

12

When the network stalls, no blocks/rounds are created and no transactions can be committed at all.

To make a key registration, you need to make/commit a transaction to the blockchain.
So if the network is split 50/50, you just cannot make a key registration at all.

A round takes 4.5s only when the network is not partitioned and a sufficient percentage of the nodes are honest.
If the network is partitioned 50/50, there is no new round created: 1 round = infinite amount of time (until the network recovers).

1 Like
13

Also, if you are interested, there is actually a formal proof in Coq (i.e., a proof verified by a computer and not just a human) that the Algorand network never forks even in case of network partitioning.

There is a very detailed report there: algorand-verification/report.pdf at master · runtimeverification/algorand-verification · GitHub

You will see at the bottom right of the first page that network partitioning is considered.

Actually, the Algorand blockchain is secure not only when there is a split in the network but also when an adversary has full control of the delivery or non-delivery of all messages sent by the nodes. This is an extremely strong adversary. The network split you are considering is a very particular case of this.

1 Like
14

ok, i get it…

so the correct answer is that china or russia or both can block algorand indefinitly if they decide to firewall their algo stakeholders…

or the attacker needs just to bomb few datacenters and all algo is down…

should I accept this as the answer as it should work, or is there any way how to suggest improvement to Silvio? @fabrice … do you realize there is huge flow in it?

I understand that this cannot be solved by the governance as it just decides percentage of the use how much money will the early backers will receive… Or is it?

15

Yes. And this is unavoidable, not just for Algorand but for any blockchain.

The CAP theorem (CAP theorem - Wikipedia) essentially says at a high level, when rephrased in a blockchain setting, that:

  • either what you mentioned is true: putting a firewall splitting everything 50/50 blocks the blockchain indefinitely [CP in CAP].
  • or you can allow double spending [AP in CAP].

Many blockchains seem to have chosen the second option.
BitCoin and Ethereum for example are clearly an example where if you were to have a firewall for even 10min-1h, it would be free double spending for everyone.

Algorand decided to go the CP/security route.

Already today, you would need to bomb more than a single cloud region for that. (Just bombing all the datacenters in a region would not destroy 20% of the stake to my knowledge.)

As the Algorand stake becomes more and more decentralized, it will become next to impossible: you would have to bomb hundreds of locations.
(This is one big advantage of the Algorand protocol is that the performance of the network essentially does not degrade even with thousands or millions of participation nodes.)

If you manage to do that, I think the issue with the Algos is quite a secondary question…

Unfortunately, theoretical computer science and the CAP theorem says this flaw is unavoidable for a fully automated system.

That being said, if there were to be a long-lasting firewall, there are many possible solutions.
Just one possible idea (I have not thought it through, but it’s to show that you can do things): have an update of the software that would essentially split the blockchain in the two regions, by considering only as the online accounts, the accounts that are in your region. This new software would only allow for governance votes (and no other transactions). From there, it becomes possible to have a governance consensus on the best next step.

Note that thanks to the choice of security, no money was ever lost in the process!
Compare with blockchains favoring availability over consistency: adversaries could, in the same context, double spend as many tokens as they want and launder it in a way it becomes impossible to fix anything later.

I want to argue that these blockchains would be in a much worse situation as after all these double-spending transactions than Algorand: the token essentially lost all its value and meaning.
Yes, you would always be able to transact, but what does it mean if your transaction will just be reverted in 10 days when it is realized that it comes from a double spend?

It is true that Algorand would be stalled, but it would be stalled in a very safe way.

I would add the following: another very useful property of Algorand is fast network partition recovery. After the network partitions recover, Algorand starts almost immediately to process new transactions properly. So if there is a one hour Internet split, there is no need to do anything, Algorand will just stall for one hour and restarts immediately afterwards. Compare that with blockchain favoring availability, where there would be a need to revert all double-spent transactions (which can have catastrophic consequences to the end users).

I’m not completely sure to understand the relation with early backers.

16

Thank you for your explanation.

So do I understand it correctly that because you believe you have only two choices, you decide to go with one of them and block all transactions processing because you do not believe that the situation can happen.

Instead of that I suggest that in the case that this situation occur, and we should solve it by the software update, lets define it and prepare for such scenario… There is also third choice - mix. (In case of real network split, let allow people do doble spending for short time, and allow standard people do real transactions)

I believe it is much worse to halt all transactions for few days then to be prepared and define what happens when there will be war or national firewall issues…

I am doing this for the protocol owners to think little more about these scenarios, and perhaps in one year after they read this will come with some solutions… I want to see algo prosper therefore I am looking to the weak spots, and this is one of them…

Early backers are another weak spot as they own approx 3B algos according to other thread, and it is more then half and someone got brilliant idea to give them full power of how much algo will be redistributed towards them in the future… (hypercaptitalism)

17

No problem, hypercapitalism will solve everything. Namely, there will be private chains, which will not stall, and these will be owned by the hypercapitalists (not the “poor” early backers)… Money is like a living thing, tries to reproduce itself on all levels, flowing around obstacles…

18

In the situation you are considering (full network split where nodes from one region cannot communicate to nodes from another region), unfortunately, double spending for a short time actually means that an adversary controlling nodes in both regions can double spend all their money.

Most likely, malicious people and organizations would immediately do it.
If they use bots monitoring the blockchain, they can do it even if the fork lasts 5s.
But then, when an honest person receives a payment, they can never know if it will be reverted later.
And this may happen to anyone, even if they did not deal directly with a malicious party.

Concretely, suppose user A is malicious and has 1M Algos.
Leveraging the network split between two regions (region 1 and region 2), user A sell their 1M Algos for another cryptocurrency in both regions.
User A can use decentralized or centralized exchanges for example.
In any case, these sold Algos will arrive to another user or exchange B1 in region 1 and B2 in region 2.
B1 and B2 may then use these 1M Algos for many other purposes.
At the end, any user may be receiving some of these double spent Algos, even if they only transact with friends (because their friends might have received these double spent Algos).

Now, network partition stops, what do you do?
There is a need to erase 1M Algos from the system.
Who will lose them?

This is not just theoretical: Ethereum Classic suffered several times from double spent attacks for example. And to avoid losing money, many exchanges now require a huge number of confirmations for Ethereum Classic (see Coinbase requiring 10,000 confirmations - https://help.coinbase.com/en/coinbase/trading-and-funding/sending-or-receiving-cryptocurrency/why-is-my-transaction-pending).
Algorand on the other side wants to provide immediate finality, that is that transactions are confirmed immediately once committed to a block. To get this property, you need to favor consistency over availability.

This is not to say that favoring consistency over availability is always the best choice.
And there are many cases where you may want to favor availability over consistency.
At the end of the day, this is a question of trade-offs and specific use cases.
Example outside of blockchains: if you are a huge online retailer, it is more important that your website is always up. If by mistake this means that your sell unavailable items from time to time for example, then you can just have a recovery mechanism cancelling the order (and potentially offering a discount for the issue).

But if you want to say that a cryptocurrency ensures immediate finality like Algorand (i.e.e, once the transaction is accepted, it can never be reverted, so that users can safely just wait for a single confirmation without taking any risk), then you necessarily need to have the blockchain stall in case of a 50/50 participation.

19

Why dont you consider that preparing for solution when there is case of network stuck eg for 30 minutes, 1 hour, 5 days is something good?

I agree that algo should provide immediate finality, but in very very rare cases under special conditions, when users are informed about it, I believe to network work is much better then the network not to work…

Also consider, that there might be other solutions for the issue… For example lowering required percentage for network to accept the next block block in time. Should I brainstorm how to solve the issue, or we put head to the send when there is an issue with statement that God has thought it through and there is no way to change it?

I am not saying that this is how it should work from tomorrow, and I believe wider discussion is needed, not just between us two…

20

OK, back to network partition… I think that’s why private sidechains would be important.
E.g. Slovakia would have a chain, Hungary another, and they could communicate on the main chain.
But I haven’t heard much about this feature lately, although it was on the agenda of Prof. Micali
more than a year ago. And I think that is really worrying: a project is announced, then… dead
silence. This year’s announcement of 46000 tps is different: here a deadline was also given: by
the end of this year.

Ceterum censeo, I think there should be an AMA with Prof. Micali!