Implements: #29 #32

The implementation is optimized for 2 inputs and width 5. Further reference can be found on: https://github.com/dusk-network/documentation/issues/26

In order to generalize over different tree types, we need a structure that generalize over different entities that we want to store, and the length of the proof branches.

The goal is to be able to write PoseidonTree<Note>, PoseidonTree<Nullifier> and specify the branch depth.

PoseidonTree<T> needs T to implement the trait AsScalar, which calculates a scalar based on the type.

This PR includes work to close the following issues:

• [x] Refactor actual lib to work with plonk including the sponge hash. Closes #5
• [x] Add merkle tree hashing logic for Scalar and Variable as a gadget. Closes #9
• [x] Implement the merkle-tree proof generator as a gadget to use in the rest of libs where we need to perform merkle openning proofs. Closes #10
• [x] Implement needed Kelvin-related Traits. Closes #12
• [x] Implement From<Branch> forPoseidonBranch`. Close #13
• [x] Create a wrapping type over Scalar to define the Content trait over it. Closes #14
• [x] Finnish up documentation of the library. Closes #3
• [x] Refactor auto-doc uploads to gh-pages. Closes #15

Current master is broken since Poseidon cannot be build using "canon" as feature.

Most likely it has to do with some breaking change in the dependencies that weren't using proper semver.

We need to be able to implement/derive Canon for the trees that we use in our Smart Contracts. Therefore this crate needed a refactor so that the Annotations and Tree structures that it exports carry the Canon traits implemented propperly.

• Removed legacy trait implementations such as kelvin::Content , ByteHash & others which have been deprecated.
• Enforce that PoseidonTree and PoseidonBranch store types which implement Canon<canonical::Store>
• Refactor all of the trait implementations to have Canon implemented.
• Fixed & refactored the extend_storage_scalar macro so that it derives Canon.
• Refactored the error handling to use correctly the Store::InvalidEncoding cannonical error type.
• Removed the Associative trait bound for PoseidonTree & PoseidonBranch & PoseidonIterator.
• Remove Blake2b in favor of canon_host::MemStore.

Closes #79

IMPORTANT

This PR can not be merged until:

• kelvin integration with canonical/port to no_std gets released. See this
• kelvin being no_std. See this

Will replace the paths by the crates.io versions once we start the bumping cascade which is blocked by the issues mentioned above.

We should move to Rust 2018 module definition also in Poseidon.

Most importantly, we have to fix the module path of the sponge_hash function. Currently we have:

use poseidon252::sponge::sponge::sponge_hash;

Where sponge is written three time, that's ridiculous. It's starting to spread in all our repos since we're using a lot the sponge's hash function; that's why we need to refactor as soon is doable.

The idea would be having something like:

use poseidon252::sponge::hash;

The same is applying for the gadget, so instead of:

use poseidon252::sponge::sponge::sponge_hash_gadget

it should be:

use poseidon252::sponge::gadgets::hash

The module path would be more clear, and we'll still have no naming conflict since we can import just sponge, so we'll have a code that instead of:

// here we're typing `sponge` four times
use poseidon252::sponge::sponge::{sponge_hash, sponge_hash_gadget};

sponge_hash(&[…]);
sponge_hash_gadget(&[…])

We'll have:

use poseidon252::sponge;

sponge::hash(&[…]);
sponge::gadgets::hash(&[…])

Of course you can always import directly the gadget or the hash if there is no conflict.

While I was working withthe PoseidonTree I took a look to the internals of the push() function. https://github.com/dusk-network/Poseidon252/blob/master/src/tree/tree.rs#L85-L96

And I realized that in order to collect the size to set the idx of the new entry we do a lot of computation, when we maybe could store the last used idx and just increase it on each iteration. At the end, the tree is append only so we don't even need to worry about decreasing the number in the deletions since the tree is append-only.

The Poseidon's version tag in github starts from v1.0.0 then goes to v0.1.0 and jump directly to v5.0.0.

We should probably normalize them, adding the tags for version v0.2.0, v0.3.0 and v0.4.0 to the proper commits – assuming the versions bump was correctly made in Cargo.toml, and maybe rename the tag of v1.0.0 to legacy or something like that, but not a version number: given a different version would clash with Cargo.toml content, but it might be worth to keep a reference to that commit.

Once https://github.com/dusk-network/kelvin/issues/37 is closed, we should implement this new types of Merkle Trees within this library and replace the actual Sparse Merkle Trees that we're using now.

On this way, we can have fixed-size branches (height is always the same) so the Proofs can always be obtained using the same PreProcessedCircuit.

Summary

Add benchmarks for the merkle-opening circuit

• Circuit compilation
• Proof creation
• Proof verification We need benchmarks in order to track performance throughout the development.

Possible solution design or implementation

In this issue we will add the benchmark to measure the proof creation and verification of one poseidon zk merkle opening circuit. Running multiple merkle openings in the same circuit is left for future implementation.

Additional context

First mentioned in #81

Added

• Add support for rkyv-impl under no_std
• Add ranno version 0.1 to dependencies [#180]

Changed

• Change PoseidonBranch to have two fields - root and path. The path is now a fixed length array. [#189]
• Change PoseidonTree to build only with the alloc feature [#180]
• Change PoseidonTree to take a generic Keyed over the leaf type instead of a PoseidonAnnotation [#180]
• Make PoseidonTree::new const [#180]
• Update microkelvin from 0.15 to 0.17 [#180]
• Update nstack from 0.14.0-rc to 0.16 [#180]

Removed

• Remove PoseidonBranch Default implementation [#189]
• Remove std feature [#180]
• Remove canon and persistence features [#180]
• Remove Error struct [#180]
• Remove canonical and canonical-derive from dependencies [#180]
• Remove PoseidonMaxAnnotation [#180]

Fixed

• Fix merkle opening circuit [#181]
• Fix CHANGELOG version links [#191]

Summary

I would like us to introduce Hash traits, for allowing for generic implementations of hashes producing BlsScalars.

Possible solution design or implementation

At least one trait, here with working name Hasher, should be implemented, taking the type and a Hasher to "feed" itself to the hasher.

trait Hash {
    fn hash<H: Hasher>(&self, hasher: &mut H);
}

trait Hasher {
    fn finish(&self) -> BlsScalar;
    fn write(&mut self, bytes: &[u8]);
    fn write_scalars(&mut self, bytes: &[BlsScalar]);
}

This structure is very similar to std::hash::Hash.

Additional context

This would significantly reduce the footprint of the code downstream, and allow us to structure the ad-hoc to_hash_inputs functions - implemented almost everywhere in downstream code - a little better than currently.

It is debatable whether this functionality fully belongs in this crate, as opposed to a fully-fledged dusk-crypto crate, but lets leave it for the future.

Summary

I would like that PoseidonBranch be made Copy, such that structures made including branches can also be made Copy. This is necessary to have proper default implementations of the dusk_plonk::Circuit trait for structures including arrays of branches.

Possible solution design or implementation

Derive Copy trait.

Additional context

In an effort to make generating the transfer circuits' keys and proofs less tricky, we're refactoring them to be on the stack using const generics.

Summary

We need benchmarks in order to track performance throughout the development.

Possible solution design or implementation

In this issue we will add the benchmark to measure the native poseidon cipher and the proof creation and verification of the poseidon cipher circuit.

Additional context

First mentioned in #81

Describe what you want implemented Use component_boolean to check for the index bits in our merkle opening circuit.

Describe "Why" this is needed Reduce gate count.

Describe alternatives you've considered N/A

Additional context Originally posted by @vlopes11 in https://github.com/dusk-network/Poseidon252/pull/182#discussion_r974735025: The original purpose of this block was to validate that we have only zeroes/ones, and that we have one, and only one 1; the rest being 0.

It was written before we had component_boolean available, which now completely supersede this implementation. What we need is to run the boolean component for every of these bits (so we guarantee they are either 0 or 1, and check that they add to 1 (so we guarantee that we have one, and only one 1).

Describe what you want implemented The features of a crate should be named accordingly to the features they enable, and not the names or technicalities of its dependencies. I propose a restructuring of the features of this crate.

Describe "Why" this is needed Currently the features included with this crate are:

default
alloc
rkyv-impl

Almost the entire crate sits behind the alloc feature with following exceptions:

cipher::PoseidonCipher                                                                                   
perm_uses::two_outputs                                                                                   
sponge::hash                                                                                             
sponge::truncated::hash 

I propose that this is terribly confusing, and as such we should rethink the features of the crate.