feat(stdlibs): add `math/overflow`

[leohhhn]

Description

This PR ports over the overflow stdlib to Gno. The addition of this library will enable adding Coin functionality already existing in tm2's coin.go the Coin/Coins in Gno.

The tests pass fully, and the library was simply copy-pasted.

As per the conversation below, this PR also deprecates/removes the examples/ package for overflow, as it makes more sense to have overflow be a part of stdlibs.

This will unblock #1696.

cc @thehowl

Contributors' checklist...

• [x] Added new tests, or not needed, or not feasible
• [x] Provided an example (e.g. screenshot) to aid review or the PR is self-explanatory
• [x] Updated the official documentation or not needed
• [x] No breaking changes were made, or a BREAKING CHANGE: xxx message was included in the description
• [x] Added references to related issues and PRs
• [x] Provided any useful hints for running manual tests
• [ ] Added new benchmarks to generated graphs, if any. More info here.

[codecov[bot]]

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 48.25%. Comparing base (b2f12a9) to head (15e23cd). Report is 4 commits behind head on master.

Additional details and impacted files

@@           Coverage Diff           @@
##           master    #1698   +/-   ##
=======================================
  Coverage   48.25%   48.25%           
=======================================
  Files         408      408           
  Lines       62338    62338           
=======================================
  Hits        30081    30081           
  Misses      29749    29749           
  Partials     2508     2508           

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[deelawn]

How does it compare to https://github.com/gnolang/gno/blob/master/examples/gno.land/p/demo/maths/overflow.gno?

Should we remove that from the demo packages if we are making it part of the stdlib? I think it makes sense for it to only exist in one place

[leohhhn]

@deelawn

Good point! I didn't realize we had this in the examples.

2 things:

• They are not 100% identical from what I can see
• I am not sure if there is an "order of deployment" - I'm not sure it's possible to use onchain packages within the stdlibs. Is there a predecence that needs to be met with this? Ie, you can use stdlibs in onchain packages, but not the other way around?

[deelawn]

Overflow protection seems like such a core feature of a blockchain that the package should be included our standard library, especially if they are used by other parts of the standard library. Perhaps it can live in math/overflow given how related it is to math. Maybe we can reconcile the differences between these two packages and deprecate the existing demo space package. What do you think?

[leohhhn]

@deelawn

We are using gnolang/overflow to check our coins in tm2 in coin.go, while the examples version package is slightly different - reference the top comment in the examples/ package.

I've ported the examples/ version package code over to math/overflow. Tests pass.

It would be great if we can get some more eyes on this, since tm2 overflow != examples/ overflow, and with this PR the gnoVM stdlibs overflow.

Bit of a tangent - I'm not sure what the reason for this is, but it seems running gno test . --verbose in the gnovm/stdlibs/math dir even before making any changes causes a machine panic.

[thehowl]

+1 for math/overflow. I haven't reviewed properly, so wouldn't know to advise yet on which one we should pick. Will try to take a look this week

[deelawn]

I think that, based on this comment in the package implementation, we should go with that code if we want to move it into the standard library. It includes a quotient bug fix and bundles the output of go generate in the same overflow.gno file. This is code is contained in the overflow_impl.go file in the original go implementation.

[kristovatlas]

Great effort to address overflow conditions in stdlib.

Note also that integer underflow is a concern. I typically see this less often while browsing code in the wild compared to overflow, but back in 2018 Tantikul and Ngamsuriyaroj scanned nearly 40k contracts from Etherscan and found a detection correlation rate between integer overflows and underflows of 0.3 in the same code contracts, so it seems to be a prevalent issue. [paper]

For this reason, whenever I'm writing docs that recommend a particular approach to security, I'd rather have people use math/big by default to deal with both vuln classes, and only resort to using the overflow library if efficiency is required and underflows aren't a concern. Alternatively, we could augment this overflow library to also handle underflow conditions and throw an error for either. Thoughts?

[thehowl]

@kristovatlas do note that the package being added does handle the cases of underflow, as well: https://go.dev/play/p/EJy_HjxuUSG

Your take on the fact that contracts should use bigints by default is interesting. There is a discussion ongoing on this regard: #764. bigint is a builtin type in Gno currently, but I was thinking it may be better to hold it back in favour of uint256 for managing quantites like token supplies etc., both for performance but also because I see in having a bigint type an implication: the underlying memory representation is not bounded, and "combining user input" with it should be done with the same care as with a []byte.

But, I'm starting to consider that the tradeoff may be worth it if it avoids a whole class of problems, especially within the blockchian context.

For what concerns this library, it'd be great if you could double-check the code and help verify especially the change to the Quotient functions (which are the only ones different from the original), and perhaps suggest a better name that conveys this libraries works for underflows, too. Then I suggest we move the conversation to #764 to determine whether we should add full support for bigint as a built-in type :)

[leohhhn]

From the PR review call on March 14th, discussing this with @jaekwon:

• Port math/overflow into the GnoVM stdlibs to be used for smaller ints (int64 & less),
• Add OnBloc's implementation of uint256 to examples/gno.land/p/demo, battle test it, see how it works, and later down the line consider adding it to GnoVM stdlibs or implementing a native uint256 Gno type.

[notJoon]

Add OnBloc's implementation of uint256 to examples/gno.land/p/demo, battle test it, see how it works, and later down the line consider adding it to GnoVM stdlibs or implementing a native uint256 Gno type.

There are currently no tests for u256 on the gnoswap side, so I'll add a test and put it on the p/demo side first :)

cc: @r3v4s @dongwon8247

[kristovatlas]

One thing that's a little odd is overloading the "ok" return value to signal both overflow/underflow and zero divisor. I can't think of a security issue, though.

[kristovatlas]

Sorry for the delay, ran into a few compilation issues while reviewing and I didn't want to rush the analysis. After staring at it a good long while and writing my own tests, I'm totally happy with the overflow.gno library. Once this PR is merged, I plan to just document the code a little better since this library can be security-critical for gno devs.

[kristovatlas]

Regarding the ambiguity of not mentioning underflows specifically, just a little more code commenting will be sufficient to make this clear. And I will add a handful more tests to drive home the point.

[leohhhn]

@thehowl @kristovatlas

I've looked at your comments & suggestions. Can we move forward with this merge?

@thehowl, once we merge this, I can update the gnolang/overflow repo to match.

[kristovatlas]

@thehowl @kristovatlas

I've looked at your comments & suggestions. Can we move forward with this merge?

@thehowl, once we merge this, I can update the gnolang/overflow repo to match.

Sorry, my last comment was a little confusing. I meant that I plan to personally annotate this after merger. It is ready to be merged IMHO

[notJoon]

In the math_int8.gno file, the paths for the Add8, Sub8, Mul8, and Quo8 functions are recognized as math/overflow. It seems that this file also needs to be modified the import path.

[leohhhn]

Trying to fix the tests, I'm running into a weird issue:

• Some consts are defined in stdlibs/math/const.gno, contained within the math package
• Overflow is using them but it seems that for some reason the package does not see them Specifically:

panic: fail on files/maths_int8.gno: got unexpected error: math/overflow/overflow.gno:35: name MaxUint32 not declared:

So maths_int8, as well as some other files are using overflow, which is using MaxUint32 and other consts from package math. Even though we're importing math in overflow, we are getting this error.

Investigating now.

EDIT: for reference, I fixed the import issue by adding the missing constants to tests/imports.go in 61b0cca & b3b3daa

cc @Kouteki

EDIT: btw, seems that stdlibs/math/all_test.gno is failing unrelated. This is most likely a separate issue - weird that this is not caught by CI. (tested with gno test . -v in gnovm/stdlibs/math)

[leohhhn]

@thehowl

Ok, this is the current state: Fixed up the doc comment, and moved the tests around as you suggested here.

Removed p/demo/maths, but since it also included some functionality (ret fractions) used in p/demo/groups, I decided to remove all math functionality and rename it to ret while keeping the needed stuff.

PR should be good to go.