diff options
| -rw-r--r-- | README.mediawiki | 2 | ||||
| -rw-r--r-- | bip-0340.mediawiki | 55 | ||||
| -rw-r--r-- | bip-0340/reference.py | 4 | ||||
| -rw-r--r-- | bip-0340/test-vectors.csv | 4 | ||||
| -rw-r--r-- | bip-0340/test-vectors.py | 20 | ||||
| -rw-r--r-- | bip-0350.mediawiki | 2 |
6 files changed, 75 insertions, 12 deletions
diff --git a/README.mediawiki b/README.mediawiki index 0d834b1..015038e 100644 --- a/README.mediawiki +++ b/README.mediawiki @@ -1077,7 +1077,7 @@ Those proposing changes should consider that ultimately consent may rest with th | Bech32m format for v1+ witness addresses | Pieter Wuille | Standard -| Draft +| Final |- | [[bip-0351.mediawiki|351]] | Applications diff --git a/bip-0340.mediawiki b/bip-0340.mediawiki index c99b77a..c941916 100644 --- a/bip-0340.mediawiki +++ b/bip-0340.mediawiki @@ -86,7 +86,7 @@ Despite halving the size of the set of valid public keys, implicit Y coordinates 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''. @@ -116,7 +116,7 @@ The following conventions are used, with constants as defined for [https://www.s *** Let ''y = c<sup>(p+1)/4</sup> mod p''. *** Fail if ''c ≠ 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 ==== @@ -138,7 +138,7 @@ As an alternative to generating keys randomly, it is also possible and safe to r 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 The algorithm ''Sign(sk, m)'' is defined as: @@ -174,7 +174,7 @@ It should be noted that various alternative signing algorithms can be used to pr 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 The algorithm ''Verify(pk, m, sig)'' is defined as: @@ -197,7 +197,7 @@ Note that the correctness of verification relies on the fact that ''lift_x'' alw Input: * 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 The algorithm ''BatchVerify(pk<sub>1..u</sub>, m<sub>1..u</sub>, sig<sub>1..u</sub>)'' is defined as: @@ -213,6 +213,50 @@ The algorithm ''BatchVerify(pk<sub>1..u</sub>, m<sub>1..u</sub>, sig<sub>1..u</s 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. +=== Usage Considerations === + +==== Messages of Arbitrary Size ==== + +The signature scheme specified in this BIP accepts byte strings of arbitrary size as input messages.<ref>In theory, the message size is restricted due to the fact that SHA256 accepts byte strings only up to size of 2^61-1 bytes.</ref> +It is understood that implementations may reject messages which are too large in their environment or application context, +e.g., messages which exceed predefined buffers or would otherwise cause resource exhaustion. + +Earlier revisions of this BIP required messages to be exactly 32 bytes. +This restriction puts a burden on callers +who typically need to perform pre-hashing of the actual input message by feeding it through SHA256 (or another collision-resistant cryptographic hash function) +to create a 32-byte digest which can be passed to signing or verification +(as for example done in [[bip-0341.mediawiki|BIP341]].) + +Since pre-hashing may not always be desirable, +e.g., when actual messages are shorter than 32 bytes,<ref>Another reason to omit pre-hashing is to protect against certain types of cryptanalytic advances against the hash function used for pre-hashing: If pre-hashing is used, an attacker that can find collisions in the pre-hashing function can necessarily forge signatures under chosen-message attacks. If pre-hashing is not used, an attacker that can find collisions in SHA256 (as used inside the signature scheme) may not be able to forge signatures. However, this seeming advantage is mostly irrelevant in the context of Bitcoin, which already relies on collision resistance of SHA256 in other places, e.g., for transaction hashes.</ref> +the restriction to 32-byte messages has been lifted. +We note that pre-hashing is recommended for performance reasons in applications that deal with large messages. +If large messages are not pre-hashed, +the algorithms of the signature scheme will perform more hashing internally. +In particular, the signing algorithm needs two sequential hashing passes over the message, +which means that the full message must necessarily be kept in memory during signing, +and large messages entail a runtime penalty.<ref>Typically, messages of 56 bytes or longer enjoy a performance benefit from pre-hashing, assuming the speed of SHA256 inside the signing algorithm matches that of the pre-hashing done by the calling application.</ref> + +==== Domain Separation ==== + +It is good cryptographic practice to use a key pair only for a single purpose. +Nevertheless, there may be situations in which it may be desirable to use the same key pair in multiple contexts, +i.e., to sign different types of messages within the same application +or even messages in entirely different applications +(e.g., a secret key may be used to sign Bitcoin transactions as well plain text messages). + +As a consequence, applications should ensure that a signed application message intended for one context is never deemed valid in a different context +(e.g., a signed plain text message should never be misinterpreted as a signed Bitcoin transaction, because this could cause unintended loss of funds). +This is called "domain separation" and it is typically realized by partitioning the message space. +Even if key pairs are intended to be used only within a single context, +domain separation is a good idea because it makes it easy to add more contexts later. + +As a best practice, we recommend applications to use exactly one of the following methods to pre-process application messages before passing it to the signature scheme: +* Either, pre-hash the application message using ''hash<sub>name</sub>'', where ''name'' identifies the context uniquely (e.g., "foo-app/signed-bar"), +* or prefix the actual message with a 33-byte string that identifies the context uniquely (e.g., the UTF-8 encoding of "foo-app/signed-bar", padded with null bytes to 33 bytes). + +As the two pre-processing methods yield different message sizes (32 bytes vs. at least 33 bytes), there is no risk of collision between them. + == Applications == There are several interesting applications beyond simple signatures. @@ -248,6 +292,7 @@ The reference implementation is for demonstration purposes only and not to be us 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 +* 2023-04: Allow messages of arbitrary size == Footnotes == diff --git a/bip-0340/reference.py b/bip-0340/reference.py index 162bb88..b327e0a 100644 --- a/bip-0340/reference.py +++ b/bip-0340/reference.py @@ -96,8 +96,6 @@ def pubkey_gen(seckey: bytes) -> bytes: return bytes_from_point(P) def schnorr_sign(msg: bytes, seckey: bytes, aux_rand: bytes) -> bytes: - if len(msg) != 32: - raise ValueError('The message must be a 32-byte array.') d0 = int_from_bytes(seckey) if not (1 <= d0 <= n - 1): raise ValueError('The secret key must be an integer in the range 1..n-1.') @@ -121,8 +119,6 @@ def schnorr_sign(msg: bytes, seckey: bytes, aux_rand: bytes) -> bytes: return sig def schnorr_verify(msg: bytes, pubkey: bytes, sig: bytes) -> bool: - if len(msg) != 32: - raise ValueError('The message must be a 32-byte array.') if len(pubkey) != 32: raise ValueError('The public key must be a 32-byte array.') if len(sig) != 64: diff --git a/bip-0340/test-vectors.csv b/bip-0340/test-vectors.csv index a1a63e1..6723391 100644 --- a/bip-0340/test-vectors.csv +++ b/bip-0340/test-vectors.csv @@ -14,3 +14,7 @@ index,secret key,public key,aux_rand,message,signature,verification result,comme 12,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F69E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B,FALSE,sig[0:32] is equal to field size
13,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E177769FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141,FALSE,sig[32:64] is equal to curve order
14,,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC30,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E17776969E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B,FALSE,public key is not a valid X coordinate because it exceeds the field size
+15,0340034003400340034003400340034003400340034003400340034003400340,778CAA53B4393AC467774D09497A87224BF9FAB6F6E68B23086497324D6FD117,0000000000000000000000000000000000000000000000000000000000000000,,71535DB165ECD9FBBC046E5FFAEA61186BB6AD436732FCCC25291A55895464CF6069CE26BF03466228F19A3A62DB8A649F2D560FAC652827D1AF0574E427AB63,TRUE,message of size 0 (added 2022-12)
+16,0340034003400340034003400340034003400340034003400340034003400340,778CAA53B4393AC467774D09497A87224BF9FAB6F6E68B23086497324D6FD117,0000000000000000000000000000000000000000000000000000000000000000,11,08A20A0AFEF64124649232E0693C583AB1B9934AE63B4C3511F3AE1134C6A303EA3173BFEA6683BD101FA5AA5DBC1996FE7CACFC5A577D33EC14564CEC2BACBF,TRUE,message of size 1 (added 2022-12)
+17,0340034003400340034003400340034003400340034003400340034003400340,778CAA53B4393AC467774D09497A87224BF9FAB6F6E68B23086497324D6FD117,0000000000000000000000000000000000000000000000000000000000000000,0102030405060708090A0B0C0D0E0F1011,5130F39A4059B43BC7CAC09A19ECE52B5D8699D1A71E3C52DA9AFDB6B50AC370C4A482B77BF960F8681540E25B6771ECE1E5A37FD80E5A51897C5566A97EA5A5,TRUE,message of size 17 (added 2022-12)
+18,0340034003400340034003400340034003400340034003400340034003400340,778CAA53B4393AC467774D09497A87224BF9FAB6F6E68B23086497324D6FD117,0000000000000000000000000000000000000000000000000000000000000000,99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999,403B12B0D8555A344175EA7EC746566303321E5DBFA8BE6F091635163ECA79A8585ED3E3170807E7C03B720FC54C7B23897FCBA0E9D0B4A06894CFD249F22367,TRUE,message of size 100 (added 2022-12)
diff --git a/bip-0340/test-vectors.py b/bip-0340/test-vectors.py index d1bf6b2..317f2ec 100644 --- a/bip-0340/test-vectors.py +++ b/bip-0340/test-vectors.py @@ -249,6 +249,20 @@ def vector14(): return (None, pubkey, None, msg, sig, "FALSE", "public key is not a valid X coordinate because it exceeds the field size") +def varlen_vector(msg_int): + seckey = bytes_from_int(int(16 * "0340", 16)) + pubkey = pubkey_gen(seckey) + aux_rand = bytes_from_int(0) + msg = msg_int.to_bytes((msg_int.bit_length() + 7) // 8, "big") + sig = schnorr_sign(msg, seckey, aux_rand) + comment = "message of size %d (added 2022-12)" + return (seckey, pubkey, aux_rand, msg, sig, "TRUE", comment % len(msg)) + +vector15 = lambda : varlen_vector(0) +vector16 = lambda : varlen_vector(0x11) +vector17 = lambda : varlen_vector(0x0102030405060708090A0B0C0D0E0F1011) +vector18 = lambda : varlen_vector(int(100 * "99", 16)) + vectors = [ vector0(), vector1(), @@ -264,7 +278,11 @@ vectors = [ vector11(), vector12(), vector13(), - vector14() + vector14(), + vector15(), + vector16(), + vector17(), + vector18(), ] # Converts the byte strings of a test vector into hex strings diff --git a/bip-0350.mediawiki b/bip-0350.mediawiki index 9873d80..439b2a2 100644 --- a/bip-0350.mediawiki +++ b/bip-0350.mediawiki @@ -5,7 +5,7 @@ Author: Pieter Wuille <pieter@wuille.net> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0350 - Status: Draft + Status: Final Type: Standards Track Created: 2020-12-16 License: BSD-2-Clause |