Smart Contracts - Solidity: Build a big/arbitrary-length integer math library

[monicanagent]

CypherPoker's smart contracts must be able to run positive integer calculations that exceed Ethereum's native 256-bit integer limit. This can be accomplished through a big or arbitrary-length integer library in Solidity that may be modeled on the one used in the game: https://github.com/monicanagent/cypherpoker/blob/master/Libraries/P2P3/CryptoWorker/src/crypto/math/BigInt.as

As a minimum requirement (additional functions may be required in the future), the library contract will need to support the following operations:

(x^y) mod z

Or:

"x" to the power of "y" modulo "z"

Within the 256-bit limit, this can be natively expressed in Solidity as:

uint256 result=(x ** y) % z;

Since each operation here is discrete, the result of (x ** y) must be within the 256-bit limit which requires input values that are too small to provide any security.

In a non-arbitrary library implementation each parameter must support a positive integer value up to 2048 bits but ideally parameter sizes would be arbitrary.

Although Solidity requires two discrete operations (exponentiation & modulo), the ideal implementation would efficiently handle both as one.

[Metaception]

If I may ask, how much of this functionality is working right?
I am in need of a BigInt library as well, but there was none to be found.

I am attempting to make one myself, but I am unfamiliar with these algorithms so progress has been very slow.

I have tested the powMod, multMod, and mod in the online Solidity compiler and they are not producing the expected result.
Am I using them incorrectly?

[monicanagent]

I've put off working on this library indefinitely as I've discovered that I can achieve similar results using Solidity's mulmod. I stopped working on powMod which currently appears to be experiencing overflows (https://github.com/monicanagent/cypherpoker/blob/master/ethereum/solidity/BigInt.sol), although the conversion to/from BigInt and basic math functions seem to work fine.

If you're looking to achieve modular exponentiation within 256 bits then the following function works well (all of my testing has been successful):

function modExp(uint256 base, uint256 exp, uint256 mod) internal returns (uint256 result)  {
   result = 1;
   for (uint count = 1; count <= exp; count *= 2) {
      if (exp & count != 0)
         result = mulmod(result, base, mod);
      base = mulmod(base, base, mod);
   }
}

This function runs through at most "exp" loops so it's fairly efficient but it should be noted that at 256 loops "count" resets back to 0, effectively causing an infinite loop. That means that you can only use values that are 255 bits or shorter. With the following modifications you may be able to squeeze in all 256 bits but I haven't tested this yet:

function modExp(uint256 base, uint256 exp, uint256 mod) internal returns (uint256 result)  {
   result = 1;
   for (uint count = 1; count <= exp; (count = (count*2)-1)) {
      if (exp & (count+1) != 0)
         result = mulmod(result, base, mod);
      base = mulmod(base, base, mod);
   }
}

As long as you can work with modulo values that are within the (2^256)-1 range you can use practically unlimited exponent sizes simply by calling the modExp function repeatedly. For example, using the exponents a and b:

(((m^a) mod P)^b) mod P) = (m^ab) mod P

If each of our exponents is smaller than (2^256)-1 then we can chain our results to produce the same result as if we'd done one calculation using a single composite exponent, ab, effectively increasing our exponent to any arbitrary size (as long as we can provide enough gas to cover the calculations). You can find more details here

[Metaception]

I was hoping to work with 1024-bits for the base, exponential, and modulo values.
Bummer :(

Though for my application, only mulmod is needed. PowMod would have been nice, but it not necessary.

So I was wondering if mod and mulmod was working?
Mod gave me erroneous results and mulmod caused the online compiler to crash.

Great work though, I am hoping to implement the more efficient algorithms from this library and Leemon's JS library that this one is based off.

P.S. Here is my current work, it is pretty bad though.

EDIT: Link fixed

[riordant]

Hey, I know this is an old thread but I built out a full bigint library for Solidity: https://github.com/zcoinofficial/solidity-BigNumber/

[monicanagent]

This looks great! Thanks for sharing it; I'll definitely have a further look into your big number contracts.

[riordant]

No problem, I intend to get it added to EthPM and Consensys live-libs soon, and to get it properly audited. It's pretty well tested as is