Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Trie: verifyProof() error on nested embeded nodes / batch() function UX issues #1055

Closed
Lion17 opened this issue Feb 28, 2019 · 10 comments
Closed

Comments

@Lion17
Copy link

Lion17 commented Feb 28, 2019

When you try to call the verifyProof function for a node that is embedded in another node, which in turn is also embedded, an error occurs.

To reproduce:

var Trie = require('merkle-patricia-tree')

trie = new Trie()
var ops = [
   { type: 'put', key: 'dog', value: 'puppy' }
 , { type: 'put', key: 'doge', value: 'coin' }
]

trie.batch(ops,
 () => {
  Trie.prove(trie, 'doge', function (err, prove) {
   if (err) console.log(err)
   else
    Trie.verifyProof(trie.root, 'doge', prove, function (err, value) {
     if (err) console.log(err)
     else console.log(value.toString())
    })
  })
 }
)

Output:

node proof.js
Error: Unexpected end of proof
at Object.exports.verifyProof (/home/local/tmp/node_modules/merkle-patricia-tree/proof.js:122:6)
at Function.verifyProof (/home/local/tmp/node_modules/merkle-patricia-tree/index.js:56:32)
at /home/local/tmp/proof.js:14:10
at /home/local/tmp/node_modules/merkle-patricia-tree/proof.js:33:5
at /home/local/tmp/node_modules/merkle-patricia-tree/baseTrie.js:520:18
at /home/local/tmp/node_modules/async/dist/async.js:473:16
at iteratorCallback (/home/local/tmp/node_modules/async/dist/async.js:1064:13)
at /home/local/tmp/node_modules/async/dist/async.js:969:16
at Object._return [as return] (/home/local/tmp/node_modules/merkle-patricia-tree/baseTrie.js:545:13)
at processNode (/home/local/tmp/node_modules/merkle-patricia-tree/baseTrie.js:325:34)

The reason is that only the variant with one level of embedded nodes is considered. This can be seen in file proof.js:82, where the key length is compared with 1, while with multiple nesting of nodes the key will be longer. In our case, it is equal to 2.

@holgerd77
Copy link
Member

Same here, PR would be great together with a test case. 😄

@holgerd77
Copy link
Member

holgerd77 commented Dec 8, 2020

Tried to make this example run by updating the code from above to the latest MPT v4 version, came up with to be run in ts-node:

import { BaseTrie as Trie } from 'merkle-patricia-tree'
import { BatchDBOp } from 'merkle-patricia-tree/db'
const trie = new Trie()

async function run() {
  const ops = [
    { type: 'put', key: Buffer.from('dog'), value: Buffer.from('puppy') },
    { type: 'put', key: Buffer.from('doge'), value: Buffer.from('coin') }
  ] as BatchDBOp[]

  await trie.batch(ops)
  const proof = await Trie.prove(trie, Buffer.from('doge'))
  const value = await Trie.verifyProof(trie.root, Buffer.from('doge'), proof)
  return value
}

run()
.then((value) => {
  console.log(value)
})
.catch((error) => {
    console.log(error)
})

This is still not running and we should give this use case another look (and also have a look at the bug here).

  1. TypeScript complained about the constant string type definitions in BatchDBOp which triggered a cast to BatchDBOp to be needed. We might want to generally change the types to be just string types //cc @ryanio ?
  2. This rose the need to import BatchDBOp, was also trickier than I thought, the import from above actually doesn't work yet

@holgerd77 holgerd77 changed the title verifyProof error on nested embeded nodes verifyProof error on nested embeded nodes / batch() function UX issues Dec 8, 2020
@zmitton
Copy link
Contributor

zmitton commented Dec 27, 2020

Original error should have been taken care of when proof.js was eliminated in favor of basetrie.js proof implementation.

Is the issue you're seeing now

(1) an error in the way the trie is getting build, or
(2) an error during the verification process
The later is probably something I should look at but I doubt its the case

@holgerd77
Copy link
Member

@zmitton thanks for the answer, can't remember TBH. Will just leave open here for someone to re-evaluate at some point.

@holgerd77
Copy link
Member

@ryanio do you have got some insight if this might still be an issue? 🤔

@holgerd77 holgerd77 changed the title verifyProof error on nested embeded nodes / batch() function UX issues Trie: verifyProof() error on nested embeded nodes / batch() function UX issues Jun 11, 2021
@ryanio
Copy link
Contributor

ryanio commented Jun 11, 2021

I am not familiar with this issue yet but I will give the example scripts a try to see what could be going on and will report back.

I'll also take a look at the BatchDBOp[] type issue, I'm surprised that ts was complaining about the string type as it seems to be correct, I'll see if there's something we can do to ease development when trying to use trie.batch(opts) without needing any fancy casting.

@ryanio ryanio self-assigned this Jun 11, 2021
@zmitton
Copy link
Contributor

zmitton commented Jun 29, 2021

The written error reported is "unexpected end of proof", and its coming from the proof.js file. Both that error meseage and the file have been eliminated. I believe I wrote a similar situation to return "missing node error".

But now that I look through the code, I cant find that error anymore. I think it should be somewhere around here:

value = await this.db.get(node as Buffer)

Note: Although the behavior of the tree may be to return null when a missing key is looked up, the behavior of the underlaying db (not part of the API!) should return an error when a missing key is looked up. Two completely different things!

something like

    if (value) {
      foundNode = decodeNode(value)
    } else{
      return new Error("missing trie node")
    }

I could be wrong. I dont have time to work on this but I hope the information is helpful

@acolytec3
Copy link
Contributor

acolytec3 commented Jul 23, 2021

The written error reported is "unexpected end of proof", and its coming from the proof.js file. Both that error meseage and the file have been eliminated. I believe I wrote a similar situation to return "missing node error".

But now that I look through the code, I cant find that error anymore. I think it should be somewhere around here:

value = await this.db.get(node as Buffer)

Note: Although the behavior of the tree may be to return null when a missing key is looked up, the behavior of the underlaying db (not part of the API!) should return an error when a missing key is looked up. Two completely different things!

something like

    if (value) {
      foundNode = decodeNode(value)
    } else{
      return new Error("missing trie node")
    }

I could be wrong. I dont have time to work on this but I hope the information is helpful

I don't know that I fully understand the logic of why the db not finding a node should generate an error versus a null value but as here our code does check for the key not found error condition in the db and then just returns null to the trie module in such cases. It throws on other errors.

@ethereumjs ethereumjs deleted a comment Jan 13, 2022
@holgerd77
Copy link
Member

Is this still an issue or can we close after 3 years? 😅

Lol. 😛

@ryanio
Copy link
Contributor

ryanio commented Jan 13, 2022

I think this is okay now, we might have solved it as part of #1368, I ran the example script in #1055 (comment) and got back a valid value: <Buffer 63 6f 69 6e>

If someone would like to follow up please open a new issue with a reproducible script so we can help.

@ryanio ryanio closed this as completed Jan 13, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

5 participants