@simo5 @neverpanic @soatok this is one of my pet peeve rants: we have signature formats. (Several of them, even). Cryptographic standards define functions that map a collection of byte strings to some other byte strings. Files can store byte strings. What we are somewhat lacking is fully specified public key formats, but even that we have some (Tink defines it's own and can read/write many of the existing formats). The signature should just be the byte string given as the output of the signing algorithm. It's the public key that needs the information for verifying the signature.
So if I give you a public key (including a definition of the full algorithm used, all the hash functions and security parameters etc), then you can verify a signature.
If you want crypto agility, then the thing you need is support for key sets, i.e. multiple, equally trusted keys. That allows you to add, promote, and delete keys in a distributed environment. You have two options for the signature format in this case (and Tink supports both): either you keep the unmodified signature, try all public keys and call the signature verified if it verified under one of the public keys (great for comparability), or you put a short and meaningless identifier in front of the signature, which allows you to directly jump to the right public key. Better performance, but not compatible with libraries that don't support key sets in the same way.
In both cases, this composite algorithm retains EUF-CMA/SUF-CMA as long as all keys in the key set are trusted and have EUF-CMA/SUF-CMA.
Interestingly, pretty much all other types of signature formats, such as JWT (and as far as I know PGP) violate EUF-CMA and definitely violate SUF-CMA, so I argue (fairly strongly, given all the attacks due to these violations), that the Tink way of supporting key sets and signatures is the correct approach.