# Berblom Algorithm
## Short Explanation
The Berblom algorithm is a method to determine the maximum amount of trust between a set of trust anchors and a target in a Web of Trust (WoT).
Berblom is a modified Ford-Fulkerson to support multi-source single-sink flow networks, where source nodes are the trust anchors and the sink is the target binding whose trust amount is to be determined.
For path resolution in between rounds, a backwards [BFS] derivative is used, which uses the "flow capacity" of path as a tie-breaker and is aware of trust depth limitations.
The algorithm returns maximum trust amounts **and** a list of flow paths.
However, due to how Ford-Fulkerson works, these flow paths don't necessarily reflect actual trust delegations - some paths may use "back-flow"/reverse edges, which are Ford-Fulkerson's method to allow backtracking in a residual graph.
A [Path Consolidation] step needs to be run in the end to resolve any reverse edges. The result of this is a set of fully valid "trust paths" that don't conflict with each other.
## Differences to Ford-Fulkerson
The foundation for the Berblom algorithm is the [Ford-Fulkerson algorithm].
In comparison to a classic Ford-Fulkerson, there are three main differences that change how the Berblom algorithm operates:
- Ford-Fulkerson assumes a single-source single-sink graph.
- In Ford-Fulkerson's model, nodes have an unlimited throughput and only the edges are limiting throughput.
- In Ford-Fulkerson's model, flow is unlimited in its depth.
Berblom trust networks differ quite a bit:
- Multi-source single-sink graphs are supported.
- Not just edges limit flow, but nodes also have a flow capacity and may further limit flow.
- In a Web-of-Trust graph, each edge may limit the flow to a certain depth.
Specifically the depth limitation of flow significantly increases the complexity of the algorithm, as Ford-Fulkerson's reverse edges can no longer be used unconditionally.
It also changes the path finding algorithm, which must perform trust depth checks at each step and whose length arithmetic changes when using reverse edges.
One key difference that helps quite a bit to understand how Berblom works is that it focuses on the paths during each step.
The traditional Ford-Fulkerson also works with paths, but only as a tool to detect flow.
The focus is more on the holistic network properties than the individual paths, i.e. the maximum flow.
Berblom does not only compute the full flow, but it's also crucial to calculate correct trust paths during this process.
This results in a different algorithmic approach where a lot of focus goes into keeping and building correct representations of paths.
So, when reading the following sections, try to think about the paths and how trust is "rerouted" when backtracking, even though the algorithm works on a consistent residual network.
## Properties
The input of the algorithm is a graph with the following properties.
- Directed
- Can be cyclic
- Can be disconnected
- Multiple source nodes
- Single target node
- Edges have a maximum "flow" capacity
- Nodes have a maximum "flow" capacity
While finding the maximum flow, the following overall properties must be upheld on the graph:
- The capacity of each edge must not be exceeded.
- The capacity of each node must not be exceeded.
- The maximum total flow must not exceed the total capacity of all source nodes.
- The used flow from source nodes must equal the receiving flow on the target node.
## Berblom without depths
In the following, the Berblom algorithm will be explained without considering trust depths, i.e. all nodes have infinite trust depth (full recursive trust).
This should give you a first understanding and some intuition of how the algorithm works.
For brevity's sake, the binding `Target, target@foo.example` will be referred to as `Binding`
Let's consider the following graph:
Trust anchors `TA1` and `TA2` provide a maximum combined flow of `120`.
**Round 1:**
The first round starts with backwards path finding from the `Target` binding.
The optimal backwards path is `Binding -> Target -> CB2 -> CT1 -> TA1`, as it's the shortest path to a trust anchor with the highest throughput.
→ The result is added trust of `80`, the backwards path `Binding -> Target -> CB2 -> CT1 -> TA1`, and the following residual network.
The consumed flow of all forward edges has been subtracted and all valid reverse edges have been added.
There's no longer a path from `TA2` to `Target` using only forward edges.
However, the reverse edge allows backtracking some previously consumed flow.
**Round 2**
The second round continues using the same residual network for path finding:
→ The result is added trust of `40` (increasing the total to `120`), and the new backwards path `Binding -> Target -> CT3 -> CT2 -> CT1 -> CB2 -> CB1 -> TA2`.
After this round, we have arrived at the following new residual network state.
As you can see, reverse edges have been added once more for all forward edges that have been visited.
The flow capacity of the used reverse edge between `CB2 -> CT1` is lowered by 40 and the forward edge between `CT1 -> CB2` is restored by 40 (green edges).
**Round 3:**
Path finding is performed once more, but no further path can be found.
The algorithm terminates with a total trust of `120` and the follwing two paths:
- `P1: TA1 -> CB1 -> CB2 -> Target -> Binding`
- `P2: TA2 -> CB1 -> CB2 -> -> CT1 -> CT2 -> CT3 -> Target -> Binding`
#### Ford-Fulkerson with Trust Depth
The algorithm becomes a bit more involved when trust depths are considered.
In a WoT it's possible to forward trust, i.e. to allow trusted parties to make decisions for oneself.
This process is called _trust delegation_.
Trust can be delegated transitively, from one certificate to many others.
However, to not allow endless recursive trust, trust delegations come with a _depth_ restriction. This effectively limits the delegation process so that trust is only forwarded up to a maximum of `Y` times.
Let's look at the previous example, but this time around with some trust depths.
Consider the following graph, which provides a special annotation on each edge.
- `t:X` means a trust amount of `X`.
- `d:Y` means a trust depth of `Y`.
If no trust depth is provided, trust may not be further delegated.
**Round 1:**
The first round starts with backwards path finding from the `Target` binding.
The optimal backwards path is `Binding -> Target -> CB2 -> CT1 -> TA1`, as it's the shortest path to a trust anchor with the highest throughput. All the depth restrictions are sufficient for this path.
→ The result is added trust of `80`, the backwards path `Binding -> Target -> CB2 -> CT1 -> TA1`, and the following residual network.
The forward path is `P1: TA1 -> CB1 -> CB2 -> Target -> Binding`.
Just like in the previous run without depth limitations, reverse edges have been added. However, this time with **trust depth** limitations.
The reverse edge that's relevant for us is between `CB2 ~~> CT1`.
The trust depth that is used on this edge is the remaining possible depth from `CT1` when coming from `TA1 -> CT1`, which in this case is `3`.
The reason for this is, that if we were to backtrack this connection, we effectively simulate a rerouting of trust in path `P1` from `TA1 -> CT1 -> CB2` towards `TA1 -> CT1 -> CT2`.
To make sure this simulated operation is valid, we must ensure that the trust depth constraint is upheld.
> **NOTE:** There is a more detailed and approachable explanation on how reverse edges are calculated in the document about [Creation of Reverse Edges](./002_Creation_of_Reverse_Edges.md).
**Round 2:**
The second round of the algorithm starts and the path finding from the `Target` binding is run on the new state of the residual network.
This now finds a backwards path from `Binding -> Target -> CT3 -> CT2 -> CT1` and then terminates. When considering the edge `CT1 -> CB2`, the current path length of `4` prevent using that reverse edge, which is limited to a depth of `3`.
(This depth limitation on the reverse edge can be interpreted intuitively to mean: We can not reroute the path `P1` from `TA1` to `Binding` via `CT2`, because that alternative path is one hop longer, and the depth limitation of `3` on the edge from `TA1` to `CT1` is insufficient for this extra step.)
The algorithm terminates with a total trust of `80` and the single path `P1: TA1 -> CB1 -> CB2 -> Target -> Binding`.
[BFS]: https://en.wikipedia.org/wiki/Breadth-first_search
[Ford-Fulkerson algorithm]: https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm
[Path Consolidation]: ../003_Path_Consolidation/001_Path_Consolidation.md