Deep-dive into the Web of Trust

This article will explore some of the different parameters implemented by the Duniter Web of Trust -WoT- and how some of their values were chosen for their application in the Ğ1 currency.

No prior knowledge of the topic is required as I will shed light on all specific terms and ideas I will cover. This being said, we will however go into depth on the duniter protocol -limiting ourselves to its WoT of course- as well as a bit of graph theory. It is my view that such detail is mandatory for a good understanding of the WoT. To make it easier on you, we’ll gradually go into detail, starting with a broader view.

Prerequisites

Before reading this article we recommend getting familiar with the Ğ1 license and with the Relative Theory of Money

Why do we need a Web of Trust?

There are two reasons we need it :

1. To make sure that only one Universal Dividend is produced per member at each specified creation interval -in the Ğ1’s case this interval is set as daily 86 400 seconds-, it is the monetary parameter known as dt-.
2. To identify the nodes hashing the blocks and assign them each a personalised difficulty. This custom difficulty proof of work is there to avoid the blockchain’s validation mechanism becoming too centralised as is the case with many 'non-libre’ cryptocurrencies.

Wait, what’s a ‘monetary parameter’ ?

Every currency implementing Duniter has its own blockchain whose behaviour is dictated by a set of ‘parameters’ -defined in block zero, the so-called genesis block- that can be tweaked to achieve the desired results. At the time of writing this article, the Duniter protocol -aka DUP- has a total of 21 parameters of which 10 are for the WoT alone. We’ll focus on these 10.

Suffice to say that in the Ğ1’s case, the DU is created every 24 hours -86 400 seconds- but this interval -set through the time derivative dt parameter- can have a different value in an other implementation of the protocol.

I won’t write about the second parameter having to do with the proof of work, it’s outside our scope here, just know that the Web of Trust allows us to identify the members providing hashing power, which we couldn’t do without it. This crucial feature means we can impose a rotation between the members hashing the blocks so that no single rich individual or group invests in a giant ‘hash farm’ and takes a hold of the blockchain, paralysing the community!

Let’s go back to the first objective: to make sure that each member can only have one account. As we all know, achieving zero-risk isn’t possible, our goal is therefore not to create a WoT within which fraud would be absolutely impossible but instead to discourage it. Here is a rewording of our goal in 4 smaller ones :

1. To make the certification process lengthy enough that all members exercise due diligence and are wary of risks.
2. To make fraudulent acts as hard as we can to the extent that they become pointless.
3. To ensure that any Sybil attacks have a negligible impact on the currency -by ensuring that illegitimate double Universal Dividends have no significant bearing on the legitimate monetary mass-
4. To slow the growth of ‘Sybil regions’ to give enough time for the community to react and isolate the threat.

Wait, a Sybil what ?

A Sybil attack, is the name given to attacks perpetrated on a reputation system through the creation of fake identities. A Web of Trust is a specific instance of a Reputation System.

There are plenty of Sybil attack scenarios we can think of and just as many reasons why their perpetrators would want to carry them out. Our objective is that the configuration of the WoT protects both users and its IT backbone infrastructure against these attacks.

This means that micro-attacks performed by small groups of individuals looking for personal enrichment are of no interest to us. The web’s role isn’t to deter these attacks, this being instead the role of the community. Just like the town you live in is responsible for providing your tap water and electricity but isn’t responsible for any burglaries etc. Much in the same way, Duniter’s WoT guarantees us all a functional currency and that’s quite a feat in itself!

The importance of having our own certification system

We are regularly offered to switch over to third-party or state-owned authentication systems but these are centralised and go against the principles of our community. We feel that we would lose our independence and universality by adopting a state-controlled system. People without an official state-provided identity or homeless people would also run the risk of being excluded from the WoT. It is of the utmost importance that we remain free from any state or corporation. To this day we depend only on the Internet and yet, were it to fail, there are already alternatives being tested around the world for a decentralised network.

A few foundational concepts on graph theory

A bit of vocabulary

• Graph: set of points -called ‘vertices’- joined by edges -called paths/walks-.

• Simple graph: a graph with no loops and with no multiple edges. That is, each edge connects two distinct endpoints and no two edges have the same endpoints. A simple edge is an edge that is not part of a multiple adjacency -of edges-. In many cases, graphs are assumed to be simple unless specified otherwise. Wikipedia

• Directed graph: a graph in which the edges have a distinguished direction, from one vertex to another. A directed edge can also be called a path or walk. Wikipedia Arrow A –> B is therefore different from arrow B –> A.

• Endpoints: the edge with vertex A –> B has A and B as endpoints, respectively as start and end of the path/walk.

• Isolated vertex: a vertex whose degree is zero, that is, a vertex with no incident edges. Wikipedia

• Degree of a vertex: number of its incident edges -in and out-.

• Out-degree of vertex A: number of outbound edges / tail ends from A.

• In-degree of vertex A: number of incoming edges / head ends to A.

• Path: -aka “walk”- path to follow to get from vertex A to vertex B.

Definition of the Duniter Web of Trust

The Duniter WoTs -one per currency- are simple directed graphs without isolated vertices. The vertices are the members and the edges are the certifications given and received.

Directed, what does that mean?

The responsibility of issuing a certification is unique and personal to the certifier. The trust he/she places in the receiver cannot be imposed in the other direction although in most circumstances both parties equally trust each other.

In addition, all vertices are either currently active members or past-members. Past-member vertices are in a specific ‘deactivated state’ and can no longer issue or receive certifications although the ones already issued or received to/from other members are still considered ‘pending’ to avoid the web collapsing like a house of cards.

If these old members don’t come back into the web, their pending certifications will eventually expire and they will switch from ‘deactivated’ to ‘isolated’ vertices.

To wrap up with old members, after a certain period of time -set in the currency’s parameters - their deactivated vertex is removed from the web and the associated identity is ‘revoked’. The person who owned the account can no longer use this identity but is free to join the web with another one. :-)

What do you mean by ‘identity’?

An identity is a set of three pieces of information: a public key, a name and a blockstamp. A blockstamp points to a specific block in the chain. Its main use is to freeze the point in time at which an identity was created and to link this identity to a specific chain and of course, a currency -each currency having its own blockchain-.

An identity can be in any one of 5 different status: pending, member, old member, revoked or excluded.

Let’s take a simple example:

A -> B -> C
     |
     \--> D

If, for whatever reason, A were to lose its member status, the web would crumble and all other members would be excluded as a consequence. To avoid this, the certification from A –> B will remain valid until its expiry date, leaving enough time for B to receive certifications from C or D.

Because our WoT doesn’t have any isolated vertices, each new identity created needs to be pulled into the web with all of the certifications it has received -in the same block-. This calls for a temporary ‘buffer’ storage space for pending identities and the certifications they’ve received. This storage space is called ‘the pool’ -of Duniter nodes- which we could also have called the ‘sandbox’ as that’s the name used in Duniter’s code. I might add that these ‘pools’ also include other documents and metadata not mentioned here.

Exploring the rules behind a Duniter Web of Trust

The Duniter WoTs -one per currency- work with a set of eight fundamental rules, themselves enforced through eleven different parameters. Ten of these parameters are set within the genesis block, the eleventh one - msPeriod- having being hard-coded in the Ğ1’s code subsequently.

1.Distance rule and referent members (stepMax and xPercent)

These two parameters are closely linked and together define the ‘distance rule’. The ‘distance rule’ can only be described after defining what a ‘referent member’ is:

Referent member: member A is said to be ‘referent’ if and only if the total of his/her degrees are greater than or equal to CEIl-N^-1/stepMax-- where N is the total number of members.** As the size of the web will grow this number will grow too, meaning it will take more certification issuances to become a referent member as the number of certifications needed to become a member shouldn’t change.

Let’s now define the distance rule:

Distance rule: member A is said to observe this rule if and only if for a subset xPercent% of referent members R there exists a path of length less than or equal to stepMax between R and A.**

Referent members only exist so that the distance rule can take effect, they have no special privileges over non-referent members. In a perfect web, that is one in which each member has certified all members he/she legitimately can, all members would be referent members. However, because the web progressively grows in size and because members die and are replaced by new ones, there are always members at any given time t who haven’t yet certified all members they legitimately could. These members would hinder the evolution of the web if they were taken into account in the calculation of the distance rule and the web would effectively stop growing. -You can see what would happen if the notion of ‘referent member’ didn’t exist by going to the ‘gaussianWotQuality’ page on currency-monit and activating ‘if the concept of referent members didn’t exist’-.

When is the distance rule applied?

Because verifying the application of the distance rule is calculation-greedy, it is only performed when a new identity gets confirmed into the web or an existing member gets renewed. Exception to the rule: the distance rule is not observed in the genesis block -when the web is first implemented-.

2. Rule of the minimum number of certifications needed (sigQty)

This is the simplest rule, it essentially says that each member must at any given time -meaning in any single block- have received at least sigQty active certifications. If, for whatever reason, member A were to have less than sigQty active certifications in a given block, he/she would cease being a member and be required to publish a request for identity renewal.

3. The membership renewal rule (msValidity, msPeriod and msWindow)

Bear in mind that a membership doesn’t last a lifetime but instead has a lifespan set to msValidity seconds.

Every single member -or old member who hasn’t revoked his identity or been excluded- can request a membership renewal so long as the last request was made more than msPeriod seconds ago -if a member has never requested a renewal, the date of last renewal is equal to the timestamp at which his membership was first created. A new request will be stored in the ‘pool’ for a maximum of msWindow seconds before it’s included in the blockchain. Once again, this can only happen once/if the member meets both the siqQty rule and the distance rule -if these criterion are already matched it’s just a case of waiting for a new block to be mined-.

If a member hasn’t requested a renewal for longer than msValidity seconds, he/she automatically ceases being a member. From this moment on, the ex-member has another msValidity window to renew his/her membership. When this period of 2 × msValidity runs out, the membership will expire and this identity will never be available for use again in the web. If the person so desires, he/she will have to start from zero to regain access to the WoT.

4. Rule of certification lifespan (sigValidity)

All certifications included in the blockchain expire sigValidity seconds after they were issued.

5. Rule of limited supply of active certifications (sigStock)

By ‘active certifications’ we refer to certifications included in the blockchain and that haven’t yet expired.

The total of active certifications issued by any member at any single time must be less than or equal to sigStock. When this threshold is reached the member will have to wait for one of his active certifications to expire before he/she can issue a new one.

6. Rule of the time period between two certification issuances. (sigPeriod)

As soon as a certification issued by member A gets included in the blockchain, he/she will be unable to issue a new one before another sigPeriod seconds.

7. Expiry of a certification issuance (sigWindow)

When a certification is issued by member A, it will be stored in the ‘pool’ for a maximum of sigWindow seconds. If the certification hasn’t been included in the blockchain by then, it will be cancelled and the member’s sigStock will be repleted by one.

8. Lifespan of a ‘pending’ active certification (idtyWindow)

When a new identity is created, it is stored in the ‘pool’ for a maximum of idtyWindow seconds. If the person hasn’t achieved member status by then, the certification will simply be cancelled.

Details on some of the WoT’s peculiarities at the genesis block.

The aforementioned rules can only be enforced with an existing web. They cannot be observed when first creating the web, that is when defining the genesis block.

Only rules 2 and 5 can be observed at the genesis block.

The genesis block has to be manually created by the founding members. In practice this means that there must be a choice of which identities to include on the premise that all of them observe rules 2 and 5. In addition, the genesis block must be signed with the private key of one of these identities.

As soon as the genesis block has been created, the other identities can start mining the blockchain and the member who begat block #0 effectively looses the decision power he had at creation.

Why these rules and application cases in the Ğ1

1. Distance and maximum size

The distance rule is there to curb the maximum size of a Sybil region as well as that of the monetary community as a whole. The xpercent parameter prevents the creation of a ‘faction’ that could take hold of the blockchain.

The Sybil regions are isolated from the rest of the graph in the sense that they can only receive certifications from other ill-intentioned Sybil members. As a consequence, the shortest edge/path between a legitimate member and a Sybil one has to have the attack’s author as an endpoint. The maximum depth the Sybil region can attain is therefore contingent on the distance between the attacking edge-s- and the xpercent% closest referent members, this distance is known as stepAttackers. The maximum size of a Sybil region created by sigQty members depends on the L parameter, defined as L = sigQty/sigStock:

Maximum Sybil region size = (sigStock-sigQty)*(1-L^(stepMax-stepAttackers))/(1-L)

The maximum size of the Web of Trust is given by the following formula:

WoTmax = (sigStock)*L^(stepMax-1)

However we know for a fact that members will never use all of their available certifications. Many studies have proven that we all know a maximum average of fifty people, let’s then replace sigStock by fifty:

WoTavg= (50)*(sigQty/50)^(stepMax-1)

Our goal with the Ğ1 is to create a community of about one million members enjoying the world’s first true catallaxy -free economy with a spontaneous order of things-. Let’s see how we can tweak the pair of sigQty and stepMax- to reach this size:

The maximum size of a Sybil region grows linearly with sigQty but exponentially with stepMax. Logic has it that we need to keep stepMax as low as possible to ensure sufficient strength to the web. The above graph shows that the lowest value of stepMax for a web of a million members is of 5. This is an order of magnitude and is likely to be much higher in reality, we cannot measure it for sure.

For sigQty we can choose a value of 4 for a web of 1.5 million members or 5 for half a million members. Bear in mind these are gross figures and could be significantly higher, we are talking anywhere between 1 and 10 million in reality. Calculating WOTavg gives us a pretty good idea of how the web would scale bearing in mind that it considers all members are referent members too -which isn’t the case as explained previously-. Hence the maximum size of the web is likely larger, a ballpark figure of half a million is enough for now especially knowing that the smaller sigQty is, the easier it is to launch a Sybil attack -it’s easier to find four accomplices than five-. For security reasons we have settled on five:

stepMax = 5 sigQty = 5 sigStock >= 50

The maximum size of a Sybil region therefore is: (sigStock-sigQty)*(1-(sigStock/5)^(5-stepAttackers))/(1-(sigStock/5))

with sigStock = 50 we have a Sybil region of: 45*(1-10^(5-stepAttackers))/(-9)

A good practice for protecting the web is to maximise stepAttackers. That’s why we decided that referent members in the genesis block had to be at least four steps away from each other.

Another way to keep a Sybil attack at bay, were it slow enough for members to notice it, would be for referent members to ‘stretch’ the web intentionally to limit the growth of the region by ensuring that the attackers’ legitimate certifications received in the first place aren’t renewed. But what if bot accounts were created and certified each other super fast and following all rules, how would we counter that? By introducing a minimum length of time between two certifications!

2. Time is our friend

To help us deter a Sybil attack, we’ve decided to impose a minimum period of time between any two certifications issued from a single account. This parameter called sigPeriod affords us a greater chance to detect the formation of a ‘hostile’ faction.

Here is a graph showing the evolution of a Sybil region with the variation of sigPeriod:

As you’ll easily be able to tell, there is a strong link between the growth speed of the region and sigPeriod. As evidenced here, we need a sigPeriod high enough in order to ensure that the legitimate web can grow at least as fast as a Sybil region. In addition, the higher sigPeriod is, the more members will exercise their certification power gingerly, the action coming at a higher ‘cost’.

There are numerous advantages to giving sigPeriod a high value and no technical barriers to it, hence our choice of five days.

We could have also gone for seven days -one week- for the sake of simplicity however there was an underlying idea behind our choice which was quite simply the pace of today’s life. Certifying someone can be a lengthy process as one needs to make sure he/she is correctly applying the Ğ1 licence and people nowadays wait for the weekend to enjoy a bit of free-time. Thus the idea to allow one to certify at the end of every working week -five days- instead of a whole calendar one.

3. Trust me now, trust me forever? (sigValidity, msValidity)

There would be two main drawbacks to a lifetime membership in the Ğ1’s Web of Trust:

First of all we need to take into account that some members will pass and those accounts should no longer produce the Universal Dividend. Secondly it is of the utmost importance that ‘rogue’ accounts can be excluded from the web at some point.

To achieve this, certifications have a limited lifetime and members need to seek renewal from their peers after sigValidity time. On the other hand, this time can’t be too short that members would spend more time seeking renewal than they would exchanging in the currency. Furthermore, a certification with too short a lifetime would foster careless certifying behaviours. The act of certifying must have a ‘perceived’ cost high-enough to make it feel like an important act. Lastly, we also wanted this lifetime to be easy enough to remember. Historically speaking, we first settled on the values of sigPeriod and sigStock, meant one could issue all of his/her certifications in 495 days, one year was therefore not long enough. We deemed three years to be too much and that’s how we agreed on two years in the end.

Thinking that a deceased member could continue producing the UD for two long years without anyone benefitting from it was also something we needed to address. We choose a value of one year for msValidity. The act of renewing every year is done through one of the clients interacting with the blockchain, through a simple click on a button. This parameter is less important than others and is mostly there to ‘prune’ the web of past or inactive members who don’t renew their membership.

4. Keeping the pools free of information glut -(idtyWindow, sigWindow, msWindow)

The pools need to be cleaned up on a regular basis to avoid them clogging up with information and to ensure that machines with less calculating power can still run a Duniter node.

To achieve this, identities with pending membership approval and the corresponding certifications have to remain the shortest time possible in the pool while still having a chance of making it into the blockchain.

For the Ğ1, our opinion was that two months would be enough for all potential certifiers to agree on a specific identity to certify. We also wanted a time period that would be easy enough to remember by all. We settled on two months, and gave this value to all three parameters idtyWindow, sigWindow and msWindow.

5. Avoiding single members from ‘knowing too many people’ (sigStock)

Many sociology studies have shown that we all know an average of fifty people. This of course is an average, some of us know more than fifty people, others much less. Once again we went for a number that would be easy to remember. Although sigStock’s impact on the size of a Sybil region is fairly limited, its value nonetheless has to be kept reasonable. We settled on hundred.

6. Avoiding locking minorities (xpercent)

It’s easy enough to become a referent member, one of the Sybil strategies could therefore be to create a region of referent members. Such a region would grow slower than otherwise but could confer a locking power to its members by using the distance rule. That’s why the distance rule cannot be calculated on 100% of the referent members. Hence the introduction of the xpercent parameter which defines the percentage of referent members needing to be less than five edges -steps- from each other.

This percentage needs to be low enough to prevent the formation of a locking minority -referent Sybil members being too far from legitimate referent members-. On the other hand, it needs to be high enough so as to restrict the maximum size of the Sybil region through the distance rule. The xpercent parameter was one of the hardest to define, we therefore reserve ourselves the right of modifying its value during the Ğ1 experiment.

We were inspired by the Pareto principle: if at least 20% of members give good density to the web, 80% of the referent members will be five or less steps from any other member -referent or non-. The maximum value for xpercent is therefore 80%, anything above that and the distance rule could be too restrictive for legitimate use cases. With security our top concern, we chose the maximum value of 80%.

7. Spam protection with (msPeriod)

This parameter stands out a bit on its own, as it was added after the genesis block. It is there to protect the Duniter P2P infrastructure against ‘spam’ attacks. We had to think of a strategy against attacks such as high-frequency membership renewal requests -i.e: in every block, every five minutes- or worse still, hundreds of these requests per minute to flood the Duniter nodes. Without such limits, nodes are supposed to address all renewal requests, even in cases where they were last published five minutes ago! The msPeriod parameter was given the same value as idtyWindow, sigWindow and msWindow, i.e. two months.