Update 18 November, 2021

So this week we hand over to Gab
As you know he’s not one to brag
But he’s quietly fixed a messaging snag
By storing SectionChains in a DAG
OK, it’s not a Lambo or even a Jag
But for network ops it’s really fab
Give it a look if that’s your bag

General progress

@danda has created UML diagrams for all the Safe Network crates, making it easy to see how they all fit together. For non-tech folk the ability to look through the names of the code blocks and how they link gives an insight into the working of the network. Similar to seeing all the cogs in a watch, you may not understand all the details of the pitch and the number of teeth, but it can be good to see the cogs behind the bezel to get a better understanding of its workings. You can see bare, compact, and full versions of each crate, in increasing levels of detail, with green blocks representing traits, blue structs, and yellow enums. The site is best viewed in Chrome.

A ‘bare’ SVG representation of the sn_dbc crate

Meanwhile @qi_ma and @lionel.faber are turning their attention to implementing the Anti-Entropy pattern to the process of distributed key generation.

OK over to Gabriel (@bochaco).

Handling Network Knowledge

Network knowledge describes the processes by which Elders keep track of the topology of the network. Because Safe is asynchronous and always changing, this is done on a need-to-know basis, whereby when a node contacts another node they first get their knowledge in sync by exchanging Anti-Entropy (AE) messages.

In order to reduce messaging, we now have a DAG to keep track of all SectionChains and a PrefixMap to store current section SAPs. The following explains how that affects AE and SAP verification when an initial message is rejected.

SectionChain

A SectionChain is one of the most important tools available to a node, as it enables it to check if a piece of data or a message is valid (has network authority).

A SectionChain is a linked list of section keys, where the key of each block in the chain is signed by the key of the previous block, all the way back to the genesis key.

Each block in the chain contains the section key that the Elders were - at that particular moment - using to sign all agreement procedures. Every time the Elders change (churn), a new section key is generated and a new block is added to the SectionChain.

How is it used to verify messages and data? Well, any piece of content or information signed by a section key can be verified by looking at the SectionChain. If the key is found there, it means that piece of content/information was signed by the section in the past and therefore it has network authority.

Anti-Entropy Retry and Redirect

The network uses a set of Anti-Entropy (AE) messages for nodes to sync themselves up about the topology of the network and section they belong to. Every message sent to a node or another section must include the destination’s current section key for the message to be accepted by the recipient. If this is not the case, the recipient will reject the message, returning it to the sender within an AE-Retry message. The AE-Retry message contains up-to-date information about its section, i.e. the current Section Authority Provider (SAP), which lists the current section Elders, and the current section key (see the AE chapter in the Primer).

A similar flow of events is triggered when a message is sent to an incorrect section, which can be caused by the sender lacking the latest information about the topology of the network. The recipient will also reject the message sending it back to the sender within an AE-Redirect message. In this case the AE-Redirect message contains the SAP of the section where the message should be resent to.

When the sender receives a new SAP through an AE-Retry or AE-Redirect message, it first needs to verify it is a valid and trusted SAP, i.e. verify the SAP corresponds to the network the sender trusts.

In order to do so, the node needs to check that the section key found in the received SAP is cryptographically verifiable with the SectionChain all the way to the genesis key, otherwise a malicious node could be redirecting it to a different (non-Safe) network or to malicious peers or sections. This is why each Anti-Entropy message also carries a ProofChain so the original sender can verify and trust the new SAP.

A ProofChain is the most recent few blocks of the SectionChain - we don’t need to send the full SectionChain if we were recently in contact with another section, just the delta.

What’s changed?

Up until now, each node would keep a copy of its own SectionChain and SAP. This was used to validate any incoming message or new SAP received in AE messages, and also to build a ProofChain when sending AE messages to other peers.

Which was fine for sections we know, but for distant, unknown sections it created a fair bit of extra work.

Let’s say we send a message and it gets returned saying we need to redirect it to a section we have not contacted before, and including that unknown section’s SAP. We know the section by its XOR address prefix, but we don’t know anything else about it, or it us. We have not seen its SAP before and we don’t have a ProofChain. So before we can resend the message to the new section we need to send additional messages to exchange SectionChains, which is complex and prone to error.

This is why we’ve been recently working on having all nodes keep track of all other sections’ SectionChains. This allows each node to provide a ProofChain to peers not only when updating them with their own section’s SAP, but also when an AE-Redirect message tells them to do so for a remote section.

This removes some AE traffic and complexity, and also allows nodes to ensure they are only interacting with peers they trust to belong to the same network, by cryptographically verifying any section key they receive all the way to the genesis key.

But how can we store this information securely and efficiently, so that nodes can access it when they need to and so that it is updated on splits and churn?

We have now implemented a DAG (directed acyclic graph) to keep track of all the SectionChains and a PrefixMap (a register mapping a section’s prefix to its SAP) to store all sections’ current SAPs.

The DAG

The network starts with a genesis key, which is the very first block in the genesis section’s SectionChain, and the very first node’s key is signed by the genesis key to create the second block in this SectionChain. As nodes start joining this very first section, i.e. the genesis section, the SectionChain keeps growing.

At some point, when the genesis section has grown in size with enough members to split into two separate sections, the two sets of peers that will become Elders will agree on which will become their own section key (through the DKG process). Once they’ve all finished agreeing on the two new section keys, the current set of Elders will come to an agreement to split the section, signing the two new section keys with current section key, and creating two branches in the genesis section’s SectionChain.

This process is repeated in each of the two new branches, independently of one another. They split into more sections, creating more branches in their respective SectionChains. This naturally forms a DAG, each of the vertices containing a section key and the signature made with the preceding vertex’s section key.

Given any section key, its ProofChain can be built from the DAG by collecting all the vertices (section keys and signatures) which are in the path from the genesis key to that section key. Note that since the sections never merge but only split, there is always a unique path from the genesis key to any other section key in the DAG, in other words, there’s a unique proof chain from genesis key for any given section key.

This development is detailed in this PR.


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!

63 Likes

First! The Wheel of Time turns, and Ages come and pass, leaving memories that become legend. Legend fades to myth, and even myth is long forgotten when the Age that gave it birth comes again. … There are neither beginnings nor endings to the Wheel of Time. But it was a beginning. Go, Go Team MaidSafe!


Privacy. Security. Freedom

28 Likes

second! now read

14 Likes

THirrd I actually read some of this - thankfully its not all poetry.

There was one poet from Ayrshire. Thats plenty.

10 Likes

You have been at that potato juice again, haven’t you?

17 Likes

Thanks so much to the entire Maidsafe team for all of your hard work! The world needs the SAFE Network now more than ever. :racehorse:

16 Likes

Sixth I’m losing my touch :frowning:

11 Likes

Thanks for sharing :+1:

8 Likes

Nah, you just wore the writing off your F5 key and were missing the refresh…
Now shoosh, Im trying to read.

3 Likes

Nowhere near first!

Shift to DAG is very interesting and sounds cool but after one read I’m nowhere near understanding except at the basic level of: reduces messaging, so I better read again :relaxed: but I have one question which is why does this result in a DAG rather than a tree? A diagram might make this obvious, but just reading it sounds like each split should create a tree like structure, but obviously I’m not understanding the structure.

Anyway, sounds like a really important step, thank you @bochaco and team. :clap:

PS UML diagrams from @danda very useful. Almost tempting me back to code!

18 Likes

Excellent! Been quietly waiting for this to come about at some point!!

@bochaco :muscle::beers::partying_face:

The poetry is pretty ace too! :grinning_face_with_smiling_eyes:

16 Likes

Nice early update.

:thinking: apt install gPlanarity

:beer:

9 Likes

Parsec was a DAG right? So is it back?:smirk:

Doesn’t a DAG give problems with centralization?

5 Likes

What is required to get a video of someone from (or the entire) Maidsafe team performing this set to music? At least two of you play guitar (you know who you are :smirk:)…

18 Likes

When there is churn some Elder/s of a section could be changed/replaced by other/s, so a new set of Elders become the new Section Authority Providers without splitting, i.e. same prefix as previous set of Elders in that same section. This new SAP has a new section key which is added to the DAG.

16 Likes

A DAG is a form of a tree basically. In time it will be pruned meaning many genesis type nodes. For us the whole DAG i.e. every section can be stored on the Safe network as chunks. So centralised in a decentralised data store :smiley: Rather than each node having to store this and give to others they can take snapshots they are happy with etc. So leaves in the tree they trust (or have checked).

i.e. seems like a huge data structure but it’s quite small and also able to be pruned easily.

Kinda was, well PARSEC used a DAG but stored everything on that DAG. That proposition was a fully ordered everything and here it’s a tree of secure linked lists so limits the size and makes it self referential. That list gives us secure keys and data signed by one of these keys is valid data. It’s quite nice and more CRDT or partial order than total order (it has resolvable forks)

27 Likes

Can we have a reggae version?

9 Likes

Here you go

So this week we hand over to Gab and ting
As you know he’s not one to brag in a Babylon
But he’s quietly fixed a messaging snag sensimilla
By storing SectionChains in a DAG irie
OK, it’s not a Lambo or even a Jag, Jah
But for network ops it’s really fab Rastafari
Give it a look if that’s your bag, rewind

15 Likes

Slain :joy::rofl::rofl:

7 Likes