Comments (71)
@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.
from bips.
One reason to give good domain separation advice is that inevitably people will apply this scheme to mostly non-bitcoin contexts and then create vulnerabilities for bitcoin usage due to domain sep failures.
As far as why someone would want to avoid an extra compression function call-- for latency critical signing (e.g. you want to sign messages from a network server with a lowest possible latency) the extra compression function call is a 50% increase in signing latency if you don't have SHA-NI.
As for the CR assumption, -- because keeping it is a violation of a best practice. This violation is irrelevant in Bitcoin because of the strong assumptions elsewhere and because of the extremely important benefits (linear time txn validation). But elsewhere these issues don't arise. That said: using BIP340 outside of bitcoin is already a violation of cryptographic best practices as the NSA has made a very strong recommendation to not use ECC smaller than 384-bits.
from bips.
One could say that they are byte strings and it's recommended that they're selected to be valid utf-8 text?
from bips.
I'm not a very big fan of making the concept of an application tag an explicit part of BIP340. It raises questions ("how do I guarantee my tag hasn't been used somewhere? is there a global registry? how dangerous is it if someone accidentally picks the same tag as me?") or may just result in many potential users just setting it to some example default. In reality domain separation matters more within applications/protocols (where keys risk being used for multiple purposes) than across domains entirely (where it's very hard to guarantee).
This is somewhat confusing for me since you then proceed to propose making two different kinds of application tags explicit in BIP340. I guess you meant as an explicit part of the signing and verification algorithms as described in pseudocode. For me this distinction is not as clear since whether they are written in pseudocode or not people will have to implement both these domain separation approaches and then may ask questions about both of them. Having people stop, think and ask questions actually seems like a good thing. My proposition is that it would just be better for everyone if there was only one method of domain separation rather than two.
I think what @sipa meant to say (correct me if I'm wrong) was to keep the interface sign(sk, message)
and then tell the user that it is a good idea to think about domain separation and give two possible recommended ways of doing it.
Re only one method: I think we can actually phrase this as one method because in the end it always boils down to prefixing the message with 64 bytes, just in one case the message is hashed before passed to the API. Anyway, it may be helpful to spend one explanatory sentence on the possibility to prehash messages because the existing interface turned out to be confusing to people who're familiar with ECDSA.
I agree with @roconnor-blockstream in that counting compression functions is rather pointless if you are doing an ecmult.
I think what @roconnor-blockstream said is only true for signing and the ability to precompute midstates helps also for verification. But I fully agree in the end, saving one compression isn't worth the hassle, even if you take verification into account.
from bips.
I agree with your statement about the security of your proposal and am in favor of the proposal. I think of the two methods as "what BIP341 is doing" and "a good way to work around what BIP341 is doing". You reject this characterization and prefer to state there are just two ways to do domain separation in BIP340 and BIP341 just happens to use one of them. In any case there seems to be no practical or important disagreement here. Sorry for the confusion.
from bips.
Ping @jonasnick, @real-or-random.
from bips.
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.
from bips.
@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.
from bips.
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.
from bips.
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.
from bips.
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.
from bips.
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.
from bips.
@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"
from bips.
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.
from bips.
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.
from bips.
@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.
from bips.
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.
from bips.
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.
from bips.
@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.
from bips.
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.
from bips.
@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.
from bips.
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.
from bips.
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.
from bips.
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.
from bips.
@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).
from bips.
@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.
from bips.
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.
from bips.
@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.
from bips.
@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.
from bips.
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.
from bips.
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.
from bips.
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.
from bips.
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.
from bips.
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.
from bips.
Isn't it possible that there will be useful applications of BIP340 in the Bitcoin protocol itself outside of BIP341? It may not be desirable to hash the message in those situations either.
There are certainly ways to get domain separation leaving things the way they are but I'm not sure if they're better than just hashing things. The BIP341 message space is any 32 bytes, so in order to separate your application from it you have to make sure you don't sign a 32 byte message. A simple way to do this is to pad the application tag to be at least 33 bytes long and prefix it to the message (so even the empty message is not 32 bytes long).
from bips.
Or change the BIP340 tag, to say, "BIP340m". If you were to do that padding thing, you should make sure to make it a whole compression block so it can be cached.
from bips.
Oh I wasn't aware of this post by Trevor, and I actually had something similar in mind.
Isn't it possible that there will be useful applications of BIP340 in the Bitcoin protocol itself outside of BIP341? It may not be desirable to hash the message in those situations either.
Yes, I think there are interesting use cases in Bitcoin itself and in the Bitcoin ecosystem (Layer 2, ....), and those are the interesting ones because there's potential for reusing keys.
Anyway, I don't think there's an optimal solution but here's a proposal which is close enough from point of view and separates different applications:
- Applications other than Taproot/Bitcoin should add a "protocol identifier" (or "application identifier") as a second tag
SHA256(id)||SHA256(id)
after the already existingBIP340/challenge
orBIP340/nonce
tags, essentially creating doubly-tagged nonce and challenge hashes. - Other applications can then use variable length messages.
Note: I write "Taproot/Bitcoin" here because it's never really clear what an "application" is. If this was used in the future in Bitcoin Core for other purposes than Taproot, is this a separate application or not? That needs to be decided on a case-by-case basis. For simplicity I'll just write "Taproot" in the following.
The spirit of this proposal is that the second tag is conceptually an application-identifier, i.e., a constant. This pushes the separation between different purposes within the same application to the user, and Taproot does this with tagged message hashes. There's not necessarily an additional "tag" or "context" string in the sign/verify API which the application can pass (may depend on the implementation, see below).
I don't think there's an issue with pushing separation between different purposes within the same application down to the user. Users anyway need to parse and interpret messages in virtually all cases, and if they don't get this right or if they don't understand why separation of purposes is important, it's probably naive to believe that we'll magically solve this problem by giving them an additional API argument. We can of course add a sentence that tells them that they should prefix their messages with a fixed-length identifier if they use hashes for different purposes.
Since the second tag is conceptually an application-identifier, there's the option that the midstate may be precomputed during context creation or in an additional schnorrsig contect in libs like libsecp256k1. (That is an API change in libsecp2565k1 etc, but I don't think it's necessary to discuss this here in detail, it's just an option to think about.)
A potential disadvantage is that users may start to put variable data in the tag, and then this is not great because signed variable data should go into the challenge hash after R, because R randomizes the hash (that's the entire reason why random-prefix collision resistance could be enough) [1]. But I don't think that's a large issue. Depending on the API of a concrete implementation, this either won't be possible (or inefficient), or it's an abuse of the API, and we can't do much about it except telling the user not do it.
Advantages:
- This proposal does not affect Taproot at all.
- Keeping the existing tags means that the challenge and nonce hash are always separated, and all hashes have at least some tag.
- Other applications are always separated from Taproot. The second tag (64 bytes) is longer than the Taproot message (32 byte). So for both hashes, the total number of hashed bytes in other applications is always larger than the total number of hashed bytes for Taproot.
- The aux hash is left as it is but nothing bad happens if somebody will add the second tag there too.
- The burden of additional complexity or increased running time is pushed to applications other than Taproot, making clear that BIP340's primary purpose is Taproot.
- Other applications can still precompute the midstate after both tags if they wish, and then there's no performance penalty at all. Other implementations like libsecp256k1 may choose to precompute the midstate only for the first tag.
I believe @LLFourn 's suggestion to prefix the message with a 33byte tag would have very similar properties, and I think that's a good proposal, too. I prefer mine slightly because it's more efficient and because of this also more likely to be picked up -- in the end we need to hope that people will implement what we suggest.
[1] Trevor solves this by adding the tag a second time after R but I think this is overkill. https://narkive.com/tLM6oRaL:1.5524.111
from bips.
BIP340's primary purpose is Taproot.
I think this is false.
As sipa already noted, Bitcoin depends on the CR of SHA256 already. It doesn't seem unreasonable to me that all other Bitcoin applications of BIP340 sign messages with their own application specific tagged hash. Even though those specific Bitcoin applications may not strictly depend on the CR of SHA256. If the CR of SHA256 fails, then today's Bitcoin protocol also fails, and there doesn't seem to be much point in maintaining Bitcoin applications without Bitcoin.
As far as I can tell, all this dancing around is to (1) avoid assuming full CR of SHA256 or (2) saving 1 extra call to the SHA256 compression function. Supporting non-32 byte messages can only useful for (1) Non-bitcoin applications that don't themselves already assume the CR of SHA256 or (2) Bitcoin applications that for some reason cannot stand to have 1 extra call the the SHA256 compression function.
TBH, I'm still baffled as to why we there is so much hand-wringing over 1 extra call to the SHA256 compression function. We already know how to do application separation with BIP340. Every application simply uses their own tag in the tagged message the pass to BIP340.
from bips.
TBH, I'm still baffled as to why we there is so much hand-wringing over 1 extra call to the SHA256 compression function. We already know how to do application separation with BIP340. Every application simply uses their own tag in the tagged message the pass to BIP340.
I don't think that's a bad choice. But if we do this, then we should change the BIP accordingly and mandate that the message is prehashed with a tagged hash because otherwise domain separation is not guaranteed. That adds complexity too, and I don't see how this is clearly simpler or superior over the other proposals here.
I personally don't care much about a single SHA256 compression. My main concern with this is that people won't like it and simply hash the variable-length message into the challenge hash instead as an "optimization". People tend to bring things like this or CR vs RPCR up. A standard which everyone will end up adapting to their own "needs" (if justified or not) is useless, and this is one of the reasons why we have 3 variants of ChaCha20, and at least 5 variants of EdDSA.
from bips.
As far as I can tell, all this dancing around is to (1) avoid assuming full CR of SHA256 or (2) saving 1 extra call to the SHA256 compression function. Supporting non-32 byte messages can only useful for (1) Non-bitcoin applications that don't themselves already assume the CR of SHA256 or (2) Bitcoin applications that for some reason cannot stand to have 1 extra call the the SHA256 compression function.
For me the concern is purely about API at this point. There are two considerations:
- How likely is the proposal to actually make it into libsecp256k1 which may not want to support passing in your own mid-states and may not want to expose functions for the user to created tagged hashes themselves.
- How annoying is it for the user and therefore how likely is it that people will roll their own to avoid whatever is proposed.
Using a tagged hash on the message seems to be not ideal for either of these. The user has to get a tagged hash from somewhere or has to roll their own. libsecp256k1 might provide it but this might not be desirable.
I like @real-or-random's proposal. It is an elegant translation of Tevors idea and solves the problem. I think its success hinges upon:
Since the second tag is conceptually an application-identifier, there's the option that the midstate may be precomputed during context creation or in an additional schnorrsig contect in libs like libsecp256k1. (That is an API change in libsecp2565k1 etc, but I don't think it's necessary to discuss this here in detail, it's just an option to think about.)
If having a schnorr "context" is acceptable in libsecp256k1 then this is the best non-BIP modifying solution to me. It is close to what I am doing already.
from bips.
extra compression function call is a 50% increase in signing latency if you don't have SHA-NI.
I find it hard to believe that one extra compression function has that much overhead compared to calling secp256k1_ecmult_gen
.
Edit: Ah, I suppose nonces can be precomputed in advance.
from bips.
Exactly.
from bips.
Not just the nonces can be precomputed, but the entire midstate up to just before the message. This would hold regardless of whether the application prefix goes before R or before the message.
from bips.
True, so long as it was setup to end on a compression block boundary. Though that does make the precomp more expensive, it isn't be a huge amount.
from bips.
Here's a nit: Currently, the BIP says that tags are UTF-8 encoded. We may want to change this to ASCII or just use "byte strings" instead if we allow user-specified tags (in whatever form), just because it's simpler and these things are supposed to be constants anyway. I assume noone here believes that adding UTF-8 encoders to implementations like libsecp256k1 is a sane idea, and then we may just as well change the BIP accordingly.
from bips.
I implemented @real-or-random's suggestion in secp256kfun here.
I'd say it's a small improvement over what I was doing before (just changing "BIP340" to something else) because it separates protocol and application separation. I am still a fan of updating the BIPs to unify the domain separation approach between variable length and pre-hashed messages. This would allow me to get rid of MessageKind
.
I force the user to provide a utf8 string for their tag if doing a variable length message (and just tell them to make sure their hash is tagged differently if doing a prehashed message). Saying it must be valid ASCII would be annoying because then I would have to check that I guess. Allowing any byte string in the library but advising that it should just be valid utf8 in the BIP is fine I think.
from bips.
I'm not a very big fan of making the concept of an application tag an explicit part of BIP340. It raises questions ("how do I guarantee my tag hasn't been used somewhere? is there a global registry? how dangerous is it if someone accidentally picks the same tag as me?") or may just result in many potential users just setting it to some example default. In reality domain separation matters more within applications/protocols (where keys risk being used for multiple purposes) than across domains entirely (where it's very hard to guarantee).
However, I think it's important that domain separation is mentioned, recommended, and easy to do. After some discussion with @real-or-random and @roconnor-blockstream, I suggest this:
- BIP340 is amended to permit non-32-byte messages
- A recommendation is added about how to construct the message in one of two ways:
- Use a tagged hash with an application-specific tag of the message payload. This means the security now becomes reliant on collision resistance of the tagged hash function (but that's the case already if you use hashes inside the message). This is what BIP341 happens to use.
- Prefix your (unhashed) message payload with an application-specific 64-byte tag. This means you have the ability to not rely on collision resistance for security, but comes at the cost of one extra SHA256 compression (however, if you really want to, you can precompute the expansion phase of that compression, as it's 64-byte aligned in the overall challenge hash).
As the two methods have different length (32 bytes vs 64+ bytes) there is no risk of collision between them.
from bips.
One advantage of this proposal that I failed to see earlier is that it will work with lazy/bad implementations that don't care about the possibility to add tags before R. If your implementation allows for variable-length messages, you can always follow this recommendation. And if it doesn't, you're forced to use 32byte messages but then you can prehash and again follow this recommendation.
from bips.
I'd like to add to @sipa's comment that in case ii. prefixing messages with 64-byte application tags means that if you are precomputing R then you can in turn precompute the entire midstate up to and including the application tag. And if you are not precomputing R, then it would seem that you have an ecmult
to contend with that would presumably dwarf the cost of the compression functions.
from bips.
I'm not a very big fan of making the concept of an application tag an explicit part of BIP340. It raises questions ("how do I guarantee my tag hasn't been used somewhere? is there a global registry? how dangerous is it if someone accidentally picks the same tag as me?") or may just result in many potential users just setting it to some example default. In reality domain separation matters more within applications/protocols (where keys risk being used for multiple purposes) than across domains entirely (where it's very hard to guarantee).
This is somewhat confusing for me since you then proceed to propose making two different kinds of application tags explicit in BIP340. I guess you meant as an explicit part of the signing and verification algorithms as described in pseudocode. For me this distinction is not as clear since whether they are written in pseudocode or not people will have to implement both these domain separation approaches and then may ask questions about both of them. Having people stop, think and ask questions actually seems like a good thing. My proposition is that it would just be better for everyone if there was only one method of domain separation rather than two.
However, I think it's important that domain separation is mentioned, recommended, and easy to do. After some discussion with @real-or-random and @roconnor-blockstream, I suggest this:
* BIP340 is amended to permit non-32-byte messages * A recommendation is added about how to construct the message in one of two ways: 1. Use a tagged hash with an application-specific tag of the message payload. This means the security now becomes reliant on collision resistance of the tagged hash function (but that's the case already if you use hashes inside the message). This is what BIP341 happens to use. 2. Prefix your (unhashed) message payload with an application-specific 64-byte tag. This means you have the ability to not rely on collision resistance for security, but comes at the cost of one extra SHA256 compression (however, if you really want to, you can precompute the expansion phase of that compression, as it's 64-byte aligned in the overall challenge hash).
As the two methods have different length (32 bytes vs 64+ bytes) there is no risk of collision between them.
I think this a good proposal in so far as modifying the BIP341 is out of the question. I agree with @roconnor-blockstream in that counting compression functions is rather pointless if you are doing an ecmult. This plus the decreased implementation complexity makes it preferable than what @real-or-random suggested earlier.
from bips.
Re only one method: I think we can actually phrase this as one method because in the end it always boils down to prefixing the message with 64 bytes, just in one case the message is hashed before passed to the API. Anyway, it may be helpful to spend one explanatory sentence on the possibility to prehash messages because the existing interface turned out to be confusing to people who're familiar with ECDSA.
I think it might be difficult to phrase that in a way that is useful for someone implementing it. The code to implement the two methods is totally different.
My plan is to keep a enum like:
pub enum MessageKind {
Prehashed,
Plain { tag: &'static str }
}
and get users to pass it into sign sign(sk, msg, msgkind)
. Or maybe they should pass it in at context creation time.
FWIW I have warmed to the idea that signing BIP341 hashes should be hassle free and that it's everyone else that should have to prefix things with 64 bytes to work around that. I still feel it's not ideal but I'm glad we had this discussion since it gives me a clear way forward. Thanks all. I will go ahead with @sipa's proposal above.
from bips.
FWIW I have warmed to the idea that signing BIP341 hashes should be hassle free and that it's everyone else that should have to prefix things with 64 bytes to work around that.
It's becoming a philosophical point at this point, but I disagree we should see it this way. I don't think BIP341 is exceptional as a user of BIP340: it too has a tag (it's using a tagged hash with tag "TapSighash").
from bips.
Its tagged hash only separates it from other pre-hashed messages. If instead of (or in addition to) using a tagged hash, BIP341 prefixed its message hashes with 0x06 + "BIP341"
before signing then there would be no need for other applications to use tagged hashes to sign a pre-hashed messages or to shift their message space by 32+ bytes for variable length messages. Just prefixing the pre-hashed or variable length message with 0x07 + "MYPROTO"
would allow them to be completely certain that no signature from their protocol could ever be used on a Bitcoin transaction.
I think it's fine to reserve the first 32-bytes of the message space for BIP341/pre-hashed messages but, philosophically speaking, that certainly looks like a privilege to me!
from bips.
I must be missing something, because the above sounds very confused to me.
I suggest two mechanisms for constructing the message:
- msg = TaggedHash(apptag, payload)
- msg = 64byte_apptag + payload
Do you agree that as long as the used apptags are unique within each group, there is no risk of collisions? Within (1), only if collision resistance of SHA256 holds; within (2) only rpp/rpsp is needed.
Now, BIP341 uses (1) with apptag="TapSighash". Anything else can also use (1), with another tag. Or they can use (2), with whatever tag.
I don't see what is special about BIP341: it uses one of the prescribed methods, and its only privilege is the use of the tag "TagSighash".
from bips.
Regarding tags being byte arrays rather than names/strings: #211
from bips.
But I fully agree in the end, saving one compression isn't worth the hassle, even if you take verification into account.
Not if your intention is to verify that signature inside of a zero-knowledge proof system, which presumably someone at some point will want to do.
from bips.
@maaku Ok this is an interesting point.
In the end this really depends on whether the message is public or not. If you use a variable-length message and the message is partially secret, then yes, this could affect you. But if you want to use a zero-knowledge proof, then the question is why you use BIP340 signatures in the first place. The reason can't be compatibility with Bitcoin because then you don't have variable-length messages. Maybe the reason is compatibility with some other system which has decided to rely BIP340, and you can't change this other system. But that's a lot of speculation at that point, and I'm not sure if those cases are relevant.
This is somewhat related to #62. But if you want to construct blind signatures for Bitcoin transactions, what @sipa proposed here does not affect you either.
from bips.
I saw @jonasnick made a PR to implement this: bitcoin-core/secp256k1#844. Thanks! I also implemented the proposal around here.
I am not sure what others think but I am still very much in support of having variable length messages in the secp256k1 API and as part of the spec. While working on DLC stuff I've noticed this "message hash" creep out and become an unhelpful abstraction in itself. For an example in the wild see these test cases which test against message hashes rather than just messages: https://github.com/discreetlogcontracts/dlcspecs/blob/master/test/dlc_schnorr_test.json
I also remember when we were setting up a DLC we had problems because one implementation was interpreting the output of SHA256 as a U256 and then passing the little-endian encoding to the sign function. It took quite some time to get to the bottom of this on slack.
from bips.
I am not sure what others think but I am still very much in support of having variable length messages in the secp256k1 API and as part of the spec. While working on DLC stuff I've noticed this "message hash" creep out and become an unhelpful abstraction in itself. For an example in the wild see these test cases which test against message hashes rather than just messages: https://github.com/discreetlogcontracts/dlcspecs/blob/master/test/dlc_schnorr_test.json
After thinking about this again, I claim much of the discussion here depends on whether the API boundary is. While we touched about this, I don't think this issue has been brought up very explicitly.
So we're talking about a standard doc here, but we all know in the end it will be implemented, typically in a library.
I believe what @sipa has in mind is that libraries provide a sign(sk, m)
API, and advice (e.g., in docs) callers to set m
either to 1) a 32-byte hash of a message, 2) a messages prefixed with a 64-byte tag. This pushes down the responsibility of intra-application domain separation entirely down to the user while still maintaining a "best effort" inter-application domain separation.
This is what is proposed in bitcoin-core/secp256k1#844 currently (except for the advice).
I believe what @LLFourn has in mind is that libraries should just do the right thing themselves, and take care of encoding messages including tagging etc.
(Note that I just use @sipa and @LLFourn here to give names to the proposal. We all agree that this is a purely technical discussion and the involved persons don't matter.)
There pros and cons to both sides of course. But if the BIP is written in mind with @sipa's approach, it seems cumbersome or at least inelegant to force @LLFourn's approach onto this, and this becomes apparent in secp25k1fun. So I think what secp25k1fun does is simply not nicely compatible this BIP. I think if one wants a simple API around BIP340, then one needs to decide for one of the two ways in the library. And this is of course not great for interoperability... But I don't think we can do much about this if we want to stick with sign(sk, m)
and not change the BIP to sign(sk, m, tag)
(and see #207 (comment) for reasons why this change is not great).
If you ask me, I believe the user should have full control over the message for maximum flexibility. Anyway, we can't stop the user from encoding anything into message, nor can't we magically save him from any encoding/decoding issues. I'm not too concerned that @sipa's approach hands over a foot gun to the user. If the users don't get intra-application domain separation right, no library will be enough to save them. And inter-application domain separation is not that big of an issue.
If one adds advice/docs to bitcoin-core/secp256k1#844, then it will still leave the user with no practical way to follow this advice: "Okay, if I'm supposed to prehash the message then please give me a function for this!". And this is indeed strange. Any library that implements BIP340 has all the functionality included, so why would it not offer this to the user? [1]
So for me the ideal API has sign(sk, m)
but also alternatives like hash_and_sign(sk, m)
and tag_and_sign(sk, m, tag)
[2]. And it has nice API docs that explain domain separation and how it can be done.
[1] In the case of secp256k1 in particular, I think some of this is due to secp256k1 being thought as "the crypto library used for Bitcoin Core (and only for Bitcoin Core)". Since Bitcoin Core anyway implements SHA256, so there's no need to export it in secp256k1. But I believe this is the wrong way to look at it, simply because the maintainers have decided to target other users than only Bitcoin Core.
[2] Don't pin me down to the exact names. This can also be done by providing only sign(sk, m)
and "helper" functions like SHA256(m)
and tag_message(m, tag)
.
from bips.
While working on DLC stuff I've noticed this "message hash" creep out and become an unhelpful abstraction in itself. For an example in the wild see these test cases which test against message hashes rather than just messages: https://github.com/discreetlogcontracts/dlcspecs/blob/master/test/dlc_schnorr_test.json
I think much of this comes from users being familiar with ECDSA signatures and libsecp256k1's misleading API that expects prehashed messages.
I also remember when we were setting up a DLC we had problems because one implementation was interpreting the output of SHA256 as a U256 and then passing the little-endian encoding to the sign function. It took quite some time to get to the bottom of this on slack.
Yeah, ok, but this is just plain wrong. Hashes are byte strings, not integers. Maybe some of this thinking comes from the fact that Bitcoin sometimes interprets hashes as unsigned integers in little-endian...
Both of these examples are bad but I can't really see how they relate to this discussion or what we should about it.
from bips.
There pros and cons to both sides of course. But if the BIP is written in mind with @sipa's approach, it seems cumbersome or at least inelegant to force @LLFourn's approach onto this, and this becomes apparent in secp25k1fun. So I think what secp25k1fun does is simply not nicely compatible this BIP.
I agree. FWIW, I think the way it works now in schnorr_fun
is very awkward. I'm thinking there should just be a Message
enum like:
pub enum Message<'a> {
// The message has already been hashed
Prehashed(&'a [u8;32]),
// Will tag the hash with `tag` and use the resulting state to hash `message`
Unhashed { tag: &'a static str, &'a [u8] },
// Does not pre-hash the message
Plain { tag: &'static str, message: &'a [u8] }
}
With the variants corresponding to the three cases you suggested.
So for me the ideal API has
sign(sk, m)
but also alternatives likehash_and_sign(sk, m)
andtag_and_sign(sk, m, tag)
[2]. And it has nice API docs that explain domain separation and how it can be done.
If you provide sign_*
APIs you probably want to provide verify_*
versions too! And then what about adaptor signatures, MuSig etc? In rust it's easy enough to ask the Message<'a>
enum to hash itself into a SHA256
instance so I don't need to worry about creating multiple function variants in the API.
Both of these examples are bad but I can't really see how they relate to this discussion or what we should about it.
Isn't whether to support variable length messages in BIP340 the discussion we're having? Motivating in-the-wild examples of problems with the current API seemed relevant. I don't want to make too much of them. These kind of mistakes might not result in security issues but the current API is at least more time consuming than it needs to be to get right (and my observations demonstrate this is not just a theoretical).
from bips.
If you provide
sign_*
APIs you probably want to provideverify_*
versions too!
Indeed.
And then what about adaptor signatures, MuSig etc? In rust it's easy enough to ask the
Message<'a>
enum to hash itself into aSHA256
instance so I don't need to worry about creating multiple function variants in the API.
Am I right that your concern is that there will be too many choices then with musig_prehashed
, s2c_unhashed
, etc... ? I agree, this really looks like a mess. But I think it the API is okay if we provide SHA256
and tag_message
functions instead, as in my footnote 2.
The enum looks reasonable to me but I agree, none of this is particularly elegant. Do think offering only "plain" messages in the sign function but then also encoding functions (SHA256
and tag_message
)? The more I think about this, the more I think this is the right way and in the spirit of the proposed BIP changes. Those don't prescribe a way of encoding messages, they just offer recommendations.
Both of these examples are bad but I can't really see how they relate to this discussion or what we should about it.
Isn't whether to support variable length messages in BIP340 the discussion we're having? Motivating in-the-wild examples of problems with the current API seemed relevant. I don't want to make too much of them. These kind of mistakes might not result in security issues but the current API is at least more time consuming than it needs to be to get right (and my observations demonstrate this is not just a theoretical).
Sorry, yeah, in-the-wild examples are certainly relevant in general. My feeling was just that the reasons why these two examples went wrong are not related to the BIP or variable-length messages. (If you think they are, please explain. I might just miss the connection). Let me me expand on what I wrote.
While working on DLC stuff I've noticed this "message hash" creep out and become an unhelpful abstraction in itself. For an example in the wild see these test cases which test against message hashes rather than just messages: https://github.com/discreetlogcontracts/dlcspecs/blob/master/test/dlc_schnorr_test.json
I think much of this comes from users being familiar with ECDSA signatures and libsecp256k1's misleading API that expects prehashed messages.
So I believe people familiar with common ECDSA APIs just learned in the wrong way. This is the wrong model for BIP340, and in this case, people need to learn. Even if we wanted to modify the BIP340 to be closer to people's expectations, I don't see a way to do this. Due to pk and R being hashed in Schnorr, we can't have the user compute the hash. And if users want to pass hashes as messages, they can do this right now (as in Taproot), and there's nothing wrong with it.
I also remember when we were setting up a DLC we had problems because one implementation was interpreting the output of SHA256 as a U256 and then passing the little-endian encoding to the sign function. It took quite some time to get to the bottom of this on slack.
Yeah, ok, but this is just plain wrong. Hashes are byte strings, not integers. Maybe some of this thinking comes from the fact that Bitcoin sometimes interprets hashes as unsigned integers in little-endian...
Both the ECDSA API and the BIP340 API expects the message to be a byte string. If the user confuses integers with byte strings, then this is an issue but again I don't see what we should do about this in the BIP340.
from bips.
As a user (and I'm using bip340 via libsecp today for the offers draft), I dislike the confusion caused by having two signing modes, which then gets reflected into more complex libsecp APIs :(
Details: We have sighash_from_merkle(messagname
, fieldname
, merkle
) -> sha256 which uses tag
= "lightning" || messagename
|| fieldname
, and returns BIP-340 recommended m = SHA256(SHA256(tag
) || SHA256(tag
) || merkle
).
(messagename and fieldname are defined in the spec).
The clear guidance in BIP-340 was a delight. This was a fairly simple process, and I know how to optimize it later.
I would have more difficulty coming up with a process, let alone optimizing, a non-hashing variant. I would actually like the BIP-340 use-of-tags advice to be presented as How To Do Things, rather than noted as a recommendation.
Please don't make me work too hard! :)
from bips.
The clear guidance in BIP-340 was a delight. This was a fairly simple process, and I know how to optimize it later.
Just for my understanding: What guidance are you referring to? The current BIP does not (yet) provide guidance on how to handle variable-length messages.
from bips.
The clear guidance in BIP-340 was a delight. This was a fairly simple process, and I know how to optimize it later.
Just for my understanding: What guidance are you referring to? The current BIP does not (yet) provide guidance on how to handle variable-length messages.
It does: it tells you to hash it and prepend a tag :)
from bips.
Am I right that your concern is that there will be too many choices then with musig_prehashed, s2c_unhashed, etc... ? I agree, this really looks like a mess. But I think it the API is okay if we provide SHA256 and tag_message functions instead, as in my footnote 2.
The enum looks reasonable to me but I agree, none of this is particularly elegant. Do think offering only "plain" messages in the sign function but then also encoding functions (SHA256 and tag_message)? The more I think about this, the more I think this is the right way and in the spirit of the proposed BIP changes. Those don't prescribe a way of encoding messages, they just offer recommendations.
Yes that seems like the easiest way forward.
Sorry, yeah, in-the-wild examples are certainly relevant in general. My feeling was just that the reasons why these two examples went wrong are not related to the BIP or variable-length messages. (If you think they are, please explain. I might just miss the connection). Let me me expand on what I wrote.
They are related because if they were using the variable length API they couldn't have made these mistakes. As absurdly unlikely as the "little-endian" encoding thing is to ever occur again, it's just an (extreme) example of the friction that is created by hashing things. Of course, out of all the friction that comes into dealing with Bitcoin as a system this doesn't even make the top 20. I guess I just want to have nice things for once!
Details: We have sighash_from_merkle(messagname, fieldname, merkle) -> sha256 which uses tag = "lightning" || messagename || fieldname, and returns BIP-340 recommended m = SHA256(SHA256(tag) || SHA256(tag) || merkle).
I can think of three ways that you could have gone about this with the current spec:
- Put
messagename
andfieldname
in the tag (what you did). This means to optimize it you have to keep around a precomputed sha256 state for every distinctmessagename
-fieldname
combination. - Only put
lightning
in the tag. Then specify a standard way to prefix the main message with a purpose string like<messagename>/<fieldname>;
. This means only keeping around one pre-computed hash for all "lightning" related signatures and would be just as efficient as (1) as long as the prefix is 23 bytes or less. - Use a tagged hash with
messagename
andfieldname
to produce the merkle tree itself. Or do something like (2) where the tagged hash is just "lightning" and each node hash (or maybe just the root) is prefixed by a purpose string so you don't have to keep one pre-computed tag for every possible combination. This is option is optimal.
My preference would be for (3) since it is optimal and follows more closely to how BIP341 uses BIP340.
The clear guidance in BIP-340 was a delight. This was a fairly simple process, and I know how to optimize it later.
I would have more difficulty coming up with a process, let alone optimizing, a non-hashing variant. I would actually like the
BIP-340 use-of-tags advice to be presented as How To Do Things, rather than noted as a recommendation.
With the variable length message API you don't have to optimize it since it is already optimal. The procedure is:
- create zeroed array of
64 + msg.len
length. - write tag to the first
tag.len
bytes - write
msg
from the 65th byte onwards. - sign the array
If for some reason you didn't want to go with (3) then I suggest using the variable length API would be preferable to (1) and (2) in most cases. The one exception is where don't want to allocate your message in contiguous memory because it's too big or something.
Granted, (1) is the most straightforward choice but I'm not sure if it should be the "standard". Now that I think about it -- this is not the first time I've seen (1). @benthecarman originally suggested committing to a message type in the tag. This seems to be your intuition as well. I objected since if we wanted to make it optimal we would have to keep all these tagged hashes around for every kind of message we might sign/verify.
Of course we are only talking about nanoseconds here but having the standard way of signing arbitrary messages being variable length and therefore unoptimizable is good way to stop people wasting their time pre-computing things. In my view that is worth adding complexity to the BIP but I don't feel too strongly about it anymore.
from bips.
The clear guidance in BIP-340 was a delight. This was a fairly simple process, and I know how to optimize it later.
Just for my understanding: What guidance are you referring to? The current BIP does not (yet) provide guidance on how to handle variable-length messages.
It does: it tells you to hash it and prepend a tag :)
Well, not really. BIP340 defines a tagged hash function hash_tag(x)
and uses it internally. It doesn't say you should use this function to preprocess your messages. (Not that it matters for the discussion -- the BIP could of course to changed to say this and I see that this is your suggestion.)
Of course we are only talking about nanoseconds here but having the standard way of signing arbitrary messages being variable length and therefore unoptimizable is good way to stop people wasting their time pre-computing things.
True and I don't even think that these optimizations in the nanosecond range are the most interesting thing here. Pre-hashing the messages potentially degrades the security of the signature scheme because then we need collision resistance instead of random-prefix preimage resistance and random-prefix second preimage resistance. This was one of the main motivations to discuss this (see initial comment in this issue). I don't think we should simply throw away this potential security benefit (and this is why I'd prefer not to recommend what the lightning spec does). This is in the line of @sipa's suggestion in #207 (comment).
By the way, here's what the EdDSA RFC says, which specifies Ed25519, Ed25519ph (=prehashed), Ed25519ctx (=context, what we call tag) in the relevant sections:
https://www.rfc-editor.org/rfc/rfc8032.html#section-4 (This brings up another aspect, namely "single pass".)
https://www.rfc-editor.org/rfc/rfc8032.html#section-8.3
These many variants are really confusing... Idk. With that in mind, I tend to think that keeping the possible variants out of the formal spec (and just as a recommendation)is actually a good idea. Then users can and will still do what they want but at least every API implementing BIP340 will be compatible with it.
In my view that is worth adding complexity to the BIP but I don't feel too strongly about it anymore.
So, it's easier to have a discussion about concrete proposals. What's your proposal? (Sorry if the answer to that question can be found somewhere above. I'm somewhat lost in this discussion, and I feel I'm not the only one. But this feeling should not discourage us from having the discussion.)
from bips.
True and I don't even think that these optimizations in the nanosecond range are the most interesting thing here. Pre-hashing the messages potentially degrades the security of the signature scheme because then we need collision resistance instead of random-prefix preimage resistance and random-prefix second preimage resistance. This was one of the main motivations to discuss this (see initial comment in this issue). I don't think we should simply throw away this potential security benefit (and this is why I'd prefer not to recommend what the lightning spec does). This is in the line of @sipa's suggestion in #207 (comment).
I dismissed this point since if CR is broken in SHA256 then we are in serious in general. But on second thought I agree with you. If CR in SHA256 is broken then it would be better to only be putting out fires in things related to the bitcoin protocol and not every other layer above it just because it uses BIP340 for something.
https://www.rfc-editor.org/rfc/rfc8032.html#section-4 (This brings up another aspect, namely "single pass".)
I couldn't figure out what they meant by "single pass" here?
So, it's easier to have a discussion about concrete proposals. What's your proposal? (Sorry if the answer to that question can be found somewhere above. I'm somewhat lost in this discussion, and I feel I'm not the only one. But this feeling should not discourage us from having the discussion.)
I think @sipa 's proposal is the best way forward. It looks like we are in furious agreement on that :).
FWIW if I put everything I've learned from this thread together and if we could do it all again, then I think changing BIP341 to prefix its message with 0x06"BIP341"
and then saying "all applications using BIP340 should prefix their message with a 1-byte tag length and application tag" would be my pick for since it requires no discussion of "pre-hashing" or "hash tagging" and is optimal.
from bips.
I dismissed this point since if CR is broken in SHA256 then we are in serious in general. But on second thought I agree with you. If CR in SHA256 is broken then it would be better to only be putting out fires in things related to the bitcoin protocol and not every other layer above it just because it uses BIP340 for something.
I think it's really hard to predict what could happen. Even CR is not binary thing. Maybe will be possible to collide blocks but not transactions, who knows?
I guess if your protocol relies on block hashes or transaction hashes somewhere (like Bitcoin itself but also Lightning for instance), then it doesn't matter in the end. But there could be other applications, even in the Bitcoin world.
https://www.rfc-editor.org/rfc/rfc8032.html#section-4 (This brings up another aspect, namely "single pass".)
I couldn't figure out what they meant by "single pass" here?
I think they mean that the signing algorithms needs to process the message for the nonce hash and then a second time for the challenge hash.
So, it's easier to have a discussion about concrete proposals. What's your proposal? (Sorry if the answer to that question can be found somewhere above. I'm somewhat lost in this discussion, and I feel I'm not the only one. But this feeling should not discourage us from having the discussion.)
I think @sipa 's proposal is the best way forward. It looks like we are in furious agreement on that :).
FWIW if I put everything I've learned from this thread together and if we could do it all again, then I think changing BIP341 to prefix its message with0x06"BIP341"
and then saying "all applications using BIP340 should prefix their message with a 1-byte tag length and application tag" would be my pick for since it requires no discussion of "pre-hashing" or "hash tagging" and is optimal.
Ok, I think I'll try to create a PR then.
from bips.
At a high level this all sounds good. I'm not going to spend too much time on it, but if someone opens a PR I'm happy to look over it.
from bips.
For x-reference, there's been some discussion relevant to this on the mailing list https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019193.html with respect to a CHECKSIGFROMSTACK opcode taking a variable length non hashed message (0-520 bytes).
from bips.
Related Issues (20)
- bip-schnorr/taproot agree on terminology of points HOT 6
- bip-taproot: Add security argument HOT 5
- bip-taproot: Internal pubkey construction seems to be inconsistent. HOT 3
- bip-taproot: Motivation section doesn't address motivation clearly HOT 2
- Diagram under "Constructing and spending Taproot outputs" doesn't show HOT 2
- bip-taproot/tapscript: Prevention length-extension attacks in public key tweaking HOT 6
- bip-schnorr: Euler's criterion
- bip-schnorr: Inaccurate proof of quadratic residuosity HOT 2
- Syntactical issue in taproot footnote 16 HOT 2
- bip-taproot: Publick key tweak resulting in point-at-infinity HOT 5
- bip-schnorr: Add k values to test-vectors HOT 8
- Avoiding the EC multiplication during signing by using precomputed pubkey data HOT 15
- Squareness vs oddness tie-breaker for public keys HOT 8
- Discussion on power analysis attacks HOT 47
- bip-schnorr: nonce uses hash instead of PRF HOT 2
- Synthetic randomness for batch verification HOT 2
- Clarify relationship between synthetic nonces and anti-covert-channel HOT 1
- bip340: Cite malleability issues with other schemes
- bip-340: Reduce size of batch verification randomizers to 128 bits HOT 4
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from bips.