VM: analyze the correctness and semantics of the SIGNEXTEND opcode

[jochem-brouwer]

This particular line of SIGNEXTEND looks extremely fishy. I apparently "sign extend" a value (second item on stack) which also takes some kind of byte length (?) argument (first item on stack), and pops these two values and puts the result of this signextend operation on the stack. But apparently if I want to sign extend 31 bytes (first stack argument), the result is the same as the byte argument (second stack argument).

Compared to Geths code, it looks wrong. See the operation (num is uint256). This is the implementation of uint256 extend: the check here the value is not changed when we have more than 31 bytes, while we don't change the value if it is more than 30 bytes.

To do's:

• [ ] Figure out the exact semantics of SIGNEXTEND
• [ ] Verify that our code is correct and that SIGNEXTEND with 31 bytes is indeed does not change the value and thus puts that on the stack.

CC https://github.com/ethereum/tests/pull/1013

[holgerd77]

it is a no-op

Thanks for this write-up! What does this particular line mean, seems important to understand the whole thing. 😋

[jochem-brouwer]

In this comment I try to describe my understanding of SIGNEXTEND.

SIGNEXTEND is an opcode which takes two arguments: the byte index k and a value val. Value is considered an integer, so not an unsigned integer, and is thus expressed in two's complement. The result of SIGNEXTEND is that the val which is considered k + 1 bytes long, is now extended to a 32 bytes / 256 bits integer (so also in Two's complement).

If this opcode would just consider the input and output as uint, then the operation is easy; just zero out the higher bits. But for integers, this would not take care of the signature of the value. If the value is positive, then the 8k + 7 bit of the value is 0, but if it is 1, it is negative. The higher order bits of the value should copy this value.

Why is k=31 does result in the value not being changed

If k=31 then the bit at bit 255 (note: bits are 0-indexed here) is the signature. However, we want to fill the higher order bits with this value. Since we only have 256 bits in total, there are no higher order bits, so we can just put val on the stack.

Yellow paper:

Stack overflow related question: https://ethereum.stackexchange.com/questions/63062/evm-signextend-opcode-explanation

[holgerd77]

Thanks, that also gives some valuable context. I was just really only referring to the word no-op though. What does this exactly mean?

[jochem-brouwer]

Sorry, I was writing the comment to explain the semantics and it was not a direct reply to your comment.

I should edit, it is not a no-op, it pops the first value from stack and thus does not edit the second (the value).

[holgerd77]

Ok, one more try: what does no-op mean (even if it is not meant here)?

[jochem-brouwer]

Ah right sorry for the misunderstanding. With no-op I mean: this would not change anything to the environment when comparting the environment before running the opcode and after running the opcode. So no changes to memory, stack or storage.

(This would actually never make sense here in the SIGNEXTEND opcode, since it takes 2 items from the stack and puts 1 item on the stack, so the stack is always changed - will edit my comments).

[axic]

It was based on evmone (from around 2019): https://github.com/ethereum/evmone/blob/20bd8f2e3e34660bc0c2d817d169105fc118aba0/lib/evmone/instructions.cpp#L162-L176

[holgerd77]

Seems an associated ethereum/tests test case has been merged, will close.