Taproot’s basic signature scheme, relevant to nonce and MuSig2 analysis

A scientific and technical article. WordPress version; formulas are presented in LaTeX-compatible text format.

Annotation

BIP-340 defines a strictly defined, byte-level scheme for 64-byte Schnorr signatures over the secp256k1 curve. It became the cryptographic foundation of Taproot: a fixed signature format, X-only public keys, tagged hashing, key-prefixed challenge, and nonce parity canonicalization form a unified mechanism designed for both consensus use and secure extension to aggregated signatures.

A central cryptanalytic fact is that the secrecy of the private key in a Schnorr signature depends linearly on the uniqueness and unpredictability of the nonce. Reusing the same effective nonce for different messages transforms the key recovery problem from a difficult discrete logarithm problem into a simple calculation modulo the group order. In MuSig2, the risks expand: single-party deterministic nonce generation cannot be transferred to a multi-party interactive procedure; unique session nonces, commitments, and protection against context spoofing are required.

Status and scope of the standard

BIP-340 was published on January 19, 2020, as a Standards Track BIP and has a status of  Final . The document defines Schnorr signatures for secp256k1; it does not, in itself, describe Taproot scripts or sighash transactions. The connection to Taproot is practical: BIP-341 uses BIP-340 verification for key-path spending, and BIP-327 builds MuSig2 on top of the same algebra.

Component	Role	Cryptanalytic meaning
BIP-340	Signature, encoding, tagged hashes, verification	Defines what exactly is considered a valid 64-byte signature.
secp256k1	Bitcoin Elliptical Group	Security relies on the practical difficulty of ECDLP.
Taproot / BIP-341	Using BIP-340 in UTXO spending	Makes the correctness of the implementation consensus critical.
MuSig2 / BIP-327	Interactive aggregation of keys and signatures	Adds malicious accomplice threats and nonce lifecycle.

Mathematical model

The work is carried out in the group of points of the elliptic curve secp256k1:

\[ E: y^2 \equiv x^3 + 7 \pmod p \]

Where

\[ p = \texttt{0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F} \]

The order of the base point  G is

\[ n = \texttt{0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141}. \]

The private key is a scalar  dsuch that  1 <= d < n; the public key is a point  P = dG. The ECDLP conjecture states that  P it is computationally infeasible to find ,  d given the correct parameters and the current state of computation.

X-only presentation

The public key and nonce are represented only by a 32-byte X-coordinate. The function either  lift_x(x) recovers a single point with a given X-coordinate and an even Y-coordinate or rejects the input. Therefore, an X-only key corresponds to a compressed SEC key with the prefix  0x02.

Practical implications.  The points  P and  -P have the same X-coordinate. BIP-340 disambiguates this with a parity rule; when signing, the secret scalar is normalized to a point with even  y(P). Consequently, a single X-only public key corresponds to two scalars  d and  n-d, but they represent the same normalized BIP-340 identity.

BIP-340 design

Tagged hashing

To separate domains, the standard defines:

\[ \operatorname{hash}_{name}(x)=\operatorname{SHA256}(\operatorname{SHA256}(tag)\parallel\operatorname{SHA256}(tag)\parallel x). \]

Three independent tags are essential for the implementation:  BIP0340/aux, ,  BIP0340/nonce and  BIP0340/challenge. A double tag hash forms exactly 64 bytes, or one SHA-256 block, allowing for optimization of the hash’s internal state.

A cryptanalytic example:  Reusing “naked” SHA-256 in different protocols creates the risk of interprotocol input or nonce duplication. Tagged hashing is an engineering boundary between contexts: a nonce generated for BIP-340 must not match a nonce from another protocol with the same key and message.

Key prefixation

Challenge contains the public key:

\[ e=\operatorname{int}(\operatorname{hash}_{\mathrm{BIP0340/challenge}}(r\parallel pk\parallel m))\bmod n. \]

Without inclusion,  pk the signature for  P could be algebraically transferred to the associated key  P+aG by modifying  s. This is critical for BIP32 unhardened derivation and Taproot tweaked keys, which use additive key transformations.

Signing algorithm

Below is the normative logic of Default Signing in a compact form. All operations on scalars are performed modulo  n.

Вход: sk (32 байта), m (произвольная длина), aux (32 байта)
d' = int(sk); отвергнуть, если d' == 0 или d' >= n
P = d' * G
d = d', если y(P) чётен; иначе d = n - d'
t = bytes(d) XOR hash_BIP0340/aux(aux)
k' = int(hash_BIP0340/nonce(t || bytes(P) || m)) mod n
отвергнуть, если k' == 0
R = k' * G
k = k', если y(R) чётен; иначе k = n - k'
e = int(hash_BIP0340/challenge(bytes(R) || bytes(P) || m)) mod n
s = (k + e*d) mod n
sig = bytes(R) || bytes(s)
вернуть sig после локальной Verify(P, m, sig)

The signature is of the form  sig = r || s, where each part occupies 32 bytes;  r = x(R). The basic equation is:

\[ sG = R + eP. \]

Synthetic nonce

The standard XORs the normalized secret  d with  aux , then concatenates the result with  P and the message. The additional 32 bytes of additional randomness are recommended: they aren’t the sole security feature, but they do improve resistance to fault injection and some side-channel attacks.

If entropy is unavailable, BIP-340 allows for a non-repeating counter or a zero-based array, but this is a compromise, not the preferred mode. In production systems, a CSPRNG, strong key isolation, and exclusive path testing are required.

Verification and canonicity

Вход: pk (32 байта), m, sig (64 байта)
P = lift_x(int(pk)); отвергнуть при ошибке
r = int(sig[0:32]); отвергнуть, если r >= p
s = int(sig[32:64]); отвергнуть, если s >= n
e = int(hash_BIP0340/challenge(bytes(r) || bytes(P) || m)) mod n
R = s*G - e*P
отвергнуть, если R бесконечность, y(R) нечётен или x(R) != r
принять

Parity checking  y(R) and comparison  x(R)=r transform an X-only record into a canonical representation. Unlike ECDSA, where a valid pair  (r,s) implies validity  (r,n-s), BIP-340 constructively eliminates similar trivial signature mutability.

Historical context.  In Bitcoin, the mutability of ECDSA signatures was the practical reason for the normalization of low-S and subsequent consensus/policy constraints. BIP-340 was designed with a fixed format and unambiguous verification to avoid repeating this class of problems.

Cryptanalytic Fact: Nonce Repeat

For two BIP-340 signatures of the same key with the same effective nonce  k and hence the same point  R, we have:

\[ s_1 = k + e_1d \pmod n, \qquad s_2 = k + e_2d \pmod n. \]

Subtraction destroys nonce:

\[ s_1-s_2=(e_1-e_2)d \pmod n. \]

If  e_1 != e_2 (mod n), the secret key is recovered directly:

\[ d=(s_1-s_2)(e_1-e_2)^{-1}\pmod n. \]

This isn’t an attack on secp256k1 or a “SHA-256 hack.” It’s a consequence of the linear signature equation when the premise is violated: the nonce must be secret, one-time, and correctly context-bound.

Historical analogues

Event / defect class	What happened	Lesson for BIP-340
PlayStation 3 ECDSA (2010)	A repeatable nonce was used for signatures; the linear structure of ECDSA allowed the private key to be extracted.	Determinism is only acceptable if the implementation is correct, context-separated, and error-free.
Android Bitcoin RNG incidents (2013)	Insufficient/faulty randomness in execution environments resulted in predictable or duplicate ECDSA nonces and loss of funds.	The system RNG cannot be considered absolutely reliable; a synthetic derivation nonce is useful.
Wallets with biased nonces	Partially predictable nonces in ECDSA/Schnorr yield a hidden-number-problem system that is often solvable by lattice methods given a sufficient number of signatures.	Even without exact replication, nonce bit leaks are dangerous when scaling samples.

For research monitoring, a repeat of  r a single X-only key among signatures is a strong indicator of a potential nonce failure, but it is not proof: a duplicate  r means the same canonical nonce and requires analysis of the message, key, and full signature. Any attempt to extract keys from other people’s signatures without permission is unethical and may be illegal; appropriate applications include auditing one’s own keys, testnets, CTFs, and publicly disclosed research.

Why is the nonce in BIP-340 special?

Due to parity normalization, BIP-340 uses  an effective  scalar  k: if the source point  k'G has an odd Y-coordinate, the algorithm replaces the scalar with  n-k'. Repetition analysis must operate on the canonicalized point  R, not just the internal value of the nonce generator.

Furthermore, challenge depends on  r || pk || m. Therefore, for one,  R different messages almost always produce different  e, and the recovery formula becomes applicable. However, if an identical message is signed with the same key and the same nonce, identical signatures are obtained, which in itself does not yield a second independent equation, but still indicates insecure state management.

MuSig2 and multiparty risk

Schnorr linearity allows for key aggregation and the creation of a single signature, externally indistinguishable from a single-user signature. In MuSig2, participants work with an aggregated key and a set of public nonces; the resulting signature preserves BIP-340 form  (r,s). This improves the privacy and efficiency of n-of-n schemes, but shifts nonce protection from a local concern to a protocol concern.

Why Default Signing Can’t Be Ported to MuSig2

BIP-340 explicitly warns that standard deterministic nonce generation, like any other purely deterministic method, is insecure for multisignature protocols. This is because a malicious participant can adaptively choose their messages, nonces, or session parameters in an attempt to replicate/correlate an honest partial nonce or extract information from repeated participation.

Property	Single BIP-340 signer	MuSig2 signer
Source nonce	Synthetic nonce tied to  d,P,m and aux.	Unique one-time secret nonces, tied to the entire session and protocol data.
Enemy	Usually an external observer.	Can be an active participant with influence on the session.
Repeat nonce	Reveals  d under two different challenges.	May disclose individual share of key; damage extends to joint ownership.
Engineering measure	aux randomness, self-verify, domain separation.	Nonce commitments, unique session ID, atomic “reserve and burn” nonce, rollback protection.

Nonce life cycle

A practically secure MuSig2 implementation must create a nonce before disclosure, commit it to the commit phase, disclose it only after receiving commitments from other parties, and never reuse the secret nonce—even after a cancellation, network error, or restart. A reliable storage model marks the nonce as spent before transmitting a partial signature; snapshot recovery or database rollback should not return it to the available pool.

A practical example:  A process failure between “partially signed” and “saved status” can make the nonce available again after recovery. This is cryptographically equivalent to an RNG error: the source is different, but the linear equation for the attacker remains the same.

Batch verification

BIP-340 supports batch verification. For signatures  i=1..u , inputs are verified, non-zero coefficients are selected  a_2,...,a_u, and then a single aggregate equality is checked:

\[ (s_1+a_2s_2+\cdots+a_us_u)G = R_1+a_2R_2+\cdots+a_uR_u + e_1P_1+(a_2e_2)P_2+\cdots+(a_ue_u)P_u. \]

The coefficients must be generated deterministically from a cryptographic hash of all inputs, for example, using SHA-256 and the CSPRNG ChaCha20. If all signatures are valid, the batch verification passes; if an invalid signature is present, a false acceptance is allowed only with a negligible probability.

Audit trail.  Batch verification is an optimization, not a diagnostic tool. If a batch fails, the defect must be localized using individual checks or binary partitioning of the set; it is impossible to infer which specific signature is violated based solely on a single aggregated equality.

Messages and domain separation

The current version of BIP-340 accepts messages of arbitrary size, although earlier versions limited the input to 32 bytes. For larger messages, pre-hashing is generally preferable for performance and reduces the memory requirements for signing, since the signing procedure hashes the message sequentially more than once.

Application protocols must separate domains. Two incompatible approaches are recommended: precomputing  hash_name(application_message) with a unique application tag or appending a unique 33-byte context prefix to the message. For example, a “web service login” signature should not be interpreted by a validator as authorizing a Bitcoin transaction.

Engineering audit code

Below is a secure snippet for  detecting  a repeating 32-byte field  r in the set of currently available BIP-340 signatures. It does not recover private keys and is suitable for CI, testbeds, or auditing your own logs.

from collections import defaultdict

def find_reused_r(signatures_hex):
    """signatures_hex: iterable 128-символьных hex BIP-340 signatures."""
    buckets = defaultdict(list)
    for idx, sig_hex in enumerate(signatures_hex):
        sig = bytes.fromhex(sig_hex)
        if len(sig) != 64:
            raise ValueError(f"signature #{idx}: expected 64 bytes")
        r = sig[:32]
        buckets[r.hex()].append(idx)
    return {r: indices for r, indices in buckets.items() if len(indices) > 1}

# В production дополняйте записью pk, m и идентификатора сессии.
# Совпадение r требует немедленного расследования и ротации ключа.

For a full audit, you need to index at least  (pk, r, message-id, session-id, timestamp); the secret nonces themselves should not be stored. If a suspicious match is detected, you should immediately stop using the key, preserve the evidence without publishing sensitive data, evaluate the existing signatures, and transfer the assets to a new key according to the owner’s procedures.

Boundary conditions

• Reject  pkfor which  lift_x there does not exist,  r >= p,  s >= n, an infinite point  R and a point  R with odd Y.
• Maintain 32-byte width and big-endian encoding of fields; do not allow shorthand, DER, or variant alternatives.
• Avoid using a single private key in independent nonce schemes without strict context separation; combining an inappropriate deterministic BIP-340 nonce with RFC 6979 ECDSA is especially dangerous.
• In the signing device, perform final local verification: this detects computational and induced errors before publishing a potentially informative invalid signature.
• Do not use the BIP-340 demo reference code in production: it is intended for testing and is not designed for constant-time execution.

Conclusions for cryptanalysis

BIP-340 does not weaken secp256k1; if the requirements are met, the scheme relies on ECDLP, the properties of SHA-256, and correct protocol execution. The most realistic compromise surface lies not in the discrete logarithm “solution,” but in the implementation: replay, predictability or partial nonce leakage, normalization errors, domain mixing, invalid MuSig2 state, and insecure fault handling.

For Taproot and MuSig2, the key principle is formulated as follows:  a nonce is a one-time secret resource bound to a complete cryptographic context, not simply a random number.  Adherence to this principle determines whether the private key extraction problem remains equivalent to ECDLP or degenerates into the calculation of a single modular inverse.

Sources

BIP-340: Schnorr Signatures for secp256k1:  https://nefty.ru/bip-340-schnorr-signatures-for-secp256k1/

1. P. Wuille, J. Nick, T. Ruffing.  BIP 340: Schnorr Signatures for secp256k1 . Bitcoin Improvement Proposals, status Final. https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki
2. BIP 341: Taproot: SegWit version 1 spending rules. https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki
3. BIP 327: MuSig2 for BIP340-compatible multi-signatures. https://github.com/bitcoin/bips/blob/master/bip-0327.mediawiki
4. D. Bernstein et al. Historical analyzes of ECDSA nonce failures; practical incidents illustrate implementation failures rather than weaknesses of the elliptic curve assumption.