Update BIP 340 with fresher info on multi-, threshold, and blind signatures

yannickseurin commented at 9:46 am on April 30, 2024: contributor

Info and links about multi-, threshold, and blind signatures was a bit out of date.

updating info on multi-, threshold, and blind signatures f75184b8d8

link to BIP327 2c017b0c0b

murchandamus commented at 5:35 pm on April 30, 2024: contributor

Paging @sipa, @real-or-random, and @jonasnick for review

murchandamus added the label enhancement on Apr 30, 2024

real-or-random commented at 9:54 pm on May 2, 2024: contributor

Thanks for the PR. I think all of these changes make sense, but I wonder to what extent this should be a living document. My view is that we should certainly take care of the technical /normative sections and fix bugs and clarify things there whenever necessary. This is more of a motivational section, so I think it’s not strictly required to keep it updated.

But pragmatically speaking, people keep getting confused about this, so why not point them to the recent research. It’s just a bit strange that some of these papers cite BIP340 as a motivation, so it will be a bit cyclic now after the PR. (Perhaps add a line in the changelog section?)

in bip-0340.mediawiki:65 in 2c017b0c0b outdated

61@@ -62,7 +62,7 @@ Since we would like to avoid the fragility that comes with short hashes, the ''e
62 
63 '''Key prefixing''' Using the verification rule above directly makes Schnorr signatures vulnerable to "related-key attacks" in which a third party can convert a signature ''(R, s)'' for public key ''P'' into a signature ''(R, s + a⋅hash(R || m))'' for public key ''P + a⋅G'' and the same message ''m'', for any given additive tweak ''a'' to the signing key. This would render signatures insecure when keys are generated using [[bip-0032.mediawiki#public-parent-key--public-child-key|BIP32's unhardened derivation]] and other methods that rely on additive tweaks to existing keys such as Taproot.
64 
65-To protect against these attacks, we choose ''key prefixed''<ref>A limitation of committing to the public key (rather than to a short hash of it, or not at all) is that it removes the ability for public key recovery or verifying signatures against a short public key hash. These constructions are generally incompatible with batch verification.</ref> Schnorr signatures which means that the public key is prefixed to the message in the challenge hash input. This changes the equation to ''s⋅G = R + hash(R || P || m)⋅P''. [https://eprint.iacr.org/2015/1135.pdf It can be shown] that key prefixing protects against related-key attacks with additive tweaks. In general, key prefixing increases robustness in multi-user settings, e.g., it seems to be a requirement for proving the MuSig multisignature scheme secure (see Applications below).
66+To protect against these attacks, we choose ''key prefixed''<ref>A limitation of committing to the public key (rather than to a short hash of it, or not at all) is that it removes the ability for public key recovery or verifying signatures against a short public key hash. These constructions are generally incompatible with batch verification.</ref> Schnorr signatures which means that the public key is prefixed to the message in the challenge hash input. This changes the equation to ''s⋅G = R + hash(R || P || m)⋅P''. [https://eprint.iacr.org/2015/1135.pdf It can be shown] that key prefixing protects against related-key attacks with additive tweaks. In general, key prefixing increases robustness in multi-user settings, e.g., it seems to be a requirement for proving the MuSig2 multisignature scheme secure (see Applications below).

jonasnick commented at 7:35 am on May 3, 2024:

I think this makes the case for using key prefixing weaker because a possible interpretation of the sentence now is that it is possible to use MuSig(1) without key prefix instead. Maybe give MuSig, MuSig2 and FROST as examples?

I’m just mentioning this because the question why pubkey prefixing is required by BIP 340 (and therefore does not support recovering a public key from a signature) comes up regularly.

yannickseurin commented at 8:25 am on May 3, 2024:

Agreed, more generally one could say “for proving multiparty signature protocols (such as MuSig, MuSig2, and FROST) secure”.

jonasnick commented at 7:39 am on May 3, 2024: contributor

I think it makes sense to pragmatically try to reduce the confusion the document causes to today’s readers. I think the main improvement of this PR, which I am happy to concept ACK is replacing

However, the practicality of the existing schemes is limited: most schemes in the literature have been proven secure only for the case ‘‘k-1 < n/2’’, are not secure when used concurrently in multiple sessions, or require a reliable broadcast mechanism to be secure. Further research is necessary to improve this situation.

with a reference to FROST.

yannickseurin commented at 8:23 am on May 3, 2024: contributor

I agree that the informational/motivational sections are not intended to be constantly updated, but my concern was that this document might be the entry point to the topic for many people unfamiliar with it and so it might be beneficial to have more recent pointers. But of course feel free to cherry pick whatever you like !

more precise wording for key-prefixing justification 1ed7d03393

update changelog 4dcdadee67

sipa commented at 1:05 pm on May 3, 2024: member

I’m happy with 4dcdadee675db63e241cda71cdfca9ebe96ce0bf if the other authors agree.

in bip-0340.mediawiki:269 in 4dcdadee67 outdated

263@@ -264,9 +264,9 @@ While recent academic papers claim that they are also possible with ECDSA, conse
264 
265 === Multisignatures and Threshold Signatures ===
266 
267-By means of an interactive scheme such as [https://eprint.iacr.org/2018/068 MuSig], participants can aggregate their public keys into a single public key which they can jointly sign for. This allows ''n''-of-''n'' multisignatures which, from a verifier's perspective, are no different from ordinary signatures, giving improved privacy and efficiency versus ''CHECKMULTISIG'' or other means.
268+By means of an interactive scheme such as [https://eprint.iacr.org/2020/1261.pdf MuSig2] ([[bip-0327.mediawiki|BIP327]]), participants can aggregate their public keys into a single public key which they can jointly sign for. This allows ''n''-of-''n'' multisignatures which, from a verifier's perspective, are no different from ordinary signatures, giving improved privacy and efficiency versus ''CHECKMULTISIG'' or other means.
269 
270-Moreover, Schnorr signatures are compatible with [https://web.archive.org/web/20031003232851/http://www.research.ibm.com/security/dkg.ps distributed key generation], which enables interactive threshold signatures schemes, e.g., the schemes described by [http://cacr.uwaterloo.ca/techreports/2001/corr2001-13.ps Stinson and Strobl (2001)] or [https://web.archive.org/web/20060911151529/http://theory.lcs.mit.edu/~stasio/Papers/gjkr03.pdf Gennaro, Jarecki and Krawczyk (2003)]. These protocols make it possible to realize ''k''-of-''n'' threshold signatures, which ensure that any subset of size ''k'' of the set of ''n'' signers can sign but no subset of size less than ''k'' can produce a valid Schnorr signature. However, the practicality of the existing schemes is limited: most schemes in the literature have been proven secure only for the case ''k-1 < n/2'', are not secure when used concurrently in multiple sessions, or require a reliable broadcast mechanism to be secure. Further research is necessary to improve this situation.
271+Moreover, Schnorr signatures are compatible with [https://en.wikipedia.org/wiki/Distributed_key_generation distributed key generation], which enables interactive threshold signatures schemes, e.g., the schemes described by [http://cacr.uwaterloo.ca/techreports/2001/corr2001-13.ps Stinson and Strobl (2001)], [https://link.springer.com/content/pdf/10.1007/s00145-006-0347-3.pdf Gennaro, Jarecki, Krawczyk, and Rabin (2007)], [https://eprint.iacr.org/2020/852.pdf Komlo and Goldberg (2020)], or [https://eprint.iacr.org/2023/899.pdf Chu, Gerhart, Ruffing, and Schröder (2023)]. These protocols make it possible to realize ''k''-of-''n'' threshold signatures, which ensure that any subset of size ''k'' of the set of ''n'' signers can sign but no subset of size less than ''k'' can produce a valid Schnorr signature.

real-or-random commented at 10:23 am on May 4, 2024:

0Moreover, Schnorr signatures are compatible with [https://en.wikipedia.org/wiki/Distributed_key_generation distributed key generation], which enables interactive threshold signatures schemes, e.g., the schemes by [http://cacr.uwaterloo.ca/techreports/2001/corr2001-13.ps Stinson and Strobl (2001)], by [https://link.springer.com/content/pdf/10.1007/s00145-006-0347-3.pdf Gennaro, Jarecki, Krawczyk, and Rabin (2007)], or the [https://eprint.iacr.org/2020/852.pdf FROST] scheme including its variants such as [https://eprint.iacr.org/2023/899.pdf FROST3]. These protocols make it possible to realize ''k''-of-''n'' threshold signatures, which ensure that any subset of size ''k'' of the set of ''n'' signers can sign but no subset of size less than ''k'' can produce a valid Schnorr signature.

I think spelling out the name FROST is a good idea, and it’s also more consistent with the rest of the doc. (I think we used author names only due to the lack of more common names.)

in bip-0340.mediawiki:65 in 4dcdadee67 outdated

61@@ -62,7 +62,7 @@ Since we would like to avoid the fragility that comes with short hashes, the ''e
62 
63 '''Key prefixing''' Using the verification rule above directly makes Schnorr signatures vulnerable to "related-key attacks" in which a third party can convert a signature ''(R, s)'' for public key ''P'' into a signature ''(R, s + a⋅hash(R || m))'' for public key ''P + a⋅G'' and the same message ''m'', for any given additive tweak ''a'' to the signing key. This would render signatures insecure when keys are generated using [[bip-0032.mediawiki#public-parent-key--public-child-key|BIP32's unhardened derivation]] and other methods that rely on additive tweaks to existing keys such as Taproot.
64 
65-To protect against these attacks, we choose ''key prefixed''<ref>A limitation of committing to the public key (rather than to a short hash of it, or not at all) is that it removes the ability for public key recovery or verifying signatures against a short public key hash. These constructions are generally incompatible with batch verification.</ref> Schnorr signatures which means that the public key is prefixed to the message in the challenge hash input. This changes the equation to ''s⋅G = R + hash(R || P || m)⋅P''. [https://eprint.iacr.org/2015/1135.pdf It can be shown] that key prefixing protects against related-key attacks with additive tweaks. In general, key prefixing increases robustness in multi-user settings, e.g., it seems to be a requirement for proving the MuSig multisignature scheme secure (see Applications below).
66+To protect against these attacks, we choose ''key prefixed''<ref>A limitation of committing to the public key (rather than to a short hash of it, or not at all) is that it removes the ability for public key recovery or verifying signatures against a short public key hash. These constructions are generally incompatible with batch verification.</ref> Schnorr signatures which means that the public key is prefixed to the message in the challenge hash input. This changes the equation to ''s⋅G = R + hash(R || P || m)⋅P''. [https://eprint.iacr.org/2015/1135.pdf It can be shown] that key prefixing protects against related-key attacks with additive tweaks. In general, key prefixing increases robustness in multi-user settings, e.g., it seems to be a requirement for proving multiparty signature protocols (such as MuSig, MuSig2, and FROST) secure (see Applications below).

real-or-random commented at 10:23 am on May 4, 2024:

perhaps a bit more precise:

0To protect against these attacks, we choose ''key prefixed''<ref>A limitation of committing to the public key (rather than to a short hash of it, or not at all) is that it removes the ability for public key recovery or verifying signatures against a short public key hash. These constructions are generally incompatible with batch verification.</ref> Schnorr signatures which means that the public key is prefixed to the message in the challenge hash input. This changes the equation to ''s⋅G = R + hash(R || P || m)⋅P''. [https://eprint.iacr.org/2015/1135.pdf It can be shown] that key prefixing protects against related-key attacks with additive tweaks. In general, key prefixing increases robustness in multi-user settings, e.g., it seems to be a requirement for proving multiparty signing protocols (such as MuSig, MuSig2, and FROST) secure (see Applications below).

spelling out FROST

Co-authored-by: Tim Ruffing <crypto@timruffing.de>

1f1f24f0ef

more precise wording

Co-authored-by: Tim Ruffing <crypto@timruffing.de>

5d10163efc

real-or-random approved

real-or-random commented at 9:58 am on May 6, 2024: contributor

ACK 5d10163efc36331eba5426dd854d91f0f68170f4

murchandamus commented at 3:05 pm on May 6, 2024: contributor

Given that @sipa and @jonasnick were both active here recently with conditional ACKs and changes requested, I’m also waiting for their ACKs.

jonasnick approved

jonasnick commented at 3:15 pm on May 6, 2024: contributor

I don’t know what the policy is in this repo regarding clean commit histories, but the changes look good to me.

ACK 5d10163efc36331eba5426dd854d91f0f68170f4

murchandamus commented at 3:44 pm on May 6, 2024: contributor

The BIP editors have ranging preferences on Squashing and Git Commit hygiene, so we do not require any special effort to present a neat commit history.

sipa commented at 4:04 pm on May 6, 2024: member

ACK 5d10163efc36331eba5426dd854d91f0f68170f4

murchandamus merged this on May 6, 2024

murchandamus closed this on May 6, 2024

yannickseurin deleted the branch on May 7, 2024

Update BIP 340 with fresher info on multi-, threshold, and blind signatures #1583