BIP340: Variable-length messages / domain separation

[real-or-random]

Solves https://github.com/sipa/bips/issues/207.

I tried to avoid going into collision-resistance vs random-prefix resistance. It's hard to explain, and the situation is not entirely clear, e.g., due to https://eprint.iacr.org/2015/509.pdf which claims a flaw in the paper http://www.neven.org/papers/schnorr.pdf which cite in the BIP (we may want to add a footnote to the BIP...).

TODO:

• [x] Test vectors for varlen messages
• [x] Do we want a small changelog?

@sipa Can you update the bip-taproot brach to bitcoin/master

[real-or-random]

Forced-push to address @jonasnick's comments.

[real-or-random]

Updated. This also takes the #211 into account now.

[real-or-random]

@jonasnick @sipa Would be nice to have ACKs on the method before I'll generate test vectors.

[sipa]

You seem to have a bunch of unrelated commits in here?

[real-or-random]

@sipa Can you update the bip-taproot brach to bitcoin/master

[sipa]

@real-or-random Oops, I didn't realize this was opened against my repo.

[sipa]

@real-or-random I've updated my bip-taproot branch, in case you want to update.

[real-or-random]

rebased

[sipa]

Concept ACK

[real-or-random]

cc @llfourn

[LLFourn]

ACK. 33 bytes seems straightforward and easy to explain. It looks like in schnorr_fun I already did the 64 byte pad. I'll probably just leave that as is and document it.

[real-or-random]

@jonasnick suggested in https://github.com/jonasnick/bips/pull/24#discussion_r940614556 to have an explicit upper limit of message size, e.g., 2^48 (we could also make it 2^60 or even 2^62):

Pros:

1. This will make the limit explicit. At the moment, the limit is implicitly defined, and at least for signing will depend on concrete nonce function. This could help formal methods.
2. It will avoid some potential buffer/integer overflows on 64-bit machine. Even if they are just theoretical, this could help formal verification (when applied to implementations).
3. If you really manage to pass a message of size around 2^61 B (= 2048 PiB), the limit will catch SHA256 implementations that don't check for counter overflow (e.g., the implementation in libsecp256k1 does not check in production).
4. A limit of 2^48 will also guarantee that a future half-agg spec could concatenate some number of these messages without hitting the 2^61 limit (but see below).

Cons:

1. Noone will ever sign a message of size 2048 PiB (a least before we can break dlog in secp256k1).
2. It adds a branch.

My opinion:

I don't think "Pro 4" is helpful in practice: Even if we have an upper bound of 2^48, this does not guarantee that all implementation will accept messages of this size. Many implementations will want reject them, e.g., implementations on 32-bit platforms.

Similarly, I think a limit wouldn't help make verification identical across implementations (again because implementations will have their own upper bounds).

So I tend to think that "Noone will ever sign a message of size 2048 PiB." convinces me. My standpoint is that we're just giving a generic algorithms, any application or protocol using the BIP will need to specify message formats, and this include a maximum message size, which will probably be well below 2^48. If formal methods need a limit, they could still introduce one in their theorems, and then the restricted theorem would still cover any real world protocol.

[jonasnick]

An upper bound on the message length that's much smaller than 2^61 would allow claiming that BIP-musig can sign any message that BIP-schnorr can or that BIP-half-agg can verify any signature that BIP-schnorr can. With the assumption that "Noone will ever hash an input of size 2048 PiB" (slightly strong than "Noone will ever sign a message of size 2048 PiB") then you can still make this claim (even with formal methods). I'm fine working under this assumption to avoid complexity. If you'd want to make use of an upper bound like 2^48 in a half aggregation spec you'd need to do annoying caclulations to figure out how many signatures you can actually verify and put an upper bound on that as well (the current draft already has an upper bound on it due to potential integer overflows).

Stating the upper bound that stems from SHA256 explicitly (close to 2^61) doesn't seem particularly useful right now. I think the footnote is fine.

[real-or-random]

This could also cite https://ed25519.cr.yp.to/eddsa-20150704.pdf for its last paragraph.

[sipa]

Concept ACK apart from nits.

[real-or-random]

addressed all nits by @sipa

This could also cite ed25519.cr.yp.to/eddsa-20150704.pdf for its last paragraph.

I made the effort to mention their main arguments instead (reliance on collision-resistance, need to keep the message in memory while signing). And then there's no need to cite this, this is common knowledge...

[real-or-random]

forced-push to address nits by @sipa

[sipa]

Do you want to just PR it to the bips repo now?

[real-or-random]

Do you want to just PR it to the bips repo now?

No, we have more local changes here: https://github.com/bitcoin/bips/compare/master...sipa:bips:bip-taproot

[sipa]

Opened BIPs repo PR: https://github.com/bitcoin/bips/pull/1446