acvm/pwg/
memory_op.rs

1use acir::{
2    AcirField,
3    circuit::opcodes::{MemOp, MemOpKind},
4    native_types::{Witness, WitnessMap},
5};
6
7use super::{ErrorLocation, OpcodeResolutionError};
8use super::{insert_value, witness_to_value};
9
10type MemoryIndex = u32;
11
12/// Maintains the state for solving [`MemoryInit`][`acir::circuit::Opcode::MemoryInit`] and [`MemoryOp`][`acir::circuit::Opcode::MemoryOp`] opcodes.
13pub(crate) struct MemoryOpSolver<F> {
14    /// Known values of the memory block, based on the index
15    /// This vec starts as big as it needs to, when initialized,
16    /// then evolves as we process the opcodes.
17    pub(super) block_value: Vec<F>,
18}
19
20impl<F: AcirField> MemoryOpSolver<F> {
21    /// Creates a new `MemoryOpSolver` with the values given in `init`.
22    pub(crate) fn new(
23        init: &[Witness],
24        initial_witness: &WitnessMap<F>,
25    ) -> Result<Self, OpcodeResolutionError<F>> {
26        Ok(Self {
27            block_value: init
28                .iter()
29                .map(|witness| witness_to_value(initial_witness, *witness).copied())
30                .collect::<Result<Vec<_>, _>>()?,
31        })
32    }
33
34    pub(crate) fn len(&self) -> u32 {
35        u32::try_from(self.block_value.len()).expect("expected a length that fits into a u32")
36    }
37
38    /// Convert a field element into a memory index
39    /// Only 32 bits values are valid memory indices
40    pub(crate) fn index_from_field(
41        &self,
42        index: F,
43    ) -> Result<MemoryIndex, OpcodeResolutionError<F>> {
44        index.try_to_u32().ok_or_else({
45            || OpcodeResolutionError::IndexOutOfBounds {
46                opcode_location: ErrorLocation::Unresolved,
47                index,
48                array_size: self.len(),
49            }
50        })
51    }
52
53    /// Update the '`block_value`' map with the provided index/value
54    /// Returns an '`IndexOutOfBounds`' error if the index is outside the block range.
55    pub(crate) fn write_memory_index(
56        &mut self,
57        index: MemoryIndex,
58        value: F,
59    ) -> Result<(), OpcodeResolutionError<F>> {
60        if index >= self.len() {
61            return Err(OpcodeResolutionError::IndexOutOfBounds {
62                opcode_location: ErrorLocation::Unresolved,
63                index: F::from(u128::from(index)),
64                array_size: self.len(),
65            });
66        }
67
68        self.block_value[index as usize] = value;
69        Ok(())
70    }
71
72    /// Returns the value stored in the '`block_value`' map for the provided index
73    /// Returns an '`IndexOutOfBounds`' error if the index is not in the map.
74    pub(crate) fn read_memory_index(
75        &self,
76        index: MemoryIndex,
77    ) -> Result<F, OpcodeResolutionError<F>> {
78        self.block_value.get(index as usize).copied().ok_or(
79            OpcodeResolutionError::IndexOutOfBounds {
80                opcode_location: ErrorLocation::Unresolved,
81                index: F::from(u128::from(index)),
82                array_size: self.len(),
83            },
84        )
85    }
86
87    /// Update the '`block_values`' by processing the provided Memory opcode
88    /// The opcode 'op' contains the index and value of the operation and the type
89    /// of the operation.
90    /// They are all stored as an [`acir::native_types::Expression`]
91    /// The type of 'operation' is '0' for a read and '1' for a write. It must be a constant
92    /// expression.
93    /// Index is not required to be constant but it must reduce to a known value
94    /// for processing the opcode. This is done by doing the (partial) evaluation of its expression,
95    /// using the provided witness map.
96    ///
97    /// READ: read the block at index op.index and update op.value with the read value
98    /// - 'op.value' must reduce to a witness (after the evaluation of its expression)
99    /// - the value is updated in the provided witness map, for the 'op.value' witness
100    ///
101    /// WRITE: update the block at index 'op.index' with 'op.value'
102    /// - 'op.value' must reduce to a known value
103    ///
104    /// If a requirement is not met, it returns an error.
105    pub(crate) fn solve_memory_op(
106        &mut self,
107        op: &MemOp,
108        initial_witness: &mut WitnessMap<F>,
109    ) -> Result<(), OpcodeResolutionError<F>> {
110        // Find the memory index associated with this memory operation.
111        let index = *witness_to_value(initial_witness, op.index)?;
112        let memory_index = self.index_from_field(index)?;
113
114        match op.operation {
115            MemOpKind::Read => {
116                // `value_read = arr[memory_index]`
117                let value_in_array = self.read_memory_index(memory_index)?;
118                insert_value(&op.value, value_in_array, initial_witness)
119            }
120            MemOpKind::Write => {
121                // `arr[memory_index] = value_write`
122                let value_to_write = *witness_to_value(initial_witness, op.value)?;
123                self.write_memory_index(memory_index, value_to_write)
124            }
125        }
126    }
127}
128
129#[cfg(test)]
130mod tests {
131    use std::collections::BTreeMap;
132
133    use acir::{
134        FieldElement,
135        circuit::opcodes::MemOp,
136        native_types::{Witness, WitnessMap},
137    };
138
139    use super::MemoryOpSolver;
140
141    #[test]
142    fn test_solver() {
143        let mut initial_witness = WitnessMap::from(BTreeMap::from_iter([
144            (Witness(1), FieldElement::from(1u128)),
145            (Witness(2), FieldElement::from(1u128)),
146            (Witness(3), FieldElement::from(2u128)),
147        ]));
148
149        let init = vec![Witness(1), Witness(2)];
150        // Write the value '2' at index '1' (Witness(1) holds value 1), then read into witness 4
151        let trace = vec![
152            MemOp::write_to_mem_index(Witness(1), Witness(3)),
153            MemOp::read_at_mem_index(Witness(1), Witness(4)),
154        ];
155
156        let mut block_solver = MemoryOpSolver::new(&init, &initial_witness).unwrap();
157
158        for op in trace {
159            block_solver.solve_memory_op(&op, &mut initial_witness).unwrap();
160        }
161
162        assert_eq!(initial_witness[&Witness(4)], FieldElement::from(2u128));
163    }
164
165    #[test]
166    fn test_index_out_of_bounds() {
167        let mut initial_witness = WitnessMap::from(BTreeMap::from_iter([
168            (Witness(1), FieldElement::from(1u128)),
169            (Witness(2), FieldElement::from(1u128)),
170            (Witness(3), FieldElement::from(2u128)),
171        ]));
172
173        let init = vec![Witness(1), Witness(2)];
174        // Write at index '1' (Witness(1)=1), then read at index '2' (Witness(3)=2) — out of bounds.
175        let invalid_trace = vec![
176            MemOp::write_to_mem_index(Witness(1), Witness(3)),
177            MemOp::read_at_mem_index(Witness(3), Witness(4)),
178        ];
179        let mut block_solver = MemoryOpSolver::new(&init, &initial_witness).unwrap();
180        let mut err = None;
181        for op in invalid_trace {
182            if err.is_none() {
183                err = block_solver.solve_memory_op(&op, &mut initial_witness).err();
184            }
185        }
186
187        assert!(matches!(
188            err,
189            Some(crate::pwg::OpcodeResolutionError::IndexOutOfBounds {
190                opcode_location: _,
191                index,
192                array_size: 2
193            }) if index == FieldElement::from(2u128)
194        ));
195    }
196}
acvm/pwg/memory_op.rs

acvm/pwg/
memory_op.rs
