poseidon_default.rs
1 // Copyright (c) 2025-2026 ACDC Network 2 // This file is part of the alphavm library. 3 // 4 // Alpha Chain | Delta Chain Protocol 5 // International Monetary Graphite. 6 // 7 // Derived from Aleo (https://aleo.org) and ProvableHQ (https://provable.com). 8 // They built world-class ZK infrastructure. We installed the EASY button. 9 // Their cryptography: elegant. Our modifications: bureaucracy-compatible. 10 // Original brilliance: theirs. Robert's Rules: ours. Bugs: definitely ours. 11 // 12 // Original Aleo/ProvableHQ code subject to Apache 2.0 https://www.apache.org/licenses/LICENSE-2.0 13 // All modifications and new work: CC0 1.0 Universal Public Domain Dedication. 14 // No rights reserved. No permission required. No warranty. No refunds. 15 // 16 // https://creativecommons.org/publicdomain/zero/1.0/ 17 // SPDX-License-Identifier: CC0-1.0 18 19 use crate::{serial_batch_inversion_and_mul, PoseidonGrainLFSR, PrimeField}; 20 use acdc_std::{end_timer, start_timer}; 21 use itertools::Itertools; 22 23 use anyhow::{bail, Result}; 24 25 /// Parameters and RNG used 26 #[derive(Debug, Clone, PartialEq, Eq)] 27 pub struct PoseidonParameters<F: PrimeField, const RATE: usize, const CAPACITY: usize> { 28 /// number of rounds in a full-round operation 29 pub full_rounds: usize, 30 /// number of rounds in a partial-round operation 31 pub partial_rounds: usize, 32 /// Exponent used in S-boxes 33 pub alpha: u64, 34 /// Additive Round keys. These are added before each MDS matrix application to make it an affine shift. 35 /// They are indexed by `ark[round_num][state_element_index]` 36 pub ark: Vec<Vec<F>>, 37 /// Maximally Distance Separating Matrix. 38 pub mds: Vec<Vec<F>>, 39 } 40 41 /// A field with Poseidon parameters associated 42 pub trait PoseidonDefaultField { 43 /// Obtain the default Poseidon parameters for this rate and for this prime field, 44 /// with a specific optimization goal. 45 fn default_poseidon_parameters<const RATE: usize>() -> Result<PoseidonParameters<Self, RATE, 1>> 46 where 47 Self: PrimeField, 48 { 49 /// Internal function that computes the ark and mds from the Poseidon Grain LFSR. 50 #[allow(clippy::type_complexity)] 51 fn find_poseidon_ark_and_mds<F: PrimeField, const RATE: usize>( 52 full_rounds: u64, 53 partial_rounds: u64, 54 skip_matrices: u64, 55 ) -> Result<(Vec<Vec<F>>, Vec<Vec<F>>)> { 56 let lfsr_time = start_timer!(|| "LFSR Init"); 57 let mut lfsr = 58 PoseidonGrainLFSR::new(false, F::size_in_bits() as u64, (RATE + 1) as u64, full_rounds, partial_rounds); 59 end_timer!(lfsr_time); 60 61 let ark_time = start_timer!(|| "Constructing ARK"); 62 let mut ark = Vec::with_capacity((full_rounds + partial_rounds) as usize); 63 for _ in 0..(full_rounds + partial_rounds) { 64 ark.push(lfsr.get_field_elements_rejection_sampling(RATE + 1)?); 65 } 66 end_timer!(ark_time); 67 68 let skip_time = start_timer!(|| "Skipping matrices"); 69 for _ in 0..skip_matrices { 70 let _ = lfsr.get_field_elements_mod_p::<F>(2 * (RATE + 1))?; 71 } 72 end_timer!(skip_time); 73 74 // A qualifying matrix must satisfy the following requirements: 75 // - There is no duplication among the elements in x or y. 76 // - There is no i and j such that x[i] + y[j] = p. 77 // - There resultant MDS passes all three tests. 78 79 let xs = lfsr.get_field_elements_mod_p::<F>(RATE + 1)?; 80 let ys = lfsr.get_field_elements_mod_p::<F>(RATE + 1)?; 81 82 let mds_time = start_timer!(|| "Construct MDS"); 83 let mut mds_flattened = vec![F::zero(); (RATE + 1) * (RATE + 1)]; 84 for (x, mds_row_i) in xs.iter().take(RATE + 1).zip_eq(mds_flattened.chunks_mut(RATE + 1)) { 85 for (y, e) in ys.iter().take(RATE + 1).zip_eq(mds_row_i) { 86 *e = *x + y; 87 } 88 } 89 serial_batch_inversion_and_mul(&mut mds_flattened, &F::one()); 90 let mds = mds_flattened.chunks(RATE + 1).map(|row| row.to_vec()).collect(); 91 end_timer!(mds_time); 92 93 Ok((ark, mds)) 94 } 95 96 match Self::Parameters::PARAMS_OPT_FOR_CONSTRAINTS.iter().find(|entry| entry.rate == RATE) { 97 Some(entry) => { 98 let (ark, mds) = find_poseidon_ark_and_mds::<Self, RATE>( 99 entry.full_rounds as u64, 100 entry.partial_rounds as u64, 101 entry.skip_matrices as u64, 102 )?; 103 Ok(PoseidonParameters { 104 full_rounds: entry.full_rounds, 105 partial_rounds: entry.partial_rounds, 106 alpha: entry.alpha as u64, 107 ark, 108 mds, 109 }) 110 } 111 None => bail!("No Poseidon parameters were found for this rate"), 112 } 113 } 114 } 115 116 /// A trait for default Poseidon parameters associated with a prime field 117 pub trait PoseidonDefaultParameters { 118 /// An array of the parameters optimized for constraints 119 /// (rate, alpha, full_rounds, partial_rounds, skip_matrices) 120 /// for rate = 2, 3, 4, 5, 6, 7, 8 121 /// 122 /// Here, `skip_matrices` denote how many matrices to skip before 123 /// finding one that satisfy all the requirements. 124 const PARAMS_OPT_FOR_CONSTRAINTS: [PoseidonDefaultParametersEntry; 7]; 125 } 126 127 /// An entry in the default Poseidon parameters 128 pub struct PoseidonDefaultParametersEntry { 129 /// The rate (in terms of number of field elements). 130 pub rate: usize, 131 /// Exponent used in S-boxes. 132 pub alpha: usize, 133 /// Number of rounds in a full-round operation. 134 pub full_rounds: usize, 135 /// Number of rounds in a partial-round operation. 136 pub partial_rounds: usize, 137 /// Number of matrices to skip when generating parameters using the Grain LFSR. 138 /// 139 /// The matrices being skipped are those that do not satisfy all the desired properties. 140 /// See the [reference implementation](https://extgit.iaik.tugraz.at/krypto/hadeshash/-/blob/master/code/generate_parameters_grain.sage) for more detail. 141 pub skip_matrices: usize, 142 } 143 144 impl PoseidonDefaultParametersEntry { 145 /// Create an entry in PoseidonDefaultParameters. 146 pub const fn new( 147 rate: usize, 148 alpha: usize, 149 full_rounds: usize, 150 partial_rounds: usize, 151 skip_matrices: usize, 152 ) -> Self { 153 Self { rate, alpha, full_rounds, partial_rounds, skip_matrices } 154 } 155 }