The official GnuPG documentation regarding this output is rather awkward.
The OpenPGP trust model
gpg: 3 marginal(s) needed, 1 complete(s) needed, PGP trust model
By default, GnuPG uses the OpenPGP trust model. In this, you can put trust on a key, which allows it to validate other keys.
Trusted Keys
Keys can be trusted. Trust allows keys to validate other keys. Although trust is a kind of signature on other keys, it does not get distributed when uploading keys to key servers.
There are different trust levels:
- No ownertrust assigned / not yet calculatede Trust calculation has failed; probably due to an expired keyq Not enough information for calculationn Never trust this keym Marginally trustedf Fully trustedu Ultimately trusted
(taken from the GnuPG manual, chapter key management)
Mostly important are the last three categories: your own keys are ultimately trusted; fully trusted keys' signatures are regarded equally worth your own ones; while marginal trusted keys require more signature paths to make a key valid.
Valid Keys
In the default OpenPGP trust model, a key is fully valid if:
- it is signed by enough valid keys, meaning
- you have signed it personally,
- it has been signed by one fully trusted key, or
- it has been signed by three marginally trusted keys; and
- the path of signed keys leading from K back to your own key is five steps or shorter.
(taken from the GnuPG manual, chapter 'Validating other keys on your public keyring')
Other keys are marginally valid; showing there is a trust path, yet it is not strong enough. I highlighted the word "valid" in the quote above: only fully valid keys' trust is taken in account for calculating validity! In GnuPG, the default trust model can be configured.
The manual page linked directly above also contains some examples for trust calculation, but watch out for the non-default trust model applied for simplicity!
GnuPG's Trust DB Information
This information gets printed whenever the trust database gets updated, for example after receiving them from a key server.
gpg: depth: 0 valid: 1 signed: 16 trust: 0-, 0q, 0n, 0m, 0f, 1u
gpg: depth: 1 valid: 16 signed: 115 trust: 1-, 1q, 1n, 1m, 12f, 0u
gpg: depth: 2 valid: 105 signed: 189 trust: 81-, 11q, 0n, 4m, 9f, 0u
gpg: depth: 3 valid: 29 signed: 120 trust: 19-, 9q, 0n, 0m, 1f, 0u
This output describes your web of trust. The letters represent the trust levels listed above. On level 0, you will find your own (ultimately trusted) keys. There should not be any other kind of trust on this level. This key is valid (of course).
The further output represents my interpretation which is not based on reading the (missing) documentation nor the source code: You signed 16 keys, making all of them fully valid on level 1. For 12 of them you issued full trust, one of them only marginal. Those again lead to another 105 valid keys you trust on level 2. Some of them are trusted again, leading to another 29 valid keys in level 3.
Comparing this output to what the keyservers tell, you should probably update your keyring. ;)
More trusted keys in deeper levels could create the levels 0-5 if you do not change the maximum path length of five proposed by OpenPGP's trust model.
Werner Koch, the main author of GnuPG, once stated on the GnuPG mailing list:
You would need to look at the source. However, if you known the WoT well, you should be able to figure out what this is. [...] You should consider this a debugging output.
