Web Of Trust Algorithms

One of the remaining parts to study about uCoin protocol is WoT algorithms.

With a few talks on the chat, it appears that WoT algorithm implies several consequences: minimum community size to exist, maximum size, and community growth speed. Probably non-exhaustive list.

So here is the subject: which algo to choose for which currency?

Given the following data:

  • We are dealing a space-time referential:
    • Space = members
    • Time = t
  • We have authentified members(t), members(t+1), …
  • We have authentified links(t), links(t+1), … between them

Here are few hints for algo rules:

  • maximum step (the maximum distance between two members)
  • quantity of links (in space and time)
  • quality of links (not 2 times the same link, age of the link, …)

Example: 30 members community

  • Each member must be recognized by at least 2/3 of the members

Example: 1.000 members community

  • Each member must have at least 20 links, with 2 years max old

Example: 10.000 members community

  • Each member must have at least 20 links, with 5 years max old
  • A link cannot between 2 members cannot be updated or repeated

… and so on. Have ideas?

  • each link has a duration limit (time dimension)
  • must have n links available with 5 available members (space)
  • The Wot(t) is registered, since to be available, a new link must avoid the duration limit member repetition (spacetime integration control).
  • No sign with a 2 (or 3) graph steps is available (new sign must be done by people too far from the previous signs) = Limit of trust. (Humanity is connected with something near to 4 - 5 steps, not more, study Graphs Theory).

I understand here that a same link between 2 members must not be repeated to increase its duration. With a possible repetition after each link’s validity + a waiting period, however.

Yes, this is the point. And so, to obtain a new valid sign, must be a member different of the past 5 years signs for the member, and so in fact a member with step > 1, if we define step 0 = the member, step 1 = the members who signed him in the past 5 years.

Consequence : if we need a spatial number of valid signs, so at “t”, something like 7 valid signs for “living proof” at “t”, and 5 years or temporal validation, it means you always need, passed the 5 first years within the community, 7 x 5 = 35 valid signs.

And much more, with these data now, we know he will necessary need other 35 new signs for the next 5 years, so the community will need at least 35 + 35 = 70 members to exist within 2x5 = 10 years.

So being ts the time signing temporal control, Ns the Number of People to validate the living proof at “t”, we have

  • Ns.ts signs after ts within the community
  • 2.Ns.ts people needed minimum within the community

Are you sure about second 35 signatures? I mean, with a 5 years temporal validation, it means the signatures made 5 years ago may be used for the 6th year: so we only have a 1 year validation rolling, which represents 7 signatures.

So in the end, with 7 spatial signatures + 5 years validation, we need 7x5 + 7x1 = 42 members to exist within 6 years, leading to (1 + Ts).Ns minimum people number within the community.

42 yes ! Very good :slight_smile:

1 « J'aime »

About the steps, we finally found that even with few distance (3 steps for example) we could build rather big communities.

See this article (french): théorie des 6 degrés de séparation

What’s the point? It is to see that a step (a link between to individuals) have kind of strength property: a link between you and your wife is not the same than a link between you and someone you met once in a conference. The first is stronger than the second, since you are closer to your wife in your every day life.

So, we can call weak a link done with someone you are not close to, and strong a link with someone you are ver close to. What the article says is: weak links make bigger communities, since you can make higher distance links.

To conclude, with a 3 steps constraint we could easily reach 10k members communtities, but 100k are not that hard to reach too. :wink:

Just a thought, please correct me if I’m wrong: if a minimum number of signatures is needed for a member, a maximum number may also be needed. Without this maximum the potential benefit for sybil attackers could be too high: whatever the minimum number N of signatures needed, N people can take the risk to collude in order to create an (potentially) infinite number of fake identities.
But this maximum number must be chosen wisely: with a number too close to N, it restrains the network from growing by the addition of new legitimate users; with a too big number, it becomes tempting for attackers.

This leads to another aspect: what about dynamic rules ? Rules are subject to change within time for a growing community. Could these rules be themselves part of the blockchain ?

As a quick answer: why not, we have to think a bit more about which rules to choose for the WoT.

But to be a bit more balanced, here is a little paragraph about max. distance rule which may already help us.

The max. distance rule

Any member must be at maximum n steps from any other. That is, if we have a -> b -> c -> d, then d may join the WoT since it is recognized by a. But a e individual could not join if we only have a d -> e, since e would be distance 4 from a.

It seems n = 3 is a good tradeoff to have communtities of ~100k members. Over 3 might be difficult to still have trust, but this is another debate.

Requires distance 2 members

Anyway, making fake identities with such a rule implies the fake identity to be signed by members with distance 2 from other members, since signing someone adds a step for others. So, such cheating people have to be step 2, or at least find others step 2 which will accept to sign the fake identity.

Is combo with signature delay

But then you also have the other rule avoiding signature repetition in a given period. This would imply cheaters to find other people to participate to the cheating.