Using graph analysis to prevent Sybil attacks

bodhi · August 31, 2025, 12:01pm

Background

One of the main challenges PoH may face in the upcoming years is the growing threat of Sybil attacks, especially as AI continues to improve at generating deepfakes and the network itself expands.

The two-layer defense of vouching and challenging suspicious profiles has so far done an excellent job of preventing the registry from being overrun. However, it does have limitations. For example, a single registered user could create multiple fake accounts, vouch for them using their original profile, and submit AI-generated videos convincing enough to slip past challengers during the review period. By the time such accounts are identified and removed, the damage may already be done.

To make PoH resistant against such attacks and make it future-proof, I would like to propose a new mechanism that will assign each profile a trust score and dynamically adjust the number of required vouches based on the trust levels of its network. By applying graph theory, PoH could deploy a graph-based scoring system combined with a dynamic vouching requirement. This approach would keep registration simple for legitimate users while making it exponentially harder for Sybil clusters to form.

This proposal is heavily inspired by the ideas shared by Clément in this portal back in 2023

Constructing the vouching map

We would represent the existing PoH network as a graph with the following structure:

Nodes: Every profile in the system is represented as a node (except profiles in the Vouching stage)
Edges: Vouches between users are marked as Edges

Implementing a scoring algorithm

Next, each user will be assigned a trust score based on their placement in the graph. The score will reflect the likelihood that the account belongs to a legitimate human or a sybil account. It will be based on:

Degree Centrality: Number of vouches received and given. The more the no of diverse vouches, the more trust.
Closeness to the Core: Distance from long-standing, highly trusted members. Users closer to the core are considered safer.
Web of Trust Weighting: The quality of vouches is important. A vouch from a user with a high score is considered safer than a vouch from a user with a low score.

Based on the scores, the profiles will be placed in three tiers:

Green (High score / Low Risk): Trusted core members with strong connections across the network.
Gray (Medium Score / Medium Risk): Legitimate users who are newer or on the edges of the network.
Red (Low Score / High Risk): Potential Sybils, often isolated in small clusters far from the trusted core.

When a new user registers on the platform and an existing profile vouches for the new user, then the new user’s initial tier is inherited from the risk profile of their voucher. That means:

If a Green-tiered user vouches → the new user is marked Green.
If a Gray-tiered user vouches → the new user is marked Gray
If a Red-tiered user vouches → the new user is marked Red.

How does this approach help in detecting Sybil attacks?

This approach uses the vouching pattern graph, which shows how existing registered profiles are connected and who is vouching for whom. Real, legitimate users will have diverse, close to the center, and well spread out connections (or vouches) across the network (like the Green and Gray nodes in the above image). While potential sybil profiles will show up as small, tight clusters, mostly away from the center (like the red nodes). Using the profiles’ score and which profiles fall under which tier, the system can quickly identify suspicious clusters and profiles.

Dynamic Vouching Mechanism

Currently, when a new user registers, they are marked as a “Vouching” and when someone vouches for them, they progress to the next stage of “Pending Claim”

And the no of vouches needed to proceed from “Vouching” stage to the next stage is 1 Vouch. In this new mechanism, the no of vouches required to proceed to the next round will be dynamic and will be based on which tiered (green, gray, or red) profile vouches for the new registered profile.

If vouched by either Green or Gray, then it will just require one vouch to proceed to the “Pending Claim” stage.

But if vouched by a user from the Red tier, then the no of vouches required to proceed to the next round increases exponentially until the user secures vouches from Green/Gray accounts.

Rules for the new mechanism

A new profile vouched for by a Green or Gray tier profile requires only one vouch to proceed to the “Pending Claim” stage.
If a new profile is initially vouched by a Red-tier profile, then the number of vouches required to pass doubles with each subsequent Red vouch.
And to successfully pass at least half of the total required vouches must come fromGreen or Gray users.

Example walkthrough

Alice is a new user who just registered on the Proof of Humanity platform. She needs vouches to move forward. The system uses dynamic vouching rules to decide how many vouches Alice will need, depending on the trustworthiness of those who vouch for her.

Alice’s first vouch comes from Bob, who is categorized in the red tier. As Alice receives a vouch from a red-tiered profile, she does not pass immediately to the “Pending Claim” stage. Instead, the system increases her requirement to 2 total vouches to pass to the next stage. Therefore, Alice now needs one more vouch to move forward (she already has a vouch from a red-tiered profile)

Now in this stage there are two possibilities that can unfold:

Receives vouch from Green/Grey tiered user:

Alice meets the requirement (1 Red + 1 Green/Gray)
Total required = 2, Alice has 2 vouches.
Therefore, Alice passes to the next stage

If the vouch is again from a red-tiered user:

The system increases the no of vouches required to proceed to the next round
Requirement doubles from 2 → 4 vouches total.
To pass, Alice must now have at least 2 non-Red (Green/Gray) vouches.

In this case, Alice has 2 Red vouches so far, but still needs 2 more vouches from Green/Grey tiered users to move forward. If Alice manages to get two more vouches from either Green or Gray tiered users, she will proceed to the next phase. But suppose if the third required vouch is also from a red-tiered user, then the total required vouches needed to proceed will increase and become 8. And out of which 5 vouches should be from Green/Gray tiered users to proceed to the next round.

If Alice continues to get vouched only by red-tiered users, the system keeps doubling its requirements: 16, 32, 64, and so on. And to proceed further, she needs more than half of the required vouches from either Green or Gray tiered profiles. This ensures that red clusters cannot bootstrap themselves indefinitely. Each Red vouch makes registration exponentially harder, unless the user breaks out of the cluster and earns validation from trusted parts of the graph.

Mathematical representation

Let:

r = the number of Red vouches received.

g = the number of Green and Gray vouches received.

Vreq = the total number of vouches required.

Each vouch from a red-tiered user doubles the total no of vouches required to proceed to the next stage. Then

If no Red vouches exist (r=0), then Vreq =1.
If 1 Red vouch exists, Vreq=2.
If 2 Red vouches exist, Vreq=4.
If 3 Red vouches exist, Vreq=8, and so on.

And at least half of all required vouches must come from either Green or Gray tiered profiles. That means: g>= Vreq/2

So, to advance:

For r=1 : Vreq=2, need g>=1
For r=2: Vreq=4, need g>=2
For r=3: Vreq=8, need g >=4.

Wrapping up

The combination of graph scoring and dynamic vouching gives us a flexible and adaptive defense. For honest users, the flow stays as easy as it is today i.e, a single vouch from a trusted member. But for suspicious profiles, the requirements rise exponentially, making large-scale Sybil infiltration unworkable.

This is just a preliminary proposal intended to start a conversation. Would love to hear the community’s thoughts, critiques, and suggestions on this approach and further improvements.