theupdateframework / theupdateframework/specification

Clarify client traversal of role delegation graph

Open
#177 7 comments 4 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Python
Stars
405
Forks
59
Avg merge
3d 4h
Merged PRs (30d)
1

Description

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

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with Spec v1.0.19, Section 5.6.7, and compare its cycle-avoidance wording with Examples A and B. Resolve whether traversal tracks visited roles or delegations, then clarify the section so the intended behavior for shared nodes, cycles, and delegation conditions is unambiguous.

Written by the indexing model from the issue text.

Assessment

Domain
documentation
Issue type
Documentation
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.