Forking SCP

AigarsStaks

Can't we run into a risk of fork as specific events happens just by the nature of network growth? More precisely, if the network grows organically, at certain moments some parts on chain (even large ones) might be connected to the rest just by 2-3 nodes. The consensus slices might not know about general topology so they might reside in the same segments as validating nodes.

If for some reason these "linking" 2-3 nodes would switch on/off in short period of time, several commits might happen that one chain part does not see the other, so each part would do commits on its own. No consensus slice would be broken and each chain would proceed on its own.

If after a while at least one linking node would return the network - fork would be happening.
Are remedies for this to happen?

mazieres

The specifics depend on the configuration of the network, but in most reasonable scenarios what would happen is that when the 2-3 nodes go offline, part of the network loses liveness and cannot see new transactions until the partition heals.

An example is the configuration shown in slide 25 of this talk. If node v7 drops off the network, then the rest of the network will have to wait for v7 to come back before committing any further transactions.

Note that an entirely separate question is what happens if node v7 is malicious. As depicted on the second overlay (where v7 is EVIL, not just FAILED). In that case you lose safety. A more realistic example would be what is shown in slide 21. There, if v5-v8 fail, then v9-v10 will not be able to see more transactions, but v1-v4 can continue to make progress. If v5-v8 are EVIL, not just crashed, then v9-v10 lose safety.

AigarsStaks

Yes, you are hitting the problem. For now we can reduce question just to failed state.
Provided v7 occasionally halts 2-3minutes - how network will know that it has to suspend?
Provided v7 goes down forever - will that just terminate the chain?

jed

No people will just have to update their quorum sets.

mazieres

If v7 is unavailable, there will be no progress, and nodes can determine this because they will be waiting to see a digitally signed message from v7. As Jed says, the ultimate solution is to fix the quorum sets, and ideally the network outages should prompt people to investigate, figure out that v7 is missing, and improve their quorum sets to something more robust (in which v1-3 depend on v4-6).

AigarsStaks

As you can see there are 2 strategies how to behave for nodes v1-3 and v4-6. One is to add more (other) nodes to the quorum slice, the other is to exclude the dead-body.

We cannot insist the size of every quorum slice size because network size N is changing dynamically. How can we enforce that notes v1-6 NOT TO exclude v7 form their quorum slices making 2 isolated quorums and thus forking the chain?

jed

This seems like a very unlikely scenario to me. I mean everyone that wants the network to work will be motivated to make sure they have members from 1-3 and 4-6 in their quorum set. And we assume that most people running a validator(or at least most people we care about that are running a validator) want the network to work. Therefore the validators that we care about will construct a proper quorom set.

If there is some scenario where people from 1-3 really don't want to add people from 4-6 and vice versa then maybe there should be two networks.

AigarsStaks

It might happen that i.e. new geography (does not matter real or virtual) is added to the network. One can build then the v7-type network, as majority of the territory is not aware/do not case of the network topology. Then they can issue an 1,000,000 USD sales offer to the network. Then they can down v7 and wait while parties adapts their quorum slices. Then they accept 1,000,000 offer in both isolated networks and brings v7 up, asking to be added so some nodes.
This is just quick thought scenario but might have devastating effect on all those who relay on Stellar.

AigarsStaks

Seems like quorum slices work best in balanced network, but might be risky in arbitrary DAO environment.
One solution might be to introduce Level-2 nodes, which would form backbone of the Stellar network. New nodes needs to be added on the following requirements: 1) 99.995% availability is granted; 2)all existing Level-2 nodes agrees 3) simple majority vote by Level-2 nodes for excluding a member.
Then each quorum slice would be required to add 1 or more Level-2 nodes as a must requirement. If slice holds no Level-2 node it cannot validate transactions.
Parties who would care about network would be happy to introduce Level-2 nodes, as it would grant them security, balance the network and eliminate risk of wrong intentions.

mazieres

The general strategy you are saying about tiered nodes makes sense. However, one of the major advantages of SCP over previous Byzantine agreement protocols is that you don't need all existing Level-2 nodes to agree. Thus, where previous Byzantine agreement protocols actually have to run the reconfiguration itself through Byzantine agreement, SCP allows nodes unilaterally to configure their quorum slices. Moreover, for a given set of quorum slice choices, it provides optimal safety--meaning the only circumstances in which SCP could be unsafe are those in which no other protocol could have guaranteed safety.

In general, providing this choice makes a lot of sense because of Stellar's anchor model. In particular, people should configure slices based at least in part on depository trust. At the end of the day, if I'm going to take a bunch of Stellar USD and redeem them for bank notes at Bank of America, I should make sure that BofA is in my quorum slices.

In response to your previous point about new geography, in generally people will join a network to enjoy the network affects. So if region A has a strong Stellar network and region B wants to join, region A probably will not initially place all that much trust/dependence in region B, while region B will want to ensure region A signs off on all settled transactions. That's of course different from region B trusting region A for safety (which they should not do), but it does mean depending on region A for liveness.

A rough analogy would be deploying the internet. If region A has a strong internet and region B wants to join the internet, well, region B doesn't technically have to connect to region A, but most people will still agree that region A has the real internet and that region B isn't really internet-connected when it's hosts cannot hear from region A.

AigarsStaks

In Bitcoin after some period this setup would end in voided transactions, which is different.

We are one's who will depend on the Stellar ledger. Actually we will be down even if there will be theoretical model that someone can fork the network or get it down. We cannot afford manual resolutions to liveliness. We cannot afford models which can split the existing DB.

Internet analogy is very good. If we consider Stellar-net as analogue to the Internet then consensus slice would be a routing table. If failure in routing may result in lost connectivity then failure of consensus slice might result in lost integrity. So in the early days Internet made its DNS back-bone of I guess of 8-10 nodes, which were connected N:M to make warranties that it will not go down at any scenario.

Lapin0t

I'm not going to start a new topic since my question is strongly related (moderators: please split this topic if you feel like it's better).

I am going to assume organically grown from the OP is some kind of small-world or scale-free social graph. Is quorum intersection something easy/common to achieve in such real-world networks? My intuition would say yes because such topologies have some hubs (nodes with high inbound degree) that will be in most quorums, but has there been some statistical tests (yeah, generating real-world like random graphs is hard) or actual tests on real networks?

Practically to test that, we could generate a directed graph with relatively high outbound degree, say the quorum slice are every x% of that neighbors and test for quorum intersection. This only tests for some kind of stellar configuration (flat, percent-based quorum-slice), but it may be already interesting.

AigarsStaks

It is not that I want to shake the product I am building my application on. Why can't we just patch Stellar while it is in its infancy? Absolute robustness is something, which is A MUST, and lack of it will just kill the platform.

it's all about robustness of the system.
If we think of likeliness of wrong doing, then yes, it is very unlikely that sane people would destroy their own effort.

If we consider angriness or greed of particular individuals, then yes, they may spend enough time to build v7-exploit to gain power or popularity.

mazieres

In response to @Lapin0t, organically grown means more like the internet, so a small number of tier-one backbone providers, a larger number of transit ASes, and then a much, much larger number of stub networks. The stub network in our case would be a customer of a single bank, using that bank's app, and not even necessarily knowing that his/her payments are going over Stellar. Also like the Internet, there may not be 100% agreement on who is a tier-one ISP, but there is sufficient agreement to ensure widespread overlap. The Internet periodically sees events like Level 3 vs. cogent, where one ISP challenges another ISP's tier-one status. The Stellar equivalent would probably be less disruptive--for instance US banks might be prevented from including Cuban banks in their quorum slices, but as long as there is sufficient overlap in people's transitive notions of tier-one validators, there is no problem.

For @AigarsStaks, lost connectivity is not the same thing as lost integrity. Safety and liveness are at cross purposes in a consensus algorithm. The bigger the quorums, the greater the safety and the easier it is to disrupt liveness. Conversely, smaller quorums increase liveness but require fewer bad nodes to undermine safety. What you are asking to patch sounds more like a configuration issue, not an issue with the underlying protocol. We formally analyzed the underlying consensus protocol (SCP) and showed that it has optimal safety and resistance to stuck states, meaning no other protocol can do better on these fronts. Fortunately the configuration does not need to be patched in its infancy, but can be updated at any time. Even more fortunately, if you don't like other nodes' configurations, you can unilaterally run your own validator and give it very large quorum slices, which will give you more safety (but correspondingly less liveness) than most other participants.

AigarsStaks

My problem is that within Stellar app people might transact huge amounts, perhaps, $100,000 in single transaction.

In this range, a fraudulent party may consider economically viable to buy good-Stellar-network company running a node with some number of consensus slices. Let's call it "victim". They may create another node, lets call it "holder", which preferably is in victim's slices and some more nodes around.
Now the fraudulent party switch off the "victim", an make sure the "holder" never exclude the victim from his consensus slices. How long will it take reach every other network node to manually exclude victim from their slices? What if they are in other time zones? How much time will it take to find that "holder" is designed to keep network down, so it wil never exclude the "victim"..

It also seems economically reasonable for them to build some 10-20 nodes and keep v-7 exploit secret for some prolonged period of time. At one point of time they can create i.e.some number of offers for an assets and split the network immediately. After they just sit and wait until other notes exclude v7 from their quorum slices, so their offer can execute independently in all sub-segments which are isolated now. If system is bound to back-end financial system out-side of the boundaries of Stellar network (and it is case with our app) real money may be transferred several times for the same asset.

How to protect ourselves from those scenarios?

AigarsStaks

The solution we discussed with @Kalvis, would be to allow for dynamic assignation of Horizon nodes - to ensure liveliness. There should exist set of certified Lavel2 nodes to ensue security. And there must be some off-protocol Recommendations (like ones of WWW consortium) of how to implement new node and new apps to exclude v7 exploit at any scenario.