Tests & implementation of CallDataLoad and CodeCopy

[mratsim]

Extracting discussion from https://github.com/status-im/nimbus/pull/59/files#r200313762

CallDataLoad

The current master implementation for calldataload is (from #59):

proc callDataLoad*(computation: var BaseComputation) =
  # Load call data into memory
  let origDataPos = computation.stack.popInt
  if origDataPos >= computation.msg.data.len:
    computation.stack.push(0)
    return

  let
    dataPos = origDataPos.toInt
    dataEndPosition = dataPos + 31

  if dataEndPosition < computation.msg.data.len:
    computation.stack.push(computation.msg.data[dataPos .. dataEndPosition])
  else:
    var bytes: array[32, byte]
    var presentBytes = min(computation.msg.data.len - dataPos, 32)

    if presentBytes > 0:
      copyMem(addr bytes[0], addr computation.msg.data[dataPos], presentBytes)
    else:
      presentBytes = 0

    for i in presentBytes ..< 32: bytes[i] = 0
      computation.stack.push(bytes)

With a potential simpler solution (from #65)

op callDataLoad, inline = false, startPos:
  ## 0x35, Get input data of current environment
  let start = startPos.toInt

  # If the data does not take 32 bytes, pad with zeros
  let endRange = min(computation.msg.data.len - 1, start + 31)
  let padding = start + 31 - endRange
  var value: array[32, byte] # We rely on value being initialized with 0 by default
  value[padding ..< 32] = computation.msg.data.toOpenArray(start, endRange)

  push: value # TODO, with the new implementation we can delete push for seq[byte]

CodeCopy

The current master implementation for codecopy is (from #59):

proc writePaddedResult(mem: var Memory,
                       data: openarray[byte],
                       memPos, dataPos, len: Natural,
                       paddingValue = 0.byte) =
  mem.extend(memPos, len)

  let dataEndPosition = dataPos + len - 1
  if dataEndPosition < data.len:
    mem.write(memPos, data[dataPos .. dataEndPosition])
  else:
    var presentElements = data.len - dataPos
    if presentElements > 0:
      mem.write(memPos, data.toOpenArray(dataPos, data.len - 1))
    else:
      presentElements = 0

    mem.writePaddingBytes(memPos + presentElements,
                          len - presentElements,
                          paddingValue)

proc codeCopy*(computation: var BaseComputation) =
  let (memStartPosition,
       codeStartPosition,
       size) = computation.stack.popInt(3)

  computation.gasMeter.consumeGas(
    computation.gasCosts[CodeCopy].d_handler(size),
    reason="CODECOPY: word gas cost")

  let (memPos, codePos, len) = (memStartPosition.toInt, codeStartPosition.toInt, size.toInt)

  computation.memory.writePaddedResult(computation.code.bytes, memPos, codePos, len)

With a simpler solution (from #65):

op codecopy, inline = false, memStartPos, copyStartPos, size:
  ## 0x39, Copy code running in current environment to memory.

  let (memPos, copyPos, len) = (memStartPos.toInt, copyStartPos.toInt, size.toInt)

  computation.gasMeter.consumeGas(
    computation.gasCosts[CodeCopy].m_handler(memPos, copyPos, len),
    reason="CodeCopy fee")

  computation.memory.extend(memPos, len)

  # If the data does not take 32 bytes, pad with zeros
  let lim = min(computation.code.bytes.len, copyPos + len)
  let padding = copyPos + len - lim
  # Note: when extending, extended memory is zero-ed, we only need to offset with padding value
  computation.memory.write(memPos):
    computation.code.bytes.toOpenArray(copyPos+padding, copyPos+lim)

Reference implementation

Here are the implementations in Py-EVM, Geth and Parity:

Py-EVM is doing something very complex, increasing a program counter in the "CodeStream" type. while Geth, Parity and the Yellow paper are just copying bytes?

• https://github.com/ethereum/py-evm/blob/090b29141d1d80c4b216cfa7ab889115df3c0da0/evm/vm/logic/context.py#L96-L97
• https://github.com/paritytech/parity/blob/98b7c07171cd320f32877dfa5aa528f585dc9a72/ethcore/evm/src/interpreter/mod.rs#L581-L582
• https://github.com/ethereum/go-ethereum/blob/947e0afeb3bce9c52548979daddd1e00aa0d7ba8/core/vm/instructions.go#L478-L479

Concerns

1. The current implementation is complex, with 2 nested ifs, and the proc "writePaddingBytes" that is redundant with memory.extend (which pads with 0 already)

2. The simpler codecopy has an off by one error (which see the simpler calldataload which does not suffer for this)

3. codePos (callDataLoad) and copyPos (codeCopy) can be out of bounds. For copyPos this is handled in memory.write:

proc write*(memory: var Memory, startPos: Natural, value: openarray[byte]) =
  let size = value.len
  if size == 0:
    return
  #echo size
  #echo startPos
  #validateGte(startPos, 0)
  #validateGte(size, 0)
  validateLte(startPos + size, memory.len)
  let index = memory.len
  if memory.len < startPos + size:
    memory.bytes = memory.bytes.concat(repeat(0.byte, memory.len - (startPos + size))) # TODO: better logarithmic scaling?

  for z, b in value:
    memory.bytes[z + startPos] = b

but there is no handling for outofbounds read in codePos.

TODO

• Add test cases to make sure the implementation chosen cover edge cases.
• Simplify the current implementations

cc @zah

[mratsim]

42fd80c should handle the edge cases. Tests needed:

callDataLoad: https://github.com/status-im/nimbus/blob/42fd80c00b1432bcce42f11fb755d46534ad3db9/nimbus/vm/interpreter/opcodes_impl.nim#L233-L248

codeCopy: https://github.com/status-im/nimbus/blob/42fd80c00b1432bcce42f11fb755d46534ad3db9/nimbus/vm/interpreter/opcodes_impl.nim#L278-L296

[mratsim]

It didn't bd17353