The project for the graduate algorithms class I took in Fall was to compare two algorithms for a problem of our choice. I chose to compare two trust metrics, the Advogato trust metric and Google's PageRank. Trust metrics attempt to solve the following problem: "Given a directed graph where an edge from A to B means 'A trusts B', whom should I trust?".

In the case of Advogato, the nodes are Advogato accounts and the edges are explicit certifications. In the case of Google, the nodes are web pages and the edges are links.

A good trust metric makes it difficult for an attacker to gain a large amount of trust. More specifically, we might want the amount of trust an attacker gains to be at most *linear in the cost of the attack*. It helps to think in terms of "bad" nodes, which are controlled by the attacker, "confused" nodes, which trust bad nodes, and "good" nodes, which are neither bad nor confused.

Proving a statement about the cost of an attack requires assuming something about the cost of compromising or confusing each node. Advogato assumes that the cost of confusing a node is closely related to the node's capacity, which is a function of the node's distance from the root. PageRank assumes that the cost of confusing a page is closely related to the page's popularity, which is in turn estimated by the page's PageRank score.

I discovered a problem with Advogato's security proof: it bounds the trust by the final capacities of the confused nodes rather than their capacities before the attack. An attacker can confuse a single expensive (high-capacity) node and many cheap (capacity 1) nodes, then tell the expensive node to trust the cheap nodes. Now there are many confused nodes with substantial capacity, and the attacker can get get an amount of trust equal to a constant times the *square* of the cost of the attack.

PageRank does not have this problem. The PageRank score gained by the attacker is bounded by a small constant times the total PageRank-score-before-attack of the confused pages, no matter where the attacker makes confused or bad nodes link.

For more details, you can read my paper for the algorithms class.