5

Bitcoinlib refers to the requirement that if s > ORDER / 2, then the complement of s should be used instead since it's one byte shorter

This sounds like it's referring to the inverse or negative s value, but I also know complement can be a computer science term.

The relevant code can be found here (perhaps someone adept with the Bitcoin Core code can chime in on what the code is doing), so, what is the complement of s referring to?

Improve this question

2 Answers 2

Reset to default
5

In ECDSA s can be on either side of the curve and the signature will still be valid. The term "low s" is referring to the value literally being being below the curve order (0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0). The requirement of low-s is arbitrary (high s would have worked just fine as well), and is one of the new BIP62 validity rules that are intended to combat transaction malleability.

Absent this rule, any person is able to take a Bitcoin transaction, flip s in any of its signatures, and push the transaction out again with a different TXID. Being able to do this only changes the hash of the transaction, and does not alter its validity in any way. Being able to mutate transactions breaks a number of potentially interesting transaction types in Bitcoin like payment channels, where chains of transactions will suddenly be invalidated by a parent being mutated and an alternate form included in a block.

By forcing valid transactions to always have low s this ability is removed, though a person with the private key for a transaction is still able to mutate their own transactions by resigning them with a new nonce.

Improve this answer
4
  • Fantastic! Can you write some pseudocode (or Python) which shows how to flip the s value? It's not just the negative value is it?
    – Wizard Of Ozzie
    Commented Jun 25, 2015 at 2:45
  • 2
    The pseudocode is very simple: s2 = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 - s1;
    – amaclin
    Commented Jun 25, 2015 at 4:46
  • @amaclin oh wow, so I was absolutely overthinking this. Of course, i see the logic to it now. Tangentially, why is this code so un-Pythonic? Is it basically a Python "port" of the C++ code?
    – Wizard Of Ozzie
    Commented Jun 25, 2015 at 5:14
  • 1
    python-bitcoinlib is unpythonic because it is emulating all of the structures that you find in Bitcoin Cores CPP codebase. You could make it more pythonic but it wouldn't be as useful that way.
    – Claris
    Commented Jun 25, 2015 at 20:12
2

What is the complement of s referring to?

I haven't heard that term used like that before, but reading the code, it appears to compare s to see if it's more than n/2 rounded down (where n is the order of the curve, FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141.)

If it is, it calculates n - s and uses that as s.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.