Another new `ITrie` implementation that is more eifficient and performant

[dahlia]

MerkleTrie, the only implementation of ITrie as of now, is less freedom of improvement due to the already running mainnet of Nine Chronicles. In order to improve Libplanet's own MPT performance without breaking Nine Chronicles, we should add a new implementation of ITrie with probably a different name (or we could rename MerkleTrie to LegacyMerkleTrie or such).

There are several implementation details I wish to change:

• INode.ToBencodex(): Nodes are encoded using Bencodex with no good reason. Discrimination fields should be told by just reading only the first byte.

• MerkleTrie's implementation of fragmented states (https://github.com/planetarium/libplanet/pull/1636) is just a messy cram, because it must not change the existing state root hashes.

• Key addresses are pointlessly encoded into bytes of ASCII hexadecimals of address bytes. You can hardly understand? It's not just you, as it's just nonsense. For example, address 0x636d187b4d434244a92b65b06b5e7da14b3810a9 is encoded to 36 33 36 64 31 38 37 62 34 64 34 33 34 32 34 34 61 39 32 62 36 35 62 30 36 62 35 65 37 64 61 31 34 62 33 38 31 30 61 39 with the below process:[^1]

  >>> addr = bytes.fromhex("636d187b4d434244a92b65b06b5e7da14b3810a9")
  >>> addr
  b'cm\x18{MCBD\xa9+e\xb0k^}\xa1K8\x10\xa9'
  >>> addr_hex = addr.hex()
  >>> addr_hex
  '636d187b4d434244a92b65b06b5e7da14b3810a9'
  >>> addr_hex_ascii_bytes = addr_hex.encode('ascii')
  >>> addr_hex_ascii_bytes
  b'636d187b4d434244a92b65b06b5e7da14b3810a9'
  >>> print(" ".join(map("{0:02X}".format, addr_hex_ascii_bytes)))
  36 33 36 64 31 38 37 62 34 64 34 33 34 32 34 34 61 39 32 62 36 35 62 30 36 62 35 65 37 64 61 31 34 62 33 38 31 30 61 39
  

  Every byte in such encoding only holds a single nibble, which leads to double length.

[^1]: However, we need to change BlockChain<T> as well to fix this.

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. Thank you for your contributions.