I think there's a reasonable compromise of embedding the key id of the primary key, but shipping the subkey completely.

This way we lose the ability for checking total consistency without public keys present; but we have the technological requirement you want for the user to trust the primary key (and no way to construct it from the signature).

We discussed the signature format in great detail, and looked at multiple options:

  Ed25519-Signatures:
   base64<sig1>
   base64<sig2>

  Signatures:
    ed25519:base64<sig>

  Signatures:
    ed25519 base64<sig>

  Signatures:
    base64<ed25519 | sig>

The first option was rejected by people for reasons I can't remember, and the next 2 are equivalent, albeit the one with : is easier to copy-paste (who does that for an apt signature?).

The last one we did not like because it made the code more complex because we'd have to decode to a buffer first and then copy into the appropriate struct; and also because it's not clear from looking at the plaintext which algorithms it has been signed with.