Get wrong root hash by cita-trie

[mohanson]

When get the root hash from an empty trie, cita-trie might returns the wrong hash. See codes bellows:

use cita_trie::codec::RLPNodeCodec;
use cita_trie::db::MemoryDB;
use cita_trie::trie::{PatriciaTrie, Trie};
use hex::FromHex;

use ethereum_types::*;
use keccak_hasher::KeccakHasher;
use kvdb::DBValue;
use memorydb;
use patricia_trie::{TrieFactory, TrieSpec};
use patricia_trie_ethereum::RlpCodec;

fn cita_empty_trie_root() {
    let mut memdb = MemoryDB::new();
    let mut trie = PatriciaTrie::new(&mut memdb, RLPNodeCodec::default());
    println!("{:?}", hex::encode(trie.root().unwrap()));
}

fn parity_empty_trie_root() {
    let factory = TrieFactory::<_, RlpCodec>::new(TrieSpec::Generic);
    let mut memdb = memorydb::MemoryDB::<KeccakHasher, DBValue>::new();
    let mut root = H256::default();
    let mut t = factory.create(&mut memdb, &mut root);
    println!("{:?}", t.root());
}

fn main() {
    cita_empty_trie_root();
    parity_empty_trie_root();
}

outputs:
root_hash_by_cita_trie: 0xbc2071a4de846f285702447f2589dd163678e0972a8a1b0d28b04ed5c094547f
root_hash_by_parity: 0x56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421

The hash gives by parity equals with go-Ethereum: https://github.com/ethereum/go-ethereum/blob/master/trie/trie.go#L32, so I thought there are some bugs in cita-trie.

[mohanson]

[dependencies]
cita_trie = { path = "/src/cita-trie" }
hex = "*"
# parity_ethereum = { path = "/src/parity-ethereum" }
patricia-trie = "0.3.0"
patricia-trie-ethereum = { path = "/src/parity-ethereum/util/patricia-trie-ethereum" }
memorydb = "*"
ethereum-types = "*"
keccak-hasher = { path = "/src/parity-ethereum/util/keccak-hasher" }
kvdb = "0.1"

[mohanson]

Full tests should be added. See: https://github.com/ethereum/tests/blob/develop/TrieTests

I will push a PR contains the tests in the near future.

[yejiayu]

CITA-trie uses sha3 by default, and Keccak results are different.

[yejiayu]

I tested it with keccak and the results were correct.

[mohanson]

OK.

[mohanson]

I have switched to keccak and take a full test,
assert failed at: https://github.com/ethereum/tests/blob/develop/TrieTests/trieanyorder.json#L8

and paniced at https://github.com/ethereum/tests/blob/develop/TrieTests/trietest.json#L97.

thread 'main' panicked at 'index out of bounds: the len is 16 but the index is 16', C:\src\cita-trie\src\node.rs:71:10
note: Run with `RUST_BACKTRACE=1` for a backtrace.

[mohanson]

The hash algorithm used by this branch https://github.com/cryptape/cita-trie/tree/keccak has been modified to keccak and full test have been added(tests will fail at now).

[cryptowen]

I have switched to keccak and take a full test,
assert failed at: https://github.com/ethereum/tests/blob/develop/TrieTests/trieanyorder.json#L8

and paniced at https://github.com/ethereum/tests/blob/develop/TrieTests/trietest.json#L97.

thread 'main' panicked at 'index out of bounds: the len is 16 but the index is 16', C:\src\cita-trie\src\node.rs:71:10
note: Run with `RUST_BACKTRACE=1` for a backtrace.

Found some implementation bugs:

1. For node where the child node's encoded bytes length is less than 32, the node should be encoded as a nested list other than treating the encoded child node as the value. For example, for node ExtentionNode(shared_nibbles, LeafNode(prefix, value)), the encode method now is RLP([HP(shared_nibbles), RLP([HP(prefix), value])]), which should be RLP([HP(shared_nibbles), [HP(prefix), value]])
2. The delete_at method does not reformat the trie when needed. For example, after the deletion, if a branch node only have one branch, the node should be deleted.

I fixed 1 and still working on 2.