Managing the WoT with GPG

[Peter Lebbing]

On 22/06/17 15:00, martin f krafft wrote:
> As far as I understand, the parameters --marginals-needed and
> --completes-needed can be used to define a maximum search depth D,
> so when I ask GPG to update the trustdb WRT key 0xdeadbeef, then I'd
> envision it to

Don't you mean

>        --max-cert-depth n
>               Maximum depth of a certification chain (default is 5).

? I don't see how --*-needed would limit the search depth, other than
that for an actual keyset increasing them would effectively probably
decrease the actual depth.

While in general there are probably many avenues to be more efficient
about --check-trustdb, introducing too much complexity raises the
likelihood of bugs, especially if you start to intelligently update
trust by partial traversal.

Perhaps it would already be enough to split it into three phases:

1) Consider every key signature potentially valid. Construct the graph
of signatures. Discard anything that is not rooted in an ultimately
trusted key.

2) Still assuming correctness of key signatures, now consider
ownertrust. Remove any key that clearly does not have enough trust from
further computations (but leave in place all edges in the graph of the
remaining keys).

3) Start at the ultimately trusted keys and consider each signature that
corresponds to an edge going out of a valid key. Check signatures until
full validity of a key is reached (or all signatures on a key have been
checked). Stop checking then; it can't become more than fully valid by
more signatures. The fact that a key has been added to the valid keys
means you now have more edges going out from a valid key; keep repeating.

When a key fails to become valid in 3), you could consider the criteria
of 2) again and prune some keys from the graph, but it might be
over-optimizing. Without it it might already be plenty quick.

I don't know what the current algorithm is, but given its runtime, I'm
thinking it might be "check all signatures that can be checked" followed
by "now propagate validity through ownertrust". In my sketched proposal,
a *lot* of signatures would probably remain unchecked because they can't
further affect the validity of a key.

HTH,

Peter.

-- 
I use the GNU Privacy Guard (GnuPG) in combination with Enigmail.
You can send me encrypted mail if you want some privacy.
My key is available at <http://digitalbrains.com/2012/openpgp-key-peter>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: OpenPGP digital signature
URL: </pipermail/attachments/20170622/7519260e/attachment.sig>