I'm wondering how that would play out with attenuation, where a new signature has to be made. Here are the possible scenarios:

• the signing algorithm can change on every block (ECDSA on one, Ed25519 on the next, etc). We would need a way to signal which algorithm should be used for the next signature (since the previous block chooses the key pair), and which algorithms should be used to verify each block, otherwise we'd try to verify a signature on P256 with the Ed25519 algorithm(are there possible issues when confusing curve algorithms there?). Unless there's a way from looking at the keys or signature to guess which kind they are?
• the signing algorithm is the same for the entire token. We still need a way to signal it. It can be done with a field like the root key id. That field does not need to be signed: the verifier could check that it matches the chosen root key

Apart from that field, the format would not change, keys and signatures are just byte arrays.

About the implementaton mistakes, do you think we can mandate the safer ways to sign?

I would suggest parameterizing each key with its algorithm, and leaving the signature itself opaque. The signature either verifies under a given key with a known algorithm or it doesn't.

As to whether or not you allow mix-and-match algorithms I could go either way. It seems useful in things like X.509 certificate chains to be able to use different signing algorithms, so for example you can upgrade CA certificates to new algorithms without all of their clients having to upgrade, and I suspect there are similar potential use cases here.

About the implementaton mistakes, do you think we can mandate the safer ways to sign?

The best I can suggest is documenting something to the effect of "Signers SHOULD use RFC6979 to select ECDSA ephemeral scalar k". You can also provide test vectors based on deterministic RFC6979, and mandate particular curve/digest combinations (e.g. ECDSA/P-256 w\ SHA-256, ECDSA/P-384 w\ SHA-384)

The problems with making RFC6979 a MUST are that if you want to support hardware tokens, they won't necessarily use RFC6979. Fully deterministic signature algorithms are problematic for hardware tokens due to fault attacks, so ones using RFC6979 would be best off supplementing it with added entropy. A fault attacker who is able to cause the device to produce the same k scalar for two different signatures can algebraically solve for the private key.

There's also no way for a verifier to check how k was selected, so it's really a "best practices" thing.

alright, it's starting with f38c856
I'll try to integrate new algorithms next