HomeEIPs
EIPsEIP-5000
EIP-5000

MULDIV instruction

Introduce a new instruction to perform x * y / z in 512-bit precision
StagnantStandards Track: Core
Created: 2022-03-14
Harikrishnan Mulackal (@hrkrshnn), Alex Beregszaszi (@axic), Paweł Bylica (@chfast)
DiscussionsOriginal linkEdit
1 min read

The EIP-5000 proposal introduces a new instruction, MULDIV(x, y, z), to perform ((x * y) / z) % 2**256 in 512-bit precision in Ethereum. The motivation behind this proposal is to efficiently perform fixed point multiplication and division, which are commonly used in financial applications on Ethereum. The new instruction reduces the complexity of the existing mulmod-based implementation and allows for full precision 256x256->512 multiplication in cryptographic applications. The proposal also aims to provide an instruction that can be efficiently used in both checked and unchecked arithmetic use cases. The specification of the new instruction involves popping 3 values from the stack and performing the calculation with 512-bit precision.

Video
Anyone may contribute to propose contents.
Go propose
Original

Abstract

Introduce a new instruction, MULDIV(x, y, z), to perform ((x * y) / z) % 2**256 in 512-bit precision. z = 0 is a special case for (x * y) % 2**256.

Motivation

Fixed point operations in high level languages are very commonly used on Ethereum, especially in the domain of financial applications.

While fixed point addition and subtraction can be done with merely add and sub respectively, being able to efficiently do fixedpoint multiplication and division is a very sought after feature. A commonly used workaround relies on a mulmod-based, rather complex implementation (taking around 50 instructions, excluding stack manipulation). This instruction reduces that to a single opcode.

A secondary use case is likely in cryptographic applications, where the muldiv instruction allows full precision 256x256->512 multiplication. mul(x y) (or muldiv(x, y, 1)) computes the lower order 256 bits and muldiv(x, y, 0) computes the higher order 256 bits.

Finally we aimed to provide an instruction which can be efficiently used both in checked and unchecked arithmetic use cases. By checked we mean to abort on conditions including division-by-zero and wrapping behaviour.

Specification

A new instruction is introduced: MULDIV (0x1e).

  • Pops 3 values from the stack, first x, then y and z.
  • If z == 0, r = (uint512(x) * y) / 2**256.
  • Otherwise r = (uint512(x) * y / z) % 2**256, where the intermediate calculation is performed with 512-bit precision.
  • Pushes r on the stack.
# operations `*` and `//` are done in 512 bit precision def muldiv(x, y, z): if z == 0: return (x * y) // (2**256) else: return ((x * y) // z) % (2**256)

The cost of the instruction is 8 gas (aka mid), the same as for addmod and mulmod.

Rationale

The special 0 case

All the arithmetic instructions in EVM handle division or modulo 0 specially: the instructions return 0. We have decided to break consistency in order to provide a flexible opcode, which can be used to detect wrapping behaviour.

Alternate options include:

  • Returning a flag for wrapping
  • Returning two stack items, higher and lower order bits
  • Compute the higher order 256 bits in EVM:
/// Returns `hi` such that `x × y = hi × 2**256 + mul(x, y)` function hob(uint x, uint y) returns (uint hi) { uint uint_max = type(uint).max; assembly { let lo := mul(x, y) let mm := mulmod(x, y, uint_max) hi := sub(sub(mm, lo), lt(mm, lo)) } }

While this feature is clever and useful, callers must be aware that unlike other EVM instructions, passing 0 will have a vastly different behaviour.

Argument ordering

The order of arguments matches addmod and mulmod.

Backwards Compatibility

This is a new instruction not present prior.

Test Cases

PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
MULDIV
---
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x0000000000000000000000000000000000000000000000000000000000000000
PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
MULDIV
---
0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe
PUSH 0x0000000000000000000000000000000000000000000000000de0b6b3a7640000
PUSH 0x000000000000000000000000000000000000000000000000016345785d8a0000
PUSH 0x00000000000000000000000000000000000000000000d3c21bcecceda1000000
MULDIV
---
0x00000000000000000000000000000000000000000000152d02c7e14af6800000

Security Considerations

TBA

Copyright and related rights waived via CC0.

Further reading
Anyone may contribute to propose contents.
Go propose
Adopted by projects
Anyone may contribute to propose contents.
Go propose

Not miss a beat of EIPs' update?

Subscribe EIPs Fun to receive the latest updates of EIPs Good for Buidlers to follow up.

View all
Serve EIP builders, scale Ethereum.
Resources
GitHub
Supported by