[apenwarr]

Why do you need automatic fallback? You simply define in the config file, for each peer, which protocol version to use. Then it's up to the config file distribution process - whatever it is that you do - to make the appropriate version settings, at the exact same time as they set up the public keys. The essential thing is that each peer has a fixed expectation of the security to use, rather than trying to negotiate it on the wire, which leads to downgrade attacks.

[Disclosure, I'm a Tailscale co-founder] ...and if you use Tailscale, it takes responsibility for the key exchange part. So we can tie protocol version settings to long-term state (eg. ratcheting up versions for each old node; not letting new nodes use old versions at all).