diff options
| -rw-r--r-- | light/odr.go | 98 | ||||
| -rw-r--r-- | light/state.go | 275 | ||||
| -rw-r--r-- | light/state_object.go | 267 | ||||
| -rw-r--r-- | light/state_test.go | 269 | ||||
| -rw-r--r-- | light/trie.go | 123 | ||||
| -rw-r--r-- | trie/encoding.go | 21 | ||||
| -rw-r--r-- | trie/encoding_test.go | 6 | ||||
| -rw-r--r-- | trie/errors.go | 18 | ||||
| -rw-r--r-- | trie/proof.go | 24 | ||||
| -rw-r--r-- | trie/trie.go | 5 |
10 files changed, 1091 insertions, 15 deletions
diff --git a/light/odr.go b/light/odr.go new file mode 100644 index 000000000..5ed4f2325 --- /dev/null +++ b/light/odr.go @@ -0,0 +1,98 @@ +// Copyright 2015 The go-ethereum Authors +// This file is part of the go-ethereum library. +// +// The go-ethereum library is free software: you can redistribute it and/or modify +// it under the terms of the GNU Lesser General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. +// +// The go-ethereum library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>. + +// Package light implements on-demand retrieval capable state and chain objects +// for the Ethereum Light Client. +package light + +import ( + "github.com/ethereum/go-ethereum/common" + "github.com/ethereum/go-ethereum/crypto" + "github.com/ethereum/go-ethereum/ethdb" + "github.com/ethereum/go-ethereum/rlp" + "golang.org/x/net/context" +) + +// OdrBackend is an interface to a backend service that handles odr retrievals +type OdrBackend interface { + Database() ethdb.Database + Retrieve(ctx context.Context, req OdrRequest) error +} + +// OdrRequest is an interface for retrieval requests +type OdrRequest interface { + StoreResult(db ethdb.Database) +} + +// TrieRequest is the ODR request type for state/storage trie entries +type TrieRequest struct { + OdrRequest + root common.Hash + key []byte + proof []rlp.RawValue +} + +// StoreResult stores the retrieved data in local database +func (req *TrieRequest) StoreResult(db ethdb.Database) { + storeProof(db, req.proof) +} + +// storeProof stores the new trie nodes obtained from a merkle proof in the database +func storeProof(db ethdb.Database, proof []rlp.RawValue) { + for _, buf := range proof { + hash := crypto.Sha3(buf) + val, _ := db.Get(hash) + if val == nil { + db.Put(hash, buf) + } + } +} + +// NodeDataRequest is the ODR request type for node data (used for retrieving contract code) +type NodeDataRequest struct { + OdrRequest + hash common.Hash + data []byte +} + +// GetData returns the retrieved node data after a successful request +func (req *NodeDataRequest) GetData() []byte { + return req.data +} + +// StoreResult stores the retrieved data in local database +func (req *NodeDataRequest) StoreResult(db ethdb.Database) { + db.Put(req.hash[:], req.GetData()) +} + +var sha3_nil = crypto.Sha3Hash(nil) + +// retrieveNodeData tries to retrieve node data with the given hash from the network +func retrieveNodeData(ctx context.Context, odr OdrBackend, hash common.Hash) ([]byte, error) { + if hash == sha3_nil { + return nil, nil + } + res, _ := odr.Database().Get(hash[:]) + if res != nil { + return res, nil + } + r := &NodeDataRequest{hash: hash} + if err := odr.Retrieve(ctx, r); err != nil { + return nil, err + } else { + return r.GetData(), nil + } +} diff --git a/light/state.go b/light/state.go new file mode 100644 index 000000000..e18f9cdc5 --- /dev/null +++ b/light/state.go @@ -0,0 +1,275 @@ +// Copyright 2015 The go-ethereum Authors +// This file is part of the go-ethereum library. +// +// The go-ethereum library is free software: you can redistribute it and/or modify +// it under the terms of the GNU Lesser General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. +// +// The go-ethereum library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>. + +package light + +import ( + "math/big" + + "github.com/ethereum/go-ethereum/common" + "github.com/ethereum/go-ethereum/logger" + "github.com/ethereum/go-ethereum/logger/glog" + "golang.org/x/net/context" +) + +// StartingNonce determines the default nonce when new accounts are being created. +var StartingNonce uint64 + +// LightState is a memory representation of a state. +// This version is ODR capable, caching only the already accessed part of the +// state, retrieving unknown parts on-demand from the ODR backend. Changes are +// never stored in the local database, only in the memory objects. +type LightState struct { + odr OdrBackend + trie *LightTrie + + stateObjects map[string]*StateObject +} + +// NewLightState creates a new LightState with the specified root. +// Note that the creation of a light state is always successful, even if the +// root is non-existent. In that case, ODR retrieval will always be unsuccessful +// and every operation will return with an error or wait for the context to be +// cancelled. +func NewLightState(root common.Hash, odr OdrBackend) *LightState { + tr := NewLightTrie(root, odr, true) + return &LightState{ + odr: odr, + trie: tr, + stateObjects: make(map[string]*StateObject), + } +} + +// HasAccount returns true if an account exists at the given address +func (self *LightState) HasAccount(ctx context.Context, addr common.Address) (bool, error) { + so, err := self.GetStateObject(ctx, addr) + return so != nil, err +} + +// GetBalance retrieves the balance from the given address or 0 if the account does +// not exist +func (self *LightState) GetBalance(ctx context.Context, addr common.Address) (*big.Int, error) { + stateObject, err := self.GetStateObject(ctx, addr) + if err != nil { + return common.Big0, err + } + if stateObject != nil { + return stateObject.balance, nil + } + + return common.Big0, nil +} + +// GetNonce returns the nonce at the given address or 0 if the account does +// not exist +func (self *LightState) GetNonce(ctx context.Context, addr common.Address) (uint64, error) { + stateObject, err := self.GetStateObject(ctx, addr) + if err != nil { + return 0, err + } + if stateObject != nil { + return stateObject.nonce, nil + } + return 0, nil +} + +// GetCode returns the contract code at the given address or nil if the account +// does not exist +func (self *LightState) GetCode(ctx context.Context, addr common.Address) ([]byte, error) { + stateObject, err := self.GetStateObject(ctx, addr) + if err != nil { + return nil, err + } + if stateObject != nil { + return stateObject.code, nil + } + return nil, nil +} + +// GetState returns the contract storage value at storage address b from the +// contract address a or common.Hash{} if the account does not exist +func (self *LightState) GetState(ctx context.Context, a common.Address, b common.Hash) (common.Hash, error) { + stateObject, err := self.GetStateObject(ctx, a) + if err == nil && stateObject != nil { + return stateObject.GetState(ctx, b) + } + return common.Hash{}, err +} + +// IsDeleted returns true if the given account has been marked for deletion +// or false if the account does not exist +func (self *LightState) IsDeleted(ctx context.Context, addr common.Address) (bool, error) { + stateObject, err := self.GetStateObject(ctx, addr) + if err == nil && stateObject != nil { + return stateObject.remove, nil + } + return false, err +} + +/* + * SETTERS + */ + +// AddBalance adds the given amount to the balance of the specified account +func (self *LightState) AddBalance(ctx context.Context, addr common.Address, amount *big.Int) error { + stateObject, err := self.GetOrNewStateObject(ctx, addr) + if err == nil && stateObject != nil { + stateObject.AddBalance(amount) + } + return err +} + +// SetNonce sets the nonce of the specified account +func (self *LightState) SetNonce(ctx context.Context, addr common.Address, nonce uint64) error { + stateObject, err := self.GetOrNewStateObject(ctx, addr) + if err == nil && stateObject != nil { + stateObject.SetNonce(nonce) + } + return err +} + +// SetCode sets the contract code at the specified account +func (self *LightState) SetCode(ctx context.Context, addr common.Address, code []byte) error { + stateObject, err := self.GetOrNewStateObject(ctx, addr) + if err == nil && stateObject != nil { + stateObject.SetCode(code) + } + return err +} + +// SetState sets the storage value at storage address key of the account addr +func (self *LightState) SetState(ctx context.Context, addr common.Address, key common.Hash, value common.Hash) error { + stateObject, err := self.GetOrNewStateObject(ctx, addr) + if err == nil && stateObject != nil { + stateObject.SetState(key, value) + } + return err +} + +// Delete marks an account to be removed and clears its balance +func (self *LightState) Delete(ctx context.Context, addr common.Address) (bool, error) { + stateObject, err := self.GetOrNewStateObject(ctx, addr) + if err == nil && stateObject != nil { + stateObject.MarkForDeletion() + stateObject.balance = new(big.Int) + + return true, nil + } + + return false, err +} + +// +// Get, set, new state object methods +// + +// GetStateObject returns the state object of the given account or nil if the +// account does not exist +func (self *LightState) GetStateObject(ctx context.Context, addr common.Address) (stateObject *StateObject, err error) { + stateObject = self.stateObjects[addr.Str()] + if stateObject != nil { + if stateObject.deleted { + stateObject = nil + } + return stateObject, nil + } + data, err := self.trie.Get(ctx, addr[:]) + if err != nil { + return nil, err + } + if len(data) == 0 { + return nil, nil + } + + stateObject, err = DecodeObject(ctx, addr, self.odr, []byte(data)) + if err != nil { + return nil, err + } + + self.SetStateObject(stateObject) + + return stateObject, nil +} + +// SetStateObject sets the state object of the given account +func (self *LightState) SetStateObject(object *StateObject) { + self.stateObjects[object.Address().Str()] = object +} + +// GetOrNewStateObject returns the state object of the given account or creates a +// new one if the account does not exist +func (self *LightState) GetOrNewStateObject(ctx context.Context, addr common.Address) (*StateObject, error) { + stateObject, err := self.GetStateObject(ctx, addr) + if err == nil && (stateObject == nil || stateObject.deleted) { + stateObject, err = self.CreateStateObject(ctx, addr) + } + return stateObject, err +} + +// newStateObject creates a state object whether it exists in the state or not +func (self *LightState) newStateObject(addr common.Address) *StateObject { + if glog.V(logger.Core) { + glog.Infof("(+) %x\n", addr) + } + + stateObject := NewStateObject(addr, self.odr) + stateObject.SetNonce(StartingNonce) + self.stateObjects[addr.Str()] = stateObject + + return stateObject +} + +// CreateStateObject creates creates a new state object and takes ownership. +// This is different from "NewStateObject" +func (self *LightState) CreateStateObject(ctx context.Context, addr common.Address) (*StateObject, error) { + // Get previous (if any) + so, err := self.GetStateObject(ctx, addr) + if err != nil { + return nil, err + } + // Create a new one + newSo := self.newStateObject(addr) + + // If it existed set the balance to the new account + if so != nil { + newSo.balance = so.balance + } + + return newSo, nil +} + +// +// Setting, copying of the state methods +// + +// Copy creates a copy of the state +func (self *LightState) Copy() *LightState { + // ignore error - we assume state-to-be-copied always exists + state := NewLightState(common.Hash{}, self.odr) + state.trie = self.trie + for k, stateObject := range self.stateObjects { + state.stateObjects[k] = stateObject.Copy() + } + + return state +} + +// Set copies the contents of the given state onto this state, overwriting +// its contents +func (self *LightState) Set(state *LightState) { + self.trie = state.trie + self.stateObjects = state.stateObjects +} diff --git a/light/state_object.go b/light/state_object.go new file mode 100644 index 000000000..7660c3883 --- /dev/null +++ b/light/state_object.go @@ -0,0 +1,267 @@ +// Copyright 2014 The go-ethereum Authors +// This file is part of the go-ethereum library. +// +// The go-ethereum library is free software: you can redistribute it and/or modify +// it under the terms of the GNU Lesser General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. +// +// The go-ethereum library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>. + +package light + +import ( + "bytes" + "fmt" + "math/big" + + "github.com/ethereum/go-ethereum/common" + "github.com/ethereum/go-ethereum/crypto" + "github.com/ethereum/go-ethereum/logger" + "github.com/ethereum/go-ethereum/logger/glog" + "github.com/ethereum/go-ethereum/rlp" + "golang.org/x/net/context" +) + +var emptyCodeHash = crypto.Sha3(nil) + +// Code represents a contract code in binary form +type Code []byte + +// String returns a string representation of the code +func (self Code) String() string { + return string(self) //strings.Join(Disassemble(self), " ") +} + +// Storage is a memory map cache of a contract storage +type Storage map[string]common.Hash + +// String returns a string representation of the storage cache +func (self Storage) String() (str string) { + for key, value := range self { + str += fmt.Sprintf("%X : %X\n", key, value) + } + + return +} + +// Copy copies the contents of a storage cache +func (self Storage) Copy() Storage { + cpy := make(Storage) + for key, value := range self { + cpy[key] = value + } + + return cpy +} + +// StateObject is a memory representation of an account or contract and its storage. +// This version is ODR capable, caching only the already accessed part of the +// storage, retrieving unknown parts on-demand from the ODR backend. Changes are +// never stored in the local database, only in the memory objects. +type StateObject struct { + odr OdrBackend + trie *LightTrie + + // Address belonging to this account + address common.Address + // The balance of the account + balance *big.Int + // The nonce of the account + nonce uint64 + // The code hash if code is present (i.e. a contract) + codeHash []byte + // The code for this account + code Code + // Temporarily initialisation code + initCode Code + // Cached storage (flushed when updated) + storage Storage + + // Mark for deletion + // When an object is marked for deletion it will be delete from the trie + // during the "update" phase of the state transition + remove bool + deleted bool + dirty bool +} + +// NewStateObject creates a new StateObject of the specified account address +func NewStateObject(address common.Address, odr OdrBackend) *StateObject { + object := &StateObject{ + odr: odr, + address: address, + balance: new(big.Int), + dirty: true, + codeHash: emptyCodeHash, + storage: make(Storage), + } + object.trie = NewLightTrie(common.Hash{}, odr, true) + return object +} + +// MarkForDeletion marks an account to be removed +func (self *StateObject) MarkForDeletion() { + self.remove = true + self.dirty = true + + if glog.V(logger.Core) { + glog.Infof("%x: #%d %v X\n", self.Address(), self.nonce, self.balance) + } +} + +// getAddr gets the storage value at the given address from the trie +func (c *StateObject) getAddr(ctx context.Context, addr common.Hash) (common.Hash, error) { + var ret []byte + val, err := c.trie.Get(ctx, addr[:]) + if err != nil { + return common.Hash{}, err + } + rlp.DecodeBytes(val, &ret) + return common.BytesToHash(ret), nil +} + +// Storage returns the storage cache object of the account +func (self *StateObject) Storage() Storage { + return self.storage +} + +// GetState returns the storage value at the given address from either the cache +// or the trie +func (self *StateObject) GetState(ctx context.Context, key common.Hash) (common.Hash, error) { + strkey := key.Str() + value, exists := self.storage[strkey] + if !exists { + var err error + value, err = self.getAddr(ctx, key) + if err != nil { + return common.Hash{}, err + } + if (value != common.Hash{}) { + self.storage[strkey] = value + } + } + + return value, nil +} + +// SetState sets the storage value at the given address +func (self *StateObject) SetState(k, value common.Hash) { + self.storage[k.Str()] = value + self.dirty = true +} + +// AddBalance adds the given amount to the account balance +func (c *StateObject) AddBalance(amount *big.Int) { + c.SetBalance(new(big.Int).Add(c.balance, amount)) + + if glog.V(logger.Core) { + glog.Infof("%x: #%d %v (+ %v)\n", c.Address(), c.nonce, c.balance, amount) + } +} + +// SubBalance subtracts the given amount from the account balance +func (c *StateObject) SubBalance(amount *big.Int) { + c.SetBalance(new(big.Int).Sub(c.balance, amount)) + + if glog.V(logger.Core) { + glog.Infof("%x: #%d %v (- %v)\n", c.Address(), c.nonce, c.balance, amount) + } +} + +// SetBalance sets the account balance to the given amount +func (c *StateObject) SetBalance(amount *big.Int) { + c.balance = amount + c.dirty = true +} + +// Copy creates a copy of the state object +func (self *StateObject) Copy() *StateObject { + stateObject := NewStateObject(self.Address(), self.odr) + stateObject.balance.Set(self.balance) + stateObject.codeHash = common.CopyBytes(self.codeHash) + stateObject.nonce = self.nonce + stateObject.trie = self.trie + stateObject.code = common.CopyBytes(self.code) + stateObject.initCode = common.CopyBytes(self.initCode) + stateObject.storage = self.storage.Copy() + stateObject.remove = self.remove + stateObject.dirty = self.dirty + stateObject.deleted = self.deleted + + return stateObject +} + +// +// Attribute accessors +// + +// Balance returns the account balance +func (self *StateObject) Balance() *big.Int { + return self.balance +} + +// Address returns the address of the contract/account +func (c *StateObject) Address() common.Address { + return c.address +} + +// Code returns the contract code +func (self *StateObject) Code() []byte { + return self.code +} + +// SetCode sets the contract code +func (self *StateObject) SetCode(code []byte) { + self.code = code + self.codeHash = crypto.Sha3(code) + self.dirty = true +} + +// SetNonce sets the account nonce +func (self *StateObject) SetNonce(nonce uint64) { + self.nonce = nonce + self.dirty = true +} + +// Nonce returns the account nonce +func (self *StateObject) Nonce() uint64 { + return self.nonce +} + +// Encoding + +type extStateObject struct { + Nonce uint64 + Balance *big.Int + Root common.Hash + CodeHash []byte +} + +// DecodeObject decodes an RLP-encoded state object. +func DecodeObject(ctx context.Context, address common.Address, odr OdrBackend, data []byte) (*StateObject, error) { + var ( + obj = &StateObject{address: address, odr: odr, storage: make(Storage)} + ext extStateObject + err error + ) + if err = rlp.DecodeBytes(data, &ext); err != nil { + return nil, err + } + obj.trie = NewLightTrie(ext.Root, odr, true) + if !bytes.Equal(ext.CodeHash, emptyCodeHash) { + if obj.code, err = retrieveNodeData(ctx, obj.odr, common.BytesToHash(ext.CodeHash)); err != nil { + return nil, fmt.Errorf("can't find code for hash %x: %v", ext.CodeHash, err) + } + } + obj.nonce = ext.Nonce + obj.balance = ext.Balance + obj.codeHash = ext.CodeHash + return obj, nil +}
\ No newline at end of file diff --git a/light/state_test.go b/light/state_test.go new file mode 100644 index 000000000..2c2e6daea --- /dev/null +++ b/light/state_test.go @@ -0,0 +1,269 @@ +// Copyright 2015 The go-ethereum Authors +// This file is part of the go-ethereum library. +// +// The go-ethereum library is free software: you can redistribute it and/or modify +// it under the terms of the GNU Lesser General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. +// +// The go-ethereum library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>. + +package light + +import ( + "bytes" + "math/big" + "testing" + + "github.com/ethereum/go-ethereum/common" + "github.com/ethereum/go-ethereum/core/state" + "github.com/ethereum/go-ethereum/ethdb" + "github.com/ethereum/go-ethereum/trie" + "golang.org/x/net/context" +) + +type testOdr struct { + OdrBackend + sdb, ldb ethdb.Database +} + +func (odr *testOdr) Database() ethdb.Database { + return odr.ldb +} + +func (odr *testOdr) Retrieve(ctx context.Context, req OdrRequest) error { + switch req := req.(type) { + case *TrieRequest: + t, _ := trie.New(req.root, odr.sdb) + req.proof = t.Prove(req.key) + trie.ClearGlobalCache() + case *NodeDataRequest: + req.data, _ = odr.sdb.Get(req.hash[:]) + } + req.StoreResult(odr.ldb) + return nil +} + +func makeTestState() (common.Hash, ethdb.Database) { + sdb, _ := ethdb.NewMemDatabase() + st, _ := state.New(common.Hash{}, sdb) + for i := byte(0); i < 100; i++ { + so := st.GetOrNewStateObject(common.Address{i}) + for j := byte(0); j < 100; j++ { + val := common.Hash{i, j} + so.SetState(common.Hash{j}, val) + so.SetNonce(100) + } + so.AddBalance(big.NewInt(int64(i))) + so.SetCode([]byte{i, i, i}) + so.Update() + st.UpdateStateObject(so) + } + root, _ := st.Commit() + return root, sdb +} + +func TestLightStateOdr(t *testing.T) { + root, sdb := makeTestState() + ldb, _ := ethdb.NewMemDatabase() + odr := &testOdr{sdb: sdb, ldb: ldb} + ls := NewLightState(root, odr) + ctx := context.Background() + trie.ClearGlobalCache() + + for i := byte(0); i < 100; i++ { + addr := common.Address{i} + err := ls.AddBalance(ctx, addr, big.NewInt(1000)) + if err != nil { + t.Fatalf("Error adding balance to acc[%d]: %v", i, err) + } + err = ls.SetState(ctx, addr, common.Hash{100}, common.Hash{i, 100}) + if err != nil { + t.Fatalf("Error setting storage of acc[%d]: %v", i, err) + } + } + + addr := common.Address{100} + _, err := ls.CreateStateObject(ctx, addr) + if err != nil { + t.Fatalf("Error creating state object: %v", err) + } + err = ls.SetCode(ctx, addr, []byte{100, 100, 100}) + if err != nil { + t.Fatalf("Error setting code: %v", err) + } + err = ls.AddBalance(ctx, addr, big.NewInt(1100)) + if err != nil { + t.Fatalf("Error adding balance to acc[100]: %v", err) + } + for j := byte(0); j < 101; j++ { + err = ls.SetState(ctx, addr, common.Hash{j}, common.Hash{100, j}) + if err != nil { + t.Fatalf("Error setting storage of acc[100]: %v", err) + } + } + err = ls.SetNonce(ctx, addr, 100) + if err != nil { + t.Fatalf("Error setting nonce for acc[100]: %v", err) + } + + for i := byte(0); i < 101; i++ { + addr := common.Address{i} + + bal, err := ls.GetBalance(ctx, addr) + if err != nil { + t.Fatalf("Error getting balance of acc[%d]: %v", i, err) + } + if bal.Int64() != int64(i)+1000 { + t.Fatalf("Incorrect balance at acc[%d]: expected %v, got %v", i, int64(i)+1000, bal.Int64()) + } + + nonce, err := ls.GetNonce(ctx, addr) + if err != nil { + t.Fatalf("Error getting nonce of acc[%d]: %v", i, err) + } + if nonce != 100 { + t.Fatalf("Incorrect nonce at acc[%d]: expected %v, got %v", i, 100, nonce) + } + + code, err := ls.GetCode(ctx, addr) + exp := []byte{i, i, i} + if err != nil { + t.Fatalf("Error getting code of acc[%d]: %v", i, err) + } + if !bytes.Equal(code, exp) { + t.Fatalf("Incorrect code at acc[%d]: expected %v, got %v", i, exp, code) + } + + for j := byte(0); j < 101; j++ { + exp := common.Hash{i, j} + val, err := ls.GetState(ctx, addr, common.Hash{j}) + if err != nil { + t.Fatalf("Error retrieving acc[%d].storage[%d]: %v", i, j, err) + } + if val != exp { + t.Fatalf("Retrieved wrong value from acc[%d].storage[%d]: expected %04x, got %04x", i, j, exp, val) + } + } + } +} + +func TestLightStateSetCopy(t *testing.T) { + root, sdb := makeTestState() + ldb, _ := ethdb.NewMemDatabase() + odr := &testOdr{sdb: sdb, ldb: ldb} + ls := NewLightState(root, odr) + ctx := context.Background() + trie.ClearGlobalCache() + + for i := byte(0); i < 100; i++ { + addr := common.Address{i} + err := ls.AddBalance(ctx, addr, big.NewInt(1000)) + if err != nil { + t.Fatalf("Error adding balance to acc[%d]: %v", i, err) + } + err = ls.SetState(ctx, addr, common.Hash{100}, common.Hash{i, 100}) + if err != nil { + t.Fatalf("Error setting storage of acc[%d]: %v", i, err) + } + } + + ls2 := ls.Copy() + + for i := byte(0); i < 100; i++ { + addr := common.Address{i} + err := ls2.AddBalance(ctx, addr, big.NewInt(1000)) + if err != nil { + t.Fatalf("Error adding balance to acc[%d]: %v", i, err) + } + err = ls2.SetState(ctx, addr, common.Hash{100}, common.Hash{i, 200}) + if err != nil { + t.Fatalf("Error setting storage of acc[%d]: %v", i, err) + } + } + + lsx := ls.Copy() + ls.Set(ls2) + ls2.Set(lsx) + + for i := byte(0); i < 100; i++ { + addr := common.Address{i} + // check balance in ls + bal, err := ls.GetBalance(ctx, addr) + if err != nil { + t.Fatalf("Error getting balance to acc[%d]: %v", i, err) + } + if bal.Int64() != int64(i)+2000 { + t.Fatalf("Incorrect balance at ls.acc[%d]: expected %v, got %v", i, int64(i)+1000, bal.Int64()) + } + // check balance in ls2 + bal, err = ls2.GetBalance(ctx, addr) + if err != nil { + t.Fatalf("Error getting balance to acc[%d]: %v", i, err) + } + if bal.Int64() != int64(i)+1000 { + t.Fatalf("Incorrect balance at ls.acc[%d]: expected %v, got %v", i, int64(i)+1000, bal.Int64()) + } + // check storage in ls + exp := common.Hash{i, 200} + val, err := ls.GetState(ctx, addr, common.Hash{100}) + if err != nil { + t.Fatalf("Error retrieving acc[%d].storage[100]: %v", i, err) + } + if val != exp { + t.Fatalf("Retrieved wrong value from acc[%d].storage[100]: expected %04x, got %04x", i, exp, val) + } + // check storage in ls2 + exp = common.Hash{i, 100} + val, err = ls2.GetState(ctx, addr, common.Hash{100}) + if err != nil { + t.Fatalf("Error retrieving acc[%d].storage[100]: %v", i, err) + } + if val != exp { + t.Fatalf("Retrieved wrong value from acc[%d].storage[100]: expected %04x, got %04x", i, exp, val) + } + } +} + +func TestLightStateDelete(t *testing.T) { + root, sdb := makeTestState() + ldb, _ := ethdb.NewMemDatabase() + odr := &testOdr{sdb: sdb, ldb: ldb} + ls := NewLightState(root, odr) + ctx := context.Background() + trie.ClearGlobalCache() + + addr := common.Address{42} + + b, err := ls.HasAccount(ctx, addr) + if err != nil { + t.Fatalf("HasAccount error: %v", err) + } + if !b { + t.Fatalf("HasAccount returned false, expected true") + } + + b, err = ls.IsDeleted(ctx, addr) + if err != nil { + t.Fatalf("IsDeleted error: %v", err) + } + if b { + t.Fatalf("IsDeleted returned true, expected false") + } + + ls.Delete(ctx, addr) + + b, err = ls.IsDeleted(ctx, addr) + if err != nil { + t.Fatalf("IsDeleted error: %v", err) + } + if !b { + t.Fatalf("IsDeleted returned false, expected true") + } +} diff --git a/light/trie.go b/light/trie.go new file mode 100644 index 000000000..e9c96ea48 --- /dev/null +++ b/light/trie.go @@ -0,0 +1,123 @@ +// Copyright 2015 The go-ethereum Authors +// This file is part of the go-ethereum library. +// +// The go-ethereum library is free software: you can redistribute it and/or modify +// it under the terms of the GNU Lesser General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. +// +// The go-ethereum library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>. + +package light + +import ( + "github.com/ethereum/go-ethereum/common" + "github.com/ethereum/go-ethereum/ethdb" + "github.com/ethereum/go-ethereum/trie" + "golang.org/x/net/context" +) + +// LightTrie is an ODR-capable wrapper around trie.SecureTrie +type LightTrie struct { + trie *trie.SecureTrie + originalRoot common.Hash + odr OdrBackend + db ethdb.Database +} + +// NewLightTrie creates a new LightTrie instance. It doesn't instantly try to +// access the db or network and retrieve the root node, it only initializes its +// encapsulated SecureTrie at the first actual operation. +func NewLightTrie(root common.Hash, odr OdrBackend, useFakeMap bool) *LightTrie { + return &LightTrie{ + // SecureTrie is initialized before first request + originalRoot: root, + odr: odr, + db: odr.Database(), + } +} + +// retrieveKey retrieves a single key, returns true and stores nodes in local +// database if successful +func (t *LightTrie) retrieveKey(ctx context.Context, key []byte) bool { + r := &TrieRequest{root: t.originalRoot, key: key} + return t.odr.Retrieve(ctx, r) == nil +} + +// do tries and retries to execute a function until it returns with no error or +// an error type other than MissingNodeError +func (t *LightTrie) do(ctx context.Context, fallbackKey []byte, fn func() error) error { + err := fn() + for err != nil { + mn, ok := err.(*trie.MissingNodeError) + if !ok { + return err + } + + var key []byte + if mn.PrefixLen+mn.SuffixLen > 0 { + key = mn.Key + } else { + key = fallbackKey + } + if !t.retrieveKey(ctx, key) { + break + } + err = fn() + } + return err +} + +// Get returns the value for key stored in the trie. +// The value bytes must not be modified by the caller. +func (t *LightTrie) Get(ctx context.Context, key []byte) (res []byte, err error) { + err = t.do(ctx, key, func() (err error) { + if t.trie == nil { + t.trie, err = trie.NewSecure(t.originalRoot, t.db) + } + if err == nil { + res, err = t.trie.TryGet(key) + } + return + }) + return +} + +// Update associates key with value in the trie. Subsequent calls to +// Get will return value. If value has length zero, any existing value +// is deleted from the trie and calls to Get will return nil. +// +// The value bytes must not be modified by the caller while they are +// stored in the trie. +func (t *LightTrie) Update(ctx context.Context, key, value []byte) (err error) { + err = t.do(ctx, key, func() (err error) { + if t.trie == nil { + t.trie, err = trie.NewSecure(t.originalRoot, t.db) + } + if err == nil { + err = t.trie.TryUpdate(key, value) + } + return + }) + return +} + +// Delete removes any existing value for key from the trie. +func (t *LightTrie) Delete(ctx context.Context, key []byte) (err error) { + err = t.do(ctx, key, func() (err error) { + if t.trie == nil { + t.trie, err = trie.NewSecure(t.originalRoot, t.db) + } + if err == nil { + err = t.trie.TryDelete(key) + } + return + }) + return +} diff --git a/trie/encoding.go b/trie/encoding.go index 3c172b843..761bad188 100644 --- a/trie/encoding.go +++ b/trie/encoding.go @@ -69,6 +69,27 @@ func compactHexDecode(str []byte) []byte { return nibbles } +// compactHexEncode encodes a series of nibbles into a byte array +func compactHexEncode(nibbles []byte) []byte { + nl := len(nibbles) + if nl == 0 { + return nil + } + if nibbles[nl-1] == 16 { + nl-- + } + l := (nl + 1) / 2 + var str = make([]byte, l) + for i, _ := range str { + b := nibbles[i*2] * 16 + if nl > i*2 { + b += nibbles[i*2+1] + } + str[i] = b + } + return str +} + func decodeCompact(key []byte) []byte { l := len(key) / 2 var res = make([]byte, l) diff --git a/trie/encoding_test.go b/trie/encoding_test.go index 061d48d58..2f125ef2f 100644 --- a/trie/encoding_test.go +++ b/trie/encoding_test.go @@ -57,6 +57,12 @@ func (s *TrieEncodingSuite) TestCompactHexDecode(c *checker.C) { c.Assert(res, checker.DeepEquals, exp) } +func (s *TrieEncodingSuite) TestCompactHexEncode(c *checker.C) { + exp := []byte("verb") + res := compactHexEncode([]byte{7, 6, 6, 5, 7, 2, 6, 2, 16}) + c.Assert(res, checker.DeepEquals, exp) +} + func (s *TrieEncodingSuite) TestCompactDecode(c *checker.C) { // odd compact decode exp := []byte{1, 2, 3, 4, 5} diff --git a/trie/errors.go b/trie/errors.go index a0f58f28f..fd0e6f0a9 100644 --- a/trie/errors.go +++ b/trie/errors.go @@ -27,13 +27,23 @@ import ( // information necessary for retrieving the missing node through an ODR service. // // NodeHash is the hash of the missing node +// // RootHash is the original root of the trie that contains the node -// KeyPrefix is the prefix that leads from the root to the missing node (hex encoded) -// KeySuffix (optional) contains the rest of the key we were looking for, gives a -// hint on which further nodes should also be retrieved (hex encoded) +// +// Key is a binary-encoded key that contains the prefix that leads to the first +// missing node and optionally a suffix that hints on which further nodes should +// also be retrieved +// +// PrefixLen is the nibble length of the key prefix that leads from the root to +// the missing node +// +// SuffixLen is the nibble length of the remaining part of the key that hints on +// which further nodes should also be retrieved (can be zero when there are no +// such hints in the error message) type MissingNodeError struct { RootHash, NodeHash common.Hash - KeyPrefix, KeySuffix []byte + Key []byte + PrefixLen, SuffixLen int } func (err *MissingNodeError) Error() string { diff --git a/trie/proof.go b/trie/proof.go index 2e88bb50b..0f9264942 100644 --- a/trie/proof.go +++ b/trie/proof.go @@ -17,29 +17,30 @@ import ( // also included in the last node and can be retrieved by verifying // the proof. // -// The returned proof is nil if the trie does not contain a value for key. -// For existing keys, the proof will have at least one element. +// If the trie does not contain a value for key, the returned proof +// contains all nodes of the longest existing prefix of the key +// (at least the root node), ending with the node that proves the +// absence of the key. func (t *Trie) Prove(key []byte) []rlp.RawValue { // Collect all nodes on the path to key. key = compactHexDecode(key) nodes := []node{} tn := t.root - for len(key) > 0 { + for len(key) > 0 && tn != nil { switch n := tn.(type) { case shortNode: if len(key) < len(n.Key) || !bytes.Equal(n.Key, key[:len(n.Key)]) { // The trie doesn't contain the key. - return nil + tn = nil + } else { + tn = n.Val + key = key[len(n.Key):] } - tn = n.Val - key = key[len(n.Key):] nodes = append(nodes, n) case fullNode: tn = n[key[0]] key = key[1:] nodes = append(nodes, n) - case nil: - return nil case hashNode: var err error tn, err = t.resolveHash(n, nil, nil) @@ -93,7 +94,12 @@ func VerifyProof(rootHash common.Hash, key []byte, proof []rlp.RawValue) (value keyrest, cld := get(n, key) switch cld := cld.(type) { case nil: - return nil, fmt.Errorf("key mismatch at proof node %d", i) + if i != len(proof)-1 { + return nil, fmt.Errorf("key mismatch at proof node %d", i) + } else { + // The trie doesn't contain the key. + return nil, nil + } case hashNode: key = keyrest wantHash = cld diff --git a/trie/trie.go b/trie/trie.go index 717296e27..9dfde4529 100644 --- a/trie/trie.go +++ b/trie/trie.go @@ -394,8 +394,9 @@ func (t *Trie) resolveHash(n hashNode, prefix, suffix []byte) (node, error) { return nil, &MissingNodeError{ RootHash: t.originalRoot, NodeHash: common.BytesToHash(n), - KeyPrefix: prefix, - KeySuffix: suffix, + Key: compactHexEncode(append(prefix, suffix...)), + PrefixLen: len(prefix), + SuffixLen: len(suffix), } } dec := mustDecodeNode(n, enc) |