The different actions between BinaryTrie and HexaryTrie

[hwwhww]

• Version: 1.1.0 or the latest commit (4b78035)
• Python: 3.6
• OS: osx

What was wrong?

When I was trying to switch the transaction and receipt trie from HexaryTrie to BinaryTrie for ShardingVM (ethereum/py-evm#331), I found that the APIs results of these two tries are slightly different in dealing not-found-in-dict.

HexaryTrie returns BLANK_NODE

py-trie/trie/hexary.py

Lines 69 to 79 in 4b78035

	def _get(self, node, trie_key):
	node_type = get_node_type(node)
	if node_type == NODE_TYPE_BLANK:
	return BLANK_NODE
	elif node_type in {NODE_TYPE_LEAF, NODE_TYPE_EXTENSION}:
	return self._get_kv_node(node, trie_key)
	elif node_type == NODE_TYPE_BRANCH:
	return self._get_branch_node(node, trie_key)
	else:
	raise Exception("Invariant: This shouldn't ever happen")

BinaryTrie returns None

py-trie/trie/binary.py

Lines 57 to 86 in 4b78035

	def _get(self, node_hash, keypath):
	"""
	Note: keypath should be in binary array format, i.e., encoded by encode_to_bin()
	"""
	# Empty trie
	if node_hash == BLANK_HASH:
	return None
	nodetype, left_child, right_child = parse_node(self.db[node_hash])
	# Key-value node descend
	if nodetype == LEAF_TYPE:
	if keypath:
	return None
	return right_child
	elif nodetype == KV_TYPE:
	# Keypath too short
	if not keypath:
	return None
	if keypath[:len(left_child)] == left_child:
	return self._get(right_child, keypath[len(left_child):])
	else:
	return None
	# Branch node descend
	elif nodetype == BRANCH_TYPE:
	# Keypath too short
	if not keypath:
	return None
	if keypath[:1] == BYTE_0:
	return self._get(left_child, keypath[1:])
	else:
	return self._get(right_child, keypath[1:])

What did you expect it to do?

Code to reproduce the error

from trie import (
    BinaryTrie,
    HexaryTrie,
)


hexary_trie = HexaryTrie(db={})
assert b'hello' not in hexary_trie

binary_trie = BinaryTrie(db={})
assert b'hello' not in binary_trie

result:

Traceback (most recent call last):
  File "hello.py", line 16, in <module>
    assert b'hello' not in binary_trie
AssertionError

^^^^ That's false.

I replaced None with BLANK_NODE in trie._get() function, and then the tests in py-evm are passed.

I'm afraid that I may break BinaryTrie, so I wanna check with @NIC619, could I simply replace None with BLANK_NODE in BinaryTrie._get() function?

[pipermerriam]

Looks like we may want to update HexaryTrie to return None instead of BLANK_NODE?