EIP-1051: Arithmetic overflow detection for the EVM

EIPs
5

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
6

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
7

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
8

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
9

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
10

You might look at the IELE VM, which has registers that do just keep growing in size. Like the natural numbers.

1 Like
11

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
12

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
13

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
14

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
15

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
16

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
17

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👏

18

@Arachnid I don’t see Wasm in this discussion. I don’t think it provides access to the overflow bit.

19

@gcolvin It doesn’t have it AFAIK, but it’s planned: https://github.com/WebAssembly/design/blob/master/FutureFeatures.md#integer-overflow-detection

20

@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.

21

This may be too late, but I have some toughth on thi EIP wich is one crucial to join security and effiency

I like how signed and unsigned are treated separetely
how you can perform a batch of operations and the flags only need to be checked at the end (with some exception if you mix signed and unsigned operations)

but I also have some remarks:

The ovf flag should trigger in the operations EXP and SHL

an signed sum of a positive and a negative number should not trigger the signed and should trigger the unsigned flag. The specification says “The sovf flag is set whenever the ovf flag is set, and additionally in the following circumstances”

Division by zero, and this include operations div, mod, sdiv, smod, addmodm, mulmod as well; should be treated in the flags

The signed division -(2**255) / -1 should trigger the sovf flag

The flags related to signed multiplication is wrong, it should trigger when the modulo of the ideal multiplication is bigger equal than 2**255

The signed flag should trigger with the SHL operation, this is trickier to define when

22

Hello Renan. At this point I think somebody would need to resurrect this proposal, as we haven’t heard from @Arachnid in a long while. If you want to that would be a good thing.

1 Like
23

What is the besr course of action here? do I make a new proposal or do I update this one?

24

I’ve written this proposal EIP: math checking