EIP-5000: MULDIV instruction


  Ethereum Improvement Proposals
        
        
          
            
              
            
          
        

        AllCoreNetworkingInterfaceERCMetaInformational

      



      
        
  
    

  
    
      🚧 Stagnant
    
    
    
    
    
      Standards Track: Core
    
  
  
    
      EIP-5000: MULDIV instruction
    
    
      
        
      
    
    
      
        
      
    
  

  Introduce a new instruction to perform x * y / z in 512-bit precision

  	Authors	Harikrishnan Mulackal (@hrkrshnn), Alex Beregszaszi (@axic), Paweł Bylica (@chfast)
	Created	2022-03-14
	Discussion Link	https://ethereum-magicians.org/t/muldiv-instruction/9930


  


  

  
    Table of Contents

    	Abstract
	Motivation
	Specification
	Rationale
    	The special 0 case
	Argument ordering


  
	Backwards Compatibility
	Test Cases
	Security Considerations
	Copyright



  


  
      
      
         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
      
      
    


Copyright and related rights waived via CC0.


  Citation

  Please cite this document as:

  
  Harikrishnan Mulackal (@hrkrshnn), Alex Beregszaszi (@axic), Paweł Bylica (@chfast), "EIP-5000: MULDIV instruction [DRAFT]," Ethereum Improvement Proposals, no. 5000, March 2022. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-5000.






      
    
  

  

    Ethereum Improvement Proposals


    
      
        	Ethereum Improvement Proposals


      


      	 ethereum/EIPs





      
        Ethereum Improvement Proposals (EIPs) describe standards for the Ethereum platform, including core protocol specifications, client APIs, and contract standards.