You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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:
User queries the ADS for the value of key k
ADS returns value v and its proof p
User computes the root-hash determined by v and p and compares it to their previously known root-hash r to authenticate the response. ^
User sends an update message to the ADS for key k with new value v'
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
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.
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.
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
The text was updated successfully, but these errors were encountered:
What was wrong?
Given a key
k
with valuev
, in some cases it's not possible to exploit only the information provided byget_proof(k)
to determine a new root-hash of the trie wherek
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 ofk
.)What did you expect it to do?
Authenticated Data Structures usually allow users to update values in the following fashion:
k
v
and its proofp
v
andp
and compares it to their previously known root-hashr
to authenticate the response. ^k
with new valuev'
r'
determined byk
andv'
and stores it for authenticating following queries.(^ In Ethereum Tries this differs a tiny bit in the way that
r
andp
are used to determinev
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 wayget_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 byget_proof()
, whether a literal "update" (i.e. change of value), an insertion or a removal (obviously just in respect tok
).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-hashI 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 nodeB
having only one child nodeC
:In this case the removal of
k
causesB
to be removed andC
to collapse upwards, thereforeC
should be provided in the proof fork
, to be able to update its remaining key and update hashes upwards accordingly.A visual representation will make it clear:
t
proof
proof
after deletionIn this example the node
C
corresponds to1fb7fd
, which is not included inproof
, that then collapses to13ef40
after the removal ofk
(which, for this trivial example it also corresponds to the whole trie).2.
k
is targeted to a leaf nodeL
which is child of a branch nodeB
(with no value associated) and, in respect toB
,L
is the only sibling of some other nodeS
:In this case, the removal of
k
causesL
to be removed, and sinceB
has no value associated with itB
is removed too, causingS
to collapse upwards, recreating the first scenario. ThereforeS
should be provided in the proof fork
.Visual representation:
t
proof
proof
after deletionIn this example the node
S
corresponds to873d30
which is not included inproof
. After the removal ofk
,S
collapses toef3798
(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
The text was updated successfully, but these errors were encountered: