Several issues are related to this, including at least: #589, #646, #658, #736, spec issue 19.

Summary

The reference implementation continues to try to provide a 1-to-1 mapping of roles to keyids-the-role-should-be-signed-by-in-order-to-be-valid. This is not correct: the same role may need to be validated expecting different sets of keys, based on how the role was reached in the depth-first search while looking for target information.

The bottom line here is that code should be rewritten in places like roledb, to avoid things like get_role_keyids(), or roleinfo['threshold'] or roleinfo['keyids'], etc.

Detailed explanation

I think this all comes from a deeper issue:

Per the design of TUF, roles and delegations should never be regarded as the same thing. While in the last few years, there have emerged a few additional reasons that this separation is important (TAPs 3's multi-role delegations and TAP 5's alternative repository roots, for example), my understanding of the design history is that there was not originally an expectation of a one-to-one mapping of roles to delegations pointing to them.

So let's be pedantic:

• A role is not the same thing as a delegation: a delegation is a relationship between two roles.
• A delegation is a property of the delegating role, not the delegated-to role.
• Therefore, for delegated roles, key IDs and thresholds are properties of a delegation, not properties of the delegated role.
• You cannot simply map delegated roles to the keyids that validate them: you must map keys to delegations (that is, delegator + delegatee, if we're assuming no parallel edges in the graph (which, btw, are we?)).

The graph of delegations used to be guaranteed -- in the reference implementation -- to be a simple directed graph where Root is a node with an indegree of 0 and all other nodes have an indegree of 1. I.e.: No roles delegate to Root. Root delegates to Targets. Targets can delegate to various roles, but two or more roles never delegate to the same role. The design intention, however, did not guarantee maximum indegree of 1: in the design, delegations could be promiscuous: a single role can be delegated to by multiple roles.

A result of this confusion is that roledb still represents roles as flat in certain ways, when it should not assume this. This flatness resulted in #589, #658, #736, probably #646, and presumably other forgotten issues.

Take the function roledb.get_role_keyids() as an example: get_role_keyids takes only the name of a role (and a repository name), purporting to return the keys that that role should be signed by. The trouble, though, is that different roles delegating to that role can expect different keys and validate or reject role C's target information based on those different expectations.

Specification / Avoiding Future Issues

The spec itself should be a bit clearer -- see spec issue 19 -- about this, to help prevent these issues from arising in implementations. We may also need materials elsewhere to make the role/delegation distinction clearer. When editing the metadata formats in TAPs and the like, I've tried to make sure not to reinforce this confusion (mixing roles and delegations), and we should be mindful in that way, too.

As a sidenote, note that parallel edges would also cause this issue, not just promiscuous delegations from different origin nodes -- any role with indegree > 1 would have been an issue.