# Data structures for OpenPGP Web of Trust calculations
This library offers very generic data structures for modeling OpenPGP Web of Trust graphs.
See <https://codeberg.org/openpgp/wot> for more context.
## Nodes
This WoT model distinguishes two different types of nodes:
- **certificates** (which represent an "OpenPGP certificate / public key") and
- **bindings** (which represent the relation between a certificate and an identity).
## Edges
In this WoT model, two types of edges connect nodes:
- **certifications** (which always point from a certificate to a binding) and
- **delegations** (which always point from a certificate to another certificate).
### "Amount" value on all edges
Each edge in a WoT network has an associated "amount" which quantifies how much this edge can be "relied on". The amount represents a flow capacity of that edge. Each individual "amount" in a WoT network graph is limited to a maximum value of 120 (this value is a convention in OpenPGP, it models "full trust").
Note that almost all uses of "amount" values in OpenPGP WoT are limited to a maximum value of "120", including the amount of reliance that is assigned to trust anchors.
(However, there is one context in which larger "amounts" can occur: WoT path searching can yield a set of paths, starting from multiple different trust anchors, all leading to the same target binding.
While each individual path is limited to a maximum amount of "120", the sum of the "amounts" of multiple independent paths can exceed 120. Such a set of paths quantifies independent evidence for the validity of the target binding.)
### "Depth" value on delegation edges
Besides the "amount", delegation edges have an additional value: a "depth".
The depth value signifies how many hops the issuer is willing to follow a path.
A value of "1" means that the issuer of the delegation only wants to rely on certifications that were made directly by the target certificate.
A value of "2" means that the issuer is willing to additionally rely on certifications that involve following a second delegation edge, before the final certification edge that points at a binding node.
## Example WoT network graph:
```mermaid
flowchart TD
A -->|120/1| B
B -..->|120| b0
A -..->|120| b0
b0([B, bob])
A -..->|120| b1
b1([A, alice])
classDef bind stroke-dasharray: 5 5
class b0,b1 bind;
```
This graph shows:
- Two "certificates" `A` and `B`, shown as rectangular boxes. These represent "OpenPGP certificates (or public keys)".
- Two "bindings", shown as rounded boxes. A "binding" is a (claimed) connection between a certificate and an identity: `A` is linked to the identity `alice`, while `B` is linked to the identity `bob`. The identities (`alice` and `bob`) correspond to "OpenPGP User IDs".
- Three edges that represent "certifications", shown as dotted lines. A certification is a statement by the issuer that they consider a binding to be valid. In this network, `A` and `B` are certifying their own identity bindings respectively (`A` certifies her connection to the identity `alice`, and `B` his connection to the identity `bob`). Additionally, `A` certifies the binding between `B` and `bob`.
- One edge that represents a "delegation", shown as a solid line. With it, `A` delegates authentication decisions to `B`.
Note that each edge (both certifications and delegations) have an associated "amount", in this case it is "120" on all edges.
Only the delegation edge has a second, additional, "depth" value. Here, the "depth" value on `A`'s delegation to `B` is 1 (which means that`A` is willing to rely on certifications issued by `B`, but not willing to rely on additional delegations by `B`).
## Limiting delegations with regexes
Delegation edges can have "regex" constraints. A regex on a delegation edge constrains the identities that may be authenticated along any path that uses this edge.
Typically, regexes limit the domain name part of a target identity. E.g. a delegation edge may only allow identities in the domain "example.com".
If a delegation edge has any "regex" constraints, then at least one of these regexes must match the target identity, so that the delegation edge is valid in that context.
In a multi-step path, each delegation edge that applies regex constrains (that is, each delegation edge that has one or more regexes set) must have one regex that matches the identity in the target binding. Concretely: if the target binding is an identity in "example.org", then each delegation edge that has one or more regex constraints must have one regex for "example.org", otherwise that path is not valid.
### Example for a regex constraint
In the following diagram, `A` delegates to `B`, with amount 120, depth 2, and a regex limiting target identities to the domain "example.org". This means that any path starting from `A` and going through `B` can only lead to binding nodes with an identity under the domain "example.org".
```mermaid
flowchart TD
A -->|120/2/example.org| B
B -->|120/1| C
C -..->|120| b0
C -..->|120| b1
b0([C, carol\@example.org])
b1([C, carol\@other.org])
classDef bind stroke-dasharray: 5 5
class b0,b1 bind;
```
Because of the regex constraint, when starting from `A`, only the path that leads to the binding `<C, carol@example.org>` is valid.
The delegation by `A` is saying "I am willing to rely on `B`, but only for identities under example.org". One reason for this could be that `B` is a representative of the organization "example.org", and `A` is willing to rely on `B` to authenticate identities within their own organization.
However, the binding `<C, carol@other.org>` cannot be validated via the delegation edge from `A` to `B`.
Note that the regex constraint doesn't deal with any identities that might be associated with `B`. Regex constraints only apply to identities in a target binding.