Remove bignum dependency for scripts

theuni commented at 0:36 am on March 27, 2014: member

As title suggests.

This is the first step towards breaking out scripting so that it can be used without core as a dependency. Passes all tests. I’m prepared for heavy scrutiny on this one since it’s a dangerous area. Suggestions are very welcome.

A new class (CScriptNum) has been created to be a subset of the former usage of Bignum. Operands are signed 32bit, but they may overflow after an operation, so an int64_t is used to represent the internal value.

For the sake of easier reviewing, I left out any functions and operators that weren’t already in-use, and made minimal changes to existing names and conventions.

theuni commented at 0:37 am on March 27, 2014: member

ping @sipa . I’m hoping this resembles what you had in mind.

jgarzik commented at 0:55 am on March 27, 2014: contributor

Hum. Wish you had pinged me. Had this half-done already. Oh well – fully done is better than that.

Untested, quick-review ACK. This is the direction I was headed – ScriptNum replaces BigNum. Looks good to me.

theuni commented at 2:24 am on March 27, 2014: member

@jgarzik Ah, I didn’t realize you were working on it. I’ve seen a few discussions lately about outside-access to script verification, and this seemed the logical place to start hacking toward that end.

Do you have anything in the works regarding such libification? If so, I’d definitely prefer not to duplicate the work. Otherwise, I’ll keep at it after a short detour for some build-system stuff.

sipa commented at 5:21 am on March 27, 2014: member

Oh, I (and others) have been talking about the idea of separating script evaluation (and later perhaps the whole of validation) into separate low-dependency libraries. I didn’t expect such immediate progress towards that… sorry if that caused some duplicate work.

Approach looks good to me, but this will require very careful inspection and testing.

laanwj commented at 9:45 am on March 27, 2014: member

Agree on the direction and code changes look good on first glace (though as @sipa says, as this affects consensus it will have to be thoroughly scrutinized).

sipa commented at 4:33 pm on March 29, 2014: member

I think we want unit tests for CScriptNum, to ensure their compatibility with CBigNum.

Shouldn’t be too hard I think; construct some random and non-random numbers (0, max, min, …), do some operations on combinations of them, and compare the result with doing the same operation on CBigNum (and serialize/deserialize to vectors).

theuni commented at 5:10 pm on March 29, 2014: member

@sipa Can’t believe I didn’t think of that, that’s very obviously the correct way forward with this.

Great idea, will do.

theuni commented at 2:28 am on March 31, 2014: member

I threw in a few quick tests as @sipa suggested over the weekend, and there are some significant problems. I’ll push up a fixed tomorrow.

theuni commented at 5:25 am on April 1, 2014: member

Updated, and pretty much rewritten. Lots of tests added, it now conforms to the previous usage of CBigNum as much as possible. See the note in 8ca9e9b about the usage differences.

gavinandresen commented at 2:51 pm on April 3, 2014: contributor

Code review ACK.

I also tested to make sure the unit tests can fail (ran tests against a script.h with intentionally introduced bugs).

theuni commented at 8:52 pm on April 3, 2014: member

@gavinandresen thanks for the review. Your description above finally helped me put a finger on the overflow subtleties that had been bothering me, so I made a few more changes. The nMaxNumValue/nMinNumValue were not enough to handle all overflow scenarios, so I split them into OperandValue/TotalValue. Also, the current (possibly overflown) value was not tested on subsequent math operations, so I fixed that and added the tests in script_invalid to check for them.

A quick sanity review of those changes would definitely be appreciated.

theuni commented at 11:06 pm on April 3, 2014: member

Mmm, there are still several details that aren’t quite right here. Several tests need to be added for hitting the corner cases. Will keep at it.

theuni commented at 3:50 am on April 4, 2014: member

Ok, I really think that’s everything now, sorry for all the wavering. Thanks to @gmaxwell for gently answering some dumb questions after the tunnel-vision set in. @gavinandresen I left some uglies in rather than force-pushing. No history before your comment has been rewritten.

theuni commented at 7:01 am on April 4, 2014: member

Testnet reindexed from scratch to height=208945 after the last set of changes, without issue.

theuni commented at 10:20 pm on April 4, 2014: member

@maaku I have no idea where your comment went.. Github seems to have swallowed it somehow.

0In src/script.h:
1What about zero-padded bignums? These can be more than 4 bytes in length but still pass CastToBigNum()

We no longer have a CBigNum cast, so there’s no way to get a BigNum into a script directly. But more importantly, see the previous behavior: https://github.com/bitcoin/bitcoin/pull/3965/files#diff-dedcc88d0e66b86a19981e7c175658c2L36

As I see it, CScriptNum does the same thing as before. Am I missing something?

maaku commented at 11:23 pm on April 4, 2014: contributor

Yeah, right after making that comment I figured I should double-check, and sure enough it matches the previous behavior. So I deleted the comment, but I guess you got the notification email. Sorry to waste your time with it.

On 04/04/2014 03:20 PM, Cory Fields wrote:

@maaku https://github.com/maaku I have no idea where your comment went.. Github seems to have swallowed it somehow.

|In src/script.h: What about zero-padded bignums? These can be more than 4 bytes in length but still pass CastToBigNum() |

We no longer have a CBigNum cast, so there’s no way to get a BigNum into a script directly. But more importantly, see the previous behavior: https://github.com/bitcoin/bitcoin/pull/3965/files#diff-dedcc88d0e66b86a19981e7c175658c2L36

As I see it, CScriptNum does the same thing as before. Am I missing something?

— Reply to this email directly or view it on GitHub #3965 (comment).

theuni commented at 11:29 pm on April 4, 2014: member

No worries, thanks for the review. Please point out anything you’re unsure of, it’s worth the few min it takes me to double-check. :)

maaku commented at 10:19 pm on April 5, 2014: contributor

ACK.

During the review the only part that had me worried was the setvch() and serialize() implementations, since that’s a lot of new consensus-critical code. It looked correct but rather than trust my judgement I performed an exhaustive test of all possible (non-overflow) values. It only took 661m 35.921s to run:

 0BOOST_AUTO_TEST_CASE(scriptnum_i64_2)
 1{
 2    for (int64_t i  = CScriptNum::nMinOperandValue;
 3                 i <= CScriptNum::nMaxOperandValue; ++i)
 4    {
 5        CheckCreateVch(i);
 6        CheckCreateInt(i);
 7    }
 8}
 9
10BOOST_AUTO_TEST_CASE(scriptnum_vch)
11{
12    for (int a = 0; a <= 255; ++a)
13    for (int b = 0; b <= 255; ++b)
14    for (int c = 0; c <= 255; ++c)
15    for (int d = 0; d <= 255; ++d)
16    {
17        std::vector<unsigned char> vch;
18        vch.push_back((unsigned char)a);
19        vch.push_back((unsigned char)b);
20        vch.push_back((unsigned char)c);
21        vch.push_back((unsigned char)d);
22        BOOST_CHECK(CBigNum(vch).getint() == CScriptNum(vch).getint());
23    }
24}

Passed with flying colors. Overflow values were not tested as that would have extended the run time into weeks, the overflow-related parts of the code are uncomplicated, and there is adequate coverage of those edge cases in the tests already.

This eliminates a huge dependency in the script code. Great work Cory.

in src/script.h: in 2ee6bf163b outdated

165+
166+  static const size_t nMaxNumSize = 4;
167+  static const int64_t nMaxOperandValue = 0x7FFFFFFF;
168+  static const int64_t nMinOperandValue = -nMaxOperandValue;
169+  static const int64_t nMaxTotalValue = 0x7FFFFFFFFFLL;
170+  static const int64_t nMinTotalValue = -nMaxTotalValue;

laanwj commented at 8:37 am on April 7, 2014:

Just to check: this minimum is correct? It would be easy to make mistakes here, as in principle -0x80000000 is the lowest representable value in a 32-bit int. The old CastToBigNum just checks the size of the vector so it doesn’t tell me much.

maaku commented at 3:09 pm on April 7, 2014:

Bignums have explicit sign bits, so -0x80000000 requires five bytes to represent: 0000008080.

theuni commented at 3:56 pm on April 7, 2014:

@laanwj Note that the sizes are verified in the tests:

0 ["-2147483647", "0x04 0xFFFFFFFF EQUAL"],
1 ["-2147483648", "0x05 0x0000008080 EQUAL"],

That’s confusing at first glance, but see what @maaku said above. -2147483647 is -0x7FFFFFFF, sent over the wire as 0xFFFFFFFF. So that’s the minimum value of a 4-byte operand.

I suppose it would be helpful to verify the operand bounds explicitly in the tests as well: valid: ["-2147483647", "1ADD 2147483646 EQUAL"] invalid: ["-2147483648", "1ADD 1"]

I’ll double-check that those aren’t already there and push that up.

theuni commented at 4:12 pm on April 7, 2014:

Just checked, and it’s already covered in a few places. From existing tests: valid:

0["2147483647 -2147483647 ADD", "0 EQUAL"]
1["0 -2147483647 MIN", "-2147483647 NUMEQUAL"]
2["0 -2147483647 MAX", "0 NUMEQUAL"]

invalid:

0["-2147483648 0 ADD", "NOP", "arithmetic operands must be in range [-2^31...2^31] "]
1["-2147483648", "1ADD 1", "Because we use a sign bit, -2147483648 is also 5 bytes"]

laanwj added this to the milestone 0.10.0 on Apr 16, 2014

gmaxwell commented at 7:59 am on April 17, 2014: contributor

ACK (my comments about the inclusive/exclusive ranges being unclear in the comments, aside).

I added 80 more script tests for areas of number handling that I thought were under-tested. All passed, I’ll pullreq after this is merged so I don’t conflict with it. Maaku’s tests were great though I had some concern that they didn’t test the overflows, so I added a test for the byte-pattern a,x,x,x,b where a={1..255}, b={0..255}, x={0,255} and confirmed that it threw in all the same cases.

One point where I would like a second opinion is that the change changes from throwing runtime_error to throwing the derived scriptnum_error. I don’t see any place where this would make a difference. However, most of our confidence in this code comes from unit tests which wouldn’t see long-range effects and if the exception change had an effect it would be long range. AFAICT pulltester doesn’t test blocks which get rejected due to arithmetic overflows. This should be fixed: perhaps by creating one block for each of our invalid script testcases, and one block with all the valid ones— maybe imported from the JSON. We do sync testnet which has the bulk of the unit tests in it, but perhaps we shouldn’t release this until there is some full system test (e.g. blocks over p2p) which checks the invalid cases.

theuni commented at 10:17 am on April 17, 2014: member

@gmaxwell Thanks for the thorough review. New test-cases are most welcome. If you’d like, I’d be more than happy to split this PR into two so that (your) test-cases can go in first, then the scriptnum changes. That way it’s clear that the same cases passed before and after. Reconciling some conflicts is hardly a concern compared to the possibility of introducing a consensus change.

As for the derived throw, I grepped around a bit at the time and found that it could’ve only been caught by a (…), but it’s very possible that I overlooked something. I considered throwing the old type for the sake of compatibility, but I couldn’t find any actual usage to speak of.

sipa commented at 10:41 am on April 17, 2014: member

The code and the tests look very good.

I have one suggested simplification. In the old code, the only place where bounds-checking was done (afaict) was in CastToBigNum, so when converting a byte vector to a number. I don’t think there is any need for going beyond that in CScriptNum (where this logic moved to its constructor).

This means the operators themselves don’t need bounds checking, and for example operator+= could just be: inline CScriptNum& operator+=(const CScriptNum& rhs) { m_value += rhs.m_value; }

sipa commented at 10:48 am on April 17, 2014: member

Hmm, I see the reasoning for wanting to be defensive about unexpectedly large values, as - even though conversion to CScriptNum is protected - you don’t want overflows inside the int64_t type.

Such cases would not be script evaluation errors, though, just implementation errors. An assert should suffice, I think?

in src/script.h: in 2ee6bf163b outdated

164+  }
165+
166+  static const size_t nMaxNumSize = 4;
167+  static const int64_t nMaxOperandValue = 0x7FFFFFFF;
168+  static const int64_t nMinOperandValue = -nMaxOperandValue;
169+  static const int64_t nMaxTotalValue = 0x7FFFFFFFFFLL;

sipa commented at 10:52 am on April 17, 2014:

Nit: I think the actual maximum possible total value is 0x7FFFFFFFFELL.

theuni commented at 11:28 pm on April 17, 2014:

Bound by which criteria? See the passing test:

0["549755813887", "SIZE 5 EQUAL"]

where 7FFFFFFFFF == 549755813887

gmaxwell commented at 11:33 pm on April 17, 2014:

Thats never a bignum in that example it’s just a byte vector (and can be much larger than 5 bytes).

theuni commented at 11:48 pm on April 17, 2014:

@gmaxwell Erm, I did a poor job with my point on that one.

I was stating that 7FFFFFFFFF fits neatly into 5 bytes, as shown by ‘549755813887 SIZE 5 EQUAL’, which is the criteria for nMaxTotalValue.

maaku commented at 0:16 am on April 18, 2014:

Try 9223372036854775807 SIZE 8 EQUAL – you’ll find it passes too. In this script the number is never treated as a bignum, so it never gets range checked.

The correct, most restrictive limit is 0xfffffffe == 0x7fffffff + 0x7fffffff, but as far as I can tell it doesn’t affect consensus code.

theuni commented at 0:23 am on April 18, 2014:

@maaku I considered 0xfffffffe, but decided against assuming that other operators wouldn’t be re-enabled/added in the future. The 5byte boundary is the only constraint for consideration here, no?

maaku commented at 0:35 am on April 18, 2014:

The disabled opcodes cannot be re-enabled in the future. I’m not sure why the 5 byte boundary matters here? If you re-enabled OP_MUL, for example, you could certainly do 0x7fffffff * 0x7fffffff == 0x3fffffff00000001 (eight bytes).

sipa commented at 11:34 am on April 18, 2014:

I should not have made this comment, it’s immaterial.

There is no range limit on the values of operands. There is only a size limit on which byte vectors can be converted to integers.

How about:

Only the CScriptNum constructor check the vector size (if arg.size() > 4 throw scripnum_error).
The + and - operators get an assertion that prevents int64 overflows.

I think that should be all?

theuni commented at 11:23 pm on April 17, 2014: member

@sipa: I’ve now written 4 responses to this and deleted them each in favor of doing more research… ultimately, I agree with you.

As-is, the only thing these operators protect from is something like:

0CScript() << CScriptNum(nMaxOperandValue)+1;

Which is incorrect ‘protection’, because that should be a valid operation.

Does anyone object to this change?

Anyone disagree with removing those bounds checks?

gmaxwell commented at 11:27 pm on April 17, 2014: contributor

I agree with removing them. The additional boundary testing was what concerned me enough to go write a bunch of additional script tests.

luke-jr commented at 7:13 am on April 18, 2014: member

Crazy idea: If we are potentially going to soft-fork script-upgrade in the near future, it might be worth considering just making the soft-fork remove any opcodes that have weird/complicated implementations if they’re not in use…

theuni commented at 9:48 pm on April 18, 2014: member

Cleaned up the operators as suggested by @sipa and @gmaxwell . Fixed the tests enough to build, but they need to be cleaned up to remove the old assumptions.

If you guys are reasonably happy with the way it looks, I’ll cleanup and squash it down for further review (it’s gotten pretty messy with all the fixups).

in src/script.h: in 1dae829ace outdated

119+    return serialize(m_value);
120+  }
121+
122+  static std::vector<unsigned char> serialize(const int64_t& value)
123+  {
124+    //  The input here is not range-checked. This is useful for serializing

sipa commented at 10:06 pm on April 18, 2014:

This seems to imply that there usually is a range checking when serializing. AFAIK, that is never the case.

in src/script.h: in 1dae829ace outdated

155+
156+    return result;
157+  }
158+
159+  static const size_t nMaxNumSize = 4;
160+  static const int64_t nMaxOperandValue = 0x7FFFFFFF;

sipa commented at 10:07 pm on April 18, 2014:

These can move to the unit tests now, I think.

sipa commented at 10:09 pm on April 18, 2014: member

ACK.

I made a few nits inline, but looks good.

Can you adapt the coding style, though?

script: add CScriptNum class

This class holds an int64_t and replaces the use of CBigInt for script
integrals.

48d8eb1847

script: switch to CScriptNum usage for scripts 27bff74e39

script: switch outside users to CScriptNum 4f497cd97d

script: remove bignum dependency 05e3ecffa4

script: add additional script tests 90320d6777

theuni commented at 4:40 am on April 22, 2014: member

Squashed down with the following changes:

rebased to master.
replaced busted overflow check with a good one (learned lots in the process).
added overflow check for operator-(int64_min)
cleaned up tests to match final constraints.
Matched coding style (I hope). @gmaxwell It would be much appreciated if you could run your additional script tests against the latest changes.

script: Add test for CScriptNum

Because this class replaces some usages of CBigNum, tests have been added to
verify that they function the same way. The only difference in their usage is
the handling of out-of-range numbers.

While operands are constrained to [-0x7FFFFFFF,0x7FFFFFFF], the results may
overflow. The overflowing result is technically unbounded, but in practice
it can be no bigger than the result of an operation on two operands. This
implementation limits them to the size of an int64.

CBigNum was unaware of this constraint, so it allowed for unbounded results,
which were then checked before use. CScriptNum asserts if an arithmetic
operation will overflow an int64_t, since scripts are not able to reach those
numbers anyway. Additionally, CScriptNum will throw an exception when
constructed from a vector containing more than 4 bytes This mimics the previous
CastToBigNum behavior.

b1fdd5475d

BitcoinPullTester commented at 5:21 am on April 22, 2014: none

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/b1fdd5475d9040445d7655730f262f214ea87c5f for binaries and test log. This test script verifies pulls every time they are updated. It, however, dies sometimes and fails to test properly. If you are waiting on a test, please check timestamps to verify that the test.log is moving at http://jenkins.bluematt.me/pull-tester/current/ Contact BlueMatt on freenode if something looks broken.

gmaxwell commented at 7:12 am on April 22, 2014: contributor

It indeed passes my additional tests. I’ve also started a full testnet resync and I’ll give it another visual code review tomorrow.

in src/script.h: in b1fdd5475d

31+};
32+
33+class CScriptNum
34+{
35+// Numeric opcodes (OP_1ADD, etc) are restricted to operating on 4-byte integers.
36+// The semantics are subtle, though: operands must be in the range [-2^31 +1...2^31 -1],

sipa commented at 7:42 am on April 22, 2014:

This comment is not wrong, but misleading. An input 0x0000000000 would be rejected, even though it is within that range.

sipa commented at 7:46 am on April 22, 2014: member

ACK.

laanwj merged this on May 9, 2014

laanwj closed this on May 9, 2014

laanwj referenced this in commit 1c0319bb2b on May 9, 2014

laanwj referenced this in commit 4def248b2b on May 9, 2014

DrahtBot locked this on Sep 8, 2021

Remove bignum dependency for scripts #3965