# EIP-6690: EVM Modular Arithmetic Extensions (EVMMAX)

### Create modular addition, subtraction, and multiplication opcodes.

## Abstract

This EIP proposes the addition of new optimized modular addition, subtraction and multiplication opcodes to the EVM. These support odd moduli up to 4096 bits in size.

## Motivation

Benefits of the changes proposed in this EIP:

- enables elliptic curve arithmetic operations on various curves including BLS12-381 to be implemented as EVM contracts
- For operations on values up to 256bits in size, reduces gas cost per operation by 90-95% compared to the current
`MULMOD`

and`ADDMOD`

opcodes. - for all cases where modexp precompile is useful, it could now be implemented as an EVM contract.
- enables substantial cost reductions for algebraic hash functions (e.g. MiMC/Poseidon), zkp verification in the EVM.

## Specification

### Overview

During contract execution, a contract calls a setup instruction `SETUPX`

, sourcing a modulus from a specified memory offset/size and computing several parameters used to speed up modular multiplication (referred to as "Montgomery" parameters). A zeroed memory space (whose size is a stack parameter passed to `SETUPX`

) is allocated separate from EVM memory.

The modulus, computed parameters and memory space are associated with the current call frame state and referred to as the active modulus state. If `SETUPX`

is called again to switch to a different modulus, the memory space and Montgomery parameters of the previous active modulus state remain allocated (the memory spaces of active/previously-active modulus state are separate).

New store and load opcodes `STOREX`

/`LOADX`

are used to copy multiples values to/from EVM memory and the memory space of the active modulus state.

Arithmetic is performed with `ADDMODX`

/`SUBMODX`

/`MULMODX`

opcodes which take and return no stack items, require a 3-byte immediate value appended to the opcode.

The immediate is interpreted as 3 1-byte values `z`

, `x`

, `y`

which are indexes to the array of EVMMAX values that comprise the memory space of the active modulus state.

An arithmetic operation is performed on inputs at index `x`

/`y`

placing the result in index `z`

.

### Conventions

`x === y % m`

:`x % m == y % m`

`pow(x, -1, m)`

: The modular multiplicative inverse of`x`

with respect to modulus`m`

.- Opcode definition syntax is formatted as
`mneumonic {immediate - type} {immediate2 - type} ...: stack_arg_1, stack_arg_2, ...`

where immediates are listed in the order that they proceed the opcode and stack arguments are ordered starting at the top of the stack. - In the provided pseudocode, it is assumed that opcode gas charging logic is executed prior to execution logic.
- Any exception thrown should immediately end the current execution frame and return to the caller.

### Constants

Name | Value | Description |
---|---|---|

`STOREX_BASE_GAS` | 3 | base gas cost for `STOREX` opcode |

`LOADX_BASE_GAS` | 3 | base gas cost for `LOADX` opcode |

`SETUPX_BASE_GAS` | 3 | base gas cost for `SETUPX` opcode |

`EVMMAX_MAX_MEM` | 65,536 bytes | maximum amount of EVMMAX memory that can be used in a call frame |

`MAX_MOD_SIZE` | 4096 bits | tentative modulus size limit (can probably be removed because `EVMMAX_MAX_MEM_SIZE` effectively caps the modulus size) |

`MULMODX_SUBQUADRATIC_START` | 50 | modulus size in multiples of 8 bytes where we switch to subquadratic mulmont cost model |

`SYSTEM_WORD_SIZE_BITS` | varies depending on the system | word size in bits of a client's CPU |

### Context Variables

Name | Type | Meaning |
---|---|---|

`evmmax_state` | `EVMMAXState` | a variable representing ephemeral state which exists for the duration of the current call and in the scope of the current call frame |

`evm_memory` | `bytes` | EVM memory for the current call context |

`expand_evm_memory` | `func(size_words: int)` | expands EVM memory by `size_words * 32` bytes |

`cost_evm_memory_expansion` | `func(new_size_evm_words: int) -> int` | EVM memory expansion cost function, modified according to this EIP |

`evm_stack` | object | Allows access to the stack via `pop()` and `peek(n)` which return `int` stack elements |

`contract_code` | `bytes` | code of the currently-executing contract |

`pc` | `int` | EVM program counter |

### Helpers

### New Opcodes

Mneumonic | Opcode | Immediate size (bytes) | Stack in | Stack out |
---|---|---|---|---|

SETUPX | 0x21 | 0 | 4 | 0 |

ADDMODX | 0x22 | 3 | 0 | 0 |

SUBMODX | 0x23 | 3 | 0 | 0 |

MULMODX | 0x24 | 3 | 0 | 0 |

LOADX | 0x25 | 0 | 3 | 0 |

STOREX | 0x26 | 0 | 3 | 0 |

### SETUPX

`SETUPX : mod_id, mod_offset, mod_size, vals_used`

### Gas Charging

### Execution

### LOADX

`LOADX: dst_offset, val_idx, num_vals`

### Description

Load EVMMAX values in the current active modulus state to EVM memory.

### Gas Charging

### Execution

### STOREX

`STOREX: dst_val, offset, num_vals`

### Description

Store values from EVM memory into EVMMAX memory space of the current active modulus state, validating that they are reduced by the modulus.

### Gas Charging

### Execution

### ADDMODX

`ADDMODX {z_offset - byte}, {x_offset - byte}, {y_offset - byte}:`

### Description

Compute the modular addition of two EVMMAX values, storing the result in an output.

### Gas Charging

### Execution

### SUBMODX

`SUBMODX {z_offset - byte}, {x_offset - byte}, {y_offset - byte}:`

### Description

Compute the modular subtraction of two EVMMAX values in the current active modulus state, storing the result in an output.

### Gas Charging

Same as `ADDMODX`

.

### Execution

`MULMODX`

`MULMODX {z_offset - byte}, {x_offset - byte}, {y_offset - byte}:`

### Description

Compute the Montgomery modular multiplication of two EVMMAX values in the current active modulus state, storing the result in an output.

### Gas Charging

### Execution

### Changes to Contract Execution

### EVM Memory Expansion Cost Function

Any EVM operation which expands memory `x`

bytes will charge to expand memory to `cur_evm_mem_size + x + evmmax_mem_size`

bytes where `evmmax_mem_size`

is the size of all allocated EVMMAX values in the current call context (the sum of the values used by each `mod_id`

that has been previously/currently set with `SETUPX`

).

### Jumpdest Analysis

Jumpdest analysis is modified to disallow jumps into immediate data for `ADDMDOX`

/`SUBMODX`

/`MULMODX`

.

## Rationale

### Montgomery Modular Multiplication

EVMMAX values are stored internally in Montgomery form. Expressing values in Montgomery form enables the use of Montgomery reduction in modular multiplication which gives a substantial performance gain versus naive modular multiplication.

Modular addition and subtraction on Montgomery form values is computed the same as normal.

### Memory Alignment for EVMMAX Values

`LOADX`

/`STOREX`

move 64bit-aligned big-endian values to/from the memory space of the active modulus state. `SETUPX`

memory expansion pricing is tuned to assume that values will be stored in a as 64bit-aligned values in their EVMMAX memory space.

This choice is made to keep EVMMAX memory aligned to ensure performance.

### Gas Costs

Gas models assume a rate of 1 gas per 25ns of execution time.

### ADDMODX/SUBMODX/MULMODX

`ADDMODX`

and `SUBMODX`

can each be implemented using a single extended-precision addition, and single extended precision subtraction. This justifies a linear cost model.

`MULMODX`

runtime scales quadratically with input size. After a certain threshold, the quadratic complexity of `mulmont_quadratic`

dominates and it becomes more performant to use `mulmont_subquadratic`

. Thus, there is a segmented cost model to reflect different asymptotic behavior between quadratic/subquadratic `mulmont`

.

`ADDMODX`

/`SUBMODX`

/`MULMODX`

pricing includes the cost of arithmetic and latency of accessing input values from CPU cache.

The price model assumes that the implementation will be generic for most bitwidths with the exception of 321-384bits which is priced aggressively.

### LOADX/STOREX

These perform conversion to/from Montgomery and canonical forms for each value copied (a single `mulmont`

per value converted). The overhead of memory loading/copying is covered by `cost_mulmontx`

.

### SETUPX

## Backwards Compatibility

Jumpdest analysis changes in this EIP could potentially break existing contracts where a jump destination occurs in the 3 bytes proceeding a `0x22`

/`0x23`

/`0x24`

. This is unlikely to affect many existing contracts. Further analysis of deployed contract bytecode can determine with certainty, which (if any) contracts could be broken.

## Security Considerations

## Copyright

Copyright and related rights waived via CC0.