snarkvm_circuit_types_field/
pow.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::*;
17use snarkvm_circuit_environment::{Circuit, CircuitType};
18
19#[allow(clippy::only_used_in_recursion)]
20impl<E: Environment> Pow<Field<E>> for Field<E> {
21    type Output = Field<E>;
22
23    fn pow(self, exponent: Field<E>) -> Self::Output {
24        self.pow(&exponent)
25    }
26}
27
28impl<E: Environment> Pow<Field<E>> for &Field<E> {
29    type Output = Field<E>;
30
31    fn pow(self, exponent: Field<E>) -> Self::Output {
32        self.pow(&exponent)
33    }
34}
35
36#[allow(clippy::needless_borrow)]
37impl<E: Environment> Pow<&Field<E>> for Field<E> {
38    type Output = Field<E>;
39
40    fn pow(self, exponent: &Field<E>) -> Self::Output {
41        (&self).pow(exponent)
42    }
43}
44
45impl<E: Environment> Pow<&Field<E>> for &Field<E> {
46    type Output = Field<E>;
47
48    fn pow(self, exponent: &Field<E>) -> Self::Output {
49        // Initialize the output.
50        let mut output = Field::one();
51
52        // If the exponent is a constant, eject its bits to determine whether to multiply in each iteration.
53        if exponent.is_constant() {
54            for bit in exponent.to_bits_be() {
55                // Square the output.
56                output = output.square();
57                // If `bit` is `true, set the output to `output * self`.
58                if bit.eject_value() {
59                    output *= self;
60                }
61            }
62        }
63        // If the exponent is a variable, use a ternary to select whether to multiply in each iteration.
64        else {
65            for bit in exponent.to_bits_be() {
66                // Square the output.
67                output = output.square();
68                // If `bit` is `true, set the output to `output * self`.
69                output = Field::ternary(&bit, &(&output * self), &output);
70            }
71        }
72
73        output
74    }
75}
76
77impl<E: Environment> Metrics<dyn Pow<Field<E>, Output = Field<E>>> for Field<E> {
78    type Case = (CircuitType<Field<E>>, CircuitType<Field<E>>);
79
80    fn count(case: &Self::Case) -> Count {
81        match (case.0.mode(), case.1.mode()) {
82            (Mode::Constant, Mode::Constant) => Count::is(253, 0, 0, 0),
83            (_, Mode::Constant) => match &case.1 {
84                CircuitType::Constant(constant) => {
85                    // Find the first instance (from the MSB) of a `true` bit.
86                    let exponent_bits = constant.eject_value().to_bits_be();
87                    let index = exponent_bits
88                        .iter()
89                        .position(|b| *b)
90                        .unwrap_or(console::Field::<<Circuit as Environment>::Network>::size_in_bits() - 1);
91
92                    // Calculate the number of squares and multiplications as follows:
93                    //   `num_squares` := number of remaining bits after the first nonzero bit (from MSB -> LSB)
94                    //   `num_multiplications` := number of `true` bits after the first nonzero bit (from MSB -> LSB)
95                    let num_squares =
96                        (console::Field::<<Circuit as Environment>::Network>::size_in_bits() - index - 1) as u64;
97                    let num_multiplications = exponent_bits[index + 1..].iter().map(|bit| *bit as u64).sum::<u64>();
98
99                    // The number of private variables, constraints, and gates are both: num_squares + num_multiplications
100                    let num_private = num_squares + num_multiplications;
101                    let num_constraints = num_private;
102                    Count::is(253, 0, num_private, num_constraints)
103                }
104                _ => E::halt(format!(
105                    "Constant is required to determine the `Count` for {} POW {}",
106                    case.0.mode(),
107                    case.1.mode()
108                )),
109            },
110            (Mode::Constant, _) => Count::is(0, 0, 1009, 1011),
111            (_, _) => Count::is(0, 0, 1262, 1264),
112        }
113    }
114}
115
116impl<E: Environment> OutputMode<dyn Pow<Field<E>, Output = Field<E>>> for Field<E> {
117    type Case = (CircuitType<Field<E>>, CircuitType<Field<E>>);
118
119    fn output_mode(case: &Self::Case) -> Mode {
120        match (case.0.mode(), case.1.mode()) {
121            (Mode::Constant, Mode::Constant) => Mode::Constant,
122            (mode_a, Mode::Constant) => match &case.1 {
123                CircuitType::Constant(constant) => match constant.eject_value() {
124                    value if value.is_zero() => Mode::Constant,
125                    value if value.is_one() => mode_a,
126                    _ => Mode::Private,
127                },
128                _ => E::halt("The constant is required to determine the output mode of Public * Constant"),
129            },
130            (_, _) => Mode::Private,
131        }
132    }
133}
134
135#[cfg(test)]
136mod tests {
137    use super::*;
138    use snarkvm_circuit_environment::Circuit;
139
140    const ITERATIONS: u64 = 10;
141
142    fn check_pow(
143        name: &str,
144        expected: &console::Field<<Circuit as Environment>::Network>,
145        a: &Field<Circuit>,
146        b: &Field<Circuit>,
147    ) {
148        Circuit::scope(name, || {
149            let candidate = a.pow(b);
150            assert_eq!(*expected, candidate.eject_value(), "({}^{})", a.eject_value(), b.eject_value());
151            assert_count!(Pow(Field, Field) => Field, &(CircuitType::from(a), CircuitType::from(b)));
152            assert_output_mode!(Pow(Field, Field) => Field, &(CircuitType::from(a), CircuitType::from(b)), candidate);
153        });
154    }
155
156    fn run_test(mode_a: Mode, mode_b: Mode) {
157        let mut rng = TestRng::default();
158
159        for i in 0..ITERATIONS {
160            let first = Uniform::rand(&mut rng);
161            let second = Uniform::rand(&mut rng);
162
163            let a = Field::<Circuit>::new(mode_a, first);
164            let b = Field::<Circuit>::new(mode_b, second);
165
166            let expected = first.pow(second);
167
168            let name = format!("Pow: a ^ b {i}");
169            check_pow(&name, &expected, &a, &b);
170
171            // Test one exponent.
172            let name = format!("Pow: a ^ 1 {i}");
173            let a = Field::<Circuit>::new(mode_a, first);
174            let one = Field::<Circuit>::new(mode_b, console::Field::<<Circuit as Environment>::Network>::one());
175            check_pow(&name, &first, &a, &one);
176
177            // Test one base.
178            let name = format!("Pow: 1 ^ b {i}");
179            let one = Field::<Circuit>::new(mode_a, console::Field::<<Circuit as Environment>::Network>::one());
180            let b = Field::<Circuit>::new(mode_b, second);
181            check_pow(&name, &console::Field::<<Circuit as Environment>::Network>::one(), &one, &b);
182
183            // Test zero exponent.
184            let name = format!("Pow: a ^ 0 {i}");
185            let a = Field::<Circuit>::new(mode_a, first);
186            let zero = Field::<Circuit>::new(mode_b, console::Field::<<Circuit as Environment>::Network>::zero());
187            check_pow(&name, &console::Field::<<Circuit as Environment>::Network>::one(), &a, &zero);
188
189            // Test zero base.
190            let name = format!("Mul: 0 ^ b {i}");
191            let zero = Field::<Circuit>::new(mode_a, console::Field::<<Circuit as Environment>::Network>::zero());
192            let b = Field::<Circuit>::new(mode_b, second);
193            check_pow(&name, &console::Field::<<Circuit as Environment>::Network>::zero(), &zero, &b);
194        }
195
196        let zero = console::Field::<<Circuit as Environment>::Network>::zero();
197        let one = console::Field::<<Circuit as Environment>::Network>::one();
198
199        // Test 0 ^ 0.
200        let name = "Mul: 0 ^ 0";
201        check_pow(name, &one, &Field::<Circuit>::new(mode_a, zero), &Field::<Circuit>::new(mode_b, zero));
202
203        // Test 1 ^ 0.
204        let name = "Pow: 1 ^ 0";
205        check_pow(name, &one, &Field::<Circuit>::new(mode_a, one), &Field::<Circuit>::new(mode_b, zero));
206
207        // Test 0 ^ 1.
208        let name = "Pow: 0 ^ 1";
209        check_pow(name, &zero, &Field::<Circuit>::new(mode_a, zero), &Field::<Circuit>::new(mode_b, one));
210
211        // Test 1 ^ 1.
212        let name = "Pow: 1 ^ 1";
213        check_pow(name, &one, &Field::<Circuit>::new(mode_a, one), &Field::<Circuit>::new(mode_b, one));
214    }
215
216    #[test]
217    fn test_constant_pow_constant() {
218        run_test(Mode::Constant, Mode::Constant);
219    }
220
221    #[test]
222    fn test_constant_pow_public() {
223        run_test(Mode::Constant, Mode::Public);
224    }
225
226    #[test]
227    fn test_constant_pow_private() {
228        run_test(Mode::Constant, Mode::Private);
229    }
230
231    #[test]
232    fn test_public_pow_constant() {
233        run_test(Mode::Public, Mode::Constant);
234    }
235
236    #[test]
237    fn test_private_pow_constant() {
238        run_test(Mode::Private, Mode::Constant);
239    }
240
241    #[test]
242    fn test_public_pow_public() {
243        run_test(Mode::Public, Mode::Public);
244    }
245
246    #[test]
247    fn test_public_pow_private() {
248        run_test(Mode::Public, Mode::Private);
249    }
250
251    #[test]
252    fn test_private_pow_public() {
253        run_test(Mode::Private, Mode::Public);
254    }
255
256    #[test]
257    fn test_private_pow_private() {
258        run_test(Mode::Private, Mode::Private)
259    }
260}
snarkvm_circuit_types_field/pow.rs

snarkvm_circuit_types_field/
pow.rs
