Reference implementation for the Poseidon Hashing algorithm.
Starkad and Poseidon: New Hash Functions for Zero Knowledge Proof Systems
This repository has been created so there's a unique library that holds the tools & functions required to perform Poseidon Hashes.
This hashes heavily rely on the Hades permutation, which is one of the key parts that Poseidon needs in order to work. This library uses the reference implementation of Dusk-Hades which has been designed & build by the Dusk-Network team.
The library provides the two hashing techniques of Poseidon:
The Sponge technique in Poseidon allows to hash an unlimited amount of data
into a single Scalar.
The sponge hash technique requires a padding to be applied before the data can
be hashed.
This is done to avoid hash collisions as stated in the paper of the Poseidon Hash
algorithm. See: https://eprint.iacr.org/2019/458.pdf.
The inputs of the sponge_hash are always Scalar or need to be capable of being represented
as it.
The module provides two sponge hash implementations:
Sponge hash using Scalar as backend. Which hashes the inputted Scalars and returns a single
Scalar.
Sponge hash gadget using dusk_plonk::Witness as a backend. This technique is used/required
when you want to proof pre-images of unconstrained data inside Zero-Knowledge PLONK circuits.
The Merkle Level Hashing is a technique that Poseidon is optimized-by-design
to perform.
This technique allows us to perform hashes of an entire Merkle Tree using
Dusk-Hades as backend.
The technique requires the computation of a bitflags element which is always
positioned as the first item of the level when we hash it, and it basically generated
in respect of the presence or absence of a leaf in the tree level.
This allows to prevent hashing collisions.
At the moment, this library is designed and optimized to work only with trees of ARITY
up to 4. That means that trees with a bigger ARITY SHOULD NEVER be used with this lib.
The module contains the implementation of 4 variants of the same algorithm to support the
majority of the configurations that the user may need:
Scalar backend for hashing Merkle Tree levels outside ZK-Circuits with two variants: One of them computes the bitflags item while the other assumes that it has already been computed and placed in the first Level position.
dusk_plonk::Witness backend for hashing Merkle Tree levels inside ZK-Circuits,
specifically, PLONK circuits. This implementation comes also with two variants;
One of them computes the bitflags item while the other assumes that it has already been
computed and placed in the first Level position.
```rust use duskplonk::error::Error as PlonkError; use duskposeidon::tree::{self, PoseidonBranch, PoseidonLeaf, PoseidonTree}; use rand_core::{CryptoRng, OsRng, RngCore};
use dusk_plonk::prelude::*; use nstack::annotation::Keyed;
// Depth of the merkle tree const DEPTH: usize = 17;
// Capacity of the circuit const CAPACITY: usize = 15;
// Alias for the default tree implementation
type Tree = PoseidonTree
// Leaf representation
pub struct DataLeaf { data: BlsScalar, pos: u64, }
// Keyed needs to be implemented for a leaf type and the tree key. impl Keyed<()> for DataLeaf { fn key(&self) -> &() { &() } }
impl DataLeaf {
pub fn random
Self { data, pos }
}
}
// Any leaf of the poseidon tree must implement PoseidonLeaf
impl PoseidonLeaf for DataLeaf {
// Cryptographic hash of the data leaf
fn poseidon_hash(&self) -> BlsScalar {
self.data
}
// Position on the tree
fn pos(&self) -> &u64 {
&self.pos
}
// Method used to set the position on the tree after the
// `PoseidonTree::push` call.
fn set_pos(&mut self, pos: u64) {
self.pos = pos;
}
}
struct MerkleOpeningCircuit {
branch: PoseidonBranch
impl MerkleOpeningCircuit {
/// Generate N random leaves and append them to the tree
pub fn random
// Append 1024 elements to the tree
for _ in 0..N {
let leaf = DataLeaf::random(rng);
tree.push(leaf);
}
let branch = tree.branch(N - 1).expect(
"Failed to fetch the branch of the created leaf from the tree",
);
Self { branch }
}
}
impl Circuit for MerkleOpeningCircuit { const CIRCUIT_ID: [u8; 32] = [0xff; 32];
fn gadget(
&mut self,
composer: &mut TurboComposer,
) -> Result<(), PlonkError> {
use std::ops::Deref;
let leaf: BlsScalar = *self.branch.deref();
let leaf = composer.append_witness(leaf);
let root = self.branch.root();
let root = composer.append_witness(*root);
let root_p =
tree::merkle_opening::<DEPTH>(composer, &self.branch, leaf);
composer.assert_equal(root_p, root);
Ok(())
}
fn public_inputs(&self) -> Vec<PublicInputValue> {
vec![]
}
fn padded_gates(&self) -> usize {
1 << CAPACITY
}
}
// Create the ZK keys let label = b"dusk-network"; let pp = PublicParameters::setup(1 << CAPACITY, &mut OsRng).unwrap();
// Instantiate a new tree let mut tree = Tree::default(); let mut circuit = MerkleOpeningCircuit::random(&mut OsRng, &mut tree); let (pk, vd) = circuit.compile(&pp).expect("Failed to compile circuit");
// Generate a ZK opening proof let proof = circuit .prove(&pp, &pk, label, &mut OsRng) .expect("Failed to generate proof");
// Verify the proof MerkleOpeningCircuit::verify(&pp, &vd, &proof, &[], label) .expect("Proof verification failed"); ```
This crate contains info about all the functions that the library provides as well as the documentation regarding the data structures that it exports. To check it, please feel free to go to the documentation page
This code is licensed under Mozilla Public License Version 2.0 (MPL-2.0). Please see LICENSE for further info.
Implementation designed by the dusk team.