acvm/pwg/blackbox/
mod.rs

1use acir::{
2    AcirField,
3    circuit::opcodes::{BlackBoxFuncCall, FunctionInput},
4    native_types::{Witness, WitnessMap},
5};
6use acvm_blackbox_solver::{blake2s, blake3, keccakf1600};
7
8use self::{aes128::solve_aes128_encryption_opcode, hash::solve_poseidon2_permutation_opcode};
9
10use super::{OpcodeNotSolvable, OpcodeResolutionError, insert_value};
11use crate::{BlackBoxFunctionSolver, pwg::input_to_value};
12
13pub(crate) mod aes128;
14pub(crate) mod embedded_curve_ops;
15pub(crate) mod hash;
16mod logic;
17mod range;
18pub(crate) mod signature;
19pub(crate) mod utils;
20
21use embedded_curve_ops::{embedded_curve_add, multi_scalar_mul};
22// Hash functions should eventually be exposed for external consumers.
23use hash::{solve_generic_256_hash_opcode, solve_sha_256_permutation_opcode};
24use logic::{and, xor};
25pub(crate) use range::solve_range_opcode;
26use signature::ecdsa::{secp256k1_prehashed, secp256r1_prehashed};
27
28/// Check if all of the inputs to the function have assignments
29///
30/// Returns the first missing assignment if any are missing
31fn first_missing_assignment<F>(
32    witness_assignments: &WitnessMap<F>,
33    inputs: &[FunctionInput<F>],
34) -> Option<Witness> {
35    inputs.iter().find_map(|input| {
36        if let FunctionInput::Witness(witness) = input {
37            if witness_assignments.contains_key(witness) { None } else { Some(*witness) }
38        } else {
39            None
40        }
41    })
42}
43
44/// Check if all of the inputs to the function have assignments
45fn contains_all_inputs<F>(
46    witness_assignments: &WitnessMap<F>,
47    inputs: &[FunctionInput<F>],
48) -> bool {
49    first_missing_assignment(witness_assignments, inputs).is_none()
50}
51
52/// Solve a black box function call
53/// 1. Returns an error if not all the inputs are already resolved to a value
54/// 2. Compute the output from the inputs, using the dedicated solvers
55///
56/// A blackbox is a fully specified function (e.g sha256, ecdsa signature,...)
57/// which the backend can prove execution in a more efficient way than using a generic
58/// arithmetic circuit.
59/// Solving a black box function simply means to compute the output from the inputs for
60/// the specific function.
61/// Our black box solver uses the standard rust implementation for the function if it is available.
62/// However, some functions depend on the backend, such as embedded curve operations, which depend on the
63/// elliptic curve used by the proving system. This is why the 'solve' functions takes a blackbox solver trait.
64/// The 'AcvmBigIntSolver' is also a blackbox solver, but dedicated to the BigInteger blackbox functions.
65pub(crate) fn solve<F: AcirField>(
66    backend: &impl BlackBoxFunctionSolver<F>,
67    initial_witness: &mut WitnessMap<F>,
68    bb_func: &BlackBoxFuncCall<F>,
69) -> Result<(), OpcodeResolutionError<F>> {
70    let inputs = bb_func.get_inputs_vec();
71    if !contains_all_inputs(initial_witness, &inputs) {
72        let unassigned_witness = first_missing_assignment(initial_witness, &inputs)
73            .expect("Some assignments must be missing because it does not contains all inputs");
74        return Err(OpcodeResolutionError::OpcodeNotSolvable(
75            OpcodeNotSolvable::MissingAssignment(unassigned_witness.0),
76        ));
77    }
78
79    match bb_func {
80        BlackBoxFuncCall::AES128Encrypt { inputs, iv, key, outputs } => {
81            solve_aes128_encryption_opcode(initial_witness, inputs, iv, key, outputs)
82        }
83        BlackBoxFuncCall::AND { lhs, rhs, num_bits, output } => {
84            and(initial_witness, lhs, rhs, *num_bits, output)
85        }
86        BlackBoxFuncCall::XOR { lhs, rhs, num_bits, output } => {
87            xor(initial_witness, lhs, rhs, *num_bits, output)
88        }
89        BlackBoxFuncCall::RANGE { input, num_bits } => {
90            solve_range_opcode(initial_witness, input, *num_bits)
91        }
92        BlackBoxFuncCall::Blake2s { outputs, .. } => {
93            let inputs = bb_func.get_inputs_vec();
94            solve_generic_256_hash_opcode(initial_witness, &inputs, None, outputs, blake2s)
95        }
96        BlackBoxFuncCall::Blake3 { outputs, .. } => {
97            let inputs = bb_func.get_inputs_vec();
98            solve_generic_256_hash_opcode(initial_witness, &inputs, None, outputs, blake3)
99        }
100        BlackBoxFuncCall::Keccakf1600 { inputs, outputs } => {
101            let mut state = [0; 25];
102            for (it, input) in state.iter_mut().zip(inputs.as_ref()) {
103                let witness_assignment = input_to_value(initial_witness, *input)?;
104                let lane = witness_assignment.try_to_u64();
105                *it = lane.unwrap();
106            }
107            let output_state = keccakf1600(state)?;
108            for (output_witness, value) in outputs.iter().zip(output_state.into_iter()) {
109                insert_value(output_witness, F::from(u128::from(value)), initial_witness)?;
110            }
111            Ok(())
112        }
113        BlackBoxFuncCall::EcdsaSecp256k1 {
114            public_key_x,
115            public_key_y,
116            signature,
117            hashed_message: message,
118            output,
119            predicate,
120        } => secp256k1_prehashed(
121            initial_witness,
122            public_key_x,
123            public_key_y,
124            signature,
125            message.as_ref(),
126            predicate,
127            *output,
128        ),
129        BlackBoxFuncCall::EcdsaSecp256r1 {
130            public_key_x,
131            public_key_y,
132            signature,
133            hashed_message: message,
134            output,
135            predicate,
136        } => secp256r1_prehashed(
137            initial_witness,
138            public_key_x,
139            public_key_y,
140            signature,
141            message.as_ref(),
142            predicate,
143            *output,
144        ),
145        BlackBoxFuncCall::MultiScalarMul { points, scalars, outputs, predicate } => {
146            multi_scalar_mul(backend, initial_witness, points, scalars, *predicate, *outputs)
147        }
148        BlackBoxFuncCall::EmbeddedCurveAdd { input1, input2, outputs, predicate } => {
149            embedded_curve_add(backend, initial_witness, **input1, **input2, *predicate, *outputs)
150        }
151        // Recursive aggregation will be entirely handled by the backend and is not solved by the ACVM
152        BlackBoxFuncCall::RecursiveAggregation { .. } => Ok(()),
153        BlackBoxFuncCall::Sha256Compression { inputs, hash_values, outputs } => {
154            solve_sha_256_permutation_opcode(initial_witness, inputs, hash_values, outputs)
155        }
156        BlackBoxFuncCall::Poseidon2Permutation { inputs, outputs } => {
157            solve_poseidon2_permutation_opcode(backend, initial_witness, inputs, outputs)
158        }
159    }
160}
acvm/pwg/blackbox/mod.rs

acvm/pwg/blackbox/
mod.rs
