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

The constraint for mpt key is not sound #24

Open
noel2004 opened this issue Apr 7, 2023 · 1 comment
Open

The constraint for mpt key is not sound #24

noel2004 opened this issue Apr 7, 2023 · 1 comment
Labels
bug Something isn't working

Comments

@noel2004
Copy link
Member

noel2004 commented Apr 7, 2023

Currently for N bits in the key as path part, we apply the constraint: resident * 2^N + path

The path part is constrainted to less than 2^N, while we have no constraint on resident so malice provider would be easy to manufacture a field setting part of its low N bit non-zero when being multiplied with 2^N, so as to detour the path part.

To resolve this issue, Additional constraint to restrict resident * 2^N less than Fp is required. A simple way is constraint resident not larger than 2^128 and N less than a suitable value, for example, 120. (Consider we have as much as 2^48 keys, we need ~100 bits, or say 2^100 slots avaliable to kept the chance of collision low enough according to the birthday principle)

@noel2004
Copy link
Member Author

noel2004 commented Apr 8, 2023

This also means we should truncated the key as Hash(keypreimage) % 2^128

@noel2004 noel2004 added the bug Something isn't working label Apr 8, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
Projects
None yet
Development

No branches or pull requests

1 participant