bips
bips copied to clipboard
sipa
BIP340: clarify impact of pre-hashed messages, or support variable-length messages
Context: https://github.com/bitcoin-core/secp256k1/pull/558#discussion_r457281893
Right now, BIP340 specifies that imputs are strictly 32-byte messages. This implies that for typical use cases, the message needs to be pre-hashed, and the GGM/rpp/rpsp proof doesn't exactly apply (collision resistance is required too). This is fine for our intended use case, as the message contains inevitable hashes anyway (the signature data contains the txid of outputs being spent), and thus indirectly the security is already based on collision resistance.
Apart from that, there are few technical reasons to not support variable length messages (which in some cases might not have this problem) instead, as the message is always the last input to a hash function anyway.
So we should either:
- Explain the choice for 32-byte messages, and the effect on the security assumption that implies.
- Support variable-length messages, explaining that the lack of reliance on collision resistant only really holds if the message doesn't contain any hashes itself.
Or you should do both. The choice of 32 bytes messages is the one in Bitcoin and isn't going to change, in particular to gain from not prehashing you'd totally break all sighash cache, so it is by no means a free choice.
However, in other applications that don't have that sighashing tradeoff, aren't hashing messages that substantially consist of hashes, I think non-prehashing is clearly preferable. (E.g. if we used SHA1 a non-prehashing version would still be apparently secure now, while a prehashing version would be actually broken).
So I think instead it wouldn't be a problem to say non-prehashing is a variation that an implementation could validly accept but that it isn't used in Bitcoin.
@gmaxwell Right; of course, that's what I meant by the second option. Just because BIP340 is adapted to support variable-length messages doesn't mean that its use in BIP341 would change.
This is fine for our intended use case, as the message contains inevitable hashes anyway (the signature data contains the txid of outputs being spent), and thus indirectly the security is already based on collision resistance.
A thought crossed my mind when I read this: What about ANYPREVOUT? If you don't sign the input txids and don't hash the other data before signing it then perhaps you could avoid CR altogether as a requirement assuming ANYPREVOUT becomes the default spend (for key spend as well as taproot spend). This doesn't seem to be a silver bullet though because there is always a duplicate txid attack where the attacker who controls some of the data that determines a joint tx can create another one with the same id and broadcast it first making the first one invalid surreptitiously. For example you could create a collision with the other party's HTLC timeout transaction to stop it being broadcasted (no signature forgery needed). There may be clever ways around this like making sure only the refunding party fully decides the timeout transaction but this puts quite a burden on the protocol designer and these things are already complicated enough as they are (not to mention the implementation complexity of this in bitcoin core).
So for me, just slightly modifying BIP-340 to allow messages of any length and following this up in the implementation would solve my present design dilemma. I don't think there is any impact on the DPA resistance.
@LLFourn Right, there are other reasons why CR is already needed; for one, if you can make a valid and invalid transaction or block hash collide, you can fork the network. So even ignoring anything signature related, I think it's fair to say that Bitcoin inherently relies on (double-)SHA256 collision resistance.
Another reason is the ability to precompute parts of the transaction data in the sighash; without it, you inevitably run into the O(n^2) hashing complexity we had in pre-segwit signing (where large transactions can require a substantial amount of time to just to compute the sighashes).
So yes, I think permitting variable-length messages would work. But it won't affect any usage in transaction signing, I think. The only change would be a few test vectors, and amending the BIP.
I can see the a use case for schnorr signatures for arbitrary-sized messages. In particular, oracles that make use of "committed R-point signatures" to be able to atomically sell a signature (on-chain or Lightning) can not easily use another signature scheme to sign arbitrary messages. They want their users to take their R to compute sG and then use a pay-for-DL scheme. If bip-schnorr would support this, specs building on it would be (a bit) simpler and implementations wouldn't have to include a third party lib for hashing.
On the other hand, if messages are long, then users may want to pre-hash anyway to reduce the number of unnecessarily hashed bytes as as the message is also hashed in the nonce derivation function.
There's a chance that people will want to do this (inside and outside of the Bitcoin ecosystem), and in that case I'd prefer that we specify how this should be done. And I agree, it's a simple change that doesn't really add complexity to the BIP.
You can also make a case for hashing shorter messages. If I want to hash variable-length messages of up to 16 bytes for example, it's easy to get the encoding wrong if you're forced to pass a 32-byte array.
Here's one strange observation though: It's unlikely but not impossible that someone specifies a cryptographic protocol interacting with Schnorr signatures in a non-blackbox way (we have seen many of those, e.g., Taproot itself :P) where the signer needs to reveal either the secret nonce k or the signature (but not both!) for some message m. This seems fine but if you combine this with variable-length messages and our nonce derivation function, you'd run into a very subtle length-extension attack. The attacker can then obtain k for a message m and predict k' for some message m||m'. That's bad if the attacker gets a signature on m||m' too.
Yeah, I admit it's not likely but can this be avoided easily? Normally I'd suggest to add the message to the hash before the secret key but that undermines all our anti power analysis efforts. You can also use double SHA256 but that's slow. It seems that the simplest defense is to prepend the message with its length then. Assuming 32-byte messages, we have a few bytes left in the second compression. I'm really not sure if this is worth the hassle.
The reason we believe that SHA-256 has the rpsp property is because it follows from the assumption that the SHA-256 compression function is collision resistant. But that assumption that the SHA-256 compression function is collision resistant also implies that SHA-256 itself is collision resistant.
So while, yes, it is technically possible that SHA-256 is broken and has a collision, which in turn implies that SHA-256 compression function has a collision, while at the same time magically maintaining the rpsp property in spite of the brokenness of the compression function, it seems absurd to me to design an API around this possibility.
If people want to sign variable length messages they should hash it with SHA-256 and pass those 32-bytes as the message to Schnorr.
@real-or-random Yeah, I admit it's not likely but can this be avoided easily?
Well, adding randomness into nonce generation should do this!
@roconnor-blockstream So while, yes, it is technically possible that SHA-256 is broken and has a collision, which in turn implies that SHA-256 compression function has a collision, while at the same time magically maintaining the rpsp property in spite of the brokenness of the compression function, it seems absurd to me to design an API around this possibility.
I don't think it will take much magic. rpsp is just much harder than finding collisions (unless there is something I don't understand in particular about SHA256). CR of SHA1 is broken and yet the rpp/rpsp properties still hold. But to your point, worrying about CR of SHA256 in anything remotely related to Bitcoin is wasted effort for all the reasons @sipa mentioned and this is a Bitcoin BIP after all.
Perhaps a better solution is to leave the api as is but introduce another function which let's you pass in a variable length message + a domain separator for the tagged hashes. This function then would use "my-domain/aux" and "my-domain/challenge" etc. If you are signing non-transaction messages then you are not in the bitcoin witness domain anyway so you should probably use a different tagged hash.
[edit] I forgot to stress that the reason I want this change is not because of security properties but precisely because of API ergonomics. It will make me scream inside a little bit every time I explain in code or protocol specification "No this is not a hash for security, it's a hash for a particular library's API"
I claim that the ability to find identical-prefix collisions in SHA1 outright breaks the rpsp property of SHA1 (not to mention the chosen-prefix collisions which are only 4x more expensive). I don't believe your claim that the SHA1 rpsp property isn't broken, and if I am wrong about this I would love to be corrected.
P.S. I have no strong opinions about layering an API on top of the existing Schnorr specification that takes a variable length message and hashes it with SHA256.
I claim that the ability to find identical-prefix collisions in SHA1 outright breaks the rpsp property of SHA1 (not to mention the chosen-prefix collisions which are only 4x more expensive). I don't believe your claim that the SHA1 rpsp property isn't broken, and if I am wrong about this I would love to be corrected.
This is quite a claim! I'll have to think about that.
@roconnor-blockstream In a few minutes I can break our scheme with pre-hashing and all hashes turned to sha1. I cannot do so without the pre-hashing. If I could, it would be a press generating additional break of sha1.
The MD structure of sha2 means that even an extremely weird and specialized CR break of one run of the compression function with a specific starting state is a generalized break for larger messages starting with that prefix.
The fact that someone uses a proof that having property X means that a hash function has property Y doesn't mean that failing X means it doesn't have Y in practice anymore, it just means that argument no longer works.
You can imagine a property along the lines of "probabilistic prefix collision resistant", where the function is has a small class of efficiently computable collisions but they're all among a very small number of prefixes that you'd never end up with by chance. And so you can't exploit a signer's because of their unknown-to-you R or forge generally because you can't find a point of known DL who's serialization matches the prefix.
I wouldn't argue that this is some radical improvement. But it is NOT conjectural with examples like sha1 and md5. In some applications, though not bitcoin, operating this way lowers hashing costs so it's better than free. Saves cycles and hardens a little against theoretical but realistic attacks on the hash function... What's not to love? It other applications prehashing is critical for performance or for some other reason so it isn't a good trade-off.
If I understand, you are saying it is free to break Schnorr-with-SHA1 because you can just download SHA1 collisions off the internet (not sure why you say a few minutes instead of a few microseconds). But to break rpsp you have to spend $11k per random value in order find a new idenitcal-prefix collision for that particular random value.
I suppose that is something, but SHA1 collisions only exist on the internet because someone (Google) paid for an identical-prefix collision for the empty prefix. However they could have found a collision starting from any particular random prefix for exactly the same price. Hence my claim that SHA1's rpsp is broken.
What is not to love is that, and perhaps I'm speaking of that which I do not know, signing hardware might appreciate the fact that the act of signing is always constant time and only requires a fixed amount of data. Obviously not a problem for Bitcoin wallets as we intend to only use BIP-340 for 32-byte messages in Bitcoin. But why would we write BIPs to support non-Bitcoin applications? If people want to make an IETF Schnorr standard with variable length messages, then they should go right ahead. If it happens to be compatible with BIP-340 on 32-byte messages, all the better.
@roconnor-blockstream That's a fair point, but at the same time, signing hardware shouldn't be signing things it doesn't understand, so even if BIP340 supports variable length messages, the device wouldn't implement those, because it implements transaction signing, not blind Schnorr signing.
If I understand, you are saying it is free to break Schnorr-with-SHA1 because you can just download SHA1 collisions off the internet (not sure why you say a few minutes instead of a few microseconds). But to break rpsp you have to spend $11k per random value in order find a new idenitcal-prefix collision for that particular random value.
And it took another three years of research to get this number down to 1 BTC. Noone can guarantee that it works that way but the pattern we observe is that CR is broken first and it takes a while until other properties are broken. Of course you stop using the function immediately (or actually you should have stopped earlier already) and then having three years is better than not having three years.
But why would we write BIPs to support non-Bitcoin applications?
I believe noone here has a particular application outside or inside of Bitcoin in mind (besides the committed R-point signatures which @jonasnick mentioned for Lightning. Is this Bitcoin or not?) I agree we should not care about non-Bitcoin applications in BIPs, but it's just that we may not know what the applications will be, and signatures are a standard primitive that for sure will have other uses than signing transactions even if one just looks at Bitcoin. A simple example is signing messages/BIP322 but I'm sure there are other examples in the Bitcoin ecosystem. In the end, the scheme will be implemented in libsecp256k1, which is a general purpose library, and who knows what people will build on top of it.
With Bitcoin in mind, I believe that this discussion should be dominated by the implications on the API.
[edit] I forgot to stress that the reason I want this change is not because of security properties but precisely because of API ergonomics. It will make me scream inside a little bit every time I explain in code or protocol specification "No this is not a hash for security, it's a hash for a particular library's API"
I agree.
@LLFourn Pieter informed me that I misunderstood the rpsp and, that one message must be chosen prior to the prefix. So my claims about SHA1's identical-prefix attack implying the rpsp are bogus.
It's good that I learned something, but bad that I caused so much trouble for everyone.
I brought this up in private conversation, but I figured I should post this scenario publicly.
We could imagine a HSM design divided into two layers, where the inner layer is tasked with keeping the secret key secret, and the outer layer is in charge of enforcing policy on what it will or will not sign. It is suggested that signers verify their generated signatures before returning them in order to guard against fault injection attacks that would corrupt their processing to leak the secret key data. I believe that this signature verification check is required to check that the e value is H(R||something). With the current BIP340 design, the length of something is bounded (and indeed fixed), but with the proposed amendment it would be potentially unbounded in some applications. This would imply that the inner layer needs enough memory to hold the "something" string, or needs interactive processing to be feed the "something" string twice, or maybe it is fine to let the outer layer handle the verification (though that would seem to mixup who is responsible for keeping the secret key secret).
I no longer have any strong opinion one way or the other about whether BIP340 should be amended to support variable-length messages or not. Maybe every HSM can put their own bounds on message length for whatever application they are designed for. Whether that ends up working depends on which applications make use of variable length messages. But I figured I should post the above scenario to allow it to be considered.
This would imply that the inner layer needs enough memory to hold the "something" string, or needs interactive processing to be feed the "something" string twice, or maybe it is fine to let the outer layer handle the verification
This is already a consideration that exists on existing HSMs today. They handle it by streaming processing (e.g. keeping a midstate around and processing the data as it comes in)-- so no unbounded memory usage. I'm sure you're aware of this but it wasn't explicit in your message. It doesn't even have to be two-pass for a derandomized nonce: prehash for the nonce have the host send the prehash. Compute the prehash yourself in parallel when the payload hash is sent to verify they match. That said, it's a reason why a limited size input one might be preferable for something, sure-- since you can imagine a variation where communications is extremely slow or whatnot.
Signer on a stick HSMs are not even uncommon, though I think the mostly exist due to market failure (actually running your business logic on the HSM is too hard for people to support) and incoherent security models-- people without an idea of what attacks they're protecting against but a checklist that should say they need a HSM. :)
You could also imagine an application where signatures need to be constructed or verified inside a ZKP and the additional round of prehashing nearly doubles the provers computation time ... or where that is done but the message could be hashed externally and the prehashing reduces computation time.
When you get into applications specifics which one is better really depends on the application. The "prehash-and-cash or quadratic" that we have in Bitcoin isn't that weird in and of itself.
Indeed small payload expansions seem to be completely unproblematic. Allowing messages of any lengths between 0 and 55 bytes is basically free, and there seems little reason not to support that. Allowing somewhat larger sizes upto 119 or 183 bytes for example seems reasonably fine as well. Much beyond that means users are going to be spending "a lot" of time running compression functions regardless.
I don't know if capping messages at sizes like these is a reasonable compromise, or simply evidence that we shouldn't be putting a message size cap on to begin with because we don't have reason to stop at any particular place.
@LLFourn Pieter informed me that I misunderstood the rpsp and, that one message must be chosen prior to the prefix. So my claims about SHA1's identical-prefix attack implying the rpsp are bogus.
It's good that I learned something, but bad that I caused so much trouble for everyone.
I actually learned something by thinking about your proposition. It does indeed seem to be wrong for rpsp but if you change this from "prefix" to "suffix" then I think you are right; rssp would reduce to collision resistance of compression function. This is interesting because it shows that for sha256 prefixing everything with R is not an arbitrary choice (as it would be with a random oracle).
@sipa wrote:
@roconnor-blockstream That's a fair point, but at the same time, signing hardware shouldn't be signing things it doesn't understand, so even if BIP340 supports variable length messages, the device wouldn't implement those, because it implements transaction signing, not blind Schnorr signing.
@real-or-random wrote:
A simple example is signing messages/BIP322 but I'm sure there are other examples in the Bitcoin ecosystem. In the end, the scheme will be implemented in libsecp256k1, which is a general purpose library, and who knows what people will build on top of it.
These two points strengthen my opinion that only transactions should be signed with the "BIP340" tag. Other applications within Bitcoin should use a different tag like "BIP322" in the tagged hashes. That's why the tagged hashes are there right? Adding variable length messages without an explicit tag feels like it encourages people to create signatures for different applications but without domain separation. If they make a mistake in what they allow to be signed then they may lose funds.
As an example, DLC style oracles (which is what I am working on) also have this problem where they have a public key which holds Bitcoin as a kind of pledge to not reveal their private key by signing two conflicting event outcomes with same R. A system that defines the semantics of events might be able to get the oracle to sign a single malicious event outcome which is actually a transaction.
So contrary to my initial comment on the sign function I think it makes sense to only allow 32 byte arguments and have BIP340 hard coded into it. There should just be another function that takes a tag as an argument and variable length messages. This would set a really good example about domain separation from the beginning which was a badly specified afterthought in ed25519. They make you hash your tag with the message and just sign the hash as the message which of course means you now depend on CR because of API design! Here's the amusing comments of one implementer.
A more extreme position is that the concrete tag "BIP340" should be removed from BIP340 and just make the tag a parameterization of the algorithms (with the same structure TAG/challenge etc.). Then Taproot BIP341 which is actually the thing that deals with consensus can declare that the BIP340 algorithms be parametereized with "BIP341" as the tag with a warning that no device should every sign anything other than BIP341 inputs with this tag.
It sounds a little like you're leaning towards talking about libsecp256k1 re apis. Libsecp256k1 intends to, in so much as realistic, to provide complete cryptosystems-- not a cryptosystem-do-it-yourself-kit. The callers of the library are not cryptographers, expecting them to understand and get right tags may be a bit of a dubious proposition. That said, domain sep is a big source of problems, almost everything handles it poorly... and I'd love to see it done better. I'm just dubious that dumping it on the caller is actually doing it better. Sadly unlike nonces-- which we don't require the caller, and in fact nearly forbid the caller from providing--, it can't be internalized.
(Efficient operation with tags also really is accomplished best via midstates, which makes for a kind of ugly API. E.g. you'd want a tag object, not a string)
I also don't know how much I'd recommend BIP340(based) proposals for applications where the specific curve isn't called for by bitcoin compatibility. But to the extent that other standards (and their implementations) get some of this stuff wrong, it's worthwhile to do a better job to advance the art for the sake of future implementations that might be inspired by our choices.
@LLFourn That's an interesting take. The reason we have BIP340/ there is to provide domain separation against entirely different usages of the hash function. But you're right, domain separation of signatures is another concern.
It sounds a little like you're leaning towards talking about libsecp256k1 re apis. Libsecp256k1 intends to, in so much as realistic, to provide complete cryptosystems-- not a cryptosystem-do-it-yourself-kit. The callers of the library are not cryptographers, expecting them to understand and get right tags may be a bit of a dubious proposition. That said, domain sep is a big source of problems, almost everything handles it poorly... and I'd love to see it done better. I'm just dubious that dumping it on the caller is actually doing it better.
But the current API dumps it on the caller, too? Currently the caller needs to be aware of the problem and then come up with a proper encoding of messages that ensures domain separation (and not even BIP341 does this officially). Having an explicit context argument in the API will at least force the caller to think about it.
(Efficient operation with tags also really is accomplished best via midstates, which makes for a kind of ugly API. E.g. you'd want a tag object, not a string)
We'd also have a few bytes (23?) left in the front of the message. Domain separation against other uses of the hash could still be done via midstates.
@gmaxwell @real-or-random thanks that gives me some better perspective. Reserving the 23(?) bytes in front of the message for domain separation of signatures (rather than hashes) sounds like a much better proposal if that works.
I think even the existing specification has a problem with domain separation without even considering variable length messages.
Let's say I am a crypto engineer working for a Bitcoin exchange insurer. I know about hash functions, how ECDSA works and how Schnorr works and I've read BIP340 (in it's current state). I am tasked with making sure that the exchanges we are working with do indeed have the funds they claim and have not already lost them before joining us. I can't just ask them to sign the date or something because they could have pre-signed all the dates in the future before they lost their keys in the hope that they could get a free bailout from my company.
A non-interactive scheme won't work. I will send them a challenge string which I randomly generate which they have to sign with all the UTXOs they currently own. Of course, since I am a good crypto engineer I make sure to do some domain separation. I specify that each challenge should be prefixed with OWN_CHECK before signing. I notice that my secp256k1 implementation only takes 32 byte messages. That's weird. I guess that's just because that's what Bitcoin needs. Maybe I should hash my message as well? Maybe not, BIP340 says that it's meant to sign a "message m" not a message hash per se. That's fine. I'll just do a 23 byte challenge which when prefixed with OWN_CHECK adds up to 32. More than enough statistical security!
It may come as no surprise to the people in this thread that despite my best efforts I have just created a system which allows you to steal funds from these exchanges. It should be possible to find a valid BIP341 transaction keyspend signature digest that is prefixed with OWN_CHECK given enough time. I think per challenge you send you could steal one UTXO.
The very long winded point here is if there is no domain separation at the Schnorr challenge hash then everyone using BIP340 must hash their messages before hand and domain separate their messages from BIP341 messages by using a different tagged hash (similarly ed25519 pre-hash puts a "context" before the message before hashing it). If this is the way things go then this should be stated that BIP340 is designed only to sign message hashes ECDSA style and never messages themselves and that the message hash used should be tagged with the domain. I think there is no viable variable length message option where you just make the api take a variable length message.
The much nicer solution would be as @real-or-random suggested: to put the signature domain separator in the challenge and include it in nonce generation. So for BIP341 the challenge it could be H(R || P || BIP341_padded_to_context_length || m). Then the scheme can be used to sign messages or message hashes without concern as long as the crypto engineer is not stupid to the point of being malicious by explicitly putting BIP341 as the context in something that has nothing to do with BIP341.
Of course even with no changes it would not be the end of the world. You can still do domain separation by using different tags in the hahses (this is currently what in secp256kfun/schnorr_fun by pre-computing midstates. But I just made the default tag BIP3401 which I guess makes me the one who is stupid to the point of being malicious!). For the reasons @gmaxwell stated it looks like that's a hard API to support in libsecp256k1.
Is it accurate to say that if we only support 32-byte "messages" we should strongly recommend or require that those messages be SHA256 tagged hash values, and that if we support variable length messages we need to design add our own domain separating data to the challenge?
I don't see how we can safely add variable length messages without amending taproot at this point if we are worried about domain collisions. Maybe variable length messages should be in a different BIP, which would have a different the tag in the challenge tagged hash.
I'm not sure the goal of tagging in BIP340 should be for application-level domain separation. In practice, tags have a cost - either an extra compression at runtime, or additional software complexity if we aim for having them precomputed for each tag.
I think tags make sense to separate conceptually different uses of hash function within the same application - (nonces, challenges, messages in signatures; leaves, inner nodes, tweaks in merkle trees/taproot; ...) because keys and hashes and other inputs tend be reused across them, and designing serialization in a way that never collides across these boundaries is hard, as we've seen with CVE-2012-2459 for example.
But incorporating into the signature scheme a way to change the challenge tag seems strange to me. It remains a challenge, and we'd want it domain-separated from nonce-computation I think, regardless of the application. If the message is a hash itself, we could recommend using a application-dependent tagged hash there (as BIP341 does). But for variable-length messages, I'm not so sure how to reconcile the desire for an efficient precomputed tag for the challenge with a potential desire to have an application-level tag as well. I don't think it's unreasonable to just leave it up to the application whether that's needed, and if so, prefix it to the message at a runtime cost.
Is it accurate to say that if we only support 32-byte "messages" we should strongly recommend or require that those messages be SHA256 tagged hash values, and that if we support variable length messages we need to design add our own domain separating data to the challenge?
I don't see how we can safely add variable length messages without amending taproot at this point if we are worried about domain collisions. Maybe variable length messages should be in a different BIP, which would have a different the tag in the challenge tagged hash.
(and a different tag in the nonce hash)
I agree on both points. I've been mulling the second option over the last few days. Even though this conversation started with me complaining about hashing everything, I think having variable length as a separate BIP could actually be worse. We will have to maintain two different APIs for signing and verification (or pass in some flag) one for variable length and one for signing a hash. It will get worse as we get into more exotic signing schemes and non-black box ways of using the signature scheme. For example, I have a function called anticipate_signature in my library. I would need two of these as well. Two implementations of multi-signature signing and so on. Although I dislike the idea of pushing the problem of domain separation to the up application layer, pushing it down to the library like this seems worse.
I don't think it's unreasonable to just leave it up to the application whether that's needed, and if so, prefix it to the message at a runtime cost.
To be clear, the point of my OWN_CHECK prefix example was to show why this is unreasonable. Even when they do prefix their messages it can still be completely broken. Here is another comment from Isis in ed25519-dalek which I think hits the nail on the head:
Leaving the domain separation to application designers, who thus far have produced incompatible, slightly-differing, ad hoc domain separation (at least those application designers who knew enough cryptographic theory to do so!), is therefore a bad design choice on the part of the cryptographer designing primitives which should be simple and as foolproof as possible to use for non-cryptographers. Further, later in the ed25519 signature scheme, as specified in RFC8032, the public key is added into another hash digest (along with the message, again); it is unclear to this author why there's not only one but two poorly-thought-out attempts at domain separation in the same signature scheme, and which both fail in exactly the same way. For a better-designed, Schnorr-based signature scheme, see Trevor Perrin's work on "generalised EdDSA" and "VXEdDSA".
As suggested, I looked for "generalized EdDSA" and found this moderncrypto list post: https://curves.moderncrypto.narkive.com/tLM6oRaL/generalizing-eddsa. I think the ideas here are good.
To summarize, Trevor tries to do demonstrate ed25519 done right which moves it a lot closer to BIP340. WRT to domain separtaion, he prefixes the challenge inputs with the domain separator and it's length padded to a block. He actually prefixes the inputs with two different tags which have distinct goals:
- protocol separation: Making sure that the hashed values (challenges, nonces etc) are specific to this signature scheme and not to a VRF or other kinds of proofs
- application separation: Making sure application objects like signatures cannot be re-used across different applications (despite them using the same signature scheme).
I think this is better than prefixing the message and padding to a fixed length which is what I suggested before. As has been pointed out, using the BIP340 tagged hashes for application separation is inefficient and bad for API design. Tagged hashes do the protocol separation.
So does application domain separation belong in BIP340? I would certainly like it and I think BIP341 should use it too given that it's an application. I fear making up systems of application separation for variable length messages independent of BIP341 will lead to the mess that Isis describes and two variants for each signature function that need to be maintained. The best thing to do without changing the BIPs will be to just use the application separation approach of BIP341 and hash everything with a different tagged hash. This is undesirable for the reasons already discussed but it's at least guaranteed to work.
My preferred alternative requires making a small change to the BIPs in the way Trevor suggested. I think the most straightforward change is to prefix the challenge and nonce inputs with an application defined tag g.g. a 1 byte tag length + tag (e.g 0x06"BIP341"). From my position this seems like small price to pay compared to trying to work around this problem later. There is no cost from a performance or security perspective that I can see.
Further thoughts on this are appreciated. If there's general interest in seeing how this change looks in practice I would be happy to create a PR amending the BIPs test vectors and example code over the next week (assuming the BIP authors are not interested doing this). I am not following activation discussions closely enough to gauge whether the "ship has sailed" on this one so I'll defer to the BIPs authors as to whether it's worth it at this stage.
At this point I think it is unattractive to make protocol incompatible changes purely for the sake of non-bitcoin applications. Presumably you could spec something out which wasn't incompatible.