openvm_native_circuit/poseidon2/columns.rs
1use openvm_circuit::system::memory::offline_checker::{MemoryReadAuxCols, MemoryWriteAuxCols};
2use openvm_circuit_primitives_derive::AlignedBorrow;
3use openvm_poseidon2_air::Poseidon2SubCols;
4
5use crate::{poseidon2::CHUNK, utils::const_max};
6
7/// A valid trace is composed of four types of contiguous blocks:
8///
9/// 1. **Disabled Block:** A single row marked as disabled.
10/// 2. **Simple Block:** A single row handling permutation/compression operations.
11/// 3. **Inside-Row Block:** A sequence of rows that compute the row-hash for all input matrix
12/// columns corresponding to an `MmcsVerifyBatch` input of the same height.
13/// 4. **Top-Level Block:** A sequence of rows that perform Merkle tree compression on the row hashes
14/// produced from an `MmcsVerifyBatch` input.
15#[repr(C)]
16#[derive(AlignedBorrow)]
17pub struct NativePoseidon2Cols<T, const SBOX_REGISTERS: usize> {
18 /// Columns required to compute Poseidon2 permutation.
19 pub inner: Poseidon2SubCols<T, SBOX_REGISTERS>,
20
21 // Mode-of-operation flags. Each flag is boolean, and at most one may be true.
22 // If none are true, the row is disabled.
23 /// Indicates that this top-level block row is in incorporate-row mode.
24 pub incorporate_row: T,
25 /// Indicates that this top-level block row is in incorporate-sibling mode.
26 pub incorporate_sibling: T,
27 /// Indicates that this row is part of an inside-row block.
28 pub inside_row: T,
29 /// Indicates that this row is a simple row.
30 pub simple: T,
31
32 /// Indicates the last row in an inside-row block.
33 pub end_inside_row: T,
34 /// Indicates the last row in a top-level block.
35 pub end_top_level: T,
36 /// Indicates the first row in a top-level block.
37 pub start_top_level: T,
38
39 /// The initial timestamp of the instruction, which must be identical for all top-level and
40 /// inside-row rows associated with the same instruction.
41 pub very_first_timestamp: T,
42 /// The starting timestamp of this row.
43 pub start_timestamp: T,
44
45 /// Operand `g` from the instruction. The multiplicative inverse of the size of an opened value
46 /// in the opened values array. Must be consistent for all top-level and inside-row rows
47 /// associated with the same instruction.
48 pub opened_element_size_inv: T,
49
50 /// On an `incorporate_row` row, this is the first matrix index `i` for which `log_heights[i]` equals `log_height`.
51 /// On an `incorporate_sibling` row, this holds the initial index corresponding to the `log_height` for the next
52 /// `incorporate_row` row, or `opened_length` if none exists.
53 pub initial_opened_index: T,
54
55 /// Pointer to the beginning of the `opened_values` array.
56 pub opened_base_pointer: T,
57
58 /// For rows that are not inside-row, this field should be 0. Otherwise, `is_exhausted[i]`
59 /// indicates that cell `i + 1` inside a chunk is exhausted.
60 pub is_exhausted: [T; CHUNK - 1],
61
62 pub specific: [T; max3(
63 TopLevelSpecificCols::<usize>::width(),
64 InsideRowSpecificCols::<usize>::width(),
65 SimplePoseidonSpecificCols::<usize>::width(),
66 )],
67}
68
69const fn max3(a: usize, b: usize, c: usize) -> usize {
70 const_max(a, const_max(b, c))
71}
72#[repr(C)]
73#[derive(AlignedBorrow)]
74pub struct TopLevelSpecificCols<T> {
75 /// The program counter for the VERIFY_BATCH instruction being processed.
76 pub pc: T,
77
78 /// The timestamp marking the end of processing this top-level row. For an `incorporate_sibling` row,
79 /// it increases by a fixed amount. For an `incorporate_row` row, its increase depends on the row's length
80 /// and the number of matrices involved, with additional constraints imposed by the internal bus.
81 pub end_timestamp: T,
82
83 /// Operand `a` from the instruction. Pointer to the `dimensions` array.
84 pub dim_register: T,
85 /// Operand `b` from the instruction. Pointer to the pointer of the `opened_values` array.
86 pub opened_register: T,
87 /// Operand `c` from the instruction. Pointer to the length of the `opened_values` array.
88 pub opened_length_register: T,
89 /// Operand `d` from the instruction. Provided as a hint to the run-time and (otherwise unconstrained).
90 pub proof_id: T,
91 /// Operand `e` from the instruction. Pointer to the pointer of the `index_bits` array, which
92 /// indicates the direction (left/right) of Merkle tree siblings.
93 pub index_register: T,
94 /// Operand `f` from the instruction. Pointer to the pointer of the expected Merkle root.
95 pub commit_register: T,
96
97 /// For an `incorporate_row` row, the largest matrix index `i` such that `log_heights[i]` equals `log_height`.
98 /// For an `incorporate_sibling` row, this is set to `initial_opened_index - 1` for bookkeeping.
99 pub final_opened_index: T,
100
101 /// The log height of the matrices currently being incorporated. Remains fixed on
102 /// `incorporate_row` rows and decreases by one on `incorporate_sibling` rows.
103 pub log_height: T,
104 /// The length of the `opened_values` array, i.e., the number of non-empty traces.
105 /// Equal to the value read in `opened_length_register`. Also constrained on the final row of
106 /// the top-level block (constraint depends on if we end with an `incorporate_row` or an
107 /// `incorporate_sibling`).
108 pub opened_length: T,
109
110 /// Pointer to the array of log heights.
111 pub dim_base_pointer: T,
112 /// Pointer to the array indicating Merkle proof directions.
113 pub index_base_pointer: T,
114
115 /// Memory aux columns for `dim_base_pointer` read.
116 pub dim_base_pointer_read: MemoryReadAuxCols<T>,
117 /// Memory aux columns for `opened_base_pointer` read.
118 pub opened_base_pointer_read: MemoryReadAuxCols<T>,
119 /// Memory aux columns for `opened_length` read.
120 pub opened_length_read: MemoryReadAuxCols<T>,
121 /// Memory aux columns for `index_base_pointer` read.
122 pub index_base_pointer_read: MemoryReadAuxCols<T>,
123 /// Memory aux columns for `commit_pointer` read.
124 pub commit_pointer_read: MemoryReadAuxCols<T>,
125
126 /// Index into the Merkle proof for the next sibling to incorporate.
127 /// Starts at zero in a top-level block and increments by one after each `incorporate_sibling` row.
128 pub proof_index: T,
129
130 /// Memory aux columns for reading either `initial_height` or `sibling_is_on_right`. On an
131 /// `incorporate_row` row, aux columns for reading `dims[initial_opened_index]`, and otherwise
132 /// aux columns for `index_bits[proof_index]`.
133 pub read_initial_height_or_sibling_is_on_right: MemoryReadAuxCols<T>,
134 /// Memory aux columns for reading `dims[final_opened_index]`.
135 pub read_final_height: MemoryReadAuxCols<T>,
136
137 /// Indicator for whether the sibling being incorporated (if any) is on the right. Constrained
138 /// to equal `index_bits[proof_index]` on `incorporate_sibling` rows. Unconstrained on other rows.
139 pub sibling_is_on_right: T,
140 /// Pointer to the Merkle root.
141 pub commit_pointer: T,
142 /// Memory aux columns for reading the Merkle root.
143 pub commit_read: MemoryReadAuxCols<T>,
144}
145
146#[repr(C)]
147#[derive(AlignedBorrow)]
148pub struct InsideRowSpecificCols<T> {
149 /// The columns to constrain a sequence of consecutive opened values (possibly cross-matrix).
150 /// For an inside-row row, if `i == 0` or `is_exhausted[i - 1] != 0`, then `cells[i]` contains
151 /// the information about which array the opened-value came from.
152 pub cells: [VerifyBatchCellCols<T>; CHUNK],
153}
154
155/// Information about an opened value. We refer to `opened_values` as the two-dimensional array of
156/// opened values; `opened_values[idx]` is an array of opened values.
157#[repr(C)]
158#[derive(AlignedBorrow, Copy, Clone)]
159pub struct VerifyBatchCellCols<T> {
160 /// Memory aux columns for the opened value.
161 pub read: MemoryReadAuxCols<T>,
162 /// The index into the `opened_values` array that this opened value came from.
163 pub opened_index: T,
164 /// Memory aux columns for reading `row_pointer` and length determining `row_end`; only used
165 /// when `is_first_in_row = 1`.
166 pub read_row_pointer_and_length: MemoryReadAuxCols<T>,
167 /// Pointer to the opened value itself.
168 pub row_pointer: T,
169 /// Pointer just after the row given by `opened_values[opened_index]`.
170 pub row_end: T,
171 /// Whether this cell corresponds to `opened_values[opened_index][0]`.
172 pub is_first_in_row: T,
173}
174
175#[repr(C)]
176#[derive(AlignedBorrow, Copy, Clone)]
177pub struct SimplePoseidonSpecificCols<T> {
178 pub pc: T,
179 pub is_compress: T,
180 // instruction (a, b, c)
181 pub output_register: T,
182 pub input_register_1: T,
183 pub input_register_2: T,
184
185 pub output_pointer: T,
186 pub input_pointer_1: T,
187 pub input_pointer_2: T,
188
189 pub read_output_pointer: MemoryReadAuxCols<T>,
190 pub read_input_pointer_1: MemoryReadAuxCols<T>,
191 pub read_input_pointer_2: MemoryReadAuxCols<T>,
192 pub read_data_1: MemoryReadAuxCols<T>,
193 pub read_data_2: MemoryReadAuxCols<T>,
194 pub write_data_1: MemoryWriteAuxCols<T, { CHUNK }>,
195 pub write_data_2: MemoryWriteAuxCols<T, { CHUNK }>,
196}