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

Improve check_merkle_tree_sorted to work with preimages of arbitrary length #104

Open
bigspider opened this issue Jan 25, 2023 · 1 comment
Assignees
Labels
enhancement New feature or request

Comments

@bigspider
Copy link
Collaborator

bigspider commented Jan 25, 2023

Currently, the call_check_merkle_tree_sorted function puts a limit on the length of the preimages in the Merkle tree that is checking; #90 increased it to 162, but Merkle trees used in PSBTs can have much longer elements (over 4kb for taproot control blocks defined in BIP-341, but potentially unlimited for future extensions or PSBT vendor-specific fields).

call_check_merkle_tree_sorted is currently keeping two consecutive elements at the time (in order to check the correct ordering), but memory limitations prevent from using this approach for larger preimages.

Ideally, we would like to stream each byte sequence only once, and still be able to detect which one is larger.
That's impossible in theory, but it's likely possible in most cases, and that might be good enough in practice.

@bigspider bigspider added the enhancement New feature or request label Jan 25, 2023
@bigspider
Copy link
Collaborator Author

A binary search and hash functions would allow to compare two PSBT keys in O(log(n/D)) passes using 2D bytes of RAM, where n is the size of the largest key, and D is a chosen constant. By hashing the concatenation of the first i blocks, one can find the index of the first block for which the two keys are not equal, and then compare them directly.

D could be chosen as large as it can fit on the device memory, in order to maximize the number of cases when the data is streamed only once.


A linear search would be easier to implement and have reasonable performance in practice (unlikely that the PSBT key length gets so large that the quadratic complexity becomes an issue any time soon).

@bigspider bigspider self-assigned this May 11, 2023
@bigspider bigspider added this to the 2.1.3 milestone May 11, 2023
@bigspider bigspider modified the milestones: 2.1.3, 2.2.0 Jun 26, 2023
@bigspider bigspider removed this from the 2.2.0 milestone Nov 7, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant