EIP-145 EVM bit shift instructions (Bitwise shifting instructions in EVM)
Final · EVM & execution · EIP status Final · created 2017-02-13
Adds three dedicated bit shift instructions to the EVM: SHL, SHR, and SAR. A shift operation that cost 35 gas when emulated with arithmetic operations now costs 3 gas.
Why it is needed
The EVM (Ethereum Virtual Machine) is the engine that executes smart contract code. It supports logical operations like AND and OR, and arithmetic operations like multiplication and division, but it lacked dedicated instructions for shifting bits left or right. When a shift was needed, it had to be implemented by working around it, multiplying or dividing by a power of two. This means the computer (host) running the EVM has to do more work, and the fees contracts incur go up. According to the original text, emulating SHL and SHR with arithmetic operations costs 35 gas each, but the dedicated instructions introduced by this proposal only cost 3 gas. The starting point of this proposal is to make a very commonly used basic operation in programming available at a cost comparable to other arithmetic operations.
What changes
Today
- With no dedicated shift instructions, shifts are implemented by working around it, multiplying or dividing by a power of two
- SHL and SHR emulated with arithmetic operations cost 35 gas each
- Even for the same calculation, the host takes longer to process it
After EIP-145
- Three instructions, SHL (0x1b), SHR (0x1c), and SAR (0x1d), are added to the EVM
- A single shift costs only 3 gas (verylow tier)
- The host handles the shift directly, which is more efficient
Who is affected
- Contract developer: The gas cost of code that manipulates bits drops from 35 gas per operation to 3 gas.
- Compiler teams: Added support for Solidity and LLL to emit the new instructions.
- Client teams: The three instructions must be implemented and verified with the shared tests (stShift). The cpp-ethereum implementation is linked in the original text.
- Existing contracts: The new instructions have no effect on previously created bytecode.
In depth
SHL (0x1b): left shift
Pops two values off the stack in the order arg1, arg2, and pushes the value of arg2 shifted left by arg1 bits. The result is (arg2 * 2^arg1) mod 2^256. Both the value (arg2) and the shift amount (arg1) are interpreted as unsigned numbers. If arg1 is 256 or greater, the result is 0. This is equivalent to the existing instruction combination PUSH1 2 EXP MUL.
SHR (0x1c): logical right shift
Shifts arg2 right by arg1 bits, filling the vacated high-order bits with 0. The result is floor(arg2 / 2^arg1). Both operands are interpreted as unsigned numbers, and if arg1 is 256 or greater, the result is 0. This is equivalent to PUSH1 2 EXP DIV.
SAR (0x1d): arithmetic right shift
Shifts arg2 right by arg1 bits with sign extension. That is, arg2 is interpreted as a signed number, and if it is negative, the vacated high-order bits are filled with 1. The result is floor(arg2 / 2^arg1). If arg1 is 256 or greater, the result is 0 when arg2 is nonnegative and -1 when it is negative. This is not equivalent to PUSH1 2 EXP SDIV, because the rounding direction differs: SDIV(-1, 2) is 0, but SAR(-1, 1) is -1.
Gas cost: 3 gas, verylow tier
The cost of all three shift instructions is set to 3 gas, the verylow tier. Since implementing SHL and SHR with arithmetic operations previously cost 35 gas each, this is more than ten times cheaper. It is also more efficient for the host to process than a combination of arithmetic operations.
Why the operand order is reversed from arithmetic instructions
It was designed so that the shift amount (arg1) is popped first and the value (arg2) is popped second, since pushing a value already on top of the stack is the more natural usage pattern. As a result, the operand order is reversed compared to most arithmetic instructions.
Compatibility and implementation status
Since the new instructions have no effect on previously created bytecode, there are no backward compatibility issues. The status is settled as Final. The original text links a client implementation (cpp-ethereum), compiler support (Solidity/LLL), and the shared stShift tests in the ethereum/tests repository, and the body includes 11 test cases for SHL, 11 for SHR, and 16 for SAR.