snarkvm_circuit_algorithms/pedersen/
hash_uncompressed.rs

1// Copyright (c) 2019-2025 Provable Inc.
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16use super::*;
17
18use std::borrow::Cow;
19
20impl<E: Environment, const NUM_BITS: u8> HashUncompressed for Pedersen<E, NUM_BITS> {
21    type Input = Boolean<E>;
22    type Output = Group<E>;
23
24    /// Returns the Pedersen hash of the given input as an affine group element.
25    fn hash_uncompressed(&self, input: &[Self::Input]) -> Self::Output {
26        // Ensure the input is within the size bounds.
27        let mut input = Cow::Borrowed(input);
28        match input.len() <= NUM_BITS as usize {
29            // Pad the input if it is under the required parameter size.
30            true => input.to_mut().resize(NUM_BITS as usize, Boolean::constant(false)),
31            // Ensure the input size is within the parameter size.
32            false => E::halt(format!("The Pedersen hash input cannot exceed {NUM_BITS} bits.")),
33        }
34
35        // Compute the sum of base_i^{input_i} for all i.
36        input
37            .iter()
38            .zip_eq(&self.base_window)
39            .map(|(bit, base)| Group::ternary(bit, base, &Group::zero()))
40            .fold(Group::<E>::zero(), |acc, x| acc + x)
41    }
42}
43
44impl<E: Environment, const NUM_BITS: u8> Metrics<dyn HashUncompressed<Input = Boolean<E>, Output = Group<E>>>
45    for Pedersen<E, NUM_BITS>
46{
47    type Case = Vec<Mode>;
48
49    #[inline]
50    fn count(case: &Self::Case) -> Count {
51        // Calculate the counts for constructing each of the individual group elements from the bits of the input.
52        let group_initialization_counts = case
53            .iter()
54            .map(|mode| {
55                count!(
56                    Group<E>,
57                    Ternary<Boolean = Boolean<E>, Output = Group<E>>,
58                    &(*mode, Mode::Constant, Mode::Constant)
59                )
60            })
61            .fold(Count::zero(), |cumulative, count| cumulative + count);
62
63        // Determine the modes of each of the group elements.
64        let mut modes = case.iter().map(|mode| {
65            // The `first` and `second` inputs to `Group::ternary` are always constant so we can directly determine the mode instead of
66            // using the `output_mode` macro. This avoids the need to use `CircuitType` as a parameter, simplifying the logic of this function.
67            match mode.is_constant() {
68                true => Mode::Constant,
69                false => Mode::Private,
70            }
71        });
72
73        // Calculate the cost of summing the group elements.
74        let sum_counts = match modes.next() {
75            Some(start_mode) => {
76                modes
77                    .fold((start_mode, Count::zero()), |(prev_mode, cumulative), curr_mode| {
78                        let mode = output_mode!(Group<E>, Add<Group<E>, Output = Group<E>>, &(prev_mode, curr_mode));
79                        let sum_count = count!(Group<E>, Add<Group<E>, Output = Group<E>>, &(prev_mode, curr_mode));
80                        (mode, cumulative + sum_count)
81                    })
82                    .1
83            }
84            None => Count::zero(),
85        };
86
87        group_initialization_counts + sum_counts
88    }
89}
90
91impl<E: Environment, const NUM_BITS: u8> OutputMode<dyn HashUncompressed<Input = Boolean<E>, Output = Group<E>>>
92    for Pedersen<E, NUM_BITS>
93{
94    type Case = Vec<Mode>;
95
96    #[inline]
97    fn output_mode(parameter: &Self::Case) -> Mode {
98        match parameter.iter().all(|mode| mode.is_constant()) {
99            true => Mode::Constant,
100            false => Mode::Private,
101        }
102    }
103}
104
105#[cfg(test)]
106mod tests {
107    use super::*;
108    use snarkvm_circuit_types::environment::Circuit;
109    use snarkvm_utilities::{TestRng, Uniform};
110
111    const ITERATIONS: u64 = 10;
112    const MESSAGE: &str = "PedersenCircuit0";
113    const NUM_BITS_MULTIPLIER: u8 = 8;
114
115    fn check_hash_uncompressed<const NUM_BITS: u8>(mode: Mode, rng: &mut TestRng) {
116        use console::HashUncompressed as H;
117
118        // Initialize the Pedersen hash.
119        let native = console::Pedersen::<<Circuit as Environment>::Network, NUM_BITS>::setup(MESSAGE);
120        let circuit = Pedersen::<Circuit, NUM_BITS>::constant(native.clone());
121
122        for i in 0..ITERATIONS {
123            // Sample a random input.
124            let input = (0..NUM_BITS).map(|_| bool::rand(rng)).collect::<Vec<bool>>();
125            // Compute the expected hash.
126            let expected = native.hash_uncompressed(&input).expect("Failed to hash native input");
127            // Prepare the circuit input.
128            let circuit_input: Vec<Boolean<_>> = Inject::new(mode, input);
129
130            Circuit::scope(format!("Pedersen {mode} {i}"), || {
131                // Perform the hash operation.
132                let candidate = circuit.hash_uncompressed(&circuit_input);
133                assert_eq!(expected, candidate.eject_value());
134
135                // Check constraint counts and output mode.
136                let modes = circuit_input.iter().map(|b| b.eject_mode()).collect::<Vec<_>>();
137                assert_count!(
138                    Pedersen<Circuit, NUM_BITS>,
139                    HashUncompressed<Input = Boolean<Circuit>, Output = Group<Circuit>>,
140                    &modes
141                );
142                assert_output_mode!(
143                    Pedersen<Circuit, NUM_BITS>,
144                    HashUncompressed<Input = Boolean<Circuit>, Output = Group<Circuit>>,
145                    &modes,
146                    candidate
147                );
148            });
149        }
150    }
151
152    fn check_homomorphic_addition<C: Display + Eject + Add<Output = C> + ToBits<Boolean = Boolean<Circuit>>>(
153        pedersen: &impl HashUncompressed<Input = Boolean<Circuit>, Output = Group<Circuit>>,
154        first: C,
155        second: C,
156    ) {
157        println!("Checking homomorphic addition on {first} + {second}");
158
159        // Compute the expected hash, by hashing them individually and summing their results.
160        let a = pedersen.hash_uncompressed(&first.to_bits_le());
161        let b = pedersen.hash_uncompressed(&second.to_bits_le());
162        let expected = a + b;
163
164        // Sum the two integers, and then hash the sum.
165        let candidate = pedersen.hash_uncompressed(&(first + second).to_bits_le());
166        assert_eq!(expected.eject(), candidate.eject());
167        assert!(Circuit::is_satisfied());
168    }
169
170    #[test]
171    fn test_hash_uncompressed_constant() {
172        // Set the number of windows, and modulate the window size.
173        let mut rng = TestRng::default();
174        check_hash_uncompressed::<NUM_BITS_MULTIPLIER>(Mode::Constant, &mut rng);
175        check_hash_uncompressed::<{ 2 * NUM_BITS_MULTIPLIER }>(Mode::Constant, &mut rng);
176        check_hash_uncompressed::<{ 3 * NUM_BITS_MULTIPLIER }>(Mode::Constant, &mut rng);
177        check_hash_uncompressed::<{ 4 * NUM_BITS_MULTIPLIER }>(Mode::Constant, &mut rng);
178        check_hash_uncompressed::<{ 5 * NUM_BITS_MULTIPLIER }>(Mode::Constant, &mut rng);
179    }
180
181    #[test]
182    fn test_hash_uncompressed_public() {
183        // Set the number of windows, and modulate the window size.
184        let mut rng = TestRng::default();
185        check_hash_uncompressed::<NUM_BITS_MULTIPLIER>(Mode::Public, &mut rng);
186        check_hash_uncompressed::<{ 2 * NUM_BITS_MULTIPLIER }>(Mode::Public, &mut rng);
187        check_hash_uncompressed::<{ 3 * NUM_BITS_MULTIPLIER }>(Mode::Public, &mut rng);
188        check_hash_uncompressed::<{ 4 * NUM_BITS_MULTIPLIER }>(Mode::Public, &mut rng);
189        check_hash_uncompressed::<{ 5 * NUM_BITS_MULTIPLIER }>(Mode::Public, &mut rng);
190    }
191
192    #[test]
193    fn test_hash_uncompressed_private() {
194        // Set the number of windows, and modulate the window size.
195        let mut rng = TestRng::default();
196        check_hash_uncompressed::<NUM_BITS_MULTIPLIER>(Mode::Private, &mut rng);
197        check_hash_uncompressed::<{ 2 * NUM_BITS_MULTIPLIER }>(Mode::Private, &mut rng);
198        check_hash_uncompressed::<{ 3 * NUM_BITS_MULTIPLIER }>(Mode::Private, &mut rng);
199        check_hash_uncompressed::<{ 4 * NUM_BITS_MULTIPLIER }>(Mode::Private, &mut rng);
200        check_hash_uncompressed::<{ 5 * NUM_BITS_MULTIPLIER }>(Mode::Private, &mut rng);
201    }
202
203    #[test]
204    fn test_pedersen64_homomorphism_private() {
205        // Initialize Pedersen64.
206        let pedersen = Pedersen64::constant(console::Pedersen64::setup("Pedersen64HomomorphismTest"));
207
208        let mut rng = TestRng::default();
209
210        for _ in 0..ITERATIONS {
211            // Sample two random unsigned integers, with the MSB set to 0.
212            let first = U8::<Circuit>::new(Mode::Private, console::U8::new(u8::rand(&mut rng) >> 1));
213            let second = U8::new(Mode::Private, console::U8::new(u8::rand(&mut rng) >> 1));
214            check_homomorphic_addition(&pedersen, first, second);
215
216            // Sample two random unsigned integers, with the MSB set to 0.
217            let first = U16::<Circuit>::new(Mode::Private, console::U16::new(u16::rand(&mut rng) >> 1));
218            let second = U16::new(Mode::Private, console::U16::new(u16::rand(&mut rng) >> 1));
219            check_homomorphic_addition(&pedersen, first, second);
220
221            // Sample two random unsigned integers, with the MSB set to 0.
222            let first = U32::<Circuit>::new(Mode::Private, console::U32::new(u32::rand(&mut rng) >> 1));
223            let second = U32::new(Mode::Private, console::U32::new(u32::rand(&mut rng) >> 1));
224            check_homomorphic_addition(&pedersen, first, second);
225
226            // Sample two random unsigned integers, with the MSB set to 0.
227            let first = U64::<Circuit>::new(Mode::Private, console::U64::new(u64::rand(&mut rng) >> 1));
228            let second = U64::new(Mode::Private, console::U64::new(u64::rand(&mut rng) >> 1));
229            check_homomorphic_addition(&pedersen, first, second);
230        }
231    }
232
233    #[test]
234    fn test_pedersen_homomorphism_private() {
235        fn check_pedersen_homomorphism(
236            pedersen: &impl HashUncompressed<Input = Boolean<Circuit>, Output = Group<Circuit>>,
237        ) {
238            let mut rng = TestRng::default();
239
240            for _ in 0..ITERATIONS {
241                // Sample two random unsigned integers, with the MSB set to 0.
242                let first = U8::<Circuit>::new(Mode::Private, console::U8::new(u8::rand(&mut rng) >> 1));
243                let second = U8::new(Mode::Private, console::U8::new(u8::rand(&mut rng) >> 1));
244                check_homomorphic_addition(pedersen, first, second);
245
246                // Sample two random unsigned integers, with the MSB set to 0.
247                let first = U16::<Circuit>::new(Mode::Private, console::U16::new(u16::rand(&mut rng) >> 1));
248                let second = U16::new(Mode::Private, console::U16::new(u16::rand(&mut rng) >> 1));
249                check_homomorphic_addition(pedersen, first, second);
250
251                // Sample two random unsigned integers, with the MSB set to 0.
252                let first = U32::<Circuit>::new(Mode::Private, console::U32::new(u32::rand(&mut rng) >> 1));
253                let second = U32::new(Mode::Private, console::U32::new(u32::rand(&mut rng) >> 1));
254                check_homomorphic_addition(pedersen, first, second);
255
256                // Sample two random unsigned integers, with the MSB set to 0.
257                let first = U64::<Circuit>::new(Mode::Private, console::U64::new(u64::rand(&mut rng) >> 1));
258                let second = U64::new(Mode::Private, console::U64::new(u64::rand(&mut rng) >> 1));
259                check_homomorphic_addition(pedersen, first, second);
260
261                // Sample two random unsigned integers, with the MSB set to 0.
262                let first = U128::<Circuit>::new(Mode::Private, console::U128::new(u128::rand(&mut rng) >> 1));
263                let second = U128::new(Mode::Private, console::U128::new(u128::rand(&mut rng) >> 1));
264                check_homomorphic_addition(pedersen, first, second);
265            }
266        }
267
268        // Check Pedersen128.
269        let pedersen128 = Pedersen128::constant(console::Pedersen128::setup("Pedersen128HomomorphismTest"));
270        check_pedersen_homomorphism(&pedersen128);
271    }
272}