Social Graph project ideas

Table of contents

• Social Graph project ideas
• Ideas from routing
  • Use Dijkstra's algorithm to examine the reputation towards a peer
    • Example to understand the protocol
  • Open problems from simply using Dijkstra
• Basic idea on how the system would work.
  • NETWORK/PROTOCOL discussion
    • Mapping to networking

Ideas from routing

Use Dijkstra's algorithm to examine the reputation towards a peer

Dijkstra's algorithm allows to compute the shortest path between two points of a graph. It's widely using by most of today's routing algorithms.

On key feature of the algorithm is that it doesn't only provide the user with the shortest path to a point in the graph. But also is able to provide with the paths

$\ge X$ steps compared to the shortest one.

With that, seems a bit easier to not only provide 1st level trust paths to a peer but rather also 2nd and 3rd.

Example to understand the protocol

Let's consider a simple example with nodes A, B, C, and D:

A --1-- B
|      / |
4    2   5
|  /     |
C --1-- D

1. Initialization:

• dist = {'A': 0, 'B': inf, 'C': inf, 'D': inf}
• prev = {'A': None, 'B': None, 'C': None, 'D': None}
• pq = [(0, 'A')]

2. First Iteration:

• Extract 'A' from pq: pq = []
• Send updates to neighbors B and C:
  B: new distance = 1 (update dist and prev, add to pq)
  C: new distance = 4 (update dist and prev, add to pq)
• dist = {'A': 0, 'B': 1, 'C': 4, 'D': inf}
• prev = {'A': None, 'B': 'A', 'C': 'A', 'D': None}
• pq = [(1, 'B'), (4, 'C')]

3. Second Iteration:

• Extract 'B' from pq: pq = [(4, 'C')]
• Send updates to neighbors A, C, and D:
  A: no update (already shortest path)
  C: new distance = 3 (update dist and prev, add to pq)
  D: new distance = 6 (update dist and prev, add to pq)
• dist = {'A': 0, 'B': 1, 'C': 3, 'D': 6}
• prev = {'A': None, 'B': 'A', 'C': 'B', 'D': 'B'}
• pq = [(3, 'C'), (4, 'C'), (6, 'D')]

4. Third Iteration:

• Extract 'C' from pq: pq = [(4, 'C'), (6, 'D')]
• Send updates to neighbors A, B, and D:
  A: no update (already shortest path)
  B: no update (already shortest path)
  D: new distance = 4 (update dist and prev, add to pq)
• dist = {'A': 0, 'B': 1, 'C': 3, 'D': 4}
• prev = {'A': None, 'B': 'A', 'C': 'B', 'D': 'C'}
• pq = [(4, 'C'), (6, 'D'), (4, 'D')]

5. Fourth Iteration:

• Extract 'C' from pq: pq = [(4, 'D'), (6, 'D')]
• Send updates to neighbors A, B, and D (no updates needed)

6. Fifth Iteration:

• Extract 'D' from pq: pq = [(6, 'D')]
• Since 'D' is the target, the algorithm can terminate early if desired.

7. Result:

• Shortest path from 'A' to 'D' can be reconstructed using prev: A -> B -> C -> D
• Shortest distance: 4

Open problems from simply using Dijkstra

1. Constant need to update the routing tables for all peers.
   Notice that dynamic routing requires the peers (graph nodes) to constantly update their information. While not super relevant for reputation (paths are unlike to change except for a loss of trust) it's still an issue since we need to constantly have a server running which takes care of all these things.

2. This is missing key features like authentication or extra features that commonly used routing systems like OSPF or IS-IS bring to the table.

Basic idea on how the system would work.

As a user I have 2 different things to do:

1. First, I have a hashmap (Search for a more firendly storage) where I store the ID/trust_score relation for each peer I want to add in my trust graph. The more peers, the better trust score you get when analyzing for any other ID.

• $ID=\mathbf{\text{H}}({User}_{Pk})\vee {User}_{Pk}\vee {User}_{ENS}$ It can be anything.
• $trust\mathrm{\_}score\in \{3,\dots ,0\}$

We could use ENS text records in order to add the commitment to the HashMap such that we have a public and easy-to-find place where a user can collect the latest state of the routing (reputation table) of each user we interact with.

2. I join the network/protocol

This section is where most of the issues/doubts and design decisions need to be taken. They all have pros and counts and the section tries to outline them all and try to come up with the best solution and update/upgrade paths for it for further improvement.

NETWORK/PROTOCOL discussion

Theoretically, this problem can be modeled in lots of different ways and solved in many levels of the OSI layer.

Mapping to networking

Mapping to networking the problem can be really helpful. For instance there are many architectures and protocols someone can take example from to construct a solution for the problem.

Distributed/P2P network modeling

Imagine a protocol like Kademlia for example. This allows to generate a P2P network where nodes can route messages between eachother. With a few tweaks, I think it should be possible to integrate and run Djikstra's algorithm such that we can find shortest paths.

Pros

• There's plenty of work done on Kademlia and routing in P2P networks. Although is not clear how to do it. Seems it should be fairly straightforward to adapt Kademlia and add an ad-hoc or on-the-top way to support trust-setting properties that allow the solution to work.
• Allows for a fully-decentralized solution.
• Kademlia by itself can already route all messages between peers. Such that things like 2-party PSI are less complicated to implement (trafic is already guaranteed).
• No need to come up with IP-record mechanisms.
• We have the IPs of our bucket peers. But we still need to map hash-proximity to trust proximity otherwise these IPs aren't enough.

Counts

• This forces us to do a lot more work and a much more complex solution with more failure points.

• Bandwith consumption = Battery consumption = Bad behaviour in phones or regular devices.
• Requires an APP constantly running in background.

Centralized/Client-Server modeling

Imagine we model the solution as if it was a messaging app. A centralized server has the IPs of all of the clients and clients only need to know

$ID$s to be able to interact with eachother.
This solution contains 2 variants:

• Server sends all the protocol-related messages (the 2-party PSI interactions, Djikstra's runs etc..).
• Server just helps to perform a faster translation from IP<->ID and messages are exchanged between peers.

In both of the solutions there are common pros and counts:

Pros

• Prevents all the issues of P2P networks (Sybil, DDOS, Battery/Bandwith consumption, Bootstrapping…)
• Significantly reduces the ammount of complexity of the entire solution. No network infra to be built almost.
• Is still private computation and data. Still trustless. (Even if centralized router wants to cheat, we can force the ID to auth itself via ZKP or signature).

Counts

• The owner of the centralized node can gather info about the most trusted nodes of each peer if we use the straightforward way of querying in Dijkstra.

Every time we want to find the paths to peer X, we start by asking the most trusted nodes that we have stored in our buckets. That means that if the server tracks the first IDs that we send a query to when doing Djikstra, it can easily learn

• The entire system requires this centralized machine to be able to work (even we can apply caching for IPs if the server doesn't also send the messages).
• Is less cool.

PubSub modeling

It's not clear that PubSub architecture is a good model to desing a solution arround this problem.
In any case, it has good properties hence why is left here as something that might be worth exploring at some point.

3. Ask for the shortest path to
   $I{D}_a$

Here we goooo!

Assuming we have sorted out all communication, reachability, networking etc.. Now it's time to actually figure out the shortest path and all the paths with

$Trust\ge X$.

The first thing we would do as a node