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

Saving multiplications in the last round of optimized poseidon. #4

Open
krakhit opened this issue Aug 11, 2022 · 0 comments
Open

Saving multiplications in the last round of optimized poseidon. #4

krakhit opened this issue Aug 11, 2022 · 0 comments
Labels
enhancement New feature or request good first issue Good for newcomers

Comments

@krakhit
Copy link

krakhit commented Aug 11, 2022

filecoin-Poseidon_optimized_full_filecoin

In the Optimised poseidon we can use a small change that reduces unnecessary multiplications. This was noticed by @mickeyasa

Observation: In the last round: notice that after the S box operation, the full MDS matrix is used to generate all the elements in the state of width $t$. After that the round ends and the element with index state[1] is output as the digest.

Observation: There is no need to compute all the state elements in the MDS multiplication, in the last round.

Proposal: after the S box in the last round, only compute the element with index 1 in
state'= state^(transpose).MDS
i.e just compute state'[1]
since only the digest is needed, and other elements do not matter for the digest or another sequential hash.

@krakhit krakhit added enhancement New feature or request good first issue Good for newcomers labels Aug 11, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request good first issue Good for newcomers
Projects
None yet
Development

No branches or pull requests

1 participant