I didn't mean to suggest that switching to sqlite was the only way to fix this, but if it is a promising way to fix it, that would be great. I'm sure there are other ways.

Please help me understand why this is not an option for large keyrings. Is it a performance concern? something else?

The current behavior appears to be pathologically bad for arbitrary certificates for anyone, even for people who only access the keyring for reading, and who do it without contention. The above read-only --list-keys test was done without any contention for the keyring and it still took 30s to produce < 1KiB of output from a 17MiB file.

Verifying a git tag from the "clean" version of this certificate takes ~225ms of CPU time. Verifying the same git tag from a keyring that contains the flooded version of the certificate takes ~145s. This is factor of more than 600×. Any automated git tag verification system can probably be DoSed by this behavior.

Just importing a ~666KiB certificate when this monster certificate is in the keyring consumes over 10m of CPU time:

0 dkg@alice:/tmp/cdtemp.7QJ3xD/monkeysphere$ time GNUPGHOME= gpg --export  CCD2ED94D21739E9  | gpg --import
gpg: key CCD2ED94D21739E9: 1391 signatures not checked due to missing keys
gpg: key CCD2ED94D21739E9: public key "Daniel Kahn Gillmor <dkg@fifthhorseman.net>" imported
gpg: Total number processed: 1
gpg:               imported: 1
gpg: no ultimately trusted keys found

real	10m28.703s
user	7m20.467s
sys	3m8.147s
0 dkg@alice:/tmp/cdtemp.7QJ3xD/monkeysphere$

@gniibe: I doubt that your fix really makes a difference. The majority of time is spend on searching the keyring for keys. This is why I have the gpgk thing in the works.

@gniibe -- thank you very much for tracking down these O(N^2) operations and cleaning them up. I will profile the effect of those changes and report my findings.

(i think that rG33c17a8008c3ba3bb740069f9f97c7467f156b54 is also relevant, though it was not tagged with this ticket)

For the particular problem of --list-key with pubring.gpg, I think we can say it's fixed.

fwiw, i tried gpg --import on the ascii-armored version of my C4BC2DDB38CCE96485EBE9C2F20691179038E5C6 OpenPGP certificate (22895014 octets, 54614 certifications), followed by gpg --list-keys and gpg --export | wc. I was comparing 2.2.17-1 (from the debian package in unstable) with the exact same source, just with @gniibe's two patches rG33c17a8008c3 and rGa7a043e82555 applied as well. I did this with GNUPGHOME set to an otherwise empty directory, where i had done touch pubring.gpg to avoid the keybox format. (the two runs did not share a GNUPGHOME).

Without @gniibe's patches:

$ time gpg --import < ../flooded.key
[…]
real	11m4.620s
user	8m4.156s
sys	2m58.155s
$ time gpg --list-keys
[…]
real	0m34.855s
user	0m34.781s
sys	0m0.069s
$ time gpg --export | wc
 116411  424952 16934775

real	0m37.866s
user	0m37.864s
sys	0m0.097s
$

but with @gniibe's patches:

$ time gpg --import < flooded.key
[…]
real	8m53.788s
user	5m50.769s
sys	2m58.636s
$ time gpg --list-keys
[…]
real	0m0.178s
user	0m0.151s
sys	0m0.028s
$ time gpg --export | wc
 116411  424952 16934775

real	0m1.801s
user	0m1.834s
sys	0m0.076s
$

So there is still some significant delay in --import, but @gniibe's patches even shave off ~25% of the CPU time in that case. And they remove a significantly more for CPU usage for --list-keys and --export (apparently > 90% of the CPU time).

Is there any reason that we shouldn't apply these patches to the STABLE-BRANCH-2-2 as well? The tests all appear to pass.

i also checked the CPU time for git tag -v, whether @gniibe's patches were applied or not.

without the patches:

real	2m16.258s
user	2m16.114s
sys	0m0.143s

with the patches:

real	0m0.680s
user	0m0.598s
sys	0m0.083s

So this is a huge win.

Okay, for 100000 signature this is clearly a win if no key lookup is needed.

with @gniibe's patches applied, i profiled the --import, since that is where the largest CPU cost remains. I tried two different times:

• importing into an empty pubring.gpg, which cost ~10 minutes of CPU time:

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 23.63     74.27    74.27 1671939985     0.00     0.00  parse
 22.16    143.93    69.66   191186     0.00     0.00  check_signature_over_key_or_uid
 21.19    210.55    66.62 2983453616     0.00     0.00  walk_kbnode
 21.15    277.03    66.48    54621     0.00     0.00  find_prev_kbnode
  4.60    291.49    14.46 1672049220     0.00     0.00  iobuf_skip_rest
  2.74    300.10     8.61   273083     0.00     0.00  dbg_search_packet
  0.79    302.59     2.49        1     2.49     2.49  iobuf_get_fd

in this case, the 2.9G invocations of walk_kbnode is almost exactly 54614^2, so i suspect that another O(N^2) operation exists there.

• importing into the same keyring a second time (with the certificate already present), which still costs about 30 seconds:

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 83.01     15.73    15.73        1    15.73    18.86  import_one_real
 12.98     18.19     2.46 745754172     0.00     0.00  cmp_signatures
  0.74     18.33     0.14       13     0.01     0.01  cmp_public_keys
  0.69     18.46     0.13     2069     0.00     0.00  radix64_read
  0.69     18.59     0.13   163900     0.00     0.00  read_rest
  0.42     18.67     0.08   109244     0.00     0.00  sig_comparison
  0.26     18.72     0.05   313643     0.00     0.00  iobuf_read_line

The speed here is much better, but still 30s to import something that we already have is expensive. And 745M signature comparisons seems much more than there would be if the signatures were well-indexed.

A linked list of 100000 items is not a usable data structure. The problem however is not the linked list but the DoS due to the number of signatures being well beyond the design limit. 1000 key signatures is already a large number and only few people have them. We need to put a limit on them.

About importing, there are two other works: repairing and trustdb update. We can figure out the difference by the --import-options of no-repair-keys and fast-import (to skip those works).
I think that both can be O(N^2) for number of signatures.

@gniibe, the documentation (at least on the stable branch) says that --fast-import is just a synonym for --import. is that incorrect?

@werner, I agree that having some limits put in place is not unreasonable, but i wonder how we manage those limits, especially over time and as different certifications come to light. If i encounter 500 certifications for a given certificate today, and a different set of 500 certifications tomorrow, and i'm only willing to retain, say, 250 certifications, how should i decide which ones to keep? is there some ranking or prioritization? or just first-come, first-served? These are pretty complicated tradeoffs, and potentially ultimately user-interface questions. and it would be good to try to document how we think they should work, even if we haven't got them implemented yet.

I am proposing to backport rG33c17a8008c3ba3bb740069f9f97c7467f156b54 and rGa7a043e82555a9da984c6fb01bfec4990d904690 to STABLE-BRANCH-2-2 as they represent a significant performance improvement in several specific use cases and appear to have no downsides.

Is there any reason to not do that?

@gniibe, thank you for backporting this to STABLE-BRANCH-2-2!

Is this resolved?