-
Notifications
You must be signed in to change notification settings - Fork 1
Open
Description
We should implement the optimizations described in the white paper.
These optimizations boil down to two steps:
- Swap the order of the linear and ARC layers, and pre-calculate the action of the MDS matrix on the round constants.
- Factorize the MDS matrix into a pre-sparse matrix and a sparse matrix. Their action on the state vector can be calculated in an efficient manner using sparse matrix algorithms.
(see appendix B of the white paper: https://eprint.iacr.org/2019/458.pdf)
This should also include a robust test suite to ensure the optimized hash implementation matches with the naiive "unoptimized" implementation.
See:
- Python implementation: https://github.com/ingonyama-zk/poseidon-hash/blob/1b72e87238e95d7ed8be63bd7c231b1d3a7936f3/poseidon/hash.py#L144
- Optimized reference implementation: https://extgit.iaik.tugraz.at/krypto/hadeshash/-/blob/master/code/poseidonperm_x3_64_24_optimized.sage
- Rust implementation: https://github.com/filecoin-project/neptune/blob/2b11f0ce69f52aa9594f250baa658bfe2d349ac3/src/poseidon.rs#L389
- The filecoin specification: https://spec.filecoin.io/algorithms/crypto/poseidon/#section-algorithms.crypto.poseidon.optimized-poseidon
Reactions are currently unavailable
Metadata
Metadata
Assignees
Labels
No labels