# Justification for Backwards Search

There are multiple reasons why a backwards BFS was chosen to find paths in a trust residual network.
This document aims to record and explain these reasons.

*This document is offered as background, it is not required reading for understanding the Berblom algorithm*

## Conflicts on Trust Depths

The disadvantages of forward search in a Web of Trust network **with depth limitations** become apparent very quickly.

Consider the following scenario:

![A simple conflicting network](../Diagrams/figures/BFS/Justification-for-Backwards-Search_simple_conflict.svg)

For brevity's sake, the binding `Target, target@foo.example` will be referred to as `Binding`.

Note that the path `TA -> C2 -> C3 -> Target -> Binding` is invalid due to the trust depth constraint of `2` on the edge `TA -> C2`.

### Considering forward search

There are two classes of forward-search approaches for finding a path in such graphs:

1. Use a DFS: This approach works, but it is potentially inefficient and it neither guarantees finding the shortest path nor the path with the highest trust.
2. Use a guided BFS that picks nodes based on these criteria in descending order:
    - Depth-First: Always use the path that allows the deepest lookup. This is necessary to prevent occupation of nodes during graph exploration by paths with shorter delegations. Otherwise, paths may not be found.
      Without this rule, the path `TA -> C2 -> C3` would be favored in the example figure, terminating without finding a valid path.
    - Current path length: How many hops to reach the trust anchor
    - Trust-amount: Favor the highest trust amount

The DFS approach is obviously flawed, but the issues with BFS are a bit more subtle.
Consider the following graph:

![A more complex conflicting network](../Diagrams/figures/BFS/Justification-for-Backwards-Search_complex_conflict.svg)

Since the BFS must, as previously established, use the trust depth as a primary heuristic, the path that will be found is `TA -> C2 -> C3 -> C4 -> Target -> Binding`, which is both the longest path and the path with the least trust amount.

Path length is especially crucial, as short trust chains are more expressive and should therefore be explored first.

### Searching backwards in the graph

By performing a backwards BFS, with the main heuristic being the shortest path (from the `Binding`) **and** the trust amount as a tie-breaker if multiple paths are found, we will find the shortest path with the **highest trust amount** for that path length.
When traversing the graph backward, trust depth limitations on an edge can always be immediately checked against the length of the path that leads to that edge. This is not the case when searching in the forward direction (when searching forward, depth limitation on an edge apply to future search steps deeper into the graph).
