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

Add snippet for set-equality of two u64 lists #114

Open
Sword-Smith opened this issue Jul 19, 2024 · 0 comments
Open

Add snippet for set-equality of two u64 lists #114

Sword-Smith opened this issue Jul 19, 2024 · 0 comments
Assignees

Comments

@Sword-Smith
Copy link
Contributor

Sword-Smith commented Jul 19, 2024

Add a snippet where one list (assumed to be sorted and containing unique elements) is compared to another list which is not sorted and may contain duplicates. The snippet should either return a boolean indicating set-equality or crash the VM if set equality does not hold.

The snippet can be implemented using logarithmic derivatives of the running product, where multiplicities are divined.

The mathematical expressions that are compared should be:

$ld=\sum_{i}\frac{m_i}{\alpha - l_i}$, and

$ld=\sum_{j}\frac{1}{\alpha - l_j}$

where $m_i$ is the divined-in multiplicity. $m_i$ should be constrained somehow, to either a u32 or to something smaller yet.

This snippet can be used together with that defined in #111 in neptune-core's removal record integrity program to verify that the divined-in chunk indices are correct.

@Sword-Smith Sword-Smith self-assigned this Jul 19, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant