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:
Russian ; 
German ; 
Spanish ; 
French; 
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!
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.
apt install gPlanarity
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).
