Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Normalization yields a low S

Proved
BitcoinSig.normalizeS_low

by pitimespi · Oct 26, 2026 · Mathlib 0df444a (Lean v4.33.1)

bitcoinbitcoin-mainnetconsensusderecdsaformal-verificationschnorrsecp256k1sighash

For every s<ns < ns<n, isHighS (normalizeS s) = false: after normalization s≤n/2s \le n/2s≤n/2.

Preamble
import Definitions.Def_BitcoinSig
open BitcoinSig BitcoinSer
Formal statement
theorem BitcoinSig.normalizeS_low (s : Nat) (hs : s < BitcoinSig.n) :
    BitcoinSig.isHighS (BitcoinSig.normalizeS s) = false := by sorry
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: IsValidSignatureEncoding, IsLowDERSignature, IsCompressedOrUncompressedPubKey, IsCompressedPubKey, IsDefinedHashtypeSignature, CheckSignatureEncoding, CheckPubKeyEncoding, FindAndDelete, CTransactionSignatureSerializer, SignatureHash (BASE and WITNESS_V0), EvalChecksigPreTapscript, GenericTransactionSignatureChecker::CheckECDSASignature/CheckLockTime/CheckSequence, src/script/interpreter.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/interpreter.cpp; GetScriptOp, src/script/script.cpp; CPubKey::IsValid/Verify/CheckLowS and ecdsa_signature_parse_der_lax, src/pubkey.cpp and pubkey.h; secp256k1_eckey_pubkey_parse (src/secp256k1/src/eckey_impl.h), secp256k1_ecdsa_sig_verify (ecdsa_impl.h), secp256k1_schnorrsig_verify (modules/schnorrsig/main_impl.h); BIP66, BIP143, BIP340 at bips revision 100ba872c808946155b1eeb8c4568058f2eea0a7
Read-back

What the Lean code literally says, in plain math · claude-fable-5-1 (independent sub-agent, blind: Lean code + auditor instructions only)

Read-back: BitcoinSig.normalizeS_low

Binders and hypothesis. Universally quantified over a natural number sss, with one hypothesis hshshs: s<ns < ns<n, where nnn is the constant

n=0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141.n = \texttt{0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141}.n=0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141.

No other property of nnn (primality, being a group order) is used or asserted.

Conclusion.

isHighS (normalizeS s)=false.\text{isHighS}\ (\text{normalizeS}\ s) = \text{false}.isHighS (normalizeS s)=false.

Unfolding. isHighS ttt is the Boolean decision of ⌊n/2⌋<t\lfloor n/2 \rfloor < t⌊n/2⌋<t, where ⌊n/2⌋\lfloor n/2 \rfloor⌊n/2⌋ is natural-number (floor) division; since nnn is odd, ⌊n/2⌋=(n−1)/2\lfloor n/2 \rfloor = (n-1)/2⌊n/2⌋=(n−1)/2. normalizeS sss is: n−sn - sn−s (natural-number subtraction, truncated at 000) if isHighS sss, and sss otherwise. So the conclusion reads: let

s′={n−sif s>⌊n/2⌋,sotherwise;s' = \begin{cases} n - s & \text{if } s > \lfloor n/2 \rfloor,\\ s & \text{otherwise;}\end{cases}s′={n−ss​if s>⌊n/2⌋,otherwise;​

then s′≤⌊n/2⌋s' \leq \lfloor n/2 \rfloors′≤⌊n/2⌋. Under hshshs: in the first case ⌊n/2⌋+1≤s≤n−1\lfloor n/2 \rfloor + 1 \leq s \leq n - 1⌊n/2⌋+1≤s≤n−1, so 1≤n−s≤n−⌊n/2⌋−1=⌊n/2⌋1 \leq n - s \leq n - \lfloor n/2 \rfloor - 1 = \lfloor n/2 \rfloor1≤n−s≤n−⌊n/2⌋−1=⌊n/2⌋; in the second case s′=s≤⌊n/2⌋s' = s \leq \lfloor n/2\rfloors′=s≤⌊n/2⌋ by definition of the branch. The statement is purely arithmetic on natural numbers.

Edge cases. s=0s = 0s=0 is allowed (not high, normalizes to 000). s=⌊n/2⌋s = \lfloor n/2 \rfloors=⌊n/2⌋ is not high and is left unchanged. s=⌊n/2⌋+1s = \lfloor n/2 \rfloor + 1s=⌊n/2⌋+1 is high and maps to ⌊n/2⌋\lfloor n/2 \rfloor⌊n/2⌋. The hypothesis excludes s≥ns \geq ns≥n; for such sss the definition would give n−s=0n - s = 0n−s=0, also not high, but the theorem does not cover it.

What is not said. The statement does not say anything for s≥ns \geq ns≥n. It does not say that normalizeS sss is congruent to ±s\pm s±s modulo nnn, nor that it is non-zero, nor that it is below nnn. It does not say that normalization preserves or changes the outcome of any signature verification (ecdsaVerifyRaw, pubkeyVerify). It does not say that normalizeS is idempotent, nor that it is the identity on low values (though both follow from the definition, they are not asserted). It does not mention checkLowS or byte-string signatures at all: it is about a bare natural number.

Human review
  • Endorsed by Shuze Chen · Oct 26, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Oct 26, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me