ApeWorX / ApeWorX/py-trie

[HexaryTrie] Can't use proof to compute updated root-hash on key removal

Open
#120 0 comments 0 reactions 0 assignees View on GitHub
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 |
| --- | --- | --- |
| ![scenario 1 `t`](https://user-images.githubusercontent.com/14125973/96266563-10d16900-0fc7-11eb-89e9-483f2b938938.png) | ![scenario 1 `proof`](https://user-images.githubusercontent.com/14125973/96266337-d49e0880-0fc6-11eb-845c-4057db220cc2.png) | ![case0 trie_after](https://user-images.githubusercontent.com/14125973/96267483-22ffd700-0fc8-11eb-8aa7-8347b2ce75e6.png) |

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 |
| --- | --- | --- |
| ![scenario 2 `t`](https://user-images.githubusercontent.com/14125973/96243274-cccd6c80-0fa4-11eb-9ed6-54678d62321a.png) | ![scenario 2 `proof`](https://user-images.githubusercontent.com/14125973/96243521-246bd800-0fa5-11eb-89b5-f9da307309c7.png) | ![case1 after](https://user-images.githubusercontent.com/14125973/96287386-24d69400-0fe2-11eb-8669-39d85db74730.png) |

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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.