Problematic delegation walk restriction during "update the targets role" step

[cyphar]

s5.6.7.1 of the specification reads (after some trimming):

Perform a pre-order depth-first search for metadata about the desired target, beginning with the top-level targets role. [...] If this role has been visited before, then skip this role (so that cycles in the delegation graph are avoided). [...]

A plain reading of this implies that throughout the entire depth-first search you cannot walk into the same delegation more than once even via different delegation chains. For instance, if there was a delegation from targets to roleA to roleB and a later delegation from targets to roleC to roleB then a plain reading would imply that the second delegation to roleB should be skipped because "[the] role has been visited before".

I noticed this a few months ago and it is how go-tuf/v2 currently implements the behaviour so I figured this was a TUF quirk we would need to work around for our usecase, but after speaking to @JustinCappos recently it seems that this is not the intended meaning of the sentence. Instead the intention was to stop a delegation chain delegating to some role already visited in that branch (for instance, roleA delegating to roleB delegating to roleA which would lead to a cycle) -- which explains the mention of cycles.

The current wording is quite problematic for a few reasons, as it makes large repositories with delegations controlled by different users (with different trust levels) quite fragile (a user earlier in the chain than you can cause your delegations to fail silently) and it also makes implementing features like listing all available targets in a repository very complicated (as it would require emulating this behaviour for later delegations and potentially computing inverse matches rather than treating each branch on its own).

I'd propose the wording be changed to clarify the expected behaviour. As a very rough proposal, something more like:

 7. **Perform a pre-order depth-first search for metadata about the
-  desired target, beginning with the top-level targets role.** Note: If
+  desired target, beginning with the top-level targets role**, taking note
+  of the delegation path taken when walking into each role.
+  Note: If
   any metadata requested in steps 5.6.7.1 - 5.6.7.2 cannot be downloaded nor
   validated, end the search and report that the target cannot be found.

-  1. If this role has been visited before, then skip this role
-     (so that cycles in the delegation graph are avoided).  Otherwise, if an
+  1. If this role has been visited before in the delegation path used to reach
+     this role, then skip this role (so that cycles in the delegation graph are avoided).
+     Otherwise, if an
      application-specific maximum number of roles have been visited, then go to
      step [[#fetch-target]] (so that attackers cannot cause the client to waste excessive
      bandwidth or time).  Otherwise, if this role contains metadata about the
      desired target, then go to step [[#fetch-target]].

(Line breaks broken on purpose to keep the diff readable.)

[joshuagl]

Thanks. I like the suggestion as it does indeed improve clarity.

Prior to landing this change we might want to reach out to maintainers of known implementations (go-tuf, python-tuf, rust-tuf, tough, php-tuf, ???) to see if they want to update their implementations.