sp1_core_machine/memory/instructions/
mod.rs

1use columns::NUM_MEMORY_INSTRUCTIONS_COLUMNS;
2use p3_air::BaseAir;
3
4pub mod air;
5pub mod columns;
6pub mod trace;
7
8#[derive(Default)]
9pub struct MemoryInstructionsChip;
10
11impl<F> BaseAir<F> for MemoryInstructionsChip {
12    fn width(&self) -> usize {
13        NUM_MEMORY_INSTRUCTIONS_COLUMNS
14    }
15}
16
17#[cfg(test)]
18mod tests {
19    use std::borrow::BorrowMut;
20
21    use p3_baby_bear::BabyBear;
22    use p3_field::AbstractField;
23    use p3_matrix::dense::RowMajorMatrix;
24    use sp1_core_executor::{
25        events::MemoryRecordEnum, ExecutionRecord, Instruction, Opcode, Program,
26    };
27    use sp1_stark::{
28        air::MachineAir, baby_bear_poseidon2::BabyBearPoseidon2, chip_name, CpuProver,
29        MachineProver, Val,
30    };
31
32    use crate::{
33        io::SP1Stdin,
34        memory::{columns::MemoryInstructionsColumns, MemoryInstructionsChip},
35        riscv::RiscvAir,
36        utils::run_malicious_test,
37    };
38
39    enum FailureType {
40        ConstraintsFailing,
41        CumulativeSumFailing,
42    }
43
44    struct TestCase {
45        opcode: Opcode,
46        incorrect_value: u32,
47        failure_type: FailureType,
48    }
49
50    #[test]
51    fn test_malicious_stores() {
52        let test_cases = vec![
53            TestCase {
54                opcode: Opcode::SW,
55                incorrect_value: 8,
56                failure_type: FailureType::ConstraintsFailing,
57            }, // The correct value is 0xDEADBEEF.
58            TestCase {
59                opcode: Opcode::SH,
60                incorrect_value: 0xDEADBEEF,
61                failure_type: FailureType::ConstraintsFailing,
62            }, // The correct value is 0xBEEF.
63            TestCase {
64                opcode: Opcode::SB,
65                incorrect_value: 0xDEADBEEF,
66                failure_type: FailureType::ConstraintsFailing,
67            }, // The correct value is 0xEF.
68        ];
69
70        for test_case in test_cases {
71            let instructions = vec![
72                Instruction::new(Opcode::ADD, 29, 0, 0xDEADBEEF, false, true), /* Set the stored
73                                                                                * value to 5. */
74                Instruction::new(Opcode::ADD, 30, 0, 100, false, true), // Set the address to 100.
75                Instruction::new(test_case.opcode, 29, 30, 0, false, true),
76            ];
77            let program = Program::new(instructions, 0, 0);
78            let stdin = SP1Stdin::new();
79
80            type P = CpuProver<BabyBearPoseidon2, RiscvAir<BabyBear>>;
81
82            let malicious_trace_pv_generator =
83                move |prover: &P,
84                      record: &mut ExecutionRecord|
85                      -> Vec<(String, RowMajorMatrix<Val<BabyBearPoseidon2>>)> {
86                    // Create a malicious record where the incorrect value is saved to memory.
87                    let mut malicious_record = record.clone();
88                    if let MemoryRecordEnum::Write(mem_write_record) =
89                        &mut malicious_record.memory_instr_events[0].mem_access
90                    {
91                        mem_write_record.value = test_case.incorrect_value;
92                    }
93                    prover.generate_traces(&malicious_record)
94                };
95
96            let result =
97                run_malicious_test::<P>(program, stdin, Box::new(malicious_trace_pv_generator));
98
99            match test_case.failure_type {
100                FailureType::ConstraintsFailing => {
101                    let memory_instr_chip_name = chip_name!(MemoryInstructionsChip, BabyBear);
102                    assert!(
103                        result.is_err() &&
104                            result.unwrap_err().is_constraints_failing(&memory_instr_chip_name)
105                    );
106                }
107                FailureType::CumulativeSumFailing => {
108                    assert!(
109                        result.is_err() && result.unwrap_err().is_local_cumulative_sum_failing()
110                    );
111                }
112            }
113        }
114    }
115
116    #[test]
117    fn test_malicious_loads() {
118        let test_cases = vec![
119            TestCase {
120                opcode: Opcode::LW,
121                incorrect_value: 8,
122                failure_type: FailureType::ConstraintsFailing,
123            }, // The correct value is 0xDEADBEEF.
124            TestCase {
125                opcode: Opcode::LH,
126                incorrect_value: 0xDEADBEEF,
127                failure_type: FailureType::CumulativeSumFailing,
128            }, // The correct value is 0xFFFFBEEF.
129            TestCase {
130                opcode: Opcode::LHU,
131                incorrect_value: 0xDEADBEEF,
132                failure_type: FailureType::ConstraintsFailing,
133            }, // The correct value is 0xBEEF.
134            TestCase {
135                opcode: Opcode::LB,
136                incorrect_value: 0xDEADBEEF,
137                failure_type: FailureType::CumulativeSumFailing,
138            }, // The correct value is 0xEF.
139            TestCase {
140                opcode: Opcode::LBU,
141                incorrect_value: 0xDEADBEEF,
142                failure_type: FailureType::ConstraintsFailing,
143            }, // The correct value is 0xFFFFEF.
144        ];
145
146        for test_case in test_cases {
147            let instructions = vec![
148                Instruction::new(Opcode::ADD, 29, 0, 0xDEADBEEF, false, true), /* Set the stored value to 0xDEADBEEF. */
149                Instruction::new(Opcode::ADD, 30, 0, 100, false, true), // Set the address to 100.
150                Instruction::new(Opcode::SW, 29, 30, 0, false, true),   /* Store the value to
151                                                                         * memory. */
152                Instruction::new(test_case.opcode, 25, 30, 0, false, true), /* Load the value
153                                                                             * from memory. */
154            ];
155            let program = Program::new(instructions, 0, 0);
156            let stdin = SP1Stdin::new();
157
158            type P = CpuProver<BabyBearPoseidon2, RiscvAir<BabyBear>>;
159
160            let malicious_trace_pv_generator =
161                move |prover: &P,
162                      record: &mut ExecutionRecord|
163                      -> Vec<(String, RowMajorMatrix<Val<BabyBearPoseidon2>>)> {
164                    // Create a malicious record where the incorrect value is loaded from memory.
165                    let mut malicious_record = record.clone();
166                    malicious_record.cpu_events[3].a = test_case.incorrect_value;
167                    malicious_record.memory_instr_events[1].a = test_case.incorrect_value;
168                    prover.generate_traces(&malicious_record)
169                };
170
171            let result =
172                run_malicious_test::<P>(program, stdin, Box::new(malicious_trace_pv_generator));
173
174            match test_case.failure_type {
175                FailureType::ConstraintsFailing => {
176                    let memory_instr_chip_name = chip_name!(MemoryInstructionsChip, BabyBear);
177                    assert!(
178                        result.is_err() &&
179                            result.unwrap_err().is_constraints_failing(&memory_instr_chip_name)
180                    );
181                }
182                FailureType::CumulativeSumFailing => {
183                    assert!(
184                        result.is_err() && result.unwrap_err().is_local_cumulative_sum_failing()
185                    );
186                }
187            }
188        }
189    }
190
191    #[test]
192    fn test_malicious_multiple_opcode_flags() {
193        let instructions = vec![
194            Instruction::new(Opcode::ADD, 29, 0, 5, false, true), // Set the stored value to 5.
195            Instruction::new(Opcode::ADD, 30, 0, 100, false, true), // Set the address to 100.
196            Instruction::new(Opcode::SW, 29, 30, 0, false, true),
197        ];
198        let program = Program::new(instructions, 0, 0);
199        let stdin = SP1Stdin::new();
200
201        type P = CpuProver<BabyBearPoseidon2, RiscvAir<BabyBear>>;
202
203        let malicious_trace_pv_generator =
204            |prover: &P,
205             record: &mut ExecutionRecord|
206             -> Vec<(String, RowMajorMatrix<Val<BabyBearPoseidon2>>)> {
207                // Modify the branch chip to have a row that has multiple opcode flags set.
208                let mut traces = prover.generate_traces(record);
209                let memory_instr_chip_name = chip_name!(MemoryInstructionsChip, BabyBear);
210                for (chip_name, trace) in traces.iter_mut() {
211                    if *chip_name == memory_instr_chip_name {
212                        let first_row: &mut [BabyBear] = trace.row_mut(0);
213                        let first_row: &mut MemoryInstructionsColumns<BabyBear> =
214                            first_row.borrow_mut();
215                        assert!(first_row.is_sw == BabyBear::one());
216                        first_row.is_lw = BabyBear::one();
217                    }
218                }
219                traces
220            };
221
222        let result =
223            run_malicious_test::<P>(program, stdin, Box::new(malicious_trace_pv_generator));
224        let memory_instr_chip_name = chip_name!(MemoryInstructionsChip, BabyBear);
225        assert!(
226            result.is_err() && result.unwrap_err().is_constraints_failing(&memory_instr_chip_name)
227        );
228    }
229}
sp1_core_machine/memory/instructions/mod.rs

sp1_core_machine/memory/instructions/
mod.rs
