Merge branch 'release/v0.7.10'vv0.7.10

10 files changed, 936 insertions, 0 deletions

diff --git a/ptrie/cache.go b/ptrie/cache.go
new file mode 100644
index 000000000..721dc4cf6
--- /dev/null
+++ b/ptrie/cache.go
@@ -0,0 +1,42 @@
+package ptrie
+
+type Backend interface {
+	Get([]byte) ([]byte, error)
+	Put([]byte, []byte)
+}
+
+type Cache struct {
+	store   map[string][]byte
+	backend Backend
+}
+
+func NewCache(backend Backend) *Cache {
+	return &Cache{make(map[string][]byte), backend}
+}
+
+func (self *Cache) Get(key []byte) []byte {
+	data := self.store[string(key)]
+	if data == nil {
+		data, _ = self.backend.Get(key)
+	}
+
+	return data
+}
+
+func (self *Cache) Put(key []byte, data []byte) {
+	self.store[string(key)] = data
+}
+
+func (self *Cache) Flush() {
+	for k, v := range self.store {
+		self.backend.Put([]byte(k), v)
+	}
+
+	// This will eventually grow too large. We'd could
+	// do a make limit on storage and push out not-so-popular nodes.
+	//self.Reset()
+}
+
+func (self *Cache) Reset() {
+	self.store = make(map[string][]byte)
+}
diff --git a/ptrie/fullnode.go b/ptrie/fullnode.go
new file mode 100644
index 000000000..7a7f7d22d
--- /dev/null
+++ b/ptrie/fullnode.go
@@ -0,0 +1,69 @@
+package ptrie
+
+type FullNode struct {
+	trie  *Trie
+	nodes [17]Node
+}
+
+func NewFullNode(t *Trie) *FullNode {
+	return &FullNode{trie: t}
+}
+
+func (self *FullNode) Dirty() bool { return true }
+func (self *FullNode) Value() Node {
+	self.nodes[16] = self.trie.trans(self.nodes[16])
+	return self.nodes[16]
+}
+func (self *FullNode) Branches() []Node {
+	return self.nodes[:16]
+}
+
+func (self *FullNode) Copy() Node {
+	nnode := NewFullNode(self.trie)
+	for i, node := range self.nodes {
+		nnode.nodes[i] = node
+	}
+
+	return nnode
+}
+
+// Returns the length of non-nil nodes
+func (self *FullNode) Len() (amount int) {
+	for _, node := range self.nodes {
+		if node != nil {
+			amount++
+		}
+	}
+
+	return
+}
+
+func (self *FullNode) Hash() interface{} {
+	return self.trie.store(self)
+}
+
+func (self *FullNode) RlpData() interface{} {
+	t := make([]interface{}, 17)
+	for i, node := range self.nodes {
+		if node != nil {
+			t[i] = node.Hash()
+		} else {
+			t[i] = ""
+		}
+	}
+
+	return t
+}
+
+func (self *FullNode) set(k byte, value Node) {
+	self.nodes[int(k)] = value
+}
+
+func (self *FullNode) branch(i byte) Node {
+	if self.nodes[int(i)] != nil {
+		self.nodes[int(i)] = self.trie.trans(self.nodes[int(i)])
+
+		return self.nodes[int(i)]
+	}
+	return nil
+}
diff --git a/ptrie/hashnode.go b/ptrie/hashnode.go
new file mode 100644
index 000000000..4c17569d7
--- /dev/null
+++ b/ptrie/hashnode.go
@@ -0,0 +1,22 @@
+package ptrie
+
+type HashNode struct {
+	key []byte
+}
+
+func NewHash(key []byte) *HashNode {
+	return &HashNode{key}
+}
+
+func (self *HashNode) RlpData() interface{} {
+	return self.key
+}
+
+func (self *HashNode) Hash() interface{} {
+	return self.key
+}
+
+// These methods will never be called but we have to satisfy Node interface
+func (self *HashNode) Value() Node { return nil }
+func (self *HashNode) Dirty() bool { return true }
+func (self *HashNode) Copy() Node  { return self }
diff --git a/ptrie/iterator.go b/ptrie/iterator.go
new file mode 100644
index 000000000..5714bdbc8
--- /dev/null
+++ b/ptrie/iterator.go
@@ -0,0 +1,115 @@
+package ptrie
+
+import (
+	"bytes"
+
+	"github.com/ethereum/go-ethereum/trie"
+)
+
+type Iterator struct {
+	trie *Trie
+
+	Key   []byte
+	Value []byte
+}
+
+func NewIterator(trie *Trie) *Iterator {
+	return &Iterator{trie: trie, Key: []byte{0}}
+}
+
+func (self *Iterator) Next() bool {
+	self.trie.mu.Lock()
+	defer self.trie.mu.Unlock()
+
+	key := trie.RemTerm(trie.CompactHexDecode(string(self.Key)))
+	k := self.next(self.trie.root, key)
+
+	self.Key = []byte(trie.DecodeCompact(k))
+
+	return len(k) > 0
+
+}
+
+func (self *Iterator) next(node Node, key []byte) []byte {
+	if node == nil {
+		return nil
+	}
+
+	switch node := node.(type) {
+	case *FullNode:
+		if len(key) > 0 {
+			k := self.next(node.branch(key[0]), key[1:])
+			if k != nil {
+				return append([]byte{key[0]}, k...)
+			}
+		}
+
+		var r byte
+		if len(key) > 0 {
+			r = key[0] + 1
+		}
+
+		for i := r; i < 16; i++ {
+			k := self.key(node.branch(byte(i)))
+			if k != nil {
+				return append([]byte{i}, k...)
+			}
+		}
+
+	case *ShortNode:
+		k := trie.RemTerm(node.Key())
+		if vnode, ok := node.Value().(*ValueNode); ok {
+			if bytes.Compare([]byte(k), key) > 0 {
+				self.Value = vnode.Val()
+				return k
+			}
+		} else {
+			cnode := node.Value()
+
+			var ret []byte
+			skey := key[len(k):]
+			if trie.BeginsWith(key, k) {
+				ret = self.next(cnode, skey)
+			} else if bytes.Compare(k, key[:len(k)]) > 0 {
+				ret = self.key(node)
+			}
+
+			if ret != nil {
+				return append(k, ret...)
+			}
+		}
+	}
+
+	return nil
+}
+
+func (self *Iterator) key(node Node) []byte {
+	switch node := node.(type) {
+	case *ShortNode:
+		// Leaf node
+		if vnode, ok := node.Value().(*ValueNode); ok {
+			k := trie.RemTerm(node.Key())
+			self.Value = vnode.Val()
+
+			return k
+		} else {
+			k := trie.RemTerm(node.Key())
+			return append(k, self.key(node.Value())...)
+		}
+	case *FullNode:
+		if node.Value() != nil {
+			self.Value = node.Value().(*ValueNode).Val()
+
+			return []byte{16}
+		}
+
+		for i := 0; i < 16; i++ {
+			k := self.key(node.branch(byte(i)))
+			if k != nil {
+				return append([]byte{byte(i)}, k...)
+			}
+		}
+	}
+
+	return nil
+}
diff --git a/ptrie/iterator_test.go b/ptrie/iterator_test.go
new file mode 100644
index 000000000..acfc03d63
--- /dev/null
+++ b/ptrie/iterator_test.go
@@ -0,0 +1,33 @@
+package ptrie
+
+import "testing"
+
+func TestIterator(t *testing.T) {
+	trie := NewEmpty()
+	vals := []struct{ k, v string }{
+		{"do", "verb"},
+		{"ether", "wookiedoo"},
+		{"horse", "stallion"},
+		{"shaman", "horse"},
+		{"doge", "coin"},
+		{"dog", "puppy"},
+		{"somethingveryoddindeedthis is", "myothernodedata"},
+	}
+	v := make(map[string]bool)
+	for _, val := range vals {
+		v[val.k] = false
+		trie.UpdateString(val.k, val.v)
+	}
+	trie.Commit()
+
+	it := trie.Iterator()
+	for it.Next() {
+		v[string(it.Key)] = true
+	}
+
+	for k, found := range v {
+		if !found {
+			t.Error("iterator didn't find", k)
+		}
+	}
+}
diff --git a/ptrie/node.go b/ptrie/node.go
new file mode 100644
index 000000000..2c85dbce7
--- /dev/null
+++ b/ptrie/node.go
@@ -0,0 +1,40 @@
+package ptrie
+
+import "fmt"
+
+var indices = []string{"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b", "c", "d", "e", "f", "[17]"}
+
+type Node interface {
+	Value() Node
+	Copy() Node // All nodes, for now, return them self
+	Dirty() bool
+	fstring(string) string
+	Hash() interface{}
+	RlpData() interface{}
+}
+
+// Value node
+func (self *ValueNode) String() string            { return self.fstring("") }
+func (self *FullNode) String() string             { return self.fstring("") }
+func (self *ShortNode) String() string            { return self.fstring("") }
+func (self *ValueNode) fstring(ind string) string { return fmt.Sprintf("%s ", self.data) }
+func (self *HashNode) fstring(ind string) string  { return fmt.Sprintf("%x ", self.key) }
+
+// Full node
+func (self *FullNode) fstring(ind string) string {
+	resp := fmt.Sprintf("[\n%s  ", ind)
+	for i, node := range self.nodes {
+		if node == nil {
+			resp += fmt.Sprintf("%s: <nil> ", indices[i])
+		} else {
+			resp += fmt.Sprintf("%s: %v", indices[i], node.fstring(ind+"  "))
+		}
+	}
+
+	return resp + fmt.Sprintf("\n%s] ", ind)
+}
+
+// Short node
+func (self *ShortNode) fstring(ind string) string {
+	return fmt.Sprintf("[ %s: %v ] ", self.key, self.value.fstring(ind+"  "))
+}
diff --git a/ptrie/shortnode.go b/ptrie/shortnode.go
new file mode 100644
index 000000000..73ff2914b
--- /dev/null
+++ b/ptrie/shortnode.go
@@ -0,0 +1,31 @@
+package ptrie
+
+import "github.com/ethereum/go-ethereum/trie"
+
+type ShortNode struct {
+	trie  *Trie
+	key   []byte
+	value Node
+}
+
+func NewShortNode(t *Trie, key []byte, value Node) *ShortNode {
+	return &ShortNode{t, []byte(trie.CompactEncode(key)), value}
+}
+func (self *ShortNode) Value() Node {
+	self.value = self.trie.trans(self.value)
+
+	return self.value
+}
+func (self *ShortNode) Dirty() bool { return true }
+func (self *ShortNode) Copy() Node  { return NewShortNode(self.trie, self.key, self.value) }
+
+func (self *ShortNode) RlpData() interface{} {
+	return []interface{}{self.key, self.value.Hash()}
+}
+func (self *ShortNode) Hash() interface{} {
+	return self.trie.store(self)
+}
+
+func (self *ShortNode) Key() []byte {
+	return trie.CompactDecode(string(self.key))
+}
diff --git a/ptrie/trie.go b/ptrie/trie.go
new file mode 100644
index 000000000..9fe9ea52a
--- /dev/null
+++ b/ptrie/trie.go
@@ -0,0 +1,312 @@
+package ptrie
+
+import (
+	"bytes"
+	"container/list"
+	"fmt"
+	"sync"
+
+	"github.com/ethereum/go-ethereum/crypto"
+	"github.com/ethereum/go-ethereum/ethutil"
+	"github.com/ethereum/go-ethereum/trie"
+)
+
+func ParanoiaCheck(t1 *Trie, backend Backend) (bool, *Trie) {
+	t2 := New(nil, backend)
+
+	it := t1.Iterator()
+	for it.Next() {
+		t2.Update(it.Key, it.Value)
+	}
+
+	return bytes.Compare(t2.Hash(), t1.Hash()) == 0, t2
+}
+
+type Trie struct {
+	mu       sync.Mutex
+	root     Node
+	roothash []byte
+	cache    *Cache
+
+	revisions *list.List
+}
+
+func New(root []byte, backend Backend) *Trie {
+	trie := &Trie{}
+	trie.revisions = list.New()
+	trie.roothash = root
+	trie.cache = NewCache(backend)
+
+	if root != nil {
+		value := ethutil.NewValueFromBytes(trie.cache.Get(root))
+		trie.root = trie.mknode(value)
+	}
+
+	return trie
+}
+
+func (self *Trie) Iterator() *Iterator {
+	return NewIterator(self)
+}
+
+// Legacy support
+func (self *Trie) Root() []byte { return self.Hash() }
+func (self *Trie) Hash() []byte {
+	var hash []byte
+	if self.root != nil {
+		//hash = self.root.Hash().([]byte)
+		t := self.root.Hash()
+		if byts, ok := t.([]byte); ok {
+			hash = byts
+		} else {
+			hash = crypto.Sha3(ethutil.Encode(self.root.RlpData()))
+		}
+	} else {
+		hash = crypto.Sha3(ethutil.Encode(""))
+	}
+
+	if !bytes.Equal(hash, self.roothash) {
+		self.revisions.PushBack(self.roothash)
+		self.roothash = hash
+	}
+
+	return hash
+}
+func (self *Trie) Commit() {
+	// Hash first
+	self.Hash()
+
+	self.cache.Flush()
+}
+
+// Reset should only be called if the trie has been hashed
+func (self *Trie) Reset() {
+	self.cache.Reset()
+
+	revision := self.revisions.Remove(self.revisions.Back()).([]byte)
+	self.roothash = revision
+	value := ethutil.NewValueFromBytes(self.cache.Get(self.roothash))
+	self.root = self.mknode(value)
+}
+
+func (self *Trie) UpdateString(key, value string) Node { return self.Update([]byte(key), []byte(value)) }
+func (self *Trie) Update(key, value []byte) Node {
+	self.mu.Lock()
+	defer self.mu.Unlock()
+
+	k := trie.CompactHexDecode(string(key))
+
+	if len(value) != 0 {
+		self.root = self.insert(self.root, k, &ValueNode{self, value})
+	} else {
+		self.root = self.delete(self.root, k)
+	}
+
+	return self.root
+}
+
+func (self *Trie) GetString(key string) []byte { return self.Get([]byte(key)) }
+func (self *Trie) Get(key []byte) []byte {
+	self.mu.Lock()
+	defer self.mu.Unlock()
+
+	k := trie.CompactHexDecode(string(key))
+
+	n := self.get(self.root, k)
+	if n != nil {
+		return n.(*ValueNode).Val()
+	}
+
+	return nil
+}
+
+func (self *Trie) DeleteString(key string) Node { return self.Delete([]byte(key)) }
+func (self *Trie) Delete(key []byte) Node {
+	self.mu.Lock()
+	defer self.mu.Unlock()
+
+	k := trie.CompactHexDecode(string(key))
+	self.root = self.delete(self.root, k)
+
+	return self.root
+}
+
+func (self *Trie) insert(node Node, key []byte, value Node) Node {
+	if len(key) == 0 {
+		return value
+	}
+
+	if node == nil {
+		return NewShortNode(self, key, value)
+	}
+
+	switch node := node.(type) {
+	case *ShortNode:
+		k := node.Key()
+		cnode := node.Value()
+		if bytes.Equal(k, key) {
+			return NewShortNode(self, key, value)
+		}
+
+		var n Node
+		matchlength := trie.MatchingNibbleLength(key, k)
+		if matchlength == len(k) {
+			n = self.insert(cnode, key[matchlength:], value)
+		} else {
+			pnode := self.insert(nil, k[matchlength+1:], cnode)
+			nnode := self.insert(nil, key[matchlength+1:], value)
+			fulln := NewFullNode(self)
+			fulln.set(k[matchlength], pnode)
+			fulln.set(key[matchlength], nnode)
+			n = fulln
+		}
+		if matchlength == 0 {
+			return n
+		}
+
+		return NewShortNode(self, key[:matchlength], n)
+
+	case *FullNode:
+		cpy := node.Copy().(*FullNode)
+		cpy.set(key[0], self.insert(node.branch(key[0]), key[1:], value))
+
+		return cpy
+
+	default:
+		panic("Invalid node")
+	}
+}
+
+func (self *Trie) get(node Node, key []byte) Node {
+	if len(key) == 0 {
+		return node
+	}
+
+	if node == nil {
+		return nil
+	}
+
+	switch node := node.(type) {
+	case *ShortNode:
+		k := node.Key()
+		cnode := node.Value()
+
+		if len(key) >= len(k) && bytes.Equal(k, key[:len(k)]) {
+			return self.get(cnode, key[len(k):])
+		}
+
+		return nil
+	case *FullNode:
+		return self.get(node.branch(key[0]), key[1:])
+	default:
+		panic(fmt.Sprintf("%T: invalid node: %v", node, node))
+	}
+}
+
+func (self *Trie) delete(node Node, key []byte) Node {
+	if len(key) == 0 {
+		return nil
+	}
+
+	switch node := node.(type) {
+	case *ShortNode:
+		k := node.Key()
+		cnode := node.Value()
+		if bytes.Equal(key, k) {
+			return nil
+		} else if bytes.Equal(key[:len(k)], k) {
+			child := self.delete(cnode, key[len(k):])
+
+			var n Node
+			switch child := child.(type) {
+			case *ShortNode:
+				nkey := append(k, child.Key()...)
+				n = NewShortNode(self, nkey, child.Value())
+			case *FullNode:
+				n = NewShortNode(self, node.key, child)
+			}
+
+			return n
+		} else {
+			return node
+		}
+
+	case *FullNode:
+		n := node.Copy().(*FullNode)
+		n.set(key[0], self.delete(n.branch(key[0]), key[1:]))
+
+		pos := -1
+		for i := 0; i < 17; i++ {
+			if n.branch(byte(i)) != nil {
+				if pos == -1 {
+					pos = i
+				} else {
+					pos = -2
+				}
+			}
+		}
+
+		var nnode Node
+		if pos == 16 {
+			nnode = NewShortNode(self, []byte{16}, n.branch(byte(pos)))
+		} else if pos >= 0 {
+			cnode := n.branch(byte(pos))
+			switch cnode := cnode.(type) {
+			case *ShortNode:
+				// Stitch keys
+				k := append([]byte{byte(pos)}, cnode.Key()...)
+				nnode = NewShortNode(self, k, cnode.Value())
+			case *FullNode:
+				nnode = NewShortNode(self, []byte{byte(pos)}, n.branch(byte(pos)))
+			}
+		} else {
+			nnode = n
+		}
+
+		return nnode
+
+	default:
+		panic("Invalid node")
+	}
+}
+
+// casting functions and cache storing
+func (self *Trie) mknode(value *ethutil.Value) Node {
+	l := value.Len()
+	switch l {
+	case 2:
+		return NewShortNode(self, trie.CompactDecode(string(value.Get(0).Bytes())), self.mknode(value.Get(1)))
+	case 17:
+		fnode := NewFullNode(self)
+		for i := 0; i < l; i++ {
+			fnode.set(byte(i), self.mknode(value.Get(i)))
+		}
+		return fnode
+	case 32:
+		return &HashNode{value.Bytes()}
+	default:
+		return &ValueNode{self, value.Bytes()}
+	}
+}
+
+func (self *Trie) trans(node Node) Node {
+	switch node := node.(type) {
+	case *HashNode:
+		value := ethutil.NewValueFromBytes(self.cache.Get(node.key))
+		return self.mknode(value)
+	default:
+		return node
+	}
+}
+
+func (self *Trie) store(node Node) interface{} {
+	data := ethutil.Encode(node)
+	if len(data) >= 32 {
+		key := crypto.Sha3(data)
+		self.cache.Put(key, data)
+
+		return key
+	}
+
+	return node.RlpData()
+}
diff --git a/ptrie/trie_test.go b/ptrie/trie_test.go
new file mode 100644
index 000000000..5b1c64140
--- /dev/null
+++ b/ptrie/trie_test.go
@@ -0,0 +1,259 @@
+package ptrie
+
+import (
+	"bytes"
+	"fmt"
+	"testing"
+
+	"github.com/ethereum/go-ethereum/crypto"
+	"github.com/ethereum/go-ethereum/ethutil"
+)
+
+type Db map[string][]byte
+
+func (self Db) Get(k []byte) ([]byte, error) { return self[string(k)], nil }
+func (self Db) Put(k, v []byte)              { self[string(k)] = v }
+
+// Used for testing
+func NewEmpty() *Trie {
+	return New(nil, make(Db))
+}
+
+func TestEmptyTrie(t *testing.T) {
+	trie := NewEmpty()
+	res := trie.Hash()
+	exp := crypto.Sha3(ethutil.Encode(""))
+	if !bytes.Equal(res, exp) {
+		t.Errorf("expected %x got %x", exp, res)
+	}
+}
+
+func TestInsert(t *testing.T) {
+	trie := NewEmpty()
+
+	trie.UpdateString("doe", "reindeer")
+	trie.UpdateString("dog", "puppy")
+	trie.UpdateString("dogglesworth", "cat")
+
+	exp := ethutil.Hex2Bytes("8aad789dff2f538bca5d8ea56e8abe10f4c7ba3a5dea95fea4cd6e7c3a1168d3")
+	root := trie.Hash()
+	if !bytes.Equal(root, exp) {
+		t.Errorf("exp %x got %x", exp, root)
+	}
+
+	trie = NewEmpty()
+	trie.UpdateString("A", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")
+
+	exp = ethutil.Hex2Bytes("d23786fb4a010da3ce639d66d5e904a11dbc02746d1ce25029e53290cabf28ab")
+	root = trie.Hash()
+	if !bytes.Equal(root, exp) {
+		t.Errorf("exp %x got %x", exp, root)
+	}
+}
+
+func TestGet(t *testing.T) {
+	trie := NewEmpty()
+
+	trie.UpdateString("doe", "reindeer")
+	trie.UpdateString("dog", "puppy")
+	trie.UpdateString("dogglesworth", "cat")
+
+	res := trie.GetString("dog")
+	if !bytes.Equal(res, []byte("puppy")) {
+		t.Errorf("expected puppy got %x", res)
+	}
+
+	unknown := trie.GetString("unknown")
+	if unknown != nil {
+		t.Errorf("expected nil got %x", unknown)
+	}
+}
+
+func TestDelete(t *testing.T) {
+	trie := NewEmpty()
+
+	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("5991bb8c6514148a29db676a14ac506cd2cd5775ace63c30a4fe457715e9ac84")
+	if !bytes.Equal(hash, exp) {
+		t.Errorf("expected %x got %x", exp, hash)
+	}
+}
+
+func TestEmptyValues(t *testing.T) {
+	trie := NewEmpty()
+
+	vals := []struct{ k, v string }{
+		{"do", "verb"},
+		{"ether", "wookiedoo"},
+		{"horse", "stallion"},
+		{"shaman", "horse"},
+		{"doge", "coin"},
+		{"ether", ""},
+		{"dog", "puppy"},
+		{"shaman", ""},
+	}
+	for _, val := range vals {
+		trie.UpdateString(val.k, val.v)
+	}
+
+	hash := trie.Hash()
+	exp := ethutil.Hex2Bytes("5991bb8c6514148a29db676a14ac506cd2cd5775ace63c30a4fe457715e9ac84")
+	if !bytes.Equal(hash, exp) {
+		t.Errorf("expected %x got %x", exp, hash)
+	}
+}
+
+func TestReplication(t *testing.T) {
+	trie := NewEmpty()
+	vals := []struct{ k, v string }{
+		{"do", "verb"},
+		{"ether", "wookiedoo"},
+		{"horse", "stallion"},
+		{"shaman", "horse"},
+		{"doge", "coin"},
+		{"ether", ""},
+		{"dog", "puppy"},
+		{"shaman", ""},
+		{"somethingveryoddindeedthis is", "myothernodedata"},
+	}
+	for _, val := range vals {
+		trie.UpdateString(val.k, val.v)
+	}
+	trie.Commit()
+
+	trie2 := New(trie.roothash, trie.cache.backend)
+	if string(trie2.GetString("horse")) != "stallion" {
+		t.Error("expected to have harse => stallion")
+	}
+
+	hash := trie2.Hash()
+	exp := trie.Hash()
+	if !bytes.Equal(hash, exp) {
+		t.Errorf("root failure. expected %x got %x", exp, hash)
+	}
+
+}
+
+func TestReset(t *testing.T) {
+	trie := NewEmpty()
+	vals := []struct{ k, v string }{
+		{"do", "verb"},
+		{"ether", "wookiedoo"},
+		{"horse", "stallion"},
+	}
+	for _, val := range vals {
+		trie.UpdateString(val.k, val.v)
+	}
+	trie.Commit()
+
+	before := ethutil.CopyBytes(trie.roothash)
+	trie.UpdateString("should", "revert")
+	trie.Hash()
+	// Should have no effect
+	trie.Hash()
+	trie.Hash()
+	// ###
+
+	trie.Reset()
+	after := ethutil.CopyBytes(trie.roothash)
+
+	if !bytes.Equal(before, after) {
+		t.Errorf("expected roots to be equal. %x - %x", before, after)
+	}
+}
+
+func TestParanoia(t *testing.T) {
+	t.Skip()
+	trie := NewEmpty()
+
+	vals := []struct{ k, v string }{
+		{"do", "verb"},
+		{"ether", "wookiedoo"},
+		{"horse", "stallion"},
+		{"shaman", "horse"},
+		{"doge", "coin"},
+		{"ether", ""},
+		{"dog", "puppy"},
+		{"shaman", ""},
+		{"somethingveryoddindeedthis is", "myothernodedata"},
+	}
+	for _, val := range vals {
+		trie.UpdateString(val.k, val.v)
+	}
+	trie.Commit()
+
+	ok, t2 := ParanoiaCheck(trie, trie.cache.backend)
+	if !ok {
+		t.Errorf("trie paranoia check failed %x %x", trie.roothash, t2.roothash)
+	}
+}
+
+// Not an actual test
+func TestOutput(t *testing.T) {
+	t.Skip()
+
+	base := "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+	trie := NewEmpty()
+	for i := 0; i < 50; i++ {
+		trie.UpdateString(fmt.Sprintf("%s%d", base, i), "valueeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee")
+	}
+	fmt.Println("############################## FULL ################################")
+	fmt.Println(trie.root)
+
+	trie.Commit()
+	fmt.Println("############################## SMALL ################################")
+	trie2 := New(trie.roothash, trie.cache.backend)
+	trie2.GetString(base + "20")
+	fmt.Println(trie2.root)
+}
+
+func BenchmarkGets(b *testing.B) {
+	trie := NewEmpty()
+	vals := []struct{ k, v string }{
+		{"do", "verb"},
+		{"ether", "wookiedoo"},
+		{"horse", "stallion"},
+		{"shaman", "horse"},
+		{"doge", "coin"},
+		{"ether", ""},
+		{"dog", "puppy"},
+		{"shaman", ""},
+		{"somethingveryoddindeedthis is", "myothernodedata"},
+	}
+	for _, val := range vals {
+		trie.UpdateString(val.k, val.v)
+	}
+
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		trie.Get([]byte("horse"))
+	}
+}
+
+func BenchmarkUpdate(b *testing.B) {
+	trie := NewEmpty()
+
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		trie.UpdateString(fmt.Sprintf("aaaaaaaaa%d", i), "value")
+	}
+	trie.Hash()
+}
diff --git a/ptrie/valuenode.go b/ptrie/valuenode.go
new file mode 100644
index 000000000..c593eb6c6
--- /dev/null
+++ b/ptrie/valuenode.go
@@ -0,0 +1,13 @@
+package ptrie
+
+type ValueNode struct {
+	trie *Trie
+	data []byte
+}
+
+func (self *ValueNode) Value() Node          { return self } // Best not to call :-)
+func (self *ValueNode) Val() []byte          { return self.data }
+func (self *ValueNode) Dirty() bool          { return true }
+func (self *ValueNode) Copy() Node           { return &ValueNode{self.trie, self.data} }
+func (self *ValueNode) RlpData() interface{} { return self.data }
+func (self *ValueNode) Hash() interface{}    { return self.data }