Feat/roman/tree builder

[ChickenLover]

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

[ChickenLover]

@yshekel 1) There are no rust bindings for now 2) Tree builder is just a template, so instantiations will be both in hash and in field libraries, depending on which hash it is 3) Well, if we go with the current FFI design, then we will need to reimplement the tree builder for every backend. For hash functions - yes, that will do fine, but I am not sure what to do with the tree builder in that case

[yshekel]

@yshekel

1. There are no rust bindings for now
2. Tree builder is just a template, so instantiations will be both in hash and in field libraries, depending on which hash it is
3. Well, if we go with the current FFI design, then we will need to reimplement the tree builder for every backend. For hash functions - yes, that will do fine, but I am not sure what to do with the tree builder in that case

If we can implement a generic tree builder (that is backend agnostic) then we can have the backend APIs implement only the hashes and then wrap it with the generic tree builder that calls the hashing APIs and builds the tree (and expose that to ffi in addition to hashes). I am not sure it's possible but maybe it is. Otherwise we would have to define the tree builder a backend API and have the backend implement it, per hash. Internally it can reuse templates etc. to avoid fully reimplementing like you did basically.