Remove bignum dependency for scripts #3965

theuni · 2014-03-27T00:36:42Z

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 · 2014-03-27T00:37:34Z

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

jgarzik · 2014-03-27T00:55:24Z

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 · 2014-03-27T02:24:27Z

@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 · 2014-03-27T05:21:31Z

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 · 2014-03-27T09:45:01Z

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 · 2014-03-29T16:33:57Z

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 · 2014-03-29T17:10:07Z

@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 · 2014-03-31T02:28:32Z

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 · 2014-04-01T05:25:22Z

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 · 2014-04-03T14:51:29Z

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 · 2014-04-03T20:52:07Z

@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 · 2014-04-03T23:06:34Z

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 · 2014-04-04T03:50:29Z

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 · 2014-04-04T07:01:19Z

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

theuni · 2014-04-04T22:20:05Z

@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?

maaku · 2014-04-04T23:23:06Z

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 · 2014-04-04T23:29:17Z

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 · 2014-04-05T22:19:24Z

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:

BOOST_AUTO_TEST_CASE(scriptnum_i64_2)
{
    for (int64_t i  = CScriptNum::nMinOperandValue;
                 i <= CScriptNum::nMaxOperandValue; ++i)
    {
        CheckCreateVch(i);
        CheckCreateInt(i);
    }
}

BOOST_AUTO_TEST_CASE(scriptnum_vch)
{
    for (int a = 0; a <= 255; ++a)
    for (int b = 0; b <= 255; ++b)
    for (int c = 0; c <= 255; ++c)
    for (int d = 0; d <= 255; ++d)
    {
        std::vector<unsigned char> vch;
        vch.push_back((unsigned char)a);
        vch.push_back((unsigned char)b);
        vch.push_back((unsigned char)c);
        vch.push_back((unsigned char)d);
        BOOST_CHECK(CBigNum(vch).getint() == CScriptNum(vch).getint());
    }
}

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.

laanwj · 2014-04-07T08:37:24Z

src/script.h

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.

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

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

["-2147483647", "0x04 0xFFFFFFFF EQUAL"], ["-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.

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

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

invalid:

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

gmaxwell · 2014-04-17T07:59:34Z

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 · 2014-04-17T10:17:31Z

@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 · 2014-04-17T10:41:11Z

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 · 2014-04-17T10:48:09Z

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?

sipa · 2014-04-17T10:52:49Z

src/script.h

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

Bound by which criteria? See the passing test:

["549755813887", "SIZE 5 EQUAL"]

where 7FFFFFFFFF == 549755813887

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

@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.

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.

@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?

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).

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 · 2014-04-17T23:23:46Z

@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:

CScript() << 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 · 2014-04-17T23:27:06Z

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 · 2014-04-18T07:13:51Z

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 · 2014-04-18T21:48:36Z

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).

sipa · 2014-04-18T22:06:38Z

src/script.h

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

sipa · 2014-04-18T22:07:34Z

src/script.h

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

sipa · 2014-04-18T22:09:07Z

ACK.

I made a few nits inline, but looks good.

Can you adapt the coding style, though?

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

theuni · 2014-04-22T04:40:05Z

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.

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.

BitcoinPullTester · 2014-04-22T05:21:26Z

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 · 2014-04-22T07:12:35Z

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

sipa · 2014-04-22T07:42:08Z

src/script.h

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

sipa · 2014-04-22T07:46:09Z

ACK.

b1fdd54 script: Add test for CScriptNum (Cory Fields) 90320d6 script: add additional script tests (Cory Fields) 05e3ecf script: remove bignum dependency (Cory Fields) 4f497cd script: switch outside users to CScriptNum (Cory Fields) 27bff74 script: switch to CScriptNum usage for scripts (Cory Fields) 48d8eb1 script: add CScriptNum class (Cory Fields)

After bitcoin#4076, bitcoin#3965 and bitcoin#4048 bignum.h is only used for verifying scriptnum.

laanwj reviewed Apr 7, 2014
View reviewed changes

laanwj added this to the 0.10.0 milestone Apr 16, 2014

sipa reviewed Apr 17, 2014
View reviewed changes

sipa reviewed Apr 18, 2014
View reviewed changes

src/script.h Outdated

Copy link

Member

sipa Apr 18, 2014

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

sipa reviewed Apr 18, 2014
View reviewed changes

src/script.h Outdated

Copy link

Member

sipa Apr 18, 2014

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

sipa mentioned this pull request Apr 20, 2014

Remove dependency of main on OpenSSL bignum #4076

Merged

theuni added 5 commits April 22, 2014 00:32

script: add CScriptNum class

48d8eb1

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

script: switch to CScriptNum usage for scripts

27bff74

script: switch outside users to CScriptNum

4f497cd

script: remove bignum dependency

05e3ecf

script: add additional script tests

90320d6

sipa reviewed Apr 22, 2014
View reviewed changes

src/script.h

Copy link

Member

sipa Apr 22, 2014

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

laanwj merged commit b1fdd54 into bitcoin:master May 9, 2014

laanwj added a commit to laanwj/bitcoin that referenced this pull request May 9, 2014

Move bignum.h to src/test

4def248

After bitcoin#4076, bitcoin#3965 and bitcoin#4048 bignum.h is only used for verifying scriptnum.

laanwj mentioned this pull request May 9, 2014

Move bignum.h to src/test #4159

Closed

cculianu mentioned this pull request Aug 24, 2021

Fix ScriptNum Tests #22786

Closed

bitcoin locked as resolved and limited conversation to collaborators Sep 8, 2021

Remove bignum dependency for scripts #3965

Remove bignum dependency for scripts #3965

Uh oh!

Conversation

theuni commented Mar 27, 2014

Uh oh!

theuni commented Mar 27, 2014

Uh oh!

jgarzik commented Mar 27, 2014

Uh oh!

theuni commented Mar 27, 2014

Uh oh!

sipa commented Mar 27, 2014

Uh oh!

laanwj commented Mar 27, 2014

Uh oh!

sipa commented Mar 29, 2014

Uh oh!

theuni commented Mar 29, 2014

Uh oh!

theuni commented Mar 31, 2014

Uh oh!

theuni commented Apr 1, 2014

Uh oh!

gavinandresen commented Apr 3, 2014

Uh oh!

theuni commented Apr 3, 2014

Uh oh!

theuni commented Apr 3, 2014

Uh oh!

theuni commented Apr 4, 2014

Uh oh!

theuni commented Apr 4, 2014

Uh oh!

theuni commented Apr 4, 2014

Uh oh!

maaku commented Apr 4, 2014

Uh oh!

theuni commented Apr 4, 2014

Uh oh!

maaku commented Apr 5, 2014

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

gmaxwell commented Apr 17, 2014

Uh oh!

theuni commented Apr 17, 2014

Uh oh!

sipa commented Apr 17, 2014

Uh oh!

sipa commented Apr 17, 2014

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

theuni commented Apr 17, 2014

Uh oh!

gmaxwell commented Apr 17, 2014

Uh oh!

luke-jr commented Apr 18, 2014

Uh oh!