BIP 0340 - Revision history

934: Update BIP text with latest version from https://github.com/bitcoin/bips/blob/8808e78883e4bf95/bip-0340.mediawiki

2024-05-06T17:37:17Z

Update BIP text with latest version from https://github.com/bitcoin/bips/blob/8808e78883e4bf95/bip-0340.mediawiki

← Older revision		Revision as of 17:37, 6 May 2024
Line 66:		Line 66:
	'''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.		'''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.

	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).		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 signing protocols (such as MuSig, MuSig2, and FROST) secure (see Applications below).

	We note that key prefixing is not strictly necessary for transaction signatures as used in Bitcoin currently, because signed transactions indirectly commit to the public keys already, i.e., ''m'' contains a commitment to ''pk''. However, this indirect commitment should not be relied upon because it may change with proposals such as SIGHASH_NOINPUT ([[bip-0118.mediawiki\|BIP118]]), and would render the signature scheme unsuitable for other purposes than signing transactions, e.g., [https://bitcoin.org/en/developer-reference#signmessage signing ordinary messages].		We note that key prefixing is not strictly necessary for transaction signatures as used in Bitcoin currently, because signed transactions indirectly commit to the public keys already, i.e., ''m'' contains a commitment to ''pk''. However, this indirect commitment should not be relied upon because it may change with proposals such as SIGHASH_NOINPUT ([[bip-0118.mediawiki\|BIP118]]), and would render the signature scheme unsuitable for other purposes than signing transactions, e.g., [https://bitcoin.org/en/developer-reference#signmessage signing ordinary messages].
Line 169:		Line 169:
	'''Nonce exfiltration protection''' It is possible to strengthen the nonce generation algorithm using a second device. In this case, the second device contributes randomness which the actual signer provably incorporates into its nonce. This prevents certain attacks where the signer device is compromised and intentionally tries to leak the secret key through its nonce selection.		'''Nonce exfiltration protection''' It is possible to strengthen the nonce generation algorithm using a second device. In this case, the second device contributes randomness which the actual signer provably incorporates into its nonce. This prevents certain attacks where the signer device is compromised and intentionally tries to leak the secret key through its nonce selection.

	'''Multisignatures''' This signature scheme is compatible with various types of multisignature and threshold schemes such as [https://eprint.iacr.org/~~2018~~/~~068 MuSig~~], where a single public key requires holders of multiple secret keys to participate in signing (see Applications below).		'''Multisignatures''' This signature scheme is compatible with various types of multisignature and threshold schemes such as [https://eprint.iacr.org/2020/1261.pdf MuSig2], where a single public key requires holders of multiple secret keys to participate in signing (see Applications below).
	'''It is important to note that multisignature signing schemes in general are insecure with the ''rand'' generation from the default signing algorithm above (or any other deterministic method).'''		'''It is important to note that multisignature signing schemes in general are insecure with the ''rand'' generation from the default signing algorithm above (or any other deterministic method).'''

Line 268:		Line 268:
	=== Multisignatures and Threshold Signatures ===		=== Multisignatures and Threshold Signatures ===

	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.		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.

	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.		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 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.

	=== Adaptor Signatures ===		=== Adaptor Signatures ===
Line 282:		Line 282:
	=== Blind Signatures ===		=== Blind Signatures ===

	A blind signature protocol is an interactive protocol that enables a signer to sign a message at the behest of another party without learning any information about the signed message or the signature. Schnorr signatures admit a very [http://publikationen.ub.uni-frankfurt.de/files/4292/schnorr.blind_sigs_attack.2001.pdf simple blind signature scheme] which is however insecure because it's vulnerable to [https://www.iacr.org/archive/crypto2002/24420288/24420288.pdf Wagner's attack]. ~~A known mitigation is~~ to let the signer abort a signing session with a certain probability, ~~and the resulting scheme~~ can be [https://eprint.iacr.org/2019/877 proven secure under non-standard cryptographic assumptions].		A blind signature protocol is an interactive protocol that enables a signer to sign a message at the behest of another party without learning any information about the signed message or the signature. Schnorr signatures admit a very [http://publikationen.ub.uni-frankfurt.de/files/4292/schnorr.blind_sigs_attack.2001.pdf simple blind signature scheme] which is however insecure because it's vulnerable to [https://www.iacr.org/archive/crypto2002/24420288/24420288.pdf Wagner's attack]. Known mitigations are to let the signer abort a signing session with a certain probability, which can be [https://eprint.iacr.org/2019/877 proven secure under non-standard cryptographic assumptions], or [https://eprint.iacr.org/2022/1676.pdf to use zero-knowledge proofs].

	Blind Schnorr signatures could for example be used in [https://github.com/ElementsProject/scriptless-scripts/blob/master/md/partially-blind-swap.md Partially Blind Atomic Swaps], a construction to enable transferring of coins, mediated by an untrusted escrow agent, without connecting the transactors in the public blockchain transaction graph.		Blind Schnorr signatures could for example be used in [https://github.com/ElementsProject/scriptless-scripts/blob/master/md/partially-blind-swap.md Partially Blind Atomic Swaps], a construction to enable transferring of coins, mediated by an untrusted escrow agent, without connecting the transactors in the public blockchain transaction graph.
Line 297:		Line 297:
	* 2022-08: Fix function signature of lift_x in reference code		* 2022-08: Fix function signature of lift_x in reference code
	* 2023-04: Allow messages of arbitrary size		* 2023-04: Allow messages of arbitrary size
			* 2024-05: Update "Applications" section with more recent references

	== Footnotes ==		== Footnotes ==

934: Update BIP text with latest version from https://github.com/bitcoin/bips/blob/0ea600548846d35b/bip-0340.mediawiki

2023-05-29T09:34:43Z

Update BIP text with latest version from https://github.com/bitcoin/bips/blob/0ea600548846d35b/bip-0340.mediawiki

@@ Line 90: / Line 90: @@
 For example, without tagged hashing a BIP340 signature could also be valid for a signature scheme where the only difference is that the arguments to the hash function are reordered. Worse, if the BIP340 nonce derivation function was copied or independently created, then the nonce could be accidentally reused in the other scheme leaking the secret key.
-This proposal suggests to include the tag by prefixing the hashed data with ''SHA256(tag) || SHA256(tag)''. Because this is a 64-byte long context-specific constant and the ''SHA256'' block size is also 64 bytes, optimized implementations are possible (identical to SHA256 itself, but with a modified initial state). Using SHA256 of the tag name itself is reasonably simple and efficient for implementations that don't choose to use the optimization.
+This proposal suggests to include the tag by prefixing the hashed data with ''SHA256(tag) || SHA256(tag)''. Because this is a 64-byte long context-specific constant and the ''SHA256'' block size is also 64 bytes, optimized implementations are possible (identical to SHA256 itself, but with a modified initial state). Using SHA256 of the tag name itself is reasonably simple and efficient for implementations that don't choose to use the optimization. In general, tags can be arbitrary byte arrays, but are suggested to be textual descriptions in UTF-8 encoding.
 '''Final scheme''' As a result, our final scheme ends up using public key ''pk'' which is the X coordinate of a point ''P'' on the curve whose Y coordinate is even and signatures ''(r,s)'' where ''r'' is the X coordinate of a point ''R'' whose Y coordinate is even. The signature satisfies ''s⋅G = R + tagged_hash(r || pk || m)⋅P''.
@@ Line 120: / Line 120: @@
 *** Fail if ''c &ne; y<sup>2</sup> mod p''.
 *** Return the unique point ''P'' such that ''x(P) = x'' and ''y(P) = y'' if ''y mod 2 = 0'' or ''y(P) = p-y'' otherwise.
-** The function ''hash<sub>tag</sub>(x)'' where ''tag'' is a UTF-8 encoded tag name and ''x'' is a byte array returns the 32-byte hash ''SHA256(SHA256(tag) || SHA256(tag) || x)''.
+** The function ''hash<sub>name</sub>(x)'' where ''x'' is a byte array returns the 32-byte hash ''SHA256(SHA256(tag) || SHA256(tag) || x)'', where ''tag'' is the UTF-8 encoding of ''name''.
 ==== Public Key Generation ====
@@ Line 142: / Line 142: @@
 Input:
 * The secret key ''sk'': a 32-byte array
-* The message ''m'': a 32-byte array
+* The message ''m'': a byte array
 * Auxiliary random data ''a'': a 32-byte array
@@ Line 178: / Line 178: @@
 Input:
 * The public key ''pk'': a 32-byte array
-* The message ''m'': a 32-byte array
+* The message ''m'': a byte array
 * A signature ''sig'': a 64-byte array
@@ Line 201: / Line 201: @@
 * The number ''u'' of signatures
 * The public keys ''pk<sub>1..u</sub>'': ''u'' 32-byte arrays
-* The messages ''m<sub>1..u</sub>'': ''u'' 32-byte arrays
+* The messages ''m<sub>1..u</sub>'': ''u'' byte arrays
 * The signatures ''sig<sub>1..u</sub>'': ''u'' 64-byte arrays
@@ Line 216: / Line 216: @@
 If all individual signatures are valid (i.e., ''Verify'' would return success for them), ''BatchVerify'' will always return success. If at least one signature is invalid, ''BatchVerify'' will return success with at most a negligible probability.
 == Applications ==
@@ Line 252: / Line 296: @@
 * 2022-08: Fix function signature of lift_x in reference code
 == Footnotes ==

934: Update BIP text with latest version from https://github.com/bitcoin/bips/blob/aa5b0a1009bcb903/bip-0340.mediawiki

2023-02-27T02:46:27Z

Update BIP text with latest version from https://github.com/bitcoin/bips/blob/aa5b0a1009bcb903/bip-0340.mediawiki

← Older revision		Revision as of 02:46, 27 February 2023
Line 10:		Line 10:
	Comments-Summary: No comments yet.		Comments-Summary: No comments yet.
	Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0340		Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0340
	Status: ~~Draft~~		Status: Final
	Type: Standards Track		Type: Standards Track
	License: BSD-2-Clause		License: BSD-2-Clause

934: Update BIP text with latest version from https://github.com/bitcoin/bips/blob/52f68fecd8ec9604/bip-0340.mediawiki

2022-08-25T07:58:47Z

Update BIP text with latest version from https://github.com/bitcoin/bips/blob/52f68fecd8ec9604/bip-0340.mediawiki

← Older revision		Revision as of 07:58, 25 August 2022
Line 246:		Line 246:
	For development and testing purposes, we provide a [[bip-0340/test-vectors.csv\|collection of test vectors in CSV format]] and a naive, highly inefficient, and non-constant time [[bip-0340/reference.py\|pure Python 3.7 reference implementation of the signing and verification algorithm]].		For development and testing purposes, we provide a [[bip-0340/test-vectors.csv\|collection of test vectors in CSV format]] and a naive, highly inefficient, and non-constant time [[bip-0340/reference.py\|pure Python 3.7 reference implementation of the signing and verification algorithm]].
	The reference implementation is for demonstration purposes only and not to be used in production environments.		The reference implementation is for demonstration purposes only and not to be used in production environments.

			== Changelog ==

			To help implementors understand updates to this BIP, we keep a list of substantial changes.

			* 2022-08: Fix function signature of lift_x in reference code

	== Footnotes ==		== Footnotes ==

934: Update BIP text with latest version from https://github.com/bitcoin/bips/blob/43da5dec5eaf0d81/bip-0340.mediawiki

2022-08-04T11:41:05Z

Update BIP text with latest version from https://github.com/bitcoin/bips/blob/43da5dec5eaf0d81/bip-0340.mediawiki

← Older revision		Revision as of 11:41, 4 August 2022
Line 113:		Line 113:
	** The function ''int(x)'', where ''x'' is a 32-byte array, returns the 256-bit unsigned integer whose most significant byte first encoding is ''x''.		** The function ''int(x)'', where ''x'' is a 32-byte array, returns the 256-bit unsigned integer whose most significant byte first encoding is ''x''.
	** The function ''has_even_y(P)'', where ''P'' is a point for which ''not is_infinite(P)'', returns ''y(P) mod 2 = 0''.		** The function ''has_even_y(P)'', where ''P'' is a point for which ''not is_infinite(P)'', returns ''y(P) mod 2 = 0''.
	** The function ''lift_x(x)'', where ''x'' is an integer ~~in range ''0..p-1''~~, returns the point ''P'' for which ''x(P) = x''<ref>		** The function ''lift_x(x)'', where ''x'' is a 256-bit unsigned integer, returns the point ''P'' for which ''x(P) = x''<ref>
	Given a candidate X coordinate ''x'' in the range ''0..p-1'', there exist either exactly two or exactly zero valid Y coordinates. If no valid Y coordinate exists, then ''x'' is not a valid X coordinate either, i.e., no point ''P'' exists for which ''x(P) = x''. The valid Y coordinates for a given candidate ''x'' are the square roots of ''c = x<sup>3</sup> + 7 mod p'' and they can be computed as ''y = ±c<sup>(p+1)/4</sup> mod p'' (see [https://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus Quadratic residue]) if they exist, which can be checked by squaring and comparing with ''c''.</ref> and ''has_even_y(P)'', or fails if no such point exists. The function ''lift_x(x)'' is equivalent to the following pseudocode:		Given a candidate X coordinate ''x'' in the range ''0..p-1'', there exist either exactly two or exactly zero valid Y coordinates. If no valid Y coordinate exists, then ''x'' is not a valid X coordinate either, i.e., no point ''P'' exists for which ''x(P) = x''. The valid Y coordinates for a given candidate ''x'' are the square roots of ''c = x<sup>3</sup> + 7 mod p'' and they can be computed as ''y = ±c<sup>(p+1)/4</sup> mod p'' (see [https://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus Quadratic residue]) if they exist, which can be checked by squaring and comparing with ''c''.</ref> and ''has_even_y(P)'', or fails if ''x'' is greater than ''p-1'' or no such point exists. The function ''lift_x(x)'' is equivalent to the following pseudocode:
			*** Fail if ''x ≥ p''.
	*** Let ''c = x<sup>3</sup> + 7 mod p''.		*** Let ''c = x<sup>3</sup> + 7 mod p''.
	*** Let ''y = c<sup>(p+1)/4</sup> mod p''.		*** Let ''y = c<sup>(p+1)/4</sup> mod p''.

934: Update BIP text with latest version from https://github.com/bitcoin/bips/blob/01c07e8c5b6cd52b/bip-0340.mediawiki

2022-05-05T16:46:48Z

Update BIP text with latest version from https://github.com/bitcoin/bips/blob/01c07e8c5b6cd52b/bip-0340.mediawiki

← Older revision		Revision as of 16:46, 5 May 2022
Line 237:		Line 237:
	=== Blind Signatures ===		=== Blind Signatures ===

	A blind signature protocol is an interactive protocol that enables a signer to sign a message at the behest of another party without learning any information about the signed message or the signature. Schnorr signatures admit a very [~~https~~://~~www~~.~~math~~.uni-frankfurt.de/~~~dmst~~/~~research/papers~~/schnorr.blind_sigs_attack.2001.pdf simple blind signature scheme] which is however insecure because it's vulnerable to [https://www.iacr.org/archive/crypto2002/24420288/24420288.pdf Wagner's attack]. A known mitigation is to let the signer abort a signing session with a certain probability, and the resulting scheme can be [https://eprint.iacr.org/2019/877 proven secure under non-standard cryptographic assumptions].		A blind signature protocol is an interactive protocol that enables a signer to sign a message at the behest of another party without learning any information about the signed message or the signature. Schnorr signatures admit a very [http://publikationen.ub.uni-frankfurt.de/files/4292/schnorr.blind_sigs_attack.2001.pdf simple blind signature scheme] which is however insecure because it's vulnerable to [https://www.iacr.org/archive/crypto2002/24420288/24420288.pdf Wagner's attack]. A known mitigation is to let the signer abort a signing session with a certain probability, and the resulting scheme can be [https://eprint.iacr.org/2019/877 proven secure under non-standard cryptographic assumptions].

	Blind Schnorr signatures could for example be used in [https://github.com/ElementsProject/scriptless-scripts/blob/master/md/partially-blind-swap.md Partially Blind Atomic Swaps], a construction to enable transferring of coins, mediated by an untrusted escrow agent, without connecting the transactors in the public blockchain transaction graph.		Blind Schnorr signatures could for example be used in [https://github.com/ElementsProject/scriptless-scripts/blob/master/md/partially-blind-swap.md Partially Blind Atomic Swaps], a construction to enable transferring of coins, mediated by an untrusted escrow agent, without connecting the transactors in the public blockchain transaction graph.

934: Update BIP text with latest version from https://github.com/bitcoin/bips/blob/edffe529056f6dfd/bip-0340.mediawiki

2021-12-15T15:50:56Z

Update BIP text with latest version from https://github.com/bitcoin/bips/blob/edffe529056f6dfd/bip-0340.mediawiki

← Older revision		Revision as of 15:50, 15 December 2021
Line 60:		Line 60:
	'''Schnorr signature variant''' Elliptic Curve Schnorr signatures for message ''m'' and public key ''P'' generally involve a point ''R'', integers ''e'' and ''s'' picked by the signer, and the base point ''G'' which satisfy ''e = hash(R \|\| m)'' and ''s⋅G = R + e⋅P''. Two formulations exist, depending on whether the signer reveals ''e'' or ''R'':		'''Schnorr signature variant''' Elliptic Curve Schnorr signatures for message ''m'' and public key ''P'' generally involve a point ''R'', integers ''e'' and ''s'' picked by the signer, and the base point ''G'' which satisfy ''e = hash(R \|\| m)'' and ''s⋅G = R + e⋅P''. Two formulations exist, depending on whether the signer reveals ''e'' or ''R'':
	# Signatures are pairs ''(e, s)'' that satisfy ''e = hash(s⋅G - e⋅P \|\| m)''. This variant avoids minor complexity introduced by the encoding of the point ''R'' in the signature (see paragraphs "Encoding R and public key point P" and "Implicit Y coordinates" further below in this subsection). Moreover, revealing ''e'' instead of ''R'' allows for potentially shorter signatures: Whereas an encoding of ''R'' inherently needs about 32 bytes, the hash ''e'' can be tuned to be shorter than 32 bytes, and [http://www.neven.org/papers/schnorr.pdf a short hash of only 16 bytes suffices to provide SUF-CMA security at the target security level of 128 bits]. However, a major drawback of this optimization is that finding collisions in a short hash function is easy. This complicates the implementation of secure signing protocols in scenarios in which a group of mutually distrusting signers work together to produce a single joint signature (see Applications below). In these scenarios, which are not captured by the SUF-CMA model due its assumption of a single honest signer, a promising attack strategy for malicious co-signers is to find a collision in the hash function in order to obtain a valid signature on a message that an honest co-signer did not intend to sign.		# Signatures are pairs ''(e, s)'' that satisfy ''e = hash(s⋅G - e⋅P \|\| m)''. This variant avoids minor complexity introduced by the encoding of the point ''R'' in the signature (see paragraphs "Encoding R and public key point P" and "Implicit Y coordinates" further below in this subsection). Moreover, revealing ''e'' instead of ''R'' allows for potentially shorter signatures: Whereas an encoding of ''R'' inherently needs about 32 bytes, the hash ''e'' can be tuned to be shorter than 32 bytes, and [http://www.neven.org/papers/schnorr.pdf a short hash of only 16 bytes suffices to provide SUF-CMA security at the target security level of 128 bits]. However, a major drawback of this optimization is that finding collisions in a short hash function is easy. This complicates the implementation of secure signing protocols in scenarios in which a group of mutually distrusting signers work together to produce a single joint signature (see Applications below). In these scenarios, which are not captured by the SUF-CMA model due its assumption of a single honest signer, a promising attack strategy for malicious co-signers is to find a collision in the hash function in order to obtain a valid signature on a message that an honest co-signer did not intend to sign.
	# Signatures are pairs ''(R, s)'' that satisfy ''s⋅G = R + hash(R \|\| m)⋅P''. This supports batch verification, as there are no elliptic curve operations inside the hashes. Batch verification enables significant speedups.		# Signatures are pairs ''(R, s)'' that satisfy ''s⋅G = R + hash(R \|\| m)⋅P''. This supports batch verification, as there are no elliptic curve operations inside the hashes. Batch verification enables significant speedups.<ref>The speedup that results from batch verification can be demonstrated with the cryptography library [https://github.com/jonasnick/secp256k1/blob/schnorrsig-batch-verify/doc/speedup-batch.md libsecp256k1].</ref>

	[[~~File~~:~~bip~~-~~0340~~/speedup-batch.~~png\|center\|frame\|This graph shows the ratio between the time it takes to verify ''n'' signatures individually and to verify a batch of ''n'' signatures~~. ~~This ratio goes up logarithmically with the number of signatures, or in other words: the total time to verify ''n'' signatures grows with ''O(n~~ / ~~log n)''.]]~~

	Since we would like to avoid the fragility that comes with short hashes, the ''e'' variant does not provide significant advantages. We choose the ''R''-option, which supports batch verification.		Since we would like to avoid the fragility that comes with short hashes, the ''e'' variant does not provide significant advantages. We choose the ''R''-option, which supports batch verification.

934: Update BIP text with latest version from https://github.com/bitcoin/bips/blob/19c429ee2831d898/bip-0340.mediawiki

2021-02-12T21:30:08Z

Update BIP text with latest version from https://github.com/bitcoin/bips/blob/19c429ee2831d898/bip-0340.mediawiki

← Older revision		Revision as of 21:30, 12 February 2021
Line 231:		Line 231:
	=== Adaptor Signatures ===		=== Adaptor Signatures ===

	[https://download.wpsoftware.net/bitcoin/wizardry/mw-slides/2018-05-18-l2/slides.pdf Adaptor signatures] can be produced by a signer by offsetting his public nonce with a known point ''T = t⋅G'', but not offsetting ~~his secret nonce~~.		[https://download.wpsoftware.net/bitcoin/wizardry/mw-slides/2018-05-18-l2/slides.pdf Adaptor signatures] can be produced by a signer by offsetting his public nonce ''R'' with a known point ''T = t⋅G'', but not offsetting the signature's ''s'' value.
	A correct signature (or partial signature, as individual signers' contributions to a multisignature are called) on the same message with same nonce will then be equal to the adaptor signature offset by ''t'', meaning that learning ''t'' is equivalent to learning a correct signature.		A correct signature (or partial signature, as individual signers' contributions to a multisignature are called) on the same message with same nonce will then be equal to the adaptor signature offset by ''t'', meaning that learning ''t'' is equivalent to learning a correct signature.
	This can be used to enable atomic swaps or even [https://eprint.iacr.org/2018/472 general payment channels] in which the atomicity of disjoint transactions is ensured using the signatures themselves, rather than Bitcoin script support. The resulting transactions will appear to verifiers to be no different from ordinary single-signer transactions, except perhaps for the inclusion of locktime refund logic.		This can be used to enable atomic swaps or even [https://eprint.iacr.org/2018/472 general payment channels] in which the atomicity of disjoint transactions is ensured using the signatures themselves, rather than Bitcoin script support. The resulting transactions will appear to verifiers to be no different from ordinary single-signer transactions, except perhaps for the inclusion of locktime refund logic.

934: Update BIP text with latest version from https://github.com/bitcoin/bips/blob/cf0b529e78860fa2/bip-0340.mediawiki

2021-01-01T10:07:22Z

Update BIP text with latest version from https://github.com/bitcoin/bips/blob/cf0b529e78860fa2/bip-0340.mediawiki

Show changes

934: Update BIP text with latest version from https://github.com/bitcoin/bips/blob/c134a853a9fc0657/bip-0340.mediawiki

2020-08-02T07:46:45Z

Update BIP text with latest version from https://github.com/bitcoin/bips/blob/c134a853a9fc0657/bip-0340.mediawiki

Show changes

← Older revision		Revision as of 15:50, 15 December 2021
Line 60:		Line 60:
	'''Schnorr signature variant''' Elliptic Curve Schnorr signatures for message ''m'' and public key ''P'' generally involve a point ''R'', integers ''e'' and ''s'' picked by the signer, and the base point ''G'' which satisfy ''e = hash(R \|\| m)'' and ''s⋅G = R + e⋅P''. Two formulations exist, depending on whether the signer reveals ''e'' or ''R'':		'''Schnorr signature variant''' Elliptic Curve Schnorr signatures for message ''m'' and public key ''P'' generally involve a point ''R'', integers ''e'' and ''s'' picked by the signer, and the base point ''G'' which satisfy ''e = hash(R \|\| m)'' and ''s⋅G = R + e⋅P''. Two formulations exist, depending on whether the signer reveals ''e'' or ''R'':
	# Signatures are pairs ''(e, s)'' that satisfy ''e = hash(s⋅G - e⋅P \|\| m)''. This variant avoids minor complexity introduced by the encoding of the point ''R'' in the signature (see paragraphs "Encoding R and public key point P" and "Implicit Y coordinates" further below in this subsection). Moreover, revealing ''e'' instead of ''R'' allows for potentially shorter signatures: Whereas an encoding of ''R'' inherently needs about 32 bytes, the hash ''e'' can be tuned to be shorter than 32 bytes, and [http://www.neven.org/papers/schnorr.pdf a short hash of only 16 bytes suffices to provide SUF-CMA security at the target security level of 128 bits]. However, a major drawback of this optimization is that finding collisions in a short hash function is easy. This complicates the implementation of secure signing protocols in scenarios in which a group of mutually distrusting signers work together to produce a single joint signature (see Applications below). In these scenarios, which are not captured by the SUF-CMA model due its assumption of a single honest signer, a promising attack strategy for malicious co-signers is to find a collision in the hash function in order to obtain a valid signature on a message that an honest co-signer did not intend to sign.		# Signatures are pairs ''(e, s)'' that satisfy ''e = hash(s⋅G - e⋅P \|\| m)''. This variant avoids minor complexity introduced by the encoding of the point ''R'' in the signature (see paragraphs "Encoding R and public key point P" and "Implicit Y coordinates" further below in this subsection). Moreover, revealing ''e'' instead of ''R'' allows for potentially shorter signatures: Whereas an encoding of ''R'' inherently needs about 32 bytes, the hash ''e'' can be tuned to be shorter than 32 bytes, and [http://www.neven.org/papers/schnorr.pdf a short hash of only 16 bytes suffices to provide SUF-CMA security at the target security level of 128 bits]. However, a major drawback of this optimization is that finding collisions in a short hash function is easy. This complicates the implementation of secure signing protocols in scenarios in which a group of mutually distrusting signers work together to produce a single joint signature (see Applications below). In these scenarios, which are not captured by the SUF-CMA model due its assumption of a single honest signer, a promising attack strategy for malicious co-signers is to find a collision in the hash function in order to obtain a valid signature on a message that an honest co-signer did not intend to sign.
	# Signatures are pairs ''(R, s)'' that satisfy ''s⋅G = R + hash(R \|\| m)⋅P''. This supports batch verification, as there are no elliptic curve operations inside the hashes. Batch verification enables significant speedups.		# Signatures are pairs ''(R, s)'' that satisfy ''s⋅G = R + hash(R \|\| m)⋅P''. This supports batch verification, as there are no elliptic curve operations inside the hashes. Batch verification enables significant speedups.<ref>The speedup that results from batch verification can be demonstrated with the cryptography library [https://github.com/jonasnick/secp256k1/blob/schnorrsig-batch-verify/doc/speedup-batch.md libsecp256k1].</ref>

	[[~~File~~:~~bip~~-~~0340~~/speedup-batch.~~png\|center\|frame\|This graph shows the ratio between the time it takes to verify ''n'' signatures individually and to verify a batch of ''n'' signatures~~. ~~This ratio goes up logarithmically with the number of signatures, or in other words: the total time to verify ''n'' signatures grows with ''O(n~~ / ~~log n)''.]]~~

	Since we would like to avoid the fragility that comes with short hashes, the ''e'' variant does not provide significant advantages. We choose the ''R''-option, which supports batch verification.		Since we would like to avoid the fragility that comes with short hashes, the ''e'' variant does not provide significant advantages. We choose the ''R''-option, which supports batch verification.