What kind of graph theory problems do you need to solve?

Hello everyone, I’m completely new to the world of decentralized digital currencies, and therefore also to uCoin, but I find the concept very interesting, as I believe that a radical change of monetary system is necessary and we shouldn’t wait for governments to do it.

I’ve seen that you need mathematicians, and especially graph theory specialists. I’ve studied maths a lot and graph theory a bit; now I’m a researcher in theoretical computer science, not exactly on graph theory but not far. So I was wondering what kind of problems you need to solve, to see whether I can be of any help.

Cheers!

2 « J'aime »

Hi Bastien,

For a free money system, that is based on Universal Dividend money to any human member, we developped a Web of Trust which include some parameters :

  • Limited time validity for signatures
  • max path between any member (around 4)
  • Minimum number of signatures to be considered a new member
  • max number of signatures a member can make to other members
  • Some other stuff perhaps (look at exact protocol)

Due to those parameters, and the time that is included, it is not a 2D graph, but a 3D one, with limited connexions in space (max path, limited number of signature) and time (limited time validity and also limited life exptectancy for a human (we consider 80 years).

So all of that limits the size of the WoT.

So a theoritical study could help giving some estimations of the possibilities of the WoT parameters, if we want to reach a 100 000 members stable WoT, or a 1000 000 members WoT, we understand there will be limits, and the probabalities of renewal members (member who die, replaced by newcomers etc…) will also have an influence of the WoT(t) object.

So it’s a complex subject that need probably a new approach and perhaps some simulation to know more what can happen, and what those rules allow to reach.

1 « J'aime »

Hi Galuel, and thanks.

So the question is to determine the maximum size of the WoT as a function of the parameters, right? And did someone start to work on this, is there a clean mathematical definition of the object and the constraints?

Not only the maximum, but also the medium one, because the maximum will probably not be reached so it is not the most important to know (I suppose a probalistic distribution of member choices, can give an idea of extremes and medium possibilities of a WoT).

Yes the object is fully defined by the uCoin protocol. You will find them in the uCoin official site (probably in the FAQ, or the github, somewhere…).

Ok thanks ! I’ll start looking at this in the coming weeks.

Hello Bastien.

Yes it is fully defined on the protocol but not under an exploitable form for you I guess, so if you need some clear definitions: I still have to do it.

However I can sum it up quickly here. I will notably use protocol parameters to give you this list.

Objects

  • the WoT is an oritented graph
  • each vertex represents an individual
  • each link represents a certification from an individual to another

Rules

A new vertex (individual) can be added to the WoT only if it matches the following rules:

  • if he has enough links (certifications, this is sigQuantity parameter)
  • if, given its links and the whole set of links of the WoT, he reaches at least xpercent of any other individual of the WoT with sentry level¹ through a maximum of stepMax steps (this is a parameter)

¹ Sentry level is reached by a member if he has at least 1.2 x CEIL(EXP(LN(membersCount)/stepMax)) valid links from him. Indeed if a member certifies nobody, he cannot be reached by newcomers and would block the WoT.

Note how “added to the WoT given its links” means that we actually have 2 WoTs: the current one and the potential one. We jump for current to potential (and the potential becomes the new current) if the potential one matches the rules.

Constraints

  • only individuals members of the current WoT can add new links to the WoT
  • links expire (for example after 1 year, this is sigValidity parameter)
  • each individual has a continous stock of certifications he can make (for ex. 40, this is sigStock parameter)
  • each individual has to wait a delay between each link he makes (for ex. 1 day, this is sigPeriod parameter)

You will be able to see other parameters in the protocol, but it should not be required for a WoT study.

Two important points

  • the first rule (minimum number of certifications) applies at each t, for each member

So if a certification expire at t, and the member no more match rule 1, then he is kicked from the WoT at t + 1.

  • the second rule apply for each member when he joins or renew to the WoT

Indeed, you need to regulary update your status of member: it first happen when you join, and then on a regalur basis (this is msValidity parameter). You get kicked at t + 1 if at t your join/renew expired. Your links are still valid even when you are kicked as a member.

Hope this helps!

:innocent: