# Updates:
## Hashing
- Added SpongeHasher class
- Can be used to accept any hash function as an argument
- Absorb and squeeze are now separated
- Memory management is now mostly done by SpongeHasher class, each hash
function only describes permutation kernels
## Tree builder
- Tree builder is now hash-agnostic.
- Tree builder now supports 2D input (matrices)
- Tree builder can now use two different hash functions for layer 0 and
compression layers
## Poseidon1
- Interface changed to classes
- Now allows for any alpha
- Now allows passing constants not in a single vector
- Now allows for any domain tag
- Constants are now released upon going out of scope
- Rust wrappers changed to Poseidon struct
## Poseidon2
- Interface changed to classes
- Constants are now released upon going out of scope
- Rust wrappers changed to Poseidon2 struct
## Keccak
- Added Keccak class which inherits SpongeHasher
- Now doesn't use gpu registers for storing states
To do:
- [x] Update poseidon1 golang bindings
- [x] Update poseidon1 examples
- [x] Fix poseidon2 cuda test
- [x] Fix poseidon2 merkle tree builder test
- [x] Update keccak class with new design
- [x] Update keccak test
- [x] Check keccak correctness
- [x] Update tree builder rust wrappers
- [x] Leave doc comments
Future work:
- [ ] Add keccak merkle tree builder externs
- [ ] Add keccak rust tree builder wrappers
- [ ] Write docs
- [ ] Add example
- [ ] Fix device output for tree builder
---------
Co-authored-by: Jeremy Felder <jeremy.felder1@gmail.com>
Co-authored-by: nonam3e <71525212+nonam3e@users.noreply.github.com>
# This PR
1. Adds C++ API
2. Renames a lot of API functions
3. Adds inplace poseidon2
4. Makes input const at all poseidon functions
5. Adds benchmark for poseidon2
## Brief description
This PR adds pre-computation to the MSM, for some theory see
[this](https://youtu.be/KAWlySN7Hm8?si=XeR-htjbnK_ySbUo&t=1734) timecode
of Niall Emmart's talk.
In terms of public APIs, one method is added. It does the
pre-computation on-device leaving resulting data on-device as well. No
extra structures are added, only `precompute_factor` from `MSMConfig` is
now activated.
## Performance
While performance gains are for now often limited by our inflexibility
in choice of `c` (for example, very large MSMs get basically no speedup
from pre-compute because currently `c` cannot be larger than 16),
there's still a number of MSM sizes which get noticeable improvement:
| Pre-computation factor | bn254 size `2^20` MSM, ms. | bn254 size
`2^12` MSM, size `2^10` batch, ms. | bls12-381 size `2^20` MSM, ms. |
bls12-381 size `2^12` MSM, size `2^10` batch, ms. |
| ------------- | ------------- | ------------- | ------------- |
------------- |
| 1 | 14.1 | 82.8 | 25.5 | 136.7 |
| 2 | 11.8 | 76.6 | 20.3 | 123.8 |
| 4 | 10.9 | 73.8 | 18.1 | 117.8 |
| 8 | 10.6 | 73.7 | 17.2 | 116.0 |
Here for example pre-computation factor = 4 means that alongside each
original base point, we pre-compute and pass into the MSM 3 of its
"shifted" versions. Pre-computation factor = 1 means no pre-computation.
GPU used for benchmarks is a 3090Ti.
## TODOs and open questions
- Golang APIs are missing;
- I mentioned that to utilise pre-compute to its full potential we need
arbitrary choice of `c`. One issue with this is that pre-compute will
become dependent on `c`. For now this is not the case as `c` can only be
a power of 2 and powers of 2 can always share the same pre-computation.
So apparently we need to make `c` a parameter of the precompute function
to future-proof it from a breaking change. This is pretty unnatural and
counterintuitive as `c` is typically chosen in runtime after pre-compute
is done but I don't really see another way, pls let me know if you do.
UPD: `c` is added into pre-compute function, for now it's unused and
it's documented how it will change in the future.
Resolves https://github.com/ingonyama-zk/icicle/issues/147
Co-authored with @ChickenLover
---------
Co-authored-by: ChickenLover <romangg81@gmail.com>
Co-authored-by: nonam3e <timur@ingonyama.com>
Co-authored-by: nonam3e <71525212+nonam3e@users.noreply.github.com>
Co-authored-by: LeonHibnik <leon@ingonyama.com>
## Describe the changes
This PR:
- Moves common crate attributes to the workspace Cargo.toml.
- Adds a manual release flow for bumping, tagging, and draft release
This PR is a compilation of small improvements
- Lock bindgen version for `icicle-cuda-runtime`
- Add an error message when trying to build on Mac (or any non
windows/linux machine)
- Add documentation and template files for adding new curve
- Add documentation on _params.cuh contents
- Add the script to bump all the rust crates versions to the same
version
Resolves#313
* BW scalar field is now the same as BLS base field
* add poseidon
* add merkle tree builder
* poseidon rust bindings
* implement rust bindings
* add doc comments
* remove global poseidon constants
* add custom constants API and script for generating new constants
* add the rest of the curves for poseidon
* add all the curves for real
* misname bls12-377
* typo
* partial rounds
* minor fixes
* small tweak for big performance boost
* add CHK_INIT_IF_RETURN
---------
Co-authored-by: DmytroTym <dmytrotym1@gmail.com>
* BW scalar field is now the same as BLS base field
* add poseidon
* add merkle tree builder
* poseidon rust bindings
* implement rust bindings
* add doc comments
* remove global poseidon constants
* add custom constants API and script for generating new constants
* add the rest of the curves for poseidon
* add all the curves for real
* misname bls12-377
* typo
* partial rounds
* minor fixes
* small tweak for big performance boost
* add CHK_INIT_IF_RETURN
---------
Co-authored-by: DmytroTym <dmytrotym1@gmail.com>
* Safer smart pointer that covers host and device
* Fixed MSM test
* Scalars and points in MSM are non-mutable in all cases
* change mont API (#332)
* Some Rust doc comments
---------
Co-authored-by: ChickenLover <Romangg81@gmail.com>
* fix memory error in single_stage_multi_reduction_kernel (#235)
* refactor
* refactor
* revert
* refactor: clang format
* Update icicle/appUtils/msm/msm.cu
* Added separate device context struct, returned lde
* wip - msm and eq
* added lde to cmake
* Montgomery param added in lde.cu mul function
* fixed on_device for ntt and lde
* CamelCase
* fixed msm_test, int unification, google guilde
* wip - ntt crash debugging
* async MSM with a rust wrapper
* wip ntt tests with corretness
* hotfix for correctness > 2^9
* wip on device inout mixing with correctness
* cleanup
* preserving twiddles after first call
* fixed twiddles preserving
* formatting
* removed some printing
* disable ecntt temporarily
* format
* rust fmt
* exclude target from format
* passing ntt after merge
* hotfix for linking issue
* format
* format
* draft of pr comments + correctness restored
* wip refactor + format
* domain wip
* rust format
* Merged feature branch in and Rust MSM correctness
* rust build for correct curve
* Slowdown fixed by passing release flag to cmake
* WIP field and curve
* still wip field and curve
* field and curve in rust 1.0
* Refactored rust into several crates
* Arkworks is now an option, bn254 crate created
* Rust msm and ntt wip
* A version of rust msm done, cuda runtime wrapped
* refactor rust by creating a curve folder
* vec_ops instead of lde for now
* format
---------
Co-authored-by: ImmanuelSegol <3ditds@gmail.com>
Co-authored-by: Vitalii <vitalii@ingonyama.com>
