Berblom Algorithm

Problem statement

In a Web-of-Trust (WoT) network, trust relationships are modeled as a directed graph. OpenPGP certificates act as nodes, and delegations of trust are represented by weighted edges. Each delegation can be limited by both a trust amount and a trust depth, reflecting how much trust is forwarded and how many steps it may propagate. Finally, certification edges model connections between certificates and identities (we refer to these connections as "bindings"). The challenge is to determine the maximum trust that can be established between a set of trust anchors and a target binding, whilst considering all constraints imposed by the network's structure and its delegation rules.

Unlike simple path-finding, trust computation in a WoT must account for multiple paths that may overlap or steal each other's trust capacities. Some methodology of backtracking must be utilized to prevent such issues.

Explanation

This project implements a flow computation algorithm for WoT networks, building on the abstractions provided by the wot-network crate. It provides a library for analyzing trust graphs, computing maximum trust, with the capability to visualizing the process step-by-step (to a certain degree).

Documentation for the underlying types and interfaces is available at docs.rs/wot-network.

The main algorithm is a modified Ford-Fulkerson, adapted for multi-source, single-sink graphs with additional constraints:

• Each edge (delegation) and node (certificate) can limit the flow by trust amount and trust depth.
• Delegations can be excluded for the target binding in question via regular expressions.
• Reverse edges, during Ford-Fulkerson, must also be aware of trust amounts and trust depth limitations.
• After flow computation, a path consolidation step must resolve all used reverse edges. This ensures that only valid, forward-only trust paths will be returned.

Documentation

A detailed description of the algorithm can be found in the documentation files:

1. Path finding: The inner algorithm that finds individual paths in a (residual) WoT network.

   1. Breadth-First-Search (BFS): Overview of the inner path finding algorithm.
   2. Justification for Backwards Search (not required reading): Discussion of the design decision to search paths "backward" (starting from the target node moving to the trust anchors).
   3. Traversing Reverse Edges: The outer algorithm that deals with maximum flow adds "reverse edges" to the residual network graph that the inner algorithm operates on. This section explains how path finding deals with those special edges.
   4. Cycle Detection (not required reading): A discussion of cycle detection in the inner path search algorithm.
   5. Priority Queue (not required reading): Path finding in Berblom uses a priority queue.

2. Flow Computation: The outer algorithm that finds maximum flow by combining multiple Path finding runs and adjusting the residual network.

   1. Berblom Algorithm: The main flow maximization subsystem of this algorithm.
   2. Creation of Reverse Edges: Discussion of the reverse edges that Berblom adds to the residual network (those enable the Path Finding algorithm to implicitly "redirect" flow).

3. Path consolidation: The post-processing step that normalizes the raw output of Flow Computation into a set of valid forward-paths in the original WoT network graph.

4. Glossary

The implementation also has extensive inline documentation.

Example

The binary provided in src/bin/run_test.rs can be used to run predefined test cases and visualize the flow computation process.

You may build it via cargo build --release, which will put the test binary at target/release/run_test

The output is a markdown file containing mermaid diagrams and additional information for each step of the algorithm, including the path consolidation.

To run a test case and generate a visualization:

cargo build --features=test --release
target/release/run_test <case> --output ./search_output.md

Replace <case> with one of the available test cases (see run_test --help for all available options).

Two checked-in examples of such a visualization are available as:

• example_search.md
• complex_example_search.md