🗓️ Week 9

This week, I poured 34 hours into researching, coding, and documenting 1 project, fueled by 3 cups of coffee. I participated in 1 calls to discuss goals, progress, and challenges.

An important feedback I received from Ipsilon is that I missed accounting for memory expansion cost. Much of this week was spent reviewing how expansion works and what can be optimised. This article documents my understanding of memory expansion.

The cost of memory is defined by the equation:

$C_{\mathrm{mem}}(a) \equiv G_{\mathrm{memory}} \cdot a + \left\lfloor \dfrac{a^2}{512} \right\rfloor$

Where $a$ is the words of memory expanded. Memory is expanded in multiples of evm word size of 32-bytes. For example, if a word is written to offset 3 the size of expanded memory is $3+32 = 35 \text{ bytes} \equiv 2 \text{ words}$ (rounded up).

Corresponding geth code:

square := newMemSizeWords * newMemSizeWords
linCoef := newMemSizeWords * params.MemoryGas
quadCoef := square / params.QuadCoeffDiv
newTotalFee := linCoef + quadCoef
 
 
fee := newTotalFee - mem.lastGasCost
mem.lastGasCost = newTotalFee
 
return fee, nil

Exponential dynamic cost

The last term of the equation ensures that cost of memory consumption increases exponentially. This term is equals 1 for $a=\sqrt{512} \equiv 22.627$ . This equals 724 bytes. So for the first 724 bytes the cost increases linearly and exponentially beyond that. The chart below contrast linear (blue) cost vs exponential cost (red).

Exponential cost of memory

An example allocation of 10MB memory illustrates the cost difference caused by this factor:

	Linear pricing	Exponential pricing
Gas	983040	210698240
Current gas cost at 2gwei per gas	$5.28	$1131.72

The EVM transition tool

The geth state transition tool (t8n) tool is a cli interface to geth's EVM module.

Its configurations, state, and trace logs are json files which are easy to inspect. I used the t8n tool to confirm the gas cost of 10M memory usage.

//env.json
{
  "currentCoinbase": "0x0000000000000000000000000000000000000001",
  "currentDifficulty": "0x020000",
  "currentGasLimit": "0xc900000",
  "currentNumber": "0x01",
  "currentTimestamp": "0x03e8",
  "previousHash": "0xe729de3fec21e30bea3d56adb01ed14bc107273c2775f9355afb10f594a10d9e",
  "currentBaseFee": 0,
  "blockHashes": {
    "0": "0xe729de3fec21e30bea3d56adb01ed14bc107273c2775f9355afb10f594a10d9e"
  }
}

Pre state:

// alloc.json
{
  "0x8a8eafb1cf62bfbeb1741769dae1a9dd47996192": {
    "code": "0x6001629fffe052", // <- Writes to offset `0x9fffe0`
    "balance": "0x0"
  },
  "0xd3e466177c151a06ffb427782f95bc49a4de5001": {
    "balance": "0xca00000"
  }
}

Post state:

{
  "0x0000000000000000000000000000000000000001": {
    "balance": "0xc8f5211"
  },
  "0x8a8eafb1cf62bfbeb1741769dae1a9dd47996192": {
    "code": "0x6001629fffe052",
    "balance": "0x1"
  },
  "0xd3e466177c151a06ffb427782f95bc49a4de5001": {
    "balance": "0x10adee",
    "nonce": "0x1"
  }
}

Trace:

{"pc":0,"op":96,"gas":"0xc8fadf8","gasCost":"0x3","memSize":0,"stack":[],"depth":1,"refund":0,"opName":"PUSH1"}
{"pc":2,"op":98,"gas":"0xc8fadf5","gasCost":"0x3","memSize":0,"stack":["0x1"],"depth":1,"refund":0,"opName":"PUSH3"}
{"pc":6,"op":82,"gas":"0xc8fadf2","gasCost":"0xc8f0003","memSize":0,"stack":["0x1","0x9fffe0"],"depth":1,"refund":0,"opName":"MSTORE"}
{"pc":7,"op":0,"gas":"0xadef","gasCost":"0x0","memSize":10485760,"stack":[],"depth":1,"refund":0,"opName":"STOP"}
{"output":"","gasUsed":"0xc8f0009"}

Prima facie, $1K for 10M of EVM memory is prohibitively expensive.

Next steps

Benchmark the computational cost of expansion.
I'd like to know how memory is implemented in geth, and how it works under the hood.

📞 Calls

Aug 5, 2024 - EPF Standup #8