Ethereum storage implementation at the database level - how is it stored

Question

I have read the yellow paper many times as well as various articles, I suppose if I cannot find the answer here - I will look into the code.

My understanding is that each contract account contains a storage root. and you can retrieve the root from the level db.

But what is the value in the leveldb?

Here are some of my questions:

1. LevelDB is key-value, so if we are able to use the storage root to get storage of a contract, then what is the value?

2. I am going to take a wild guess, that the value is the patrica tree?

3. If 2 is true, then isn't it extremely inefficient any time we want to execute the contract - we have to grab the storage of the entire contract.. ? If a contract has a lot of storage, then its potentially extremely slow to do so?

4. Last question - my understanding that all ERC20 token balance information is stored in the storage, then this means if I ICO to 5 million accounts - this means I now have a huge storage that is extremely slow to retrieve? - Given that the entire contract's storage is retrieved all at once.

Answer 1

Instructions that store and retrieve data are:

    SLOAD: {
        execute:       opSload,
        gasCost:       gasSLoad,
        validateStack: makeStackFunc(1, 1),
        valid:         true,
    },
    SSTORE: {
        execute:       opSstore,
        gasCost:       gasSStore,
        validateStack: makeStackFunc(2, 0),
        valid:         true,
        writes:        true,
    },

And here is how they are coded:

func opSload(pc *uint64, evm *EVM, contract *Contract, memory *Memory, stack *Stack) ([]byte, error) {
    loc := stack.peek()
    val := evm.StateDB.GetState(contract.Address(), common.BigToHash(loc))
    loc.SetBytes(val.Bytes())
    return nil, nil
}

func opSstore(pc *uint64, evm *EVM, contract *Contract, memory *Memory, stack *Stack) ([]byte, error) {
    loc := common.BigToHash(stack.pop())
    val := stack.pop()
    evm.StateDB.SetState(contract.Address(), loc, common.BigToHash(val))

    evm.interpreter.intPool.put(val)
    return nil, nil
}

SetState and GetState are implemented as this:

func (self *StateDB) GetState(addr common.Address, bhash common.Hash) common.Hash {
    stateObject := self.getStateObject(addr)
    if stateObject != nil {
        return stateObject.GetState(self.db, bhash)
    }
    return common.Hash{}
}
func (self *StateDB) SetState(addr common.Address, key, value common.Hash) {
    stateObject := self.GetOrNewStateObject(addr)
    if stateObject != nil {
        stateObject.SetState(self.db, key, value)
    }
}

// SetState updates a value in account storage.
func (self *stateObject) SetState(db Database, key, value common.Hash) {
    self.db.journal.append(storageChange{
        account:  &self.address,
        key:      key,
        prevalue: self.GetState(db, key),
    })
    self.setState(key, value)
}

// GetState returns a value in account storage.
func (self *stateObject) GetState(db Database, key common.Hash) common.Hash {
    value, exists := self.cachedStorage[key]
    if exists {
        return value
    }
    // Load from DB in case it is missing.
    enc, err := self.getTrie(db).TryGet(key[:])
    if err != nil {
        self.setError(err)
        return common.Hash{}
    }
    if len(enc) > 0 {
        _, content, _, err := rlp.Split(enc)
        if err != nil {
            self.setError(err)
        }
        value.SetBytes(content)
    }
    self.cachedStorage[key] = value
    return value
}

Merkle Patricia trie stores this data:

// Account is the Ethereum consensus representation of accounts.
// These objects are stored in the main account trie.
type Account struct {
    Nonce    uint64
    Balance  *big.Int
    Root     common.Hash // merkle root of the storage trie
    CodeHash []byte
}

As you can see the Root common.Hash member of the struct holds the hash of the internal storage of the contract. This means, wherever you update contract's storage , the hash is going to change, and as Account object is part of the entire trie, the change is going to propagate to higher nodes and the StateRoot of the block will change at the end.

So, in short:

1. Contract's storge is modifed only by key->value pairs.
2. Every modification to internal state of the contract implies updating of the whole trie.
3. Even with this design Ethereum is already very inefficient but it was designed to be safe, not fast.