[HexaryTrie] Can't use proof to compute updated root-hash on key removal
- Dominant language
- Python
- Stars
- 111
- Forks
- 54
- Avg merge
- 27m
- Merged PRs (30d)
- 1
Description
* Version: 2.0.0a4 (and below)
* Python: 3.7
* OS: linux
### What was wrong?
Given a key `k` with value `v`, in some cases it's not possible to exploit only the information provided by `get_proof(k)` to determine a new root-hash of the trie where `k` is deleted.
_(Conversely, I was not able to find a case where it's not possible to use `get_proof(k)` to determine a new root-hash after an update or an insertion of `k`.)_
### What did you expect it to do?
_Authenticated Data Structures_ usually allow users to update values in the following fashion:
1. User queries the ADS for the value of key `k`
2. ADS returns value `v` and its proof `p`
3. User computes the root-hash determined by `v` and `p` and compares it to their previously known root-hash `r` to authenticate the response. ^
5. User sends an update message to the ADS for key `k` with new value `v'`
6. **User computes the new root-hash `r'` determined by `k` and `v'` and stores it for authenticating following queries.**
_(^ In Ethereum Tries this differs a tiny bit in the way that `r` and `p` are used to determine `v` and then values are compared instead of root-hashes)_
Now, even though this library does not provide a direct method for computing a new root-hash starting from a proof and a new value, it is still possible to do so by building a "partial" trie with the nodes obtained by `get_proof()` (in a similar fashion the way `get_from_proof()` is implemented), perform the update on such trie and then retrieve its new root-hash.
Therefore it should still be possible, for a third party not storing the ADS, to perform any kind of update on `k` starting just from the proof obtained by `get_proof()`, whether a literal "update" (i.e. change of value), an insertion or a removal (obviously just in respect to `k`).
NB: I already have a initial patch for this issue (needs refining because it adds nodes also when it might not be needed), if welcome I can go ahead with a PR.
#### Code to reproduce the error
First, assume a function new_root_after_delete(root, key, proof) for retrieving the new root-hash
```python
def new_root_after_delete(root, key, proof):
trie = HexaryTrie({})
for node in proof:
trie._persist_node(node)
trie.root_hash = root
trie.delete(key)
return trie.root_hash
```
I was only able to find two scenarios in which this bug arises, and in particular only when the nodes are long enough to get hashed.
1. k is targeted to a branch node B having only one child node C:
In this case the removal of `k` causes `B` to be removed and `C` to collapse upwards, therefore `C` should be provided in the proof for `k`, to be able to update its remaining key and update hashes upwards accordingly.
```python
t = HexaryTrie({}, prune=True)
t[b"\x00\x00"] = b"a"*30
t[b"\x00"] = b"b"*30
# client side
prev_root = t.root_hash
key_to_del = b"\x00"
proof = t.get_proof(key_to_del)
new_root_after_delete(prev_root, key_to_del, proof)
```
```python
Traceback (most recent call last):
File "", line 1, in
File "", line 6, in new_root_after_delete
File "/home/matteo/src/py-trie/trie/hexary.py", line 86, in wrapped
fn(trie_self, *args)
File "/home/matteo/src/py-trie/trie/hexary.py", line 356, in delete
self._raise_missing_node(exc, key)
File "/home/matteo/src/py-trie/trie/hexary.py", line 302, in _raise_missing_node
raise MissingTrieNode(exception.args[0], self.root_hash, key, prefix=None) from exception
trie.exceptions.MissingTrieNode: Trie database is missing hash HexBytes('0x1fb7fdc5aae3c3f57d3e9cfa86bceddc19de02cf587c14a326895f451167c4af') needed to look up node at prefix None, when searching for key HexBytes('0x00') at root hash HexBytes('0x8374694098724fa740337bc9b496646c30219e9c5c87285b88e76d987d43a56d')
```
A visual representation will make it clear:
| `t` | `proof` | `proof` after deletion |
| --- | --- | --- |
|  |  |  |
In this example the node `C` corresponds to `1fb7fd`, which is not included in `proof`, that then collapses to `13ef40` after the removal of `k` (which, for this trivial example it also corresponds to the whole trie).
2. k is targeted to a leaf node L which is child of a branch node B (with no value associated) and, in respect to B, L is the only sibling of some other node S:
In this case, the removal of `k` causes `L` to be removed, and since `B` has no value associated with it `B` is removed too, causing `S` to collapse upwards, recreating the first scenario. Therefore `S` should be provided in the proof for `k`.
```python
t = HexaryTrie({}, prune=True)
t[b"\x00\x00"] = b"a"*30
t[b"\x00\x01"] = b"b"*30
# client side
prev_root = t.root_hash
key_to_del = b"\x00\x00"
proof = t.get_proof(key_to_del)
new_root_after_delete(prev_root, key_to_del, proof)
```
```python
Traceback (most recent call last):
File "", line 1, in
File "", line 6, in new_root_after_delete
File "/home/matteo/src/py-trie/trie/hexary.py", line 86, in wrapped
fn(trie_self, *args)
File "/home/matteo/src/py-trie/trie/hexary.py", line 356, in delete
self._raise_missing_node(exc, key)
File "/home/matteo/src/py-trie/trie/hexary.py", line 302, in _raise_missing_node
raise MissingTrieNode(exception.args[0], self.root_hash, key, prefix=None) from exception
trie.exceptions.MissingTrieNode: Trie database is missing hash HexBytes('0x873d300c30dc3b1d383643935e480a8ca36821ffd3803f78432a345a37e1a440') needed to look up node at prefix None, when searching for key HexBytes('0x0000') at root hash HexBytes('0xc773de0ac200c0f6f3809b2bb7b03ca1e2974068e75b1bab4b48a6a6a2a2d179')
```
Visual representation:
| `t` | `proof` | `proof` after deletion |
| --- | --- | --- |
|  |  |  |
In this example the node `S` corresponds to `873d30` which is not included in `proof`. After the removal of `k`, `S` collapses to `ef3798` (which as before, for this trivial example is also the whole trie).
I collapsed the code for convenience, since this issue is already quite long. I hope this helps, let me know if I can start a PR or provide any additional input.
Thanks
Contributor guide
Assessment
This issue has not been assessed yet.