# Creation of Reverse Edges

In the following, the logic and intention behind reverse edges will be explained.

The idea of reverse edges is to allow backtracking in the residual graph.
The mechanism of backtracking is used to solve issues like in the following scenario:

- We have two trust anchors `TA1` and `TA2` and the target `Binding` (short for the node `Target, target@foo.example`).
- There exists both a long path and a short path from `TA1` towards `Binding`.
- There exists only a single path from `TA2` towards `Binding`, which is also shared with one of the paths from `TA1`.
- During the first step, the short path between `TA1` and `Binding` will be found, using all of the available capacity on all of its edges.

![Berblom with Depth Step 1 - Path](../Diagrams/figures/Berblom/Berblom_depth_step1_path.svg)

`TA2` is now left without a valid path towards `Binding`. But if all constraints allow it, `TA1` could simply use the long path instead and free up some capacity on its short path towards `Binding`, allowing `TA2` to reach `Binding`.
This process of simulating the use of another path, or "rerouting" as we call it, is what is achieved by the introduction of reverse edges.
Providing reverse edges for the BFS and upholding certain guarantees after exploring a reverse edge, allows pathfinding whilst **simulating** rerouting of trust **without** having to adjust the residual graph.
I.e. it enables the use of a simple BFS without having to keep track of a growing set of possible paths!

## Trust Depth

In contrast to a traditional Ford-Fulkerson, we cannot just use any reverse edge when performing the BFS.
As established before, using a reverse edge effectively simulates redirection of trust along another path.

However, since trust delegations have an associated trust depth limitation, we cannot always redirect trust! We must make sure that the new path is valid, which means considering the trust depth of the path to be redirected.

Due to this, reverse edges also have a trust depth attribute.

### Calculating Trust Depth

![Reverse Edges - Example with constraints](../Diagrams/figures/Berblom/Creating-Reverse-Edges_simple_with_constraints.svg)

The function that calculates the current trust depth constraints along all nodes of a path is monotonically decreasing.
This property must be upheld to prevent trust expansion beyond the allowed constraints that are established by trust anchors.

The upper bound for trust depth is established by the first edge from the trust anchor, which in this example is the depth of `5` between `TA1 -> C1`.

Every hop along any path decreases the depth by at least `1`. Since the function must be monotonically decreasing, higher trust depths along the paths have no effect. This results in a depth of `4` on `C2`, despite `C1 -> C2` having a depth limit that allows `100`.

Trust depths can be restricted, however, which is a valid operation on a monotonically decreasing function.
Due to this, the trust depth constraint on `C3` is `2`, as `C2 -> C3` restricts the depth to `2`.

## Algorithm

![Reverse Edges - Example](../Diagrams/figures/Berblom/Creating-Reverse-Edges_simple.svg)

Consider the simple network above. It has several interesting properties, which cover everything that needs to be considered when creating reverse edges:

- The trust amount of some edges exceeds the maximum trust amount of the path that will be found. I.e. `60` vs. the overall path amount of `40`.
- An intermediate delegation (`C1 -> C2`) has a higher trust depth than a previous delegation (`TA1 -> C1`). I.e. a depth of `100` preceded by a depth of `5`.
- An intermediate delegation (`C2 -> C3`) has a much lower depth than its previous delegations.

![Reverse Edges - Example with reverse edges](../Diagrams/figures/Berblom/Creating-Reverse-Edges_simple_reverse.svg)

The only possible path that can be found is `P1: TA1 -> C1 -> C2 -> C3 -> Target` with a trust amount of 40.

- `t:X` means a trust amount of `X`.
- `d:Y` means a trust depth of `Y`.
- `pZ` is the unique ID of the path that created this reverse edge. More on that later.

> **Note** Most of the paths in Berblom are looked at backwards, as a backwards BFS is performed.
  For the creation of reverse edges, however, it's necessary to look at paths in the forward direction.

The reverse edges are created by walking through the path in a forward direction, while also adjusting forward edges.

- `TA1 -> C1` (Red dotted arrow)
    - The trust amount of `40` is subtracted from the forward edge, resulting in `t:20-d:5`.
    - Create the reverse edge with:
        - A trust amount of `40` (the amount of the path)
        - The association to `P1`, as the reverse edge was created by the first path that has been found.
        - An unlimited trust depth.
          The reasoning for this is as follows: Trust Anchors may also act as intermediate nodes if their trust is limited.
          If one were to reroute trust through this reverse edge, one would end up at the very source of the path that created this reverse edge.
          The purpose of trust depths on reverse edges is to uphold the depth constraints of the original path `P1` that created this reverse edge.
          Since we reached the source of that path, there are no constraints to consider, hence we have an unlimited trust depth.
- `C1 -> C2` (Yellow dotted arrow)
    - The trust amount of `40` is subtracted from the forward edge, resulting in `t:0-d:100`.
    - Create the reverse edge with:
        - A trust amount of `40` (the amount of the path)
        - The association to `P1`
        - A trust depth of `5`.
          The reasoning for this is as follows: When exploring the network from the back during the BFS, using this reverse edge effectively simulates what would happen if the trust from `TA1` were re-routed from `C1` onward.
          Since it simulates the redirection from `C1`, the same trust depth constraints of `C1` apply.
- `C2 -> C3` (Green dotted arrow)
    - The trust amount of `40` is subtracted from the forward edge, resulting in `t:20-d:2`.
    - Create the reverse edge with:
        - A trust amount of `40` (the amount of the path)
        - The association to `P1`
        - A trust depth of `4`.
          The same logic as on `C1 -> C2` applies.
          We use the trust depth constraints of the source node `C2`, which is the constraint of `C1` (`5` minus `1` for one hop).
- `C3 -> Target` (Blue dotted arrow)
    - The trust amount of `40` is subtracted from the forward edge, resulting in `t:0-d:1`.
    - Create the reverse edge with:
        - A trust amount of `40` (the amount of the path)
        - The association to `P1`
        - A trust depth of `2`. The same logic as on `C2 -> C3` applies.
          We use the trust depth constraints of the source node `C3`, which has been restricted by the trust depth constraint on the delegation `C2 -> C3`.
