Skip to content

Instantly share code, notes, and snippets.

@HarryR
Last active August 15, 2024 06:37
Show Gist options
  • Save HarryR/80b5ff2ce13da12edafda6d21c780730 to your computer and use it in GitHub Desktop.
Save HarryR/80b5ff2ce13da12edafda6d21c780730 to your computer and use it in GitHub Desktop.
MiMC-p/p for Solidity
# 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())
// 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 );
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment