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

A potential bug: Some leaves are MISSED when we LOAD StandardIndexedTree #3423

Open
coldstar1993 opened this issue Nov 25, 2023 · 0 comments

Comments

@coldstar1993
Copy link

issue code:
https://github.com/AztecProtocol/aztec-packages/blob/4a1e9c32b1aae52811e348d67cab468cdab89bd6/yarn-project/merkle-tree/src/standard_indexed_tree/standard_indexed_tree.ts#L245C47-L245C76

gte, lte are compared by characters (numbers) in the ASCII character set. So here is a potential bug that it would miss some Leaf when loadTree.
For example: When we load from levelDB a tree called NULLIFIER_TREE of height 16 (i.e, 2n ** BigInt(this.getDepth()) = 65536), the runtime code is as below:

this.db
        .createReadStream({
           gte: 'NULLIFIER_TREE:LEAF:0'
           lte: 'NULLIFIER_TREE:LEAF:65536'
         });

then, you could find that many leaves whose key starts with 'NULLIFIER_TREE:LEAF:7'/'NULLIFIER_TREE:LEAF:8'/'NULLIFIER_TREE:LEAF:9' will be missed.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
Status: Todo
Development

No branches or pull requests

1 participant