Add BigInt library support

alxiong commented 3 years ago

🧐 Motivation This issue is brought to my attention by a question from @wly99.

Say I want to calculate the future value of principal on a 30-year home loan:

futurePrincipal = principal * (1 + stabilityFee / 12) ** monthsLeft

since stabilityFee is a floating number, (e.g. 0.00225) so we need to multiply it by 10000 in practice; but then with the power of monthsLeft = 12 * 30 = 360, this value could easily exceed type(uint256).max.

We want arbitrary precision arithmetic for BigInt.

📝 Details

There is one sample library BigInt {} in Solidity's doc here:

// SPDX-License-Identifier: GPL-3.0
pragma solidity ^0.8.0;

struct bigint {
    uint[] limbs;
}

library BigInt {
    function fromUint(uint x) internal pure returns (bigint memory r) {
        r.limbs = new uint[](1);
        r.limbs[0] = x;
    }

    function add(bigint memory _a, bigint memory _b) internal pure returns (bigint memory r) {
        r.limbs = new uint[](max(_a.limbs.length, _b.limbs.length));
        uint carry = 0;
        for (uint i = 0; i < r.limbs.length; ++i) {
            uint a = limb(_a, i);
            uint b = limb(_b, i);
            unchecked {
                r.limbs[i] = a + b + carry;

                if (a + b < a || (a + b == type(uint).max && carry > 0))
                    carry = 1;
                else
                    carry = 0;
            }
        }
        if (carry > 0) {
            // too bad, we have to add a limb
            uint[] memory newLimbs = new uint[](r.limbs.length + 1);
            uint i;
            for (i = 0; i < r.limbs.length; ++i)
                newLimbs[i] = r.limbs[i];
            newLimbs[i] = carry;
            r.limbs = newLimbs;
        }
    }

    function limb(bigint memory _a, uint _limb) internal pure returns (uint) {
        return _limb < _a.limbs.length ? _a.limbs[_limb] : 0;
    }

    function max(uint a, uint b) private pure returns (uint) {
        return a > b ? a : b;
    }
}

contract C {
    using BigInt for bigint;

    function f() public pure {
        bigint memory x = BigInt.fromUint(7);
        bigint memory y = BigInt.fromUint(type(uint).max);
        bigint memory z = x.add(y);
        assert(z.limb(1) > 0);
    }
}

But still, would love the excellent engineers and security experts from OpenZeppelin community to take a more careful vetting and standardize it by including in future version of the library.

frangio commented 2 years ago

I think a big number library would make sense, but we would like to see a variety of use cases that would benefit from it.

The motivation given here in the issue has some problems, because it assumes stabilityFee is a decimal number, and that is also something that we don't currently have a library for.

barakman commented 2 years ago

In case this is still relevant, I posted such utility a few months ago:

OpenZeppelin / openzeppelin-contracts

Add BigInt library support #2906