Poseidon for EVMMAX
Implementation of Poseidon for EVMMAX.
Poseidon is a family of ZK-friendly hash functions used in rollups such as Starknet. A precompile for the Ethereum Virtual Machine has been proposed in EIP-5988.
EVMMAX is an extension of the EVM with optimised modular arithmetics. It has been proposed in EIP-5843 and EIP-6601.
We compare in this repository different possible solutions for implementing poseidon for the EVM or EVMMAX.
Description of Poseidon
Poseidon inputs and outputs are elements of a given finite field. Our implementations use a prime field; in that case, elements are integers modulo a (large) prime number.
We will use fixed-width hash functions. They receive rate field elements as input and produce rate field elements as output. Internally, it pads the input to a state vector S of length size (rate < size), permutes it using a permutation P and outputs rate elements of the permuted input vector P(S).
Poseidon's permutation is constructed by applying many rounds of a simpler permutation. This simpler permutation in turn is the composition of 3 basic operations:
- Ark: round constants are added to S (different for each round)
- S-Box: elements of S are taken to a power a
- Mix: the state S is multiplied by a fixed MDS-matrix M
For efficiency purposes, most rounds are actually partial. Partial rounds differ in that the S-Box is applied to a single element only instead of all state elements.
Parameters
We use the following parameters, the whole set being avaible in params. The 256bits modulus is always: 2^251 + 2^196 + 2^192 + 1
Variant | Rate | Size | S-Box | N-full | N-partial |
---|---|---|---|---|---|
Poseidon2 | 2 | 3 | 3 | 8 | 83 |
Number of Modular Operations
Permutations use additions and multiplications:
- Ark: size additions
- S-Box: 2 multiplications per element for power = 3
- Mix: size^2 multiplications + (size - 1) * size additions
Variant | Round | Add | Mult |
---|---|---|---|
Poseidon2 | Full | 9 | 15 |
Poseidon2 | Partial | 9 | 11 |
Poseidon2 | Total | 819 | 1'049 |
Note that with EVMMAX, we need to use 2 * rate multiplications to convert inputs and outputs from and to Montgomery's form.
Implementation variants
Deploiement costs can be taken as negligible given that we target many millions of calls to the hash function. Hence we aim at exploring different implementation with the goal of reducing the most the gas cost of a call, but we are also interested in execution time.
The following variants qualifiers describe implementation choices:
- std : uses standard modular arithmetic op codes.
- max : uses EVMMAX modular arithmetic op codes.
- rs : uses poseidon-rs precompile.
- cst : modulus, round constants and mds-matrix are included directly in code and pushed to the stack as needed.
- mem : modulus and mds-matrix are kept in memory and loaded on the stack as neeeded.
- unwind : rounds are concatenated one after the other in the code.
- func : rounds are function call-like to reduce code size, but imply 2 jumps per round.
Note that for EVMMAX, operations happen directly in memory, so we are obliged to load constants in memory.
Results
Here are some stats of executing poseidon hash
Variant | Implementation | CodeSize (B) | Timing (ms) | GasCost | N-ops |
---|---|---|---|---|---|
Poseidon2 | std-cst-unwind | ||||
Poseidon2 | std-mem-unwind | 21'914 | 1.446 | 38'687 | 9'793 |
Poseidon2 | std-mem-func | ||||
Poseidon2 | max-unwind | 17'950 | 0.540 | 5'549 | 2'721 |
Poseidon2 | max-func | ||||
Poseidon2 | rs |
Observations
EVMMAX brings gas savings of the order of 80% compared to a standard implementation. However, we note that the majority of these savings come from EVMMAX operation model and not from the modular arithmetic costs themselves. Indeed, we save on the numerous operations (PUSH, MLOAD, MSTORE) aiming at bringing constants to the stack for modular arithmetics. This is due to the fact that in EVMMAX, modular arithmetics happen directly in memory, and the arguments are given as immediate indices in the code.
This can be seen in the following profiling of Op Codes
Variant | Implementation | MSTORE | MLOAD | PUSH | DUP | SWAP | GasCost |
---|---|---|---|---|---|---|---|
Poseidon2 | std-cst-unwind | ||||||
Poseidon2 | std-mem-unwind | 555 | 1'911 | 2'754 | 2'066 | 653 | 23'817 |
Poseidon2 | std-mem-func | ||||||
Poseidon2 | max-unwind | 285 | 0 | 577 | 0 | 0 | 2'586 |
Poseidon2 | max-func | ||||||
Poseidon2 | rs |
Note that modular arithmetics gas costs are incompressible, and are given by
Variant | Implem | cost add | cost mul | cost set | TotalGas |
---|---|---|---|---|---|
Poseidon2 | standard | 8 x 819 | 8 x 1'049 | -- | 14'816 |
Poseidon2 | EVMMAX | 1 x 819 | 2 x 1'053 | 1 x 90 | 2'925 |
Thus we have the following gas savings distribution for EVMMAX
Variant | Implem | Stack Savings | Arith Savings | Total Savings |
---|---|---|---|---|
Poseidon2 | unwind | 21'231 (64%) | 11'891 (36%) | 33'138 |