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                payload: None,
50            }
51        })
52    }
53
54    /// Update the '`block_value`' map with the provided index/value
55    /// Returns an '`IndexOutOfBounds`' error if the index is outside the block range.
56    pub(crate) fn write_memory_index(
57        &mut self,
58        index: MemoryIndex,
59        value: F,
60    ) -> Result<(), OpcodeResolutionError<F>> {
61        if index >= self.len() {
62            return Err(OpcodeResolutionError::IndexOutOfBounds {
63                opcode_location: ErrorLocation::Unresolved,
64                index: F::from(u128::from(index)),
65                array_size: self.len(),
66                payload: None,
67            });
68        }
69
70        self.block_value[index as usize] = value;
71        Ok(())
72    }
73
74    /// Returns the value stored in the '`block_value`' map for the provided index
75    /// Returns an '`IndexOutOfBounds`' error if the index is not in the map.
76    pub(crate) fn read_memory_index(
77        &self,
78        index: MemoryIndex,
79    ) -> Result<F, OpcodeResolutionError<F>> {
80        self.block_value.get(index as usize).copied().ok_or(
81            OpcodeResolutionError::IndexOutOfBounds {
82                opcode_location: ErrorLocation::Unresolved,
83                index: F::from(u128::from(index)),
84                array_size: self.len(),
85                payload: None,
86            },
87        )
88    }
89
90    /// Update the '`block_values`' by processing the provided Memory opcode
91    /// The opcode 'op' contains the index and value of the operation and the type
92    /// of the operation.
93    /// They are all stored as an [`acir::native_types::Expression`]
94    /// The type of 'operation' is '0' for a read and '1' for a write. It must be a constant
95    /// expression.
96    /// Index is not required to be constant but it must reduce to a known value
97    /// for processing the opcode. This is done by doing the (partial) evaluation of its expression,
98    /// using the provided witness map.
99    ///
100    /// READ: read the block at index op.index and update op.value with the read value
101    /// - 'op.value' must reduce to a witness (after the evaluation of its expression)
102    /// - the value is updated in the provided witness map, for the 'op.value' witness
103    ///
104    /// WRITE: update the block at index 'op.index' with 'op.value'
105    /// - 'op.value' must reduce to a known value
106    ///
107    /// If a requirement is not met, it returns an error.
108    pub(crate) fn solve_memory_op(
109        &mut self,
110        op: &MemOp,
111        initial_witness: &mut WitnessMap<F>,
112    ) -> Result<(), OpcodeResolutionError<F>> {
113        // Find the memory index associated with this memory operation.
114        let index = *witness_to_value(initial_witness, op.index)?;
115        let memory_index = self.index_from_field(index)?;
116
117        match op.operation {
118            MemOpKind::Read => {
119                // `value_read = arr[memory_index]`
120                let value_in_array = self.read_memory_index(memory_index)?;
121                insert_value(&op.value, value_in_array, initial_witness)
122            }
123            MemOpKind::Write => {
124                // `arr[memory_index] = value_write`
125                let value_to_write = *witness_to_value(initial_witness, op.value)?;
126                self.write_memory_index(memory_index, value_to_write)
127            }
128        }
129    }
130}
131
132#[cfg(test)]
133mod tests {
134    use std::collections::BTreeMap;
135
136    use acir::{
137        FieldElement,
138        circuit::opcodes::MemOp,
139        native_types::{Witness, WitnessMap},
140    };
141
142    use super::MemoryOpSolver;
143
144    #[test]
145    fn test_solver() {
146        let mut initial_witness = WitnessMap::from(BTreeMap::from_iter([
147            (Witness(1), FieldElement::from(1u128)),
148            (Witness(2), FieldElement::from(1u128)),
149            (Witness(3), FieldElement::from(2u128)),
150        ]));
151
152        let init = vec![Witness(1), Witness(2)];
153        // Write the value '2' at index '1' (Witness(1) holds value 1), then read into witness 4
154        let trace = vec![
155            MemOp::write_to_mem_index(Witness(1), Witness(3)),
156            MemOp::read_at_mem_index(Witness(1), Witness(4)),
157        ];
158
159        let mut block_solver = MemoryOpSolver::new(&init, &initial_witness).unwrap();
160
161        for op in trace {
162            block_solver.solve_memory_op(&op, &mut initial_witness).unwrap();
163        }
164
165        assert_eq!(initial_witness[&Witness(4)], FieldElement::from(2u128));
166    }
167
168    #[test]
169    fn test_index_out_of_bounds() {
170        let mut initial_witness = WitnessMap::from(BTreeMap::from_iter([
171            (Witness(1), FieldElement::from(1u128)),
172            (Witness(2), FieldElement::from(1u128)),
173            (Witness(3), FieldElement::from(2u128)),
174        ]));
175
176        let init = vec![Witness(1), Witness(2)];
177        // Write at index '1' (Witness(1)=1), then read at index '2' (Witness(3)=2) — out of bounds.
178        let invalid_trace = vec![
179            MemOp::write_to_mem_index(Witness(1), Witness(3)),
180            MemOp::read_at_mem_index(Witness(3), Witness(4)),
181        ];
182        let mut block_solver = MemoryOpSolver::new(&init, &initial_witness).unwrap();
183        let mut err = None;
184        for op in invalid_trace {
185            if err.is_none() {
186                err = block_solver.solve_memory_op(&op, &mut initial_witness).err();
187            }
188        }
189
190        assert!(matches!(
191            err,
192            Some(crate::pwg::OpcodeResolutionError::IndexOutOfBounds {
193                opcode_location: _,
194                index,
195                array_size: 2,
196                payload: None
197            }) if index == FieldElement::from(2u128)
198        ));
199    }
200}
acvm/pwg/memory_op.rs

acvm/pwg/
memory_op.rs
