Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Clarify client traversal of role delegation graph #177

Open
ethan-lowman-dd opened this issue Jul 20, 2021 · 7 comments
Open

Clarify client traversal of role delegation graph #177

ethan-lowman-dd opened this issue Jul 20, 2021 · 7 comments

Comments

@ethan-lowman-dd
Copy link

ethan-lowman-dd commented Jul 20, 2021

Spec v1.0.19 Section 5.6.7 describes how the client should traverse the delegation graph to update the targets role. The wording on cycle avoidance could use some clarification.

The spec says:

If this role has been visited before, then skip this role (so that cycles in the delegation graph are avoided)

A "role" in this context could either refer to 1) a delegated role (a node in the delegation graph) or 2) a role entry in the roles array of the DELEGATIONS object, which represents not a role, but a delegation from one role to another (a directed edge in the delegation graph).

As a result, there are two ways the traversal could be interpreted:

  1. As we're traversing the delegation graph, skip nodes (roles) that have already been visited. This avoids visiting any one role twice, and produces the most intuitive pre-order traversals for graphs where some nodes have multiple parents (i.e. when the graph is not a tree). However, it's not true cycle detection and we may actually want to consider every edge, since different edges leading to the same role may represent different conditions of delegation (e.g. different keys, different paths, etc.).
  2. As we're traversing the delegation graph, skip edges (delegations) that have already been visited. This follows the typical definition of cycle detection. However, it produces counter-intuitive "pre-order" traversals for graphs that aren't trees, and this interpretation is not obvious from the wording in section 5.6.7.

Below are two concrete examples.

Example A:

Interpretation Traversal
1: skip visited nodes A, B, D, C
2: skip visited edges A, B, D, C, D

Example B:
(assume B's outgoing edges/delegations are ordered as [A, D]

Interpretation Traversal
1: skip visited nodes A, B, D, C
2: skip visited edges A, B, A, C, D

cc: @trishankatdatadog

@ethan-lowman-dd ethan-lowman-dd changed the title Clarify traversal of role delegation graph Clarify client traversal of role delegation graph Jul 20, 2021
@trishankatdatadog
Copy link
Member

I think in the more general case (especially multi-role delegations), you want to avoid delegations you have seen before.

So, in the typical single-role delegation case, that means you want to avoid roles you have seen before.

Even in the multi-role delegation case, you want to avoid the exact combination of roles (i.e., AND of thresholds of public keys) you have seen before, and even that can broken down into single roles (i.e., if you have seen a rolename before, even if it is being delegated a different threshold of different public keys now, you know can you avoid it because you clearly haven't found what you were looking for).

Did I miss anything @mnm678?

@mnm678
Copy link
Collaborator

mnm678 commented Jul 21, 2021

This is a good catch, and certainly something that we should clarify.

I agree with @trishankatdatadog. We want to avoid visiting the same node multiple times so that roles don't accidentally get added multiple times to a threshold, etc.

While TUF does not actually require delegations to be a tree, in most cases they will be. Further, delegators are aware of TUF semantics, and can, for example, create a new role with some similar keys if for some reason this role needs to exist at multiple levels of the graph.

@joshuagl
Copy link
Member

The legacy client in the reference implementation keeps a set() of visited role names and skips any role name (node) that it has visited before. See _preorder_depth_first_walk() in tuf/client/updater.py.

@raphaelgavache
Copy link

raphaelgavache commented Jul 22, 2021

On the new ngclient _preorder_depth_first_walk keeps a set of edges: (node, parent_node) any skips visited edges.
Do you know why it was implemented differently?

@trishankatdatadog
Copy link
Member

(i.e., if you have seen a rolename before, even if it is being delegated a different threshold of different public keys now, you know can you avoid it because you clearly haven't found what you were looking for)

I should clarify: my statement is true for some role X that you have visited alone (i.e., a single-role delegation) before seeing it later as part of a multi-role delegation. OTOH, it is not true if you visited X as part of some multi-role delegation earlier, before encountering it again later in some new multi-role delegation...

@joshuagl
Copy link
Member

joshuagl commented Jul 22, 2021

Thank you for the detailed issue @raphaelgavache!

Apologies all for the noise of the drive-by comment earlier, I wanted to some implementation examples and submitted before the comment was complete.

On the new ngclient _preorder_depth_first_walk keeps a set of edges: (node, parent_node) any skips visited edges.
Do you know why it was implemented differently?

I believe a new set of contributors drew different conclusions from the specification, further indicating the need to clarify this part of the detailed client workflow.

I'd certainly defer to @trishankatdatadog and @mnm678 here, but I my current understanding is in agreement with the ngclient authors conclusion (and yours, I believe, @raphaelgavache) that we should skip visited delegations/edges not visited roles/nodes.

@jku
Copy link
Member

jku commented Aug 23, 2021

I'd certainly defer to @trishankatdatadog and @mnm678 here, but I my current understanding is in agreement with the ngclient authors conclusion (and yours, I believe, @raphaelgavache) that we should skip visited delegations/edges not visited roles/nodes.

I can see the different potential approaches but I'm considering reverting this decision in ngclient:

  • the current spec language still seems pretty clear "If this role has been visited before, then skip this role"
  • I'd rather we do the same thing that the old client does unless we have a good reason

So I think I'll propose changing that (thanks raphael for pointing that out). If anyone has opinions, please -> theupdateframework/python-tuf#1528

ivanayov pushed a commit to ivanayov/python-tuf that referenced this issue Nov 18, 2021
This change edits the ngclient `Updater` to traverse the delegation
tree on nodes, instead of edges in order to skip already visited
nodes.

For more detailed clarification, please review
theupdateframework/specification#177

Fixes theupdateframework#1528

Signed-off-by: Ivana Atanasova <iyovcheva@iyovcheva-a02.vmware.com>
ivanayov pushed a commit to ivanayov/python-tuf that referenced this issue Nov 18, 2021
This change edits the ngclient `Updater` to traverse the delegation
tree on nodes, instead of edges in order to skip already visited
nodes.

For more detailed clarification, please review
theupdateframework/specification#177

Fixes theupdateframework#1528

Signed-off-by: Ivana Atanasova <iyovcheva@iyovcheva-a02.vmware.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

6 participants