Update 24 November, 2022

Continuing with our progress in adapting decentralised networking consensus protocols for our purposes, in this case handling section membership, this week Mostafa takes us through ABBA and MVBA. ABBA is a coin-flipping protocol for binary agreement. If a section needs another adult the elders can choose a single node to prevent mass joining, while MVBA is used to decide between competing proposals, such as which nodes should be elders in the next iteration of the section.

General progress

@roland has been hard at work on a new TestNetwork utility will to facilitate setting up the environment for node tests. We can tell the builder to generate a network with a specific SAP in a prefix and it will create a functional and configurable network with all the gaps filled in. @oetyng is now re-factoring to enable some end-to-end tests that had been disabled after the bidirectional stream work, which had been stuck for a while.

@chriso has refreshed our AWS setup and we’re now just checking how best to leverage this during PRs (to get more speed and reliability for certain tests).

@joshuef and @roland continue to reduce the number of write locks we take on the node state. These are messages to sent between elders and clients contacting them to make sure the client has up-to-date information about the section before it tries to make a request. These write locks are another place where we can block code execution and slow a node down. They’re also an unnecessary complication and a potential source of bugs. We now only take a lock on AE messages that actually update us (previously it was all AE messages). We also no longer lock during data replication or dysfunction tracking. So we’re much closer to a lean/sane Node state, which only needs write access for a small subset of tasks network-knowledge related tasks

In addition to this work, @bochaco is also working on AE messaging and removing redundant logic in client AE handling.

ABBA and MVBA

ABBA protocol

ABBA or Asynchronous Binary Byzantine Agreement is a way to solve the consensus problem in asynchronous networks. In particular, ABBA can be used for deciding a yes/no question as a group.

In this protocol, each party starts by broadcasting their preference (yes/no). If there is no majority for the initialized values, the parties start a threshold coin-tossing scheme which will produce a random result that all can agree to. ABBA is a non-deterministic protocol, its output is a random number. If we replay the input events we might get different output.

The consistency is ensured by VCBC. As covered last week, VCBC is a broadcast protocol that tries to disseminate a message from a node to the network, with all nodes agreeing on the message the node sent. VCBC protocol can be modified in order to only accept the valid and correct proposals.

We use VCBC to make sure the messages broadcast by nodes are valid. VCBC is simply a validation check. So if an elder broadcasts a proposal that anther node should be admitted into the section, the other nodes can assure themselves that the elder is not corrupt or faulty and the proposal should be taken seriously.

After that we can use rounds of ABBA to come to agreement through a threshold signature scheme which continues until the majority of the elders reach a consensus. ABBA will always terminate. It will always produce a random binary value which is used to make the decision. If we have enough votes we can commit to the proposal.

The order of elders matters. Imagine elders are ordered like this: [3,5,7,2,1]
and 3 is offline. After VCBC, we have proposals [-,P5,P7,P2,P1] The first proposal is P5. We run ABBA for P5. We know P5 is valid and all the elders have it (consistently broadcast), therefore it should be decided after a while.

The weaker validity notion

We are taking these vanilla algorithms and altering them for our purposes. Since VCBC has already validated the messages for us, we can simply require that an honest party may only decide on a value for which it has the accompanying validating data. Otherwise it gets rejected.

This allows us to make the ABBA protocol become simpler.

MVBA protocol

The Multi Values Byzantine Agreement protocol (MVBA) is used when there is more than one proposal for reaching consensus.

We can use it when multiple elders leave or multiple adults become eligible for promotion at the same time, so there a number of possible versions of the next iteration of the section.

In this scenario, each party consistently broadcast its proposals via VCBC and after receiving enough proposals from honest parties (valid) the protocol starts running a binary agreement (using ABBA) per proposal. When the first proposal gets decided the process terminates.

Membership problem

So what is all this trying to solve? It’s about promotion and demotion of elders. This process needs to happen with the agreement of a supermajority of the honest elders, and we want to avoid total order as this is very compute-intensive and not the way nature does things. We also need to handle high levels of concurrency (multiple concurrent joiners/leavers) without having to wait on order, and being able to handle or disallow forks.

Our approach is to tackle this problem using the MVBA protocol. In this scenario, each elder proposes a list of view of the elders that will be in charge of the section after the change and broadcasts it to the other elders. This continues until the majority of the elders receive sufficient proposals from the other parties. After that the proposals are voted on using the ABBA protocol so that one final list of elders is chosen at random from those proposed.

We are deeply looking at this area, as you know, and there are trade-offs and choices to be made. One improvement we can make is to use validatable proposals. Membership allows us to do that thereby decreasing the time to an agreement. Another area is concurrency. Whereas strict order does not allow concurrency there are options, these are complex options to consider, but likely much less code again. In any case, it is good to have options, but tailoring these options to the specific case of membership gives us many choices and we can then consider the trade-offs with more certainty in this use case.

56 Likes

First! … :love:


Privacy. Security. Freedom

17 Likes

Second? … …

14 Likes

Third is best put your network to the test

14 Likes

4th.
Improved test network utility perfect step for real network.
Thank you for update

13 Likes

Official testnet before Christmas?

10 Likes

Yeah, I wonder about these advances in handling membership and elders… They seem necessary for the network in the wild, but are the current ways of handling them able to handle the situations in more or less benevolent surroundings, like testnets by our community?

4 Likes

Actually I think I asked this question last year, or maybe the year before :joy::joy:

3 Likes

That the E2E tests are getting ready again is a promising insight, normally means full system test. :clap:

16 Likes

Bit of acronym soup but some tasty tidbits! Clearly this approach is more suitable than parsec’s total order approach but curious how the team feels about these protocols so far? Is there quite a bit of confidence settling on these?

Membership seems like one of, if not the last big hurdle to a minimum viable network, given the economic work is mostly done and just needs plugging in.

All sounds pretty promising and I hope results exceed expectations.

Thanks for the update as usual. Go @maidsafe!

11 Likes

Thanks so much to the entire Maidsafe team for all of your hard work! :racehorse:

9 Likes

There is a small group working on it. The algorithms themselves we are confident about, but there is a very interesting debate on just how much order we need compared with concurrency. It’s a trade off. We also have taken these algorithms and put them into code and tested them (not complete yet, but not a worry). What we are doing is looking at our specific use case of membership as opposed to some order the world utopia.

This last part is where I am really interested. It about agreeing on order but just how strict we need to be given we have validatable proposals to vote on (we can tell they are true or not). Unlike parsec (a general purpose ordering of anything) we are really focussed on specifics.

Then we have Ae and how we can allow loose order that comes back into sync with messages happening naturally.

A lot happening, but so much focus on a specific algorithm here.

An interesting adjunct here is we need some form of order for membership and that always means more work. However that means we don’t need order on Dbc transfers and these can be totally concurrent. Same with uploading data that is signed.

So we will have a degree of order on membership, but that means we can run the network ops concurrently with confidence.

Its ll very interesting stuff.

I would say so, in fact now I would say we are able to really push these algorithms into our specific use case and therefor get the best out of them.

20 Likes

Wouldn’t expect less from the team in regards to SN’s optimal operation. That’s why we’re all still here today. That and the transparency :slightly_smiling_face:
This is interesting indeed.

Now I’m curious about this debate on how much order is needed. What really is sacrificed by providing less order? Less assurances in terms of data reliability, restarts, etc? Or more a security concern?

More order of course sounds like having more work with stricter bounds but more concurrency for clients? Whereas clients doing as much as possible means less total order necessary for elders, which is faster and smoother operation of SN in an asynchronous world.

Seems like it’s all about balance and the team is in a really good place nailing this down. Thanks

11 Likes

It comes down to this.

Without strict order we can have forks. So:

A fork in elder groups could lead to split groups and then folk can try and doubespend etc.

The arguments are

  1. Can we prevent forks in membership == Yes by using strict order of members
  2. Can we just accept forks and leave them or can we resolve them without harm

2 Is where I am debating right now. I see Avalanche does that (from a video posted here the other day). I also feel with our network and how membership works (post coming soon, but we are still debating internal about it all) we have the ability to resolve forks for sure via Ae and merging member sets frequently.

So it comes down to basically

  1. Slow down and linearise membership (total order) to make sure the elders are always correct.
  2. Allow concurrent handling of member churn in a way that it is eventually consistent.

(I am on the side of 2 here, but with no concrete argument yet).

Problems are

  1. This Means if the network churns faster than we can decide on linear order then it dies.

  2. This Means if there is a fork that allows both sides of the fork to decide (approve), then we are in trouble.

What I want is concurrent membership handling with a very high level of assurance that we can handle forks for a small period. (i.e. we see a fork and recognise it as a conflict set, disallowing any decisions on either side).

And on the debate goes, it’s really deep stuff in many ways, but if you look continually at the real world, it’s not so hard.

EDIT

I should add folk talk about total order verses eventual consistency. But this is a false flag.

Strict order is eventual and in many cases much slower than eventual consistency.

i.e. Everything is eventual. However if the world underneath your consensus algorithm changes faster than you can linearise it, then you have eventual consistency for sure and also possibly lost the network.

i.e. Nothing reported or read can be said to be still correct, it just means it was correct at some point, but who knows. i.e. you get an account balance and a nanosend later a bill comes out. You got total order there, but a false balance (eventually) :slight_smile:

11 Likes

ABBA (protocol not the band) is supposed to help prevent these forks from happening with the coin flip, correct? A lot to absorb here but you breaking it down is helping immensely.

I’m going to reread the last few updates a couples times to get consistent, eventually. Once things settle I’m sure John updating the Primer (so very digestible) will help, as the reader can see the bigger picture.

8 Likes

Yes abba is great for forcing an answer true or false and in a way that a binary vote terminates and moves on. The coin flip actually breaks the loop where there are, say 4 YES and 4 NO votes. For us that is OK but our votes need to be things like, is the node lost, should we add this other node and so on. So these are binary in a way but not based on just agreeing, but agreeing on a provable fact. So we are broadcasting the truth if that makes sense.

So these wee bits of info are where binary agreement is not totally aligned with provable things we re voting on.

Yea, I know what you mean, lots of data in the last few weeks, but it’s great we all get to see and understand it.

Great community

11 Likes

Why don’t you just stop the world for a moment? Of course world = network.

4 Likes

This makes sense and clarifies the applications of the protocol, thanks.

4 Likes

Not all of us :woozy_face::joy:

3 Likes