Update 10 November, 2022

A little taster of things to come this week. As you will know, consensus mechanisms are at the core of almost all decentralised networks, including bitcoin. In fact, the chief innovation of bitcoin is arguably the blockchain’s consensus mechanism. But there’s always a tradeoff. In bitcoin and other blockchains it’s the fork-handling mechanism, which means that two versions can exist for a long time (in theory forever) and have to be resolved via PoW, which is bitcoin’s Achilles Heel.

As such, we’ve been keen to avoid consensus algorithms (as they are generally understood) where possible - do ants use them? But there are some occasions where with computer networks they are probably necessary. This is what Mostafa has been looking into, and we’ll dig deeper into that in the coming weeks.

General progress

Right now we’re revamping the CI machine process to be a bit leaner and more secure. This is very much @chriso’s baby and he’s been working to get all the elements in place including the APIs, EC2 instances, serverless functions and DDoS protection. Nearly there now.

We’re working on removing as many read/write locks as possible during data replication. This is mostly @joshuef’s domain. Josh and @bochaco have also pretty much completed the sn_node refactor to reintroduce bidirectional communications into the code. This is something we had before but it got very complex. Simplifying the codebase means we can bring it back. Still testing, but we’re already seeing stability improvements.

@roland is removing the traceroute feature. It causes bloat, it’s not proved useful (and even less so with bi-directional streams), so we’re getting rid.

Consensus mechanisms

There are many consensus mechanisms in computer science. Some are simple binary affairs, others are complex multi-variant mechanisms. The important thing to understand, though, is that they are all just tools for a job, and nothing more. That job is ensuring agreement between entities for a certain amount of time. But just as people need to agree on certain rules to get along, such as which side of the road to drive on, they don’t need to agree on everything to live side by side. Unlike blockchains, people don’t need system-wide ordering, and nor does Safe. So we need to pick the right tool for the job, do so only when necessary, and importantly make sure we are not hemmed in by that choice.

Safe is an asynchronous decentralised network. Things are changing all the time; “state”, meaning a snapshot of the current understanding we have of the world, is almost always different from the point of view of every individual node. And yet for a short time at least, these nodes need to agree.

Consensus is basically a word to say that at some point in time, everyone that matters needs to see the same state in order for an action to happen.

So how do nodes reach agreement about state? Well, that depends on the circumstance, the action and the scope.

Often on Safe, we can reach agreement through anti-entropy (AE). This is a simple exchange of information to make sure we’re talking to the current elders in a section. As such, AE could be seen as a simple, binary, local consensus mechanism, although we just think of it as a check that parties that need to be in sync are all on the same page. Certainly, it’s a far cry from bitcoin’s total system-wide order.

When elders form an agreement about a course of action, we use distributed key generation (DKG) to ensure a supermajority of elders agree. That’s a type of local, binary (yes/no) consensus too, although we don’t tend to use that word.

Then we have conflict-free replicated data types (CRDTs), which we use for mutable data. These have a logical clock, allow for concurrent access and eventually resolve forks to one state. This all happens without any consensus. Forks are fine and self resolving.

But then there are other situations where we can’t tolerate a fork, even for a nanosecond, and that’s where, as an asynchronous decentralised network, we definitely need consensus.

And there are grey areas where we can tolerate forks for a certain time, but eventually need to resolve them. These may need a formal consensus mechanism.

So where might the ants need some technical help? One is recruiting new nodes from a list of perhaps hundreds of candidates, all with a node age of zero - which one do we pick? Here we may need to rely on higher intelligence that the group can provide.

Another is Membership - managing which nodes are in a section. DKG is a blunt instrument and doesn’t handle edge cases like multiple simultaneous joins and leaves very well.

And we may need a higher level of consensus to manage DBCs across sections to prevent double spend.

This is what the team - particularly Mostafa and @davidrusu - are focussed on at the moment: implementing the right protocol in the right place at the right time. More soon folks!


Useful Links

Feel free to reply below with links to translations of this dev update and moderators will add them here:

:russia: Russian ; :germany: German ; :spain: Spanish ; :france: French; :bulgaria: Bulgarian

As an open source project, we’re always looking for feedback, comments and community contributions - so don’t be shy, join in and let’s create the Safe Network together!

45 Likes

First. Thanks @Southside

20 Likes

Second now to read

17 Likes

Wow. Show position! Cheers.

19 Likes

This is really a cool statement about the facts and requirements of the network, and is a key reason why I’ve been jazzed about the philosophical foundation of what @dirvine has been dedicated to doing from the beginning: i.e., form a network that parallels living examples.

The above statement is a great summation of living experience.

20 Likes

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

15 Likes

I’m sick(sth)

Well done everyone - back later

11 Likes

seventh this is just like school “must try harder” :frowning:

great update and I am really ready for the next release !!

12 Likes

Could DKG be implemented as (or using) a CRDT?

12 Likes

It’s being considered as part of a series of internal posts. I thnk we might get there. At least I hope to get membership close to fully crdt, but quite tricky so far. I feel confident, though.

17 Likes

PARSEC is dead, long live PARSEC! :wink:

5 Likes

It has passed, is no more. It’s a dead parrot. There will be much more on agreement/consensus in the coming weeks. All v interesting

12 Likes

Is it possible to find out what is possible and what not, by investigating it with some kind of formal logic, before putting anything into actual code? Has it been logically proven, that changes in SAP can be done without having time as a component of the network?

3 Likes

Let’s logically prove time first :wink:

No seriously, of course you don’t need time. There is a whole universe out there that works well without watches. However, if you could logically prove you need time in a decentralised system, then that would not be simple.

Here is a good video from years back, "Keeping Time in Real Systems" by Kavya Joshi - YouTube

Hope it helps

We actually try to do this with many meetings, papers and write ups. Then we generally create a mock up and test it. Then create a module/crate and test that, then add it to the network.

It helps but really until the whole thing is running and humans using it then we only get a good guess. i.e. we can only tell it is working when we have folk using it.

13 Likes

Sure, in the end, yes.

But has the network improved in this pre-human phase? I don’t have any grasp about that, because the Comnets had us as part. Every now and then we can read from these updates that stability has improved, but we never hear any metrics. I am not suspecting that it wouldn’t had improved, but it would be nice to know what that improvement means in some terms. More splits and sections? Or, more reliable data handling in one section? Both?

The reason I asked for the logic is that is seems that the split-brain problem of AE lead to Membership thing, because it didn’t work in some edge cases. And it seems that every new approach has it’s own edge cases, where it fails. So I was thinking if there is some underlying impossibility, that can be pushed to the edges, but ultimately, it’s still there?

EDIT: I added an important “not” in the “I am not suspecting…”

2 Likes

Yes, continually. We do test some things and pull them out again if they are not good enough (parsec etc.).

That is not an Ae issue, per se’ but Ae helps for sure as does gossip. There is a really long internal post on consensus and what it means. Perhaps we should post that in next week’s update to allow everyone to dive deep, but in real world terms.

Not an impossibility. Much of this is a tension between theoretical possibilities and real world issues. For instance split brain as described in the post could happen as shown, but with a probability approaching zero if the sections do gossip to each other (which they will) frequently.

So possibilities exist everywhere and guarantees nowhere. Sometimes the theory requires guarantees based on assumptions and that is how math and scientific papers work. I am an assumptions guy, more than a math guy.

A large assumption si the network is still there (I mean the Internet) another tends to be nodes can always speak to each other (never see NAT etc. in papers) and many times prior to crypto take off the assumption was running internal nodes (like Amazons Dynamo), since then the byzantine assumption is more prominent.

When you look at a paper and think, wow that’s brilliant but then think deeply about assumptions, it changes the paper. So I am dead keen on analysing assumptions.

Strict order for instance (consensus), is great, but hard to confine without re-ordering the whole planet. It also relies on some unusual assumptions, which the post I mentioned will show.

I know what you are asking for and appreciate that, but this is really hard to say, but innovations don’t act like a normal project. It can be try/fail a lot.

Overall though we are good, membership is an issue we are poking hard as hell at from many angles. However, even with stable membership (we can stabilise membership by running a stable section on our own machines) , we still have bugs in comms or close to that. Killing those will push us to the brink of launch.

18 Likes

Thank you, your reply was exactly on the level I was after.

10 Likes

Great, that is good.

I decided to post an internal doc regarding consensus etc. it is here

I hope it helps get folk thinking deeply :slight_smile: At least, I think some of it will be surprising for many. It’s great to dig in to the guts of things like this. Helps us all.

17 Likes

Thx 4 the update Maidsafe devs

Nice push forward on this week’s update
:exploding_head: by David’s write up, I’ll need decades more to understand it

Keep hacking super ants

12 Likes