3
$\begingroup$

Assume we have 4 values: $v_1,v_2,v_3$ and $v_4$. We construct a Merkle tree on top of them such that the values are leaves of the tree.

I send the values and the tree to an untrusted server. But I keep the root of the tree locally. Later on I want to modify (or replace) $v_4$ with new value $v_5$. Note that I Do NOT want to insert or delete any node. So I first verify the correctness of $v_4$ and then replace $v_4$ with $v_5$ and generate the corresponding values (to update the tree). The update operation may take many times


Question: Would regular Merkle tree suffice to check the correctness of the values and the update operation?

In other words, can the server do any replay,... attack in the above scenario?

$\endgroup$
1
$\begingroup$

What do you mean that you keep the root of the merkle tree locally? Is the merkle tree signed?

If i understand what you are saying correctly, then the server can choose not to display to the public the changes you have made and keep presenting the merkle tree for the values before you updated them.

Even if you sign the merkle tree the server can still do that. However it cannot arbitrarily change the files. Only use old values.

$\endgroup$
  • $\begingroup$ Thank you for the answer. Let me explain in more detail. There is only two parties. Data owner and the server. By "keeping the root locally" I meant the digest (or the hash value of the tree's root). So The data owner keeps it locally to verify the correctness. The data owner issues modification to a value in the tree. And it verifies the correctness of update. $\endgroup$ – user153465 Feb 8 '16 at 14:15
  • $\begingroup$ Is the merkle hash signed? Because if not the server can pretty much do whatever it likes. Except if by "only two parties" you mean that the server can only try to trick the original data owner and not someone else. $\endgroup$ – mandragore Feb 8 '16 at 14:39
  • $\begingroup$ How? when a copy of the hash root is "Kept by the client". The signature is required when " everything is outsourced". $\endgroup$ – user153465 Feb 8 '16 at 14:42
  • $\begingroup$ If you only need to worry about the server sending altered data to the original data owner then i think you are ok. As long as you have the latest value of the merkle root, the server cannot change the values without you noticing. $\endgroup$ – mandragore Feb 8 '16 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.