I’ve written up an EIP for overflow detection in the EVM, here. Feedback appreciated!
3 Likes
Thanks for putting this together, Nick.
One option would be to provide an opcode that enables overflow protection, causing a throw or revert if an overflow happens. However, this limits the manner in which overflows can be handled.
Are you thinking that the EVM can provide this low level detection, and then solidity or other languages can add default checks in the future? Ideally, newly created/compiled smart contracts should automatically throw on overflow. If developers really want to handle it differently, the language can provide a switch or annotation to prevent the compiler from generating the default checks.
1 Like
The EVM just provides a flag, and it’s up to higher level languages to decide how to utilise it. For the most part in languages like Solidity, you could check the overflow flag once per basic block.
1 Like
Support the idea, but
- Why the nonstandard naming? ‘Overflow’ for the carry flag and ‘signed overflow’ for the overflow flag. It’s a bit confusing.
- Instead of two separate flag registers, one FLAGS register (like on a cpu) with bit flags allows easier extensibility and doesn’t use new opcodes for every new flag. On x86 pushf to push the flags register and popf to set it are used.
- Given the flags register, perhaps zero and sign flag as well? They already exists on every cpu.
Using the flags register makes it easily possible to implement the ‘trap on overflow/carry’ functionality, by adding two new flags that determine throwing when they are set + flag conditional jumps which would reduce code size and gas use considerably, see:
Instead of simply reverting, the address of an arbitrary error handler could be set in the flags register (second dword?), jumped to after the flag is set with the offending instruction’s address on the stack.
2 Likes
Thanks for the feedback!
We don’t currently have any opcodes that can benefit from a ‘carry’ flag, and I thought using that terminology might imply we do. I’m happy to change it back, though.
I’m on the fence about this. It would reduce opcodes, but it would also require more work to check the register each time.
I don’t think those would actually be any easier to check and branch on than at present, would they? Without it, you can branch on 0 with DUP1 NOT JUMPI, without it it’d be FLAGS PUSH (mask) JUMPI.
I’d be concerned about adding complexity to the VM with modal flags like this.
1 Like
If any way to detect the carry flag exist it can be used to cheaply, compared to comparisons, implement an arbitrary precision arithmetic, by adding/subtracting the carry flag. On x86 there are even specialized instructions that do this, adc (add with carry) and sbw (subtract with borrow).
Fair enough. Pushf could have a byte number that means a bit to be pushed, with one special value of 0xFF that pushes the entire register. Ditto for popf (first argument the index, second the value). This combines the simplicity of one-case opcodes with extensibility.
I don’t think those would actually be any easier to check and branch on than at present, would they? Without it, you can branch on 0 with DUP1 NOT JUMPI, without it it’d be FLAGS PUSH (mask) JUMPI.
True for the zero flag without cmp and flag-conditional jumps, but not true for the sign one.
Not that much, It can be implemented as one if that pushes the address onto the stack + changes the instruction pointer to the trap handler, leaving the rest to the normal execution loop.
More generally, performance requires specialization. Complex instructions, eg. for text parsing are still being added into cpus. The RISC approach is dead.
There’s also the adoption and safety aspect. On the vm side the operation is one check each time the overflow/carry flag is set, but reimplementing the behavior in the compiler requires changing the code generation for each arithmetic instruction. Much more work and more room for errors. Setting a trap flag at the beginning is trivial to add in comparison. For these reasons I think VM is the best abstraction level to tackle the overflow problem.
That’s a bit offtopic, but given the performance characteristics of EVM the CISC-like approach would imo yield much higher benefits than it does in physical cpus. Like the solidity method selector: all these pushes and comparisons at the beginning of almost every contract execution could be replaced by a switch instruction that jumps according to an array specified directly in code, additionally switch-like ifs in code could be optimized that way by a compiler. A small advantage multiplied by billions of executions.
1 Like
One problem here is implementation difficulty. Some libraries support checking directly, others don’t. If they don’t every specified operation will be slowed down by an explicit comparison. I’d wager the libraries that support checking are in the minority (even in C++) so I’d as soon let the code that cares about overflow handle it explicitly.
2 Likes
Fair enough - though this probably also depends on it being available as a separate bit for efficiency, no?
Reasonable point. What do you see as the pros and cons of a trap handler vs a flag, then?
To be clear, either approach would require compiler changes. Solidity would have to allow you to specify when overflow is and isn’t wanted, and either check the flag or set and clear the trap handler.
Surely capturing overflow in implementations isn’t that hard? The underlying hardware already supports it.
1 Like
The EVM’s 256-bit registers are emulated using available libraries for arbitrary-precision arithmetic. The hardware is far away. Most algorithms don’t overflow, they just produce a bigger result. Try implementing your proposal in the Go VM and you may see the difficulty.
1 Like
You might look at the IELE VM, which has registers that do just keep growing in size. Like the natural numbers.
1 Like
Why slowed down? The cost of simple comparison on data already in L1 is effectively zero. The cost of manual checking in safemath should be more expensive by orders of magnitude. Go’s compiler optimization would have to be horrible for a comparison to be noticeable in any way.
Go implements big math in assembly.
I don’t know Go much, but according to this calling arbitrary native code in Go is easy and can offer big performance improvements:
name time/op
GetBucket-8 17.4ns ± 2%
GetBucketNoInline-8 17.4ns ± 2%
GetBucketASM-8 12.8ns ± 1%
in any case, I don’t think it would be possible to observe the difference between a comparison in go (assuming reasonable optimizing compiler) vs checking carry/overflow in assembly/C/C++, but in the case that it is, external code in C/C++, optionally with intrinsics or inline asm could be used.
Ah, I wasn’t clear enough - I meant a flag AND an option to trap on it. For example, for a FLAGS register defined in the following way:
struct FLAGS {
unsigned short int flags;
unsigned short int trapMask;
unsigned int trapHandler; //defaults to revert?
}
with flags’ bits defined as:
carryFlag | overFlowFlag | signFlag | zeroFlag | reserved | …
trapMask as a bitmask for traps:
carryFlagTrap | overflowFlagTrap | signFlag | zeroFlag | reserved | …
ie. when carryFlagTrap bit is set trap on setting carryFlag.
After flags are set in EVM it’s enough to:
if(FLAGS.flags&FLAGS.trapMask) {
pushOnEvmStack(evmEip);
evmEip = FLAGS.trapHandler;
}
//end current instruction
So this way, there are both flags, optional traps and everything is easily extensible.
I guess in this construction arguments 0-31 for pushf/popf could refer to flags’ and mask’s bits, 255 for the whole register, 254 for flags, 253 for trapMask and 252 for trapHandler. Perhaps 251 for trapMask with trapHandler at once, as these two fields are likely to be set together.
To be clear, either approach would require compiler changes. Solidity would have to allow you to specify when overflow is and isn’t wanted, and either check the flag or set and clear the trap handler.
Well yes, but enabling trapping on overflow could be implemented as a one dumb pushf added at the beginning, pure flags require changes in code generation for arithmetic expressions. A simple pushf could in principle be added manually after compiling, or as inline asm, with a compiler that doesn’t know traps exist.
1 Like
Fair enough. I’m concerned this pattern, while common in MCUs, isn’t really idiomatic for the EVM, though. It introduces several new concepts that haven’t previously featured.
1 Like
Coming from Rust, integer overflows always panic by default. Doing any sort of math that requires overflowing as a feature is such a niche use case, we handle it with a specialized method:
// Panic on runtime
let x = u32::max_value() + 1;
// No panic, x = 0
let x = u32::max_value().wrapping_add(1);
I realize that making all arithmetic overflows be treated as errors by default would be a breaking change for Solidity, but I really cannot think of a reason why it should not be a default.
1 Like
I don’t know if I’m confused or the discussion is, but I don’t think the behavior of native ints is the issue here, or the fact that some big-integer libraries are written in assembly. The issue is how to implement this in VMs that mostly are not written in assembly, and shouldn’t need to be. Not even C provides access to the carry bit, and neither do most big-integer libraries. So the only way to test for overflow in most cases is to not let the result overflow, then test whether it’s too big. I’m no longer sure whether this is a big performance hit, but measurements would good to have.
As for making overflows throw, that would break not just Solidity, but every EVM program that counts on the EVM having unsigned values that don’t overflow. Better that Solidity use whatever mechanism is provided to detect overflow to introduce a new type that traps.
2 Likes
I don’t know about Geth or other implementations, but the big integer primitives in Parity (implemented both in inline assembly and pure rust depending on compilation target) already return a boolean for overflows:
I’d have to look deeper into how signed ops are performed to see if it’s realistic to get SOVF flag on top, but right now it appears to me that the only performance cost for implementing this EIP in Parity EVM is just the cost of storing the flag instead of just throwing it away.
I was talking purely about changing the behavior on Solidity side by using the new opcodes, so it would be a breaking change for Solidity and hence require a semver bump to 0.5.x. No breaking changes to EVM.
3 Likes
Just to expand on this, I looked at the actual EVM interpreter and can confirm that all math is already checking for overflows and throws the flag away: in stack.push(a.overflowing_add(b).0); any overflowing_X operation returns a tuple of (result, overflow_flag), hence .0 just grabs the result.
Since there were concerns raised during the dev call about the cost of multiplication in particular, I looked at how multiplication is done internally:
- The pure Rust implementation uses 512bit (8 limbs) on stack which then checks if any of the top half of the integer is non-zero.
- The optimized Assembly code (x86_64 only) on the other hand uses only 5 registers for result (4 limbs in the array and separate register for overflow).
I also took the liberty of looking at how Geth handles things, apologies in advance if I’m missing anything here and please correct me if I’m wrong. It appears to me that all EVM math stuff is handled by arbitrary precision big.Int from math/big that gets it’s results truncated with U256 (which just uses a binary and operation with 2^256-1), so while it doesn’t return an overflow flag, it already does the expensive part of performing the multiplication with as many extra limbs as necessary, and getting the flag is just a single Cmp away. The library does expose access to limbs if a full Cmp would be excessive.
TL;DR: Both Geth and Parity already do all the heavy lifting on math that is required to extract the overflow flag, I reckon the overhead of getting and storing the flag relatively speaking should be trivial, and can be well optimized with fixed-precision libraries if benchmarks disagree.
@Arachnid: one thing that’s still not clear for me is the necessity of SOVF, it’s not mentioned in the rationale.
2 Likes
I’m new to this well I’ve been trying to take the plunge into something New but not had the confidence to be fully committed for nearly two years and I’m struggling to understand reading is not a strong point but I’m getting a lot of practice and am able to make more sense of the sites thanks to all of you that replied to this 3 Detailed discussion s which each had valid points and different problems solved this has really helped with my knowledge and understanding need more posts like these👏
@Arachnid I don’t see Wasm in this discussion. I don’t think it provides access to the overflow bit.
@gcolvin It doesn’t have it AFAIK, but it’s planned: https://github.com/WebAssembly/design/blob/master/FutureFeatures.md#integer-overflow-detection
@Arachnid yes - why the non-standard names? And perhaps, more descriptive names e.g. ISCARRY and ISOVERFLOW to go with the existing ISZERO
See The CARRY flag and OVERFLOW flag in binary arithmetic
for a detailed discussion of when to set and how to use these flags.