multiproof-rs icon indicating copy to clipboard operation
multiproof-rs copied to clipboard

Add HASH opcode

Open s1na opened this issue 5 years ago • 1 comments

Right now rebuild returns the root Node. In order to compute the root hash, the partial trie has to be walked down and up once. To improve the efficiency of verifiers we could either add a new opcode or change the semantic of the existing ones to allow the verifier to produce the correct hash once every instruction has been processed.

LEAF and EXTENSION opcodes could be modified to directly hash the node and push the hash on the stack. HASHER just reads in a hash from the sequence and doesn't need to be modified. The only question is how to handle branches, because it's not exactly clear when all the children have been added to the branch. One simple option is to introduce a HASH opcode which expects a branch node on top of stack and hashes it. There are other options too.

s1na avatar Sep 06 '19 14:09 s1na

We discussed this offline and realized another opcode is not needed. I prototyped the approach we discussed here: https://github.com/s1na/turbo-token/pull/2

s1na avatar Sep 26 '19 10:09 s1na