[cstone]

To expand on the first part: with something up front saying "this key is signed using system FOO", you'll be able to support multiple systems in the future. This means that you'll be able to handle multiple systems (and upgrades) easily.

[sethg]

If the server can handle keys that are signed by either system FOO or system BAR, and the keys themselves don’t provide any clue about how they were signed, the server can just try to verify the signature using FOO and, if that system doesn’t return a “signature valid” response, fall back to BAR.

Obviously if you’re permitting ten different signature-verification algorithms then this technique starts putting a significant load on the server, but if your protocol allows for ten different signature-verification algorithms, then you have bigger problems, right?