Implement LOW_S and NULLDUMMY softfork (BIP146) #8533

pull jl2012 wants to merge 3 commits into bitcoin:master from jl2012:bip146 changing 5 files +379 −3

jl2012 commented at 5:57 PM on August 17, 2016: contributor

This will enforce SCRIPT_VERIFY_LOW_S and SCRIPT_VERIFY_NULLDUMMY on all transactions when segwit is activated with BIP9

This PR replaces #8514
jl2012 force-pushed on Aug 17, 2016
jl2012 force-pushed on Aug 17, 2016
MarcoFalke added the label Consensus on Aug 17, 2016
dcousens commented at 10:51 PM on August 17, 2016: contributor

utACK 24c398f
jl2012 force-pushed on Aug 18, 2016
jl2012 force-pushed on Aug 19, 2016
jl2012 force-pushed on Aug 20, 2016
jl2012 force-pushed on Aug 20, 2016
jl2012 force-pushed on Aug 20, 2016
instagibbs commented at 4:53 PM on August 23, 2016: member

needs 0.13.1 milestone tag?

in qa/rpc-tests/bip146-p2p.py:None in 068e3e3aef outdated

  64 | +
  65 | +def highSifySig(sig):
  66 | +    assert(isCanonicalSig(sig))
  67 | +    rsize = sig[3]
  68 | +    s = int.from_bytes(sig[6+rsize:-1], byteorder='big')
  69 | +    assert(s <= 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0)

instagibbs commented at 4:58 PM on August 23, 2016:

Could we get constants for these long hex numbers?

in qa/rpc-tests/test_framework/key.py:None in 068e3e3aef outdated

 166 | +        assert mb_sig.raw[2] == 2
 167 | +        r_size = mb_sig.raw[3]
 168 | +        assert mb_sig.raw[4 + r_size] == 2
 169 | +        s_size = mb_sig.raw[5 + r_size]
 170 | +        s_value = int.from_bytes(mb_sig.raw[6+r_size:6+r_size+s_size], byteorder='big')
 171 | +        if s_value <= 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0:

instagibbs commented at 4:59 PM on August 23, 2016:

Constants for these too?

jl2012 commented at 9:26 AM on August 24, 2016:

@instagibbs edited

MarcoFalke added this to the milestone 0.13.1 on Aug 23, 2016
Make test framework produce lowS signatures 51c24f86bc
Implement LOW_S and NULLDUMMY softfork (BIP146) 26df793c3d
in src/main.cpp:None in 068e3e3aef outdated
```
2383 | @@ -2384,9 +2384,11 @@ bool ConnectBlock(const CBlock& block, CValidationState& state, CBlockIndex* pin
2384 |          nLockTimeFlags |= LOCKTIME_VERIFY_SEQUENCE;
2385 |      }
2386 |  
2387 | -    // Start enforcing WITNESS rules using versionbits logic.
2388 | +    // Start enforcing WITNESS, NULLDUMMY, and LOW_S rules using versionbits logic.
2389 |      if (IsWitnessEnabled(pindex->pprev, chainparams.GetConsensus())) {
2390 |          flags |= SCRIPT_VERIFY_WITNESS;
2391 | +        flags |= SCRIPT_VERIFY_LOW_S;
```
instagibbs commented at 5:37 PM on August 23, 2016:

A little worried this could allow some prankster to reorg testnet a huge amount. Side-effect of bundling the mainnet activation here.

sipa commented at 5:39 PM on August 23, 2016:

An alternative is defining a separate BIP9 rollout for this, using the same bit on mainnet as segwit, but a different bit on testnet.

instagibbs commented at 5:41 PM on August 23, 2016:

was exactly my thought. Kind of makes me cry for the 2 line SF, but oh well

jl2012 commented at 5:48 PM on August 23, 2016:

There is currently no violating txs on testnet and we could start enforcing this on testnet now.

btcdrak commented at 9:06 AM on August 25, 2016:

@instagibbs testnet is a testnet and it's being reorged massively all the time. In the last 3 months it's had about 3 major reorgs (>10,000 blocks). We should not be adding complexity for testnet.

instagibbs commented at 11:06 AM on August 25, 2016:

@btcdrak it should not be policy to not care about massive reorgs and encourage them. That said, if testnet miners want to make sure none are included by softforking now, I wouldn't complain.

btcdrak commented at 5:48 PM on August 25, 2016:

Ok the issue is moot now as rules are now enforced on testnet3.
jl2012 force-pushed on Aug 24, 2016
jameshilliard commented at 6:02 PM on August 25, 2016: contributor

tACK 26df793c3d94d3e0e9907f4455448e01f86e2dfa on my testnet pool
MarcoFalke added the label Needs backport on Aug 26, 2016
luke-jr commented at 9:21 PM on August 27, 2016: member

utACK
btcdrak commented at 8:21 AM on August 28, 2016: contributor

Tested ACK 26df793
instagibbs commented at 5:26 PM on August 29, 2016: member

utACK https://github.com/bitcoin/bitcoin/pull/8533/commits/26df793c3d94d3e0e9907f4455448e01f86e2dfa
jl2012 commented at 7:03 PM on August 29, 2016: contributor

Added script tests for some special S values
Add LOW_S script tests 70fbd8212b
jl2012 force-pushed on Aug 30, 2016
jl2012 commented at 4:15 PM on August 30, 2016: contributor

The newly added tests of 70fbd82 revealed some interesting properties of the current implementation of LOW_S. The LOW_S rule is enforced only if R and S are both below 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141. Otherwise, the CHECKSIG will return a False to the stack, instead of fail immediately.

You could find the examples here: https://github.com/jl2012/bips/blob/bip146outofrange/bip-0146.mediawiki#LOW_S
jl2012 commented at 4:49 PM on August 31, 2016: contributor

The alternative plan is to do NULLDUMMY only : #8636
dcousens commented at 3:11 AM on September 1, 2016: contributor

@jl2012 to clarify, the CHECKSIG operation can fail before a LOW_S signature is detected? Why is that an issue?

Is it because a LOW_S signature could get through conceivably if an alternative branch subsequently returns true?

Is that a bad thing? Or should we only allow canonical signatures to be allowed to be CHECKSIG'd? Meaning we'd need some kind of "pre-pass"...
jl2012 commented at 4:33 AM on September 1, 2016: contributor
@dcousens the problem is CHECKSIG won't fail immediately due to LOW_S if either R or S is out-of-range.

I think this is how it actually get processed:
1. secp256k1_scalar_check_overflow checks if R or S is overflow, if yes
2. ecdsa_signature_parse_der_lax transforms both R and S to 0
3. secp256k1_scalar_is_high checks if S is high. Since S has become 0 in step 2, it doesn't think it's high so the LOW_S rule is effectively bypassed
4. secp256k1_ecdsa_verify failed because R=S=0
5. CHECKSIG returns a 0 to the top stack; script evaluation continues
So we have a weird condition that "if R overflows, we bypass LOW_S check"

Before this was discovered, we thought the rule was simply 0x01 <= S <= 0x7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 5D576E73 57A4501D DFE92F46 681B20A0. (as described in BIP62)

Now I have to use a page of text and examples to precisely describe it: https://github.com/jl2012/bips/blob/bip146outofrange/bip-0146.mediawiki#LOW_S and without any real use case. It is difficult to justify the softfork in current form.

We could fix that by, for example, making a simple byte-to-byte comparison with 0x7FFFF...20A0 , or fix the test in libsecp256k1. Or we could simply require a null signature for failed CHECKSIG operation (see #8634).
jl2012 commented at 4:48 AM on September 1, 2016: contributor

Having said that, there won't be any irreversible harm if the softfork had been done without this being discovered. It was still a softfork and it would work as we thought for 99.99999% of transactions on the blockchain. However, if an alternative implementation did not replicate this precisely, they would fork away due to the 0.00001% of transactions.
dcousens commented at 5:31 AM on September 1, 2016: contributor

Thanks for the great explanation @jl2012, excellent point about implementation replication.
jl2012 commented at 11:41 AM on September 2, 2016: contributor

The plan is to do NULLDUMMY only (#8636), and leave LOW_S later, probably at the same time banning non-zero failing signature.

Please remove 0.13.1 tag
jl2012 closed this on Sep 2, 2016
fanquake removed this from the milestone 0.13.1 on Sep 2, 2016
MarcoFalke removed the label Needs backport on Sep 9, 2016
MarcoFalke locked this on Sep 8, 2021

Contributors

Labels

Linked (view graph)

#8514 Enforce LOW_S rules on all transactions with WITNESS BIP9 parameters #8636 Implement NULLDUMMY softfork (BIP147)