Skip to main content

State

To truly understand how State works, you must understand some basic Ethereum concepts.

We highly recommend reading the State in Ethereum guide.

Overview

Now that we've familiarized ourselves with basic Ethereum concepts, the next overview should be easy.

We mentioned that the World state trie has all the Ethereum accounts that exist.
These accounts are the leaves of the Merkle trie. Each leaf has encoded Account State information.

This enables the Polygon Edge to get a specific Merkle trie, for a specific point in time.
For example, we can get the hash of the state at block 10.

The Merkle trie, at any point in time, is called a Snapshot.

We can have Snapshots for the state trie, or for the storage trie - they are basically the same.
The only difference is in what the leaves represent:

  • In the case of the storage trie, the leaves contain an arbitrary state, which we cannot process or know what's in there
  • In the case of the state trie, the leaves represent accounts
"state/state.go
type State interface {
// Gets a snapshot for a specific hash
NewSnapshotAt(types.Hash) (Snapshot, error)

// Gets the latest snapshot
NewSnapshot() Snapshot

// Gets the codeHash
GetCode(hash types.Hash) ([]byte, bool)
}

The Snapshot interface is defined as such:

"state/state.go
type Snapshot interface {
// Gets a specific value for a leaf
Get(k []byte) ([]byte, bool)

// Commits new information
Commit(objs []*Object) (Snapshot, []byte)
}

The information that can be committed is defined by the Object struct:

"state/state.go
// Object is the serialization of the radix object
type Object struct {
Address types.Address
CodeHash types.Hash
Balance *big.Int
Root types.Hash
Nonce uint64
Deleted bool

DirtyCode bool
Code []byte

Storage []*StorageObject
}

The implementation for the Merkle trie is in the state/immutable-trie folder.
state/immutable-trie/state.go implements the State interface.

state/immutable-trie/trie.go is the main Merkle trie object. It represents an optimized version of the Merkle trie, which reuses as much memory as possible.

Executor

state/executor.go includes all the information needed for the Polygon Edge to decide how a block changes the current state. The implementation of ProcessBlock is located here.

The apply method does the actual state transition. The executor calls the EVM.

state/executor.go
func (t *Transition) apply(msg *types.Transaction) ([]byte, uint64, bool, error) {
// check if there is enough gas in the pool
if err := t.subGasPool(msg.Gas); err != nil {
return nil, 0, false, err
}

txn := t.state
s := txn.Snapshot()

gas, err := t.preCheck(msg)
if err != nil {
return nil, 0, false, err
}
if gas > msg.Gas {
return nil, 0, false, errorVMOutOfGas
}

gasPrice := new(big.Int).SetBytes(msg.GetGasPrice())
value := new(big.Int).SetBytes(msg.Value)

// Set the specific transaction fields in the context
t.ctx.GasPrice = types.BytesToHash(msg.GetGasPrice())
t.ctx.Origin = msg.From

var subErr error
var gasLeft uint64
var returnValue []byte

if msg.IsContractCreation() {
_, gasLeft, subErr = t.Create2(msg.From, msg.Input, value, gas)
} else {
txn.IncrNonce(msg.From)
returnValue, gasLeft, subErr = t.Call2(msg.From, *msg.To, msg.Input, value, gas)
}

if subErr != nil {
if subErr == runtime.ErrNotEnoughFunds {
txn.RevertToSnapshot(s)
return nil, 0, false, subErr
}
}

gasUsed := msg.Gas - gasLeft
refund := gasUsed / 2
if refund > txn.GetRefund() {
refund = txn.GetRefund()
}

gasLeft += refund
gasUsed -= refund

// refund the sender
remaining := new(big.Int).Mul(new(big.Int).SetUint64(gasLeft), gasPrice)
txn.AddBalance(msg.From, remaining)

// pay the coinbase
coinbaseFee := new(big.Int).Mul(new(big.Int).SetUint64(gasUsed), gasPrice)
txn.AddBalance(t.ctx.Coinbase, coinbaseFee)

// return gas to the pool
t.addGasPool(gasLeft)

return returnValue, gasUsed, subErr != nil, nil
}

Runtime

When a state transition is executed, the main module that executes the state transition is the EVM (located in state/runtime/evm).

The dispatch table does a match between the opcode and the instruction.

state/runtime/evm/dispatch_table.go
func init() {
// unsigned arithmetic operations
register(STOP, handler{opStop, 0, 0})
register(ADD, handler{opAdd, 2, 3})
register(SUB, handler{opSub, 2, 3})
register(MUL, handler{opMul, 2, 5})
register(DIV, handler{opDiv, 2, 5})
register(SDIV, handler{opSDiv, 2, 5})
register(MOD, handler{opMod, 2, 5})
register(SMOD, handler{opSMod, 2, 5})
register(EXP, handler{opExp, 2, 10})

...

// jumps
register(JUMP, handler{opJump, 1, 8})
register(JUMPI, handler{opJumpi, 2, 10})
register(JUMPDEST, handler{opJumpDest, 0, 1})
}

The core logic that powers the EVM is the Run loop.

This is the main entry point for the EVM. It does a loop and checks the current opcode, fetches the instruction, checks if it can be executed, consumes gas and executes the instruction until it either fails or stops.

state/runtime/evm/state.go

// Run executes the virtual machine
func (c *state) Run() ([]byte, error) {
var vmerr error

codeSize := len(c.code)

for !c.stop {
if c.ip >= codeSize {
c.halt()
break
}

op := OpCode(c.code[c.ip])

inst := dispatchTable[op]

if inst.inst == nil {
c.exit(errOpCodeNotFound)
break
}

// check if the depth of the stack is enough for the instruction
if c.sp < inst.stack {
c.exit(errStackUnderflow)
break
}

// consume the gas of the instruction
if !c.consumeGas(inst.gas) {
c.exit(errOutOfGas)
break
}

// execute the instruction
inst.inst(c)

// check if stack size exceeds the max size
if c.sp > stackSize {
c.exit(errStackOverflow)
break
}

c.ip++
}

if err := c.err; err != nil {
vmerr = err
}

return c.ret, vmerr
}