dusk-network/hades252

Implementation of the Hades permutation algorithm used in Poseidon Hashes with ZKProof capabilities.

Hades252 (deprecated)

❗ This crate is deprecated.
The hades permutation moved into dusk-poseidon.

Implementation of Hades252 permutation algorithm over the Bls12-381 Scalar field.

Documentation

To generate the Hades252 documentation:

make doc
make doc-internal

Use

Run the following to add Hades252 to the dependency section of your project's 'Cargo.toml':

cargo add dusk-hades

Hades252 has a width equals to 5; it's possible to use a different value, see How to generate the assets.

Parameters

• p = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001

• Security level is 117 -120 bits of security [NCCG] bits.

• width = 5

• Number of full rounds = 8 . There are four full rounds at the beginning and four full rounds at the end, where each full round has WIDTH quintic S-Boxes.

• Number of partial rounds = 59, where each partial round has one quintic S-Box and (width-1) identity functions.

• Number of round constants = 960

Example for ScalarStrategy

use dusk_bls12_381::BlsScalar;
use dusk_hades::{ScalarStrategy, Strategy, WIDTH};

// Generate the inputs that will permute.
// The number of values we can input is equivalent to `WIDTH`

let input = vec![BlsScalar::from(1u64); dusk_hades::WIDTH];
let mut output = input.clone();

let mut strategy = ScalarStrategy::new();
strategy.perm(output.as_mut_slice());

assert_ne!(&input, &output);
assert_eq!(input.len(), output.len());

Deviations

• Round constants for the full rounds are generated following: https://extgit.iaik.tugraz.at/krypto/hadesmimc/blob/master/code/calc_round_numbers.py

• The MDS matrix is a cauchy matrix, the method used to generate it, is noted in section "Concrete Instantiations Poseidon and Starkad"

Reference

https://eprint.iacr.org/2019/458.pdf

hades252's Issues

Prepare README for publish

Performance of Poseidon

Multiplying by MDS Matrix in the Constraint system

Currently, proof generation takes more than 60 seconds, when we use the prescribed parameters:

• Partial Rounds: 59
• Full Rounds: 8
• Width: 9

I believe I have tracked it down to the Matrix multiplication segment. Adding two LC's concatenates both vectors together. The matrix multiplication by a vector of a 9x9 matrix will produce at least 81 terms in the Linear combination.

The multiplication is done (Partial_rounds+Full_rounds) times so we have at least 72 * 81 = 6237 terms.

This would be the minimum assuming that we started with each LC having one term.

Initialization of the data

Here we are setting the first element to zero:

Hades252/src/hash.rs

Line 28 in 22fecbc

self.perm.data.push(Scalar::zero());

We need to set it to 2^(self.perm.t) - 1, according to appendix E of https://eprint.iacr.org/2019/458.pdf

Plonk update to `0.7`

Update plonk dependencies to version 0.7

Moving to PLONK/master outdated some README values

Readme.md file mentions several times the RistrettoScalar Field which is no longer being used in master impl.

Instead, it is using the Scalar & G1Affine of dusk-network/Bls12_381 which is what the PLONK repo is currently relying on as a backend.

This info should be updated as well as the parameters that provide values related to the Fr group being used in the implementation.

Fix license headers

The license headers need to correspond with what cargo-dusk-analyzer checks for.

Pre-image tests failing

Currently, running tests for a pre-image seem to be failing. This indicates that the solid version and the constraint system version are not exact parallels

Deprecate crate after migration to dusk-poseidon

Summary

This crates' logic moved to dusk-poseidon (see issue dusk-poseidon#240).

Implement Benchmarks for the new implementation done in #23

We should add the benches in order to see the improvements achieved.

Error during compilation in latest nightly rust toolchain

Error: --> /home/runner/.cargo/registry/src/github.com-1ecc6299db9ec823/dusk-hades-0.1.3/src/lib.rs:7:12
|
7 | #![feature(external_doc)]
| ^^^^^^^^^^^^ feature has been removed
|
= note: use #[doc = include_str!("filename")] instead, which handles macro invocations

Update the README.md

Since the change of API the README.md is not up to date anymore.

Use latest bls, jubjub and plonk versions

Release v0.16.0

Apply `rustfmt` to all sources

Prepare the repo to be published on crates.io

Bump BLS and Plonk

API Discussion

• In the external tests, for simplicity we use unwrap , the idiomatic way would be to use ? with a from trait for different types of Error enums.

• Currently, we allow users to do hash.add(input) however because we can only have a limited amount of inputs, we must return a Result, in case they add more than width-1 scalars. A simpler API would be to just ask the user input a vec![input1, input2,] which would reduce the number of error enums. We could also have both approaches, in case the user does not know all of the inputs before they need to hash and does not want to create temporary values.

• One possible change that could be made is to create two structs, one for the solid impl and another for gadget impl, however this will cause a lot of code duplication. Currently, there is one struct and a user will call a struct to indicate whether they want the gadget version or the solid impl

Fix the `hash` function and name it correctly

As per discussion with Dmitry, the current implementation of the hash function is not correct; also it should be named sponge_hash or something like that, since it's the Sponge function – Poseidon has also a hash function for Merkle Tree, see issue #28

Upgrade plonk to v0.5

Improve constants (`MDS`, `ARK`) usage

Currently both generation and usage of MDS matrix and round keys are not optimized, that should be fixed.

Refactor `Permutation` and `Hash` structs

The Permutation currently contains the code for both Scalar and LinearCombination, we should probably split; plus Hash struct seems a mere wrapper to Permutation, so it might be not necessary.

Make the repo no_std by default requiring `alloc` feature to use GadgetStrategy and plonk-related stuff

We no longer need any std related code. Therefore the repo can be completely no_std and only requires to use alloc feature to enable plonk and therefore the capability to fill the StandardComposer.

Partial round should apply ARK to all elements

According to the paper, the ARK must be applied to all elements at the beginning of every round.

Currently, for the partial round, we are applying ARK only for the last element

Replace rand for rand_core::OsRng for randomness source provider

This is inline with the deps we are going to use in #84 and also the direction the rust ecosystem is moving towards.

Use anyhow crate to handle plonk errors in gadgets test module

Make the tests returns Error (as is now done in the blind bid if you need a reference).

Originally posted by @ZER0 in #54 (comment)

As it was discussed in that thread, once PLONK migrates to anyhow for error handling, we can update this fact here.

Implement Poseidon Hash function for Merkle Tree

The current implementation lacks of the hash function for the Merkle Tree.

Solve docs.rs documentation uploading issues

We have a problem regarding the documentation being uploaded to docs.rs.
See: https://docs.rs/crate/dusk-hades/0.16.0-rc.0

The main problem is how we have structured our build architecture. And in order to solve the problem the crate should be split between a bin and a lib so that one takes care of the constant generation and the other takes care only about the logic of the Hades permutation algorithm.

Refactor the lib to accept WIDTH as a parameter for Hades & Poseidon hashes

Currently, Hades is tight to the WIDTH that we have on the Tx tree which is 5.

But in the bid-tree, we have a WIDTH of two.
So in order to not waste gates on useless hashes, we should implement all of the hashing functions to accept a WIDTH and so, adapt themseleves with the number of hashes that we need, not more.

Migrate to PLONK fields

Add a CHANGELOG to track changes in the crate.

Remove anyhow from dev-deps

API: use R_f or R_F

Creating a new permutation returns a Result because we currently ask for R_F.
Since we are aiming for symmetric permutation, we error if R_F % 2 != 0

A nicer API would be to ask for R_f and multiply by two. The problem is that we also ask for R_P which denotes all rounds. This would be quite unintuitive if we change to R_f because one parameter is asking for half of the full_rounds, while the other is asking for all of the partial rounds.

This may be easily solved by introducing the term "half_full_round"?

Remove all legacy methods related to poseidon_slice from the repo

This no longer applies and was implemented for the previous versions of the crate by @vlopes11 . But I belive since we have a repo just for the Poseidon algorithm things, this is duplicated and unmantained code which should be removed.

Can you confirm @vlopes11 ?

Reamde references Ristretto Scalar field when indeed we're using the BLS12_381 one

This nitpick should be fixed.

Parallelisation of verification procedure

This branch can be used to test how fast the blindbid is in terms of parallel verification.

https://github.com/dusk-network/Hades252/tree/threads_bench_blindbid

CPU : 2.2 GHz Intel Core i7

Blindbid benchmarks: width = 9, number of constraints = 3196

Verification times
1000 proofs: 121 seconds
900 proofs: 85.05 seconds
800 proofs: 74.42 seconds
700 proofs: 76.81 seconds
600 proofs: 75.62 seconds
500 proofs: 46.88 seconds
400 proofs: 39.21 seconds
300 proofs: 31.41 seconds
200 proofs: 19 seconds
100 proofs : 10 seconds

Increase of ~85% compared to sequential calculations without parallel. This is taking an average of 700ms for one blind bid proof to verify. The actual time does vary between 600ms and 800ms.

Add and generate code documentation

The code is almost undocumented, we should start to add the docs.

Update to `dusk-plonk` 0.9

Describe what you want implemented
Update dusk-plonk dependency to 0.9.

Describe "Why" this is needed
dusk-plonk 0.9 was released with major API improvements and general bug fixes. It is desirable to have these improvements available.

Describe alternatives you've considered
N/A

Additional context
N/A

Migrate to plonk master branch

Migrate all of the methods from plonk_zexe branch to plonk's master branch.

This implies:

• Refactor some types used.
• Refactor the addition&multiplication gates used for the new ones on the TurboComposer.
• Refactor the tests
• Update docs following #42

Port Hades to PLONK v0.2.0

Implement GadgetStrategy holding a &mut StandardComposer

While building the examples of the gadget usage, I've realized that it's a bit weird how you're supposed to call the gadget functions exposed for the GadgetStrategy.

Actually, you need to copy the StandardComposer by value to the hades_gadget() function and then re-declare it with the mutated state.

This is not inline with the typical gadget function usage.
The way of interacting with gadget functions should be to provide a &mut StandardComposer to the function so it gets modified (constraints get added to it) but you never need to re-declare the same object to be able to apply a gadget to it.

This is how it actually looks like:

 pub fn hades_gadget(
        composer: StandardComposer,
        pi: P,
        x: &mut [Variable],
    ) -> (StandardComposer, P) {
        #[cfg(feature = "trace")]
        let circuit_size = composer.circuit_size();

        let mut strategy = GadgetStrategy::new(composer, pi);

        strategy.perm(x);

        #[cfg(feature = "trace")]
        {
            trace!(
                "Hades permutation performed with {} constraints for {} bits",
                strategy.cs.circuit_size() - circuit_size,
                WIDTH
            );
        }

        strategy.into_inner()
    }

So how I envision this gadget function and the GadgetStrategy will look like:

/// Implements a Hades252 strategy for `Variable` as input values.
/// Requires a reference to a `ConstraintSystem`.
pub struct GadgetStrategy<'a> {
    /// A reference to the constraint system used by the gadgets
    pub cs: &'a mut StandardComposer,
}

impl<'a> GadgetStrategy<'a> {
    /// Constructs a new `GadgetStrategy` with the constraint system.
    /// In this case, the CS is embedded inside of a plonk `StandardComposer`.
    pub fn new(cs: &'a mut StandardComposer) -> Self {
        GadgetStrategy { cs }
    }

    /// Perform the hades permutation on a plonk circuit given a set of Public
    /// Inputs and a set of Variables used as inputs.
    pub fn hades_gadget(composer: &mut StandardComposer, inputs: &mut [Variable]) {
        #[cfg(feature = "trace")]
        let circuit_size = composer.circuit_size();

        let mut strategy = GadgetStrategy::new(&mut composer);

        strategy.perm(inputs);

        #[cfg(feature = "trace")]
        {
            trace!(
                "Hades permutation performed with {} constraints for {} bits",
                strategy.cs.circuit_size() - circuit_size,
                WIDTH
            );
        }
    }
//.........
}

On this way, we will be able to call the gadget on the way that is recommended by PLONK, see: https://github.com/dusk-network/plonk/blob/f2e889184961b885d9e095afe35b137165112c91/examples/3_1_final_gadget_orientation.rs#L49

The call will look like:

let mut composer = StandardComposer::new();
let mut inputs = [BlsScalar::one(); WIDTH];
GadgetStrategy::hades_gadget(&mut Composer, inputs);
// Now I have my gadget with the hades gadget printed into my internal ConstraintSystem.

Apply pattern matching to R1CS duplicate functions.

On the code we find examples of duplicated code on which we maybe can apply pattern-matching techniques:

fn input_full<T>(&self, data: &Vec<T>) -> bool {
        data.len() == self.t
    }
    pub fn width_left<T>(&self, data: &Vec<T>) -> usize {
        self.t - data.len()
    }
    pub fn input_bytes(&mut self, bytes: &[u8]) -> Result<(), PermError> {
        // Map arbitrary bytes to group using elligator2
        let scalar = Scalar::hash_from_bytes::<Sha512>(bytes);
        self.input(scalar)
    }
    pub fn input(&mut self, scalar: Scalar) -> Result<(), PermError> {
        if self.input_full(&self.data) {
            return Err(PermError::InputFull);
        }
        self.data.push(scalar);
        Ok(())
    }

or:

fn pad(&mut self) {
        let pad_amount = self.width_left(&self.data);
        let zero = Scalar::zero();
        let zeroes = vec![zero; pad_amount];

        self.data.extend(zeroes);
    }
    fn pad_lc(&mut self) {
        let pad_amount = self.width_left(&self.data_lc);
        let zero_lc: LinearCombination = Scalar::zero().into();
        let zeroes = vec![zero_lc; pad_amount];

        self.data_lc.extend(zeroes);
    }

The idea is to have only one function that operates depending on the parameter passed.
This will reduce the code complexity and provide an easier usage for the end user.

Add CI/CD to the repo.

Add a travis.yml file with all of the configurations for:

• Build & test every commit.
• Build & test every PR.
• Run benchmarks on every PR and commit.
• Send notifications to the telegram chat.

Add toolchain file to the repo

Refactor constants (ark, mds) to be populated at compile time

Currently Hades is populating ROUND_CONSTANTS and MDS_MATRIX at runtime (only once, due lazy_static), but this overhead is unnecessary since it could be done at compile time (that is preferable).

Port Hades CI from Travis to Github Actions following the standard

Bump plonk to 0.6