From ae45a39dc1cddac885090872cefc6799b4a4c1d9 Mon Sep 17 00:00:00 2001 From: obscuren Date: Sat, 28 Feb 2015 20:52:10 +0100 Subject: Secure trie --- trie/secure_trie.go | 32 ++++++++++++++++++++++++++++++++ trie/trie_test.go | 1 - 2 files changed, 32 insertions(+), 1 deletion(-) create mode 100644 trie/secure_trie.go (limited to 'trie') diff --git a/trie/secure_trie.go b/trie/secure_trie.go new file mode 100644 index 000000000..c6ef90351 --- /dev/null +++ b/trie/secure_trie.go @@ -0,0 +1,32 @@ +package trie + +import "github.com/ethereum/go-ethereum/crypto" + +type SecureTrie struct { + *Trie +} + +func NewSecure(root []byte, backend Backend) *SecureTrie { + return &SecureTrie{New(root, backend)} +} + +func (self *SecureTrie) Update(key, value []byte) Node { + return self.Trie.Update(crypto.Sha3(key), value) +} +func (self *SecureTrie) UpdateString(key, value string) Node { + return self.Update([]byte(key), []byte(value)) +} + +func (self *SecureTrie) Get(key []byte) []byte { + return self.Trie.Get(crypto.Sha3(key)) +} +func (self *SecureTrie) GetString(key string) []byte { + return self.Get([]byte(key)) +} + +func (self *SecureTrie) Delete(key []byte) Node { + return self.Trie.Delete(crypto.Sha3(key)) +} +func (self *SecureTrie) DeletString(key string) Node { + return self.Delete([]byte(key)) +} diff --git a/trie/trie_test.go b/trie/trie_test.go index 4b185f355..4b0243bcf 100644 --- a/trie/trie_test.go +++ b/trie/trie_test.go @@ -274,7 +274,6 @@ func TestLargeData(t *testing.T) { trie.Update(value2.k, value2.v) vals[string(value.k)] = value vals[string(value2.k)] = value2 - fmt.Println(value, "\n", value2) } it := trie.Iterator() -- cgit v1.2.3 From bf5365b317ba5767feb28eef9abb83328bfea099 Mon Sep 17 00:00:00 2001 From: obscuren Date: Tue, 3 Mar 2015 12:15:58 +0100 Subject: Delet => Delete --- trie/secure_trie.go | 2 +- trie/trie_test.go | 32 ++++++++++++++++++++++++++++++++ 2 files changed, 33 insertions(+), 1 deletion(-) (limited to 'trie') diff --git a/trie/secure_trie.go b/trie/secure_trie.go index c6ef90351..f49547ed8 100644 --- a/trie/secure_trie.go +++ b/trie/secure_trie.go @@ -27,6 +27,6 @@ func (self *SecureTrie) GetString(key string) []byte { func (self *SecureTrie) Delete(key []byte) Node { return self.Trie.Delete(crypto.Sha3(key)) } -func (self *SecureTrie) DeletString(key string) Node { +func (self *SecureTrie) DeleteString(key string) Node { return self.Delete([]byte(key)) } diff --git a/trie/trie_test.go b/trie/trie_test.go index 4b0243bcf..92e0df8e2 100644 --- a/trie/trie_test.go +++ b/trie/trie_test.go @@ -19,6 +19,10 @@ func NewEmpty() *Trie { return New(nil, make(Db)) } +func NewEmptySecure() *SecureTrie { + return NewSecure(nil, make(Db)) +} + func TestEmptyTrie(t *testing.T) { trie := NewEmpty() res := trie.Hash() @@ -295,3 +299,31 @@ func TestLargeData(t *testing.T) { } } } + +func TestSecureDelete(t *testing.T) { + trie := NewEmptySecure() + + vals := []struct{ k, v string }{ + {"do", "verb"}, + {"ether", "wookiedoo"}, + {"horse", "stallion"}, + {"shaman", "horse"}, + {"doge", "coin"}, + {"ether", ""}, + {"dog", "puppy"}, + {"shaman", ""}, + } + for _, val := range vals { + if val.v != "" { + trie.UpdateString(val.k, val.v) + } else { + trie.DeleteString(val.k) + } + } + + hash := trie.Hash() + exp := ethutil.Hex2Bytes("29b235a58c3c25ab83010c327d5932bcf05324b7d6b1185e650798034783ca9d") + if !bytes.Equal(hash, exp) { + t.Errorf("expected %x got %x", exp, hash) + } +} -- cgit v1.2.3 From b909a5ec18d30456c6028593448233bba0937482 Mon Sep 17 00:00:00 2001 From: obscuren Date: Tue, 3 Mar 2015 12:25:44 +0100 Subject: Trie => SecureTrie --- trie/secure_trie.go | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'trie') diff --git a/trie/secure_trie.go b/trie/secure_trie.go index f49547ed8..b9fa376b8 100644 --- a/trie/secure_trie.go +++ b/trie/secure_trie.go @@ -30,3 +30,7 @@ func (self *SecureTrie) Delete(key []byte) Node { func (self *SecureTrie) DeleteString(key string) Node { return self.Delete([]byte(key)) } + +func (self *SecureTrie) Copy() *SecureTrie { + return &SecureTrie{self.Trie.Copy()} +} -- cgit v1.2.3 From a6fe92194f0cd4b0d5d595ba78ec1195429715dd Mon Sep 17 00:00:00 2001 From: = Date: Thu, 5 Mar 2015 01:42:32 +0000 Subject: Fixed iterator bug which skips the 0x000...000 key --- trie/iterator.go | 28 +++++++++++++++++++++------- 1 file changed, 21 insertions(+), 7 deletions(-) (limited to 'trie') diff --git a/trie/iterator.go b/trie/iterator.go index 3b3ddd751..fda7c6cbe 100644 --- a/trie/iterator.go +++ b/trie/iterator.go @@ -1,6 +1,8 @@ package trie -import "bytes" +import ( + "bytes" +) type Iterator struct { trie *Trie @@ -10,22 +12,28 @@ type Iterator struct { } func NewIterator(trie *Trie) *Iterator { - return &Iterator{trie: trie, Key: make([]byte, 32)} + return &Iterator{trie: trie, Key: nil} } func (self *Iterator) Next() bool { self.trie.mu.Lock() defer self.trie.mu.Unlock() + isIterStart := false + if self.Key == nil { + isIterStart = true + self.Key = make([]byte, 32) + } + key := RemTerm(CompactHexDecode(string(self.Key))) - k := self.next(self.trie.root, key) + k := self.next(self.trie.root, key, isIterStart) self.Key = []byte(DecodeCompact(k)) return len(k) > 0 } -func (self *Iterator) next(node Node, key []byte) []byte { +func (self *Iterator) next(node Node, key []byte, isIterStart bool) []byte { if node == nil { return nil } @@ -33,7 +41,7 @@ func (self *Iterator) next(node Node, key []byte) []byte { switch node := node.(type) { case *FullNode: if len(key) > 0 { - k := self.next(node.branch(key[0]), key[1:]) + k := self.next(node.branch(key[0]), key[1:], isIterStart) if k != nil { return append([]byte{key[0]}, k...) } @@ -54,7 +62,13 @@ func (self *Iterator) next(node Node, key []byte) []byte { case *ShortNode: k := RemTerm(node.Key()) if vnode, ok := node.Value().(*ValueNode); ok { - if bytes.Compare([]byte(k), key) > 0 { + switch bytes.Compare([]byte(k), key) { + case 0: + if isIterStart { + self.Value = vnode.Val() + return k + } + case 1: self.Value = vnode.Val() return k } @@ -64,7 +78,7 @@ func (self *Iterator) next(node Node, key []byte) []byte { var ret []byte skey := key[len(k):] if BeginsWith(key, k) { - ret = self.next(cnode, skey) + ret = self.next(cnode, skey, isIterStart) } else if bytes.Compare(k, key[:len(k)]) > 0 { return self.key(node) } -- cgit v1.2.3 From 357d17ae58e6570278a3ed78a754a4ac1c346d74 Mon Sep 17 00:00:00 2001 From: obscuren Date: Thu, 5 Mar 2015 17:46:00 +0100 Subject: Start at 0 --- trie/trie_test.go | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'trie') diff --git a/trie/trie_test.go b/trie/trie_test.go index 4b185f355..21a1eb11f 100644 --- a/trie/trie_test.go +++ b/trie/trie_test.go @@ -267,14 +267,13 @@ func TestLargeData(t *testing.T) { trie := NewEmpty() vals := make(map[string]*kv) - for i := byte(1); i < 255; i++ { + for i := byte(0); i < 255; i++ { value := &kv{ethutil.LeftPadBytes([]byte{i}, 32), []byte{i}, false} value2 := &kv{ethutil.LeftPadBytes([]byte{10, i}, 32), []byte{i}, false} trie.Update(value.k, value.v) trie.Update(value2.k, value2.v) vals[string(value.k)] = value vals[string(value2.k)] = value2 - fmt.Println(value, "\n", value2) } it := trie.Iterator() -- cgit v1.2.3