MiMC-p/p for Solidity

mimc.py

# Copyright (c) 2018 HarryR
# License: LGPL-3.0+

try:
    # pysha3
    from sha3 import keccak_256
except ImportError:
    # pycryptodome
    from Crypto.Hash import keccak
    keccak_256 = lambda *args: keccak.new(*args, digest_bits=256)


SNARK_SCALAR_FIELD = 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001
DEFAULT_EXPONENT = 7
DEFAULT_ROUNDS = 91
DEFAULT_SEED = b'mimc'


def to_bytes(*args):
    for i, _ in enumerate(args):
        if isinstance(_, str):
            yield _.encode('ascii')
        elif not isinstance(_, int) and hasattr(_, 'to_bytes'):
            # for 'F_p' or 'FQ' class etc.
            yield _.to_bytes('big')
        elif isinstance(_, bytes):
            yield _
        else:
            # Try conversion to integer first?
            yield int(_).to_bytes(32, 'big')


def H(*args):
    data = b''.join(to_bytes(*args))
    hashed = keccak_256(data).digest()
    return int.from_bytes(hashed, 'big')

assert H(123) == 38632140595220392354280998614525578145353818029287874088356304829962854601866


"""
Generate a sequence of round constants

These can hard-coded into circuits or generated on-demand
"""
def mimc_constants(seed, p=SNARK_SCALAR_FIELD, R=DEFAULT_ROUNDS):
    if isinstance(seed, str):
        seed = seed.encode('ascii')
    if isinstance(seed, bytes):
        # pre-hash byte strings before use
        seed = H(seed)
    else:
        seed = int(seed)

    for _ in range(R):
        seed = H(seed)
        yield seed


"""
The MiMC cipher: https://eprint.iacr.org/2016/492

 First round

            x    k
            |    |
            |    |
           (+)---|     X[0] = x + k
            |    |
    C[0] --(+)   |     Y[0] = X[0] + C[0]
            |    |
          (n^7)  |     Z[0] = Y[0]^7
            |    |
*****************************************
 per-round  |    |
            |    |
           (+)---|     X[i] = Z[i-1] + k
            |    |
    C[i] --(+)   |     Y[i] = X[i] + C[i]
            |    |
          (n^7)  |     Z[i] = Y[i]^7
            |    |
*****************************************
 Last round
            |    |
           (+)---'     result = Z.back() + k
            |
          result
"""
def mimc(x, k, seed=DEFAULT_SEED, p=SNARK_SCALAR_FIELD, e=DEFAULT_EXPONENT, R=DEFAULT_ROUNDS):
    assert R > 2
    # TODO: assert gcd(p-1, e) == 1
    for c_i in list(mimc_constants(seed, p, R)):
        a = (x + k + c_i) % p
        x = (a ** e) % p
    return (x + k) % p


"""
The Miyaguchi–Preneel single-block-length one-way compression
function is an extended variant of Matyas–Meyer–Oseas. It was
independently proposed by Shoji Miyaguchi and Bart Preneel.

H_i = E_{H_{i-1}}(m_i) + {H_{i-1}} + m_i

The previous output is used as the key for
the next iteration.

or..

             m_i
              |
              |----,
              |    |
              v    |
H_{i-1}--,-->[E]   |
         |    |    |
         `-->(+)<--'
              |
              v
             H_i

@param x list of inputs
@param k initial key
"""
def mimc_hash(x, k=0, seed=DEFAULT_SEED, p=SNARK_SCALAR_FIELD, e=DEFAULT_EXPONENT, R=DEFAULT_ROUNDS):
    for x_i in x:
        r = mimc(x_i, k, seed, p, e, R)
        k = (k + x_i + r) % p
    return k


def _main():
    import argparse
    parser = argparse.ArgumentParser("MiMC")
    parser.add_argument('-r', '--rounds', metavar='N', type=int, default=DEFAULT_ROUNDS, help='number of rounds')
    parser.add_argument('-e', '--exponent', metavar='N', type=int, default=DEFAULT_EXPONENT, help='exponent for round function')
    parser.add_argument('-s', '--seed', type=bytes, default=DEFAULT_SEED, help='seed for round constants')
    parser.add_argument('-k', '--key', type=int, default=0, help='initial key')
    parser.add_argument('-v', '--verbose', action='store_true', default=False, help='display settings')
    parser.add_argument('cmd', nargs='?', default='test')
    parser.add_argument('subargs', nargs='*')
    args = parser.parse_args()

    exponent = args.exponent
    rounds = args.rounds
    seed = args.seed
    key = int(args.key)
    cmd = args.cmd

    if args.verbose:
        print('# exponent', exponent)
        print('# rounds', rounds)
        print('# seed', seed)
        print('# key', key)

    if cmd == "test":
        # With default parameters, known results
        assert mimc(1, 1) == 2447343676970420247355835473667983267115132689045447905848734383579598297563
        assert mimc_hash([1,1]) == 4087330248547221366577133490880315793780387749595119806283278576811074525767

        # Verify cross-compatibility with EVM/Solidity implementation
        assert mimc(3703141493535563179657531719960160174296085208671919316200479060314459804651,
                    134551314051432487569247388144051420116740427803855572138106146683954151557,
                    b'mimc') == 11437467823393790387399137249441941313717686441929791910070352316474327319704
        assert mimc_hash([3703141493535563179657531719960160174296085208671919316200479060314459804651,
                        134551314051432487569247388144051420116740427803855572138106146683954151557],
                       918403109389145570117360101535982733651217667914747213867238065296420114726,
                       b'mimc') == 15683951496311901749339509118960676303290224812129752890706581988986633412003
        print('OK')
        return 0

    elif cmd == "constants":
        for x in mimc_constants(seed, SNARK_SCALAR_FIELD, rounds):
            print(x % SNARK_SCALAR_FIELD)  # hex(x), x)

    elif cmd == "encrypt":
        for x in args.subargs:
            x = int(x)
            result = mimc(x, key, seed, SNARK_SCALAR_FIELD, exponent, rounds)
            key = mimc(key, key, seed, SNARK_SCALAR_FIELD, exponent, rounds)
            print(result)

    elif cmd == "hash":
        result = mimc_hash([int(x) for x in args.subargs], key, seed, SNARK_SCALAR_FIELD, exponent, rounds)
        print(result)

    else:
        parser.print_help()
        return 1

    return 0
        

if __name__ == "__main__":
    import sys
    sys.exit(_main())

MiMCp.sol

// Copyright (c) 2018 HarryR
// License: LGPL-3.0+

pragma solidity ^0.5.0;

/**
* Implements MiMC-p/p over the altBN scalar field used by zkSNARKs
*
* See: https://eprint.iacr.org/2016/492.pdf
*
* Round constants are generated in sequence from a seed
*/
library MiMC
{
    function GetScalarField ()
        internal pure returns (uint256)
    {
        return 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001;
    }

    function Encipher( uint256 in_x, uint256 in_k )
        public pure returns(uint256 out_x)
    {
        return MiMCpe7( in_x, in_k, uint256(keccak256("mimc")), 91 );
    }

    /**
    * MiMC-p/p with exponent of 7
    * 
    * Recommended at least 46 rounds, for a polynomial degree of 2^126
    */
    function MiMCpe7( uint256 in_x, uint256 in_k, uint256 in_seed, uint256 round_count )
        internal pure returns(uint256 out_x)
    {
        assembly {
            if lt(round_count, 1) { revert(0, 0) }

            // Initialise round constants, k will be hashed 
            let c := mload(0x40)
            mstore(0x40, add(c, 32))
            mstore(c, in_seed)

            let localQ := 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001
            let t
            let a

            // Further n-2 subsequent rounds include a round constant
            for { let i := round_count } gt(i, 0) { i := sub(i, 1) } {
                // c = H(c)
                mstore(c, keccak256(c, 32))

                // x = pow(x + c_i, 7, p) + k
                t := addmod(addmod(in_x, mload(c), localQ), in_k, localQ)              // t = x + c_i + k
                a := mulmod(t, t, localQ)                                              // t^2
                in_x := mulmod(mulmod(a, mulmod(a, a, localQ), localQ), t, localQ)     // t^7
            }

            // Result adds key again as blinding factor
            out_x := addmod(in_x, in_k, localQ)
        }
    }
       
    function MiMCpe7_mp( uint256[] memory in_x, uint256 in_k, uint256 in_seed, uint256 round_count )
        internal pure returns (uint256)
    {
        uint256 r = in_k;
        uint256 localQ = 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001;

        for( uint256 i = 0; i < in_x.length; i++ )
        {
            r = (r + in_x[i] + MiMCpe7(in_x[i], r, in_seed, round_count)) % localQ;
        }
        
        return r;
    }

    function Hash( uint256[] memory in_msgs, uint256 in_key )
        public pure returns (uint256)
    {
        return MiMCpe7_mp( in_msgs, in_key, uint256(keccak256("mimc")), 91 );
    }

    function Hash( uint256[] memory in_msgs )
        public pure returns (uint256)
    {
        return Hash( in_msgs, 0 );
    }
}