Advogato's Trust Metric

This document briefly describes the technical details of Advogato's trust metric.

The basic trust metric evaluates a set of peer certificates, resulting in a set of accounts accepted. These certificates are represented as a graph, with each account as a node, and each certificate as a directed edge. The goal of the trust metric is to accept as many valid accounts as possible, while also reducing the impact of attackers.

Advogato performs certification to three different levels: Apprentice, Journeyer, and Master. This is actually done by running the basic trust metric three times, using the "level" value in the certificate as a threshold. Thus, certification of Apprentices is computed using all certificates, while Master is computed using Master certificates only.

The computation of the trust metric is performed relative to a "seed" of trusted accounts. At the time of this writing (22 Feb 2000), the seed consists of raph, miguel, federico, and alan.

The core of the trust metric is a network flow operation. Informally, if there is a rich web of interconnections, flow reaches almost all the nodes. However, only a few accounts would be accepted from a large nest of bogus accounts, as long as there are only a few certificates from the "good" web to the bogus accounts. Those certificates represent a bottleneck in the network flow.

The remainder of this document presents the actual trust metric in more detail, as well as an argument for the security against attackers.

Mapping into graph

The mapping of certificates into a graph is dependent on a parameter: the certification level l. Each account on Advogato corresponds to a node in the graph. An edge exists from node s to node t when account s has certified account t at level l or higher.

In addition, there is a distinguished "seed" node, with predefined edges to accounts. These are currently configured in the mod_virgule source, file tmetric.c.

Assignment of capacities

The next step is to assign a capacity to each node in the graph. This is done by breath-first searching the graph from the seed, computing a shortest distance from the seed to each node.

Then, capacities are assigned simply as a function of this distance. Nodes closer to the root have high capacity, which diminishes with distance. Currently:

cap(0) = 800
cap(1) = 200
cap(2) = 200
cap(3) = 50
cap(4) = 12
cap(5) = 4
cap(6) = 2
cap(i) = 1 for i > 6

An example of the capacity assignment is shown below, although with much smaller capacities than used on Advogato:

Conversion into single source, single sink

At this point, the network flow problem is defined as a single source, multiple sink problem. In addition, capacities are specified on nodes rather than edges. Since standard network flow algorithms are specified as a single source, single sink problem with capacity constraints on edges, we modify the graph slightly. A new node, the "supersink" is added to serve as a single sink for the network flow algorithm.

Each node x is split into two nodes, x- and x+. For a node x with capacity c, an edge is added from x- to x+ with capacity c - 1. For each edge from s to t in the original graph, we add an infinite capacity edge from s+ to t- in the new graph. Finally, from each node x, we add a unit capacity edge from x- to the supersink node.

This conversion is shown graphically below:

Computation of network flow

At this point, computation of the network flow is fairly straightforward, using a standard algorithm to compute a maximum flow from the seed to the supersink, subject to the capacity constraints placed on the edges. An additional constraint is placed on the result: if there is flow on the x- to x+ edge, there must also be flow on the x- to supersink edge.

Happily, when using the standard Ford-Fulkerson algorithm (repeatedly finding an augmenting path through the residual graph until no such path exists), this constraint is easily satisfied: simply use the heuristic of always choosing the shortest augmenting path. The fact that this heuristic satisfies the constraint also proves that the maximum flow satisfying the additional constraint is equal to the maximum flow.

An example of such a flow is shown below:

Security proof

To set up the security proof, we need a model of the attack. Here, we present a simple one.

The nodes are split into three categories: good, confused, and bad. The bad nodes are under the attackers control. The confused nodes themselves represent valid accounts, but may contain certificates to the bad nodes. The good nodes are both valid accounts and have certificates only for other good nodes and confused nodes. This partition is shown graphically below:

In addition, we represent the capacity of node x as c_x. We are now ready to prove the following theorem:

Theorem 1

The number of bad servers chosen by the above metric is bounded by the sum of (c_x - 1) over each of the confused servers x.

Proof outline. Consider the cut that includes all edges from good or confused nodes to the supersink, and all edges from confused nodes to bad nodes. This is clearly a cut because there are no direct edges from good to bad nodes.

The flow from a confused node x to bad nodes cannot exceed c_x - 1, as the total flow into x is bounded by c_x and the above-mentioned constraint requires that there be unit flow from x- to the supersink if there is any flow at all. The constraint also ensures that the flow from non-chosen confused nodes is zero. Thus, the total number of bad nodes chosen is bounded by the sum of (c_x - 1) over each of the confused servers x. QED.

Note that the number of bad servers accepted depends only on the number of confused servers, not on the number of bad servers. Thus, spam attacks are frustrated.

Conclusion

The trust metric used in Advogato has a property not known in any previous trust metric: resistance to catastrophic failure in the face of a sufficiently massive attack. Instead, the number of bad nodes accepted scales linearly, and with a fairly small constant, with the number of certificates from valid accounts to bogus ones. It is also easy to compute efficiently and fairly simple to understand. As such, it should find applications in security infrastructures, as well as defining online communities, reliably excluding spammers, trolls, and other common annoyances.

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!