Nonce Grinding

What Is Nonce Grinding?

Nonce grinding is the process of repeatedly trying different nonce values until finding one that produces an output meeting a desired criterion. The term appears in two distinct Bitcoin contexts: mining and transaction optimization. In mining, grinding the block header nonce to find a valid hash is the fundamental act of proof of work. In transaction construction, nonce grinding refers to iterating ECDSA signature nonces to produce smaller signatures that consume less block space.

While both forms share the same mechanism (try values, check output, repeat), they serve different goals. Mining nonce grinding secures the network. Signature nonce grinding saves fees for individual transactions.

How It Works

Mining: Block Header Nonce

Every block header contains a 32-bit nonce field (4 bytes) that miners increment to search for a hash below the current difficulty target. The header is 80 bytes total: version, previous block hash, merkle root, timestamp, difficulty bits, and nonce. Miners double-SHA-256 hash this header, adjusting the nonce each time.

The 32-bit nonce provides approximately 4.3 billion possible values. Modern ASIC miners exhaust this range in a fraction of a second. When all nonce values are tried without finding a valid hash, miners modify the extraNonce field inside the coinbase transaction's scriptSig. Changing any byte in the coinbase transaction changes the merkle root, which produces an entirely new header to hash. This creates a two-level loop:

1. Inner loop: increment the 32-bit header nonce (fast, no recalculation needed)
2. Outer loop: increment the extraNonce, recompute the merkle root, then restart the inner loop

Miners can also vary the timestamp within protocol-allowed bounds for additional search space. The combined effect is an effectively unlimited number of candidate hashes, constrained only by hardware speed and electricity cost.

Signature Optimization: Low-R Grinding

ECDSA signatures in Bitcoin use DER (Distinguished Encoding Rules) format, where the R and S values are encoded as signed integers. When the high bit of R's first byte is set (values ≥ 0x80), DER encoding requires a leading 0x00 byte to indicate the value is positive. This means the R component can be either 32 bytes (low-R) or 33 bytes (high-R), directly affecting transaction size.

Since R values are essentially uniformly distributed 256-bit integers, approximately 50% of signatures naturally produce a high-R value. Low-R grinding iterates through different signature nonces until finding one where R fits in 32 bytes:

// Simplified low-R grinding logic (as implemented in Bitcoin Core)
// Uses RFC 6979 additional data parameter for safe iteration

fn sign_low_r(key, message_hash):
    counter = 0
    loop:
        extra_data = counter.to_bytes(4) + [0x00] * 28
        k = rfc6979_nonce(key, message_hash, extra_data)
        (R, S) = ecdsa_sign(key, message_hash, k)
        if R < 2^255:       // high bit not set, R fits in 32 bytes
            return (R, S)
        counter += 1

With a 50% success probability per attempt, the algorithm needs roughly 2 tries on average. Combined with low-S normalization (requiring S ≤ curve order / 2, standard since Bitcoin Core v0.9.0), every signature is guaranteed to be exactly 71 bytes (70 DER + 1 sighash byte) instead of potentially 72 or 73 bytes.

Deterministic Nonces and Safety

Low-R grinding is safe because it builds on RFC 6979 deterministic nonce generation. Rather than using a random number generator, RFC 6979 derives the signature nonce deterministically from the private key and message hash using HMAC-DRBG. Section 3.6 of the RFC explicitly allows an additional data input to the derivation function.

For grinding, a counter value is passed as this additional data. Each counter value produces a cryptographically independent nonce. The determinism property is preserved: the same key, message, and counter always produce the same nonce. The counter is non-secret and only controls which valid nonce is selected.

This approach sacrifices 1 bit of nonce entropy (constraining R to the lower half of the range), which is negligible against the 256-bit security of the secp256k1 curve.

Schnorr Signatures: No Grinding Needed

Schnorr signatures, activated with Taproot in November 2021 via BIP 340, eliminate the need for R-value grinding entirely. The design makes several choices that produce fixed-length signatures:

• X-only encoding: both public keys and R values use raw 32-byte x-coordinates instead of DER-encoded signed integers. Ambiguity about the y-coordinate is resolved by convention (always choose the even y).
• Fixed 64-byte format: signatures are exactly R (32 bytes) concatenated with S (32 bytes). No DER markers, no length bytes, no leading 0x00 padding.
• Implicit sighash: the default SIGHASH_ALL flag is not appended, keeping standard signatures at exactly 64 bytes (non-default sighash types add 1 byte for 65 total).

The result is a 7-byte savings per signature compared to ground ECDSA (64 vs. 71 bytes), with no computational overhead from grinding. For wallets and protocols building on P2TR outputs, this translates directly to lower fees.

Why It Matters

Signature size directly affects transaction fees. In a competitive fee market, every byte counts. For transactions with many inputs, low-R grinding can meaningfully reduce costs:

For exchanges and payment processors that batch transactions with dozens of inputs, low-R grinding saves meaningful fee costs over time. The optimization is automatic in Bitcoin Core v0.17.0+, requiring no user configuration.

Layer 2 protocols like Spark and the Lightning Network benefit from compact on-chain transactions when opening and closing channels, making signature optimization relevant for settlement efficiency.

Use Cases

• Fee reduction: wallets automatically grind for low-R signatures to minimize the virtual bytes consumed by each input, reducing fees without any user action.
• UTXO consolidation: transactions that spend many small UTXOs have many inputs, each with a signature. Low-R grinding compounds savings across all of them.
• Deterministic transaction size: guaranteed 71-byte signatures make fee estimation more accurate. Wallets can predict exact transaction size before signing, avoiding overpayment or underpayment of fees.
• Mining: the fundamental use of nonce grinding. Every valid block ever produced required a miner to find a nonce (and often an extraNonce) that produced a hash below the difficulty target.

Risks and Considerations

Nonce Reuse Is Catastrophic

If the same ECDSA nonce is used to sign two different messages with the same private key, the key can be algebraically recovered. Given two signatures (r, s₁) and (r, s₂) sharing the same r value (which indicates nonce reuse):

// Recovering the private key from reused nonce
k = (z1 - z2) / (s1 - s2) mod n    // recover nonce
d = (s1 * k - z1) / r mod n         // recover private key

This is not theoretical. In 2010, researchers demonstrated that Sony used a constant nonce for every ECDSA signature on the PlayStation 3, allowing anyone to recover Sony's code-signing key. In 2013, a bug in Android's SecureRandom caused Bitcoin wallet apps to reuse nonces, leading to the theft of funds as attackers scanned the blockchain for signatures sharing an r value. Deterministic nonces via RFC 6979 eliminate this class of vulnerability entirely.

Entropy Cost

Low-R grinding constrains R to the lower half of the 256-bit range, sacrificing 1 bit of effective entropy. Against secp256k1's 128-bit security level, this reduction is negligible: an attacker still faces 2¹²⁷ operations to recover a key, which remains computationally infeasible.

Computational Overhead

Grinding roughly doubles the average signing time (two attempts on average). For wallet software signing a handful of transactions, this is imperceptible. For high-throughput signing servers processing thousands of transactions per second, the overhead may be relevant.

Transition to Schnorr

As Taproot adoption grows, low-R grinding becomes less relevant. Schnorr signatures are inherently fixed-length, eliminating the need for any grinding optimization. The long-term trajectory is toward P2TR outputs, where signature optimization is built into the cryptographic primitive itself. For a deeper comparison of signature schemes, see Taproot and Schnorr Signatures Explained.

This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.