miden_core/deferred/
witness.rs

1use alloc::vec::Vec;
2
3use super::{
4    DeferredState, Digest, IntegrityError, MAX_PRECOMPILE_ROOTS, PrecompileError, TRUE_DIGEST,
5};
6
7/// A hydrated witness for one or more ordered deferred precompile roots.
8///
9/// Execution constructs singleton witnesses. [`Self::merge`] combines only singleton inputs and
10/// retains their roots in input order, including duplicates.
11///
12/// A witness may contain private execution data and a large hydrated DAG. Treat it as sensitive
13/// prover input, and prefer borrowing it during proving instead of cloning it.
14#[derive(Debug, Clone)]
15pub struct PrecompileWitness {
16    state: DeferredState,
17    roots: Vec<Digest>,
18}
19
20impl PrecompileWitness {
21    /// Creates a singleton witness from a hydrated, non-empty deferred execution state.
22    ///
23    /// This is the supported low-level constructor for callers that already own a
24    /// [`DeferredState`]. It retains the state's current root as the witness's sole ordered root
25    /// and rejects [`TRUE_DIGEST`], which represents an execution with no deferred statements.
26    pub fn new(state: DeferredState) -> Result<Self, PrecompileWitnessError> {
27        let root = state.root();
28        if root == TRUE_DIGEST {
29            return Err(PrecompileWitnessError::TrueRoot);
30        }
31
32        Ok(Self { state, roots: alloc::vec![root] })
33    }
34
35    /// Returns the ordered non-TRUE execution roots used as precompile-proof metadata.
36    ///
37    /// Singleton witnesses contain one root. Merged witnesses preserve input order and duplicate
38    /// occurrences because both are significant to the aggregate precompile statement.
39    pub fn roots(&self) -> &[Digest] {
40        &self.roots
41    }
42
43    /// Returns the hydrated deferred state consumed by precompile proving.
44    ///
45    /// The state may contain private execution data and can be large, so callers should prefer this
46    /// borrowed access over cloning the witness.
47    pub fn state(&self) -> &DeferredState {
48        &self.state
49    }
50
51    /// Merges ordered singleton witnesses into one aggregate witness.
52    ///
53    /// All inputs are checked for singleton shape before any deferred state is consumed. Singleton
54    /// eligibility means `roots.len() == 1`; execution provenance is not encoded or verified.
55    /// Witnesses retaining multiple roots are rejected, so roots cannot be regrouped or merged
56    /// recursively. The complete merged state is bounded by [`super::MAX_DEFERRED_ELEMENTS`].
57    pub fn merge(witnesses: Vec<Self>) -> Result<Self, PrecompileWitnessError> {
58        if witnesses.is_empty() {
59            return Err(PrecompileWitnessError::EmptyMerge);
60        }
61        if witnesses.len() > MAX_PRECOMPILE_ROOTS {
62            return Err(PrecompileWitnessError::TooManyRoots {
63                roots: witnesses.len(),
64                max: MAX_PRECOMPILE_ROOTS,
65            });
66        }
67
68        for witness in &witnesses {
69            if witness.roots.len() != 1 {
70                return Err(PrecompileWitnessError::NonSingleton);
71            }
72        }
73
74        let roots = witnesses.iter().map(|witness| witness.roots[0]).collect::<Vec<_>>();
75        let mut witnesses = witnesses.into_iter();
76        let mut state = witnesses
77            .next()
78            .expect("non-empty witness input was checked above")
79            .state
80            .compact()
81            .map_err(PrecompileWitnessError::Merge)?;
82
83        for witness in witnesses {
84            state = state.merge(witness.state).map_err(PrecompileWitnessError::Merge)?;
85        }
86
87        Ok(Self { state, roots })
88    }
89}
90
91/// Errors produced while constructing or merging precompile witnesses.
92#[derive(Debug, thiserror::Error)]
93pub enum PrecompileWitnessError {
94    /// A witness cannot represent an empty deferred execution.
95    #[error("precompile witness roots must differ from TRUE_DIGEST")]
96    TrueRoot,
97
98    /// A merge operation requires at least one singleton witness.
99    #[error("cannot merge an empty precompile witness list")]
100    EmptyMerge,
101    /// The ordered root sequence exceeds the hard allocation and folding safety ceiling.
102    #[error("precompile witness contains too many roots: found {roots}, maximum is {max}")]
103    TooManyRoots { roots: usize, max: usize },
104    /// Merge inputs must come directly from individual executions.
105    #[error("precompile witness merge inputs must each contain exactly one root")]
106    NonSingleton,
107    /// Sequential deferred-state aggregation failed.
108    #[error("failed to merge deferred precompile states: {0}")]
109    Merge(#[source] PrecompileError),
110    /// Deferred wire rehydration failed.
111    #[error(transparent)]
112    Integrity(#[from] IntegrityError),
113}
114
115#[cfg(test)]
116mod tests {
117    use alloc::sync::Arc;
118
119    use super::*;
120    use crate::{
121        Felt, ZERO,
122        deferred::{
123            DeferredContext, Node, NodeType, Payload, Precompile, PrecompileRegistry, Tag,
124            precompile_id,
125        },
126    };
127
128    fn framework_state(statement_depth: usize) -> DeferredState {
129        let mut state = DeferredState::default();
130        let mut statement = TRUE_DIGEST;
131        for _ in 0..statement_depth {
132            statement = state.register(Node::and(statement, TRUE_DIGEST)).unwrap();
133        }
134        state.log_statement(statement).unwrap();
135        state
136    }
137
138    fn singleton(statement_depth: usize) -> PrecompileWitness {
139        PrecompileWitness::new(framework_state(statement_depth)).unwrap()
140    }
141
142    #[derive(Debug, Clone, Copy)]
143    struct FixturePrecompile;
144
145    impl FixturePrecompile {
146        const NAME: &'static str = "precompile-witness-fixture";
147
148        fn tag() -> Tag {
149            Tag::precompile(precompile_id(Self::NAME), [ZERO; 3])
150                .expect("fixture id is precompile-owned")
151        }
152    }
153
154    impl Precompile for FixturePrecompile {
155        fn name(&self) -> &'static str {
156            Self::NAME
157        }
158
159        fn id(&self) -> Felt {
160            precompile_id(self.name())
161        }
162
163        fn decode(&self, args: [Felt; 3]) -> Option<NodeType> {
164            (args == [ZERO; 3]).then_some(NodeType::Data)
165        }
166
167        fn evaluate(
168            &self,
169            _args: [Felt; 3],
170            _payload: &Payload,
171            _context: &mut DeferredContext<'_>,
172        ) -> Result<Node, PrecompileError> {
173            Ok(Node::TRUE)
174        }
175    }
176
177    fn fixture_witness() -> PrecompileWitness {
178        let registry = Arc::new(PrecompileRegistry::new().with_precompile(FixturePrecompile));
179        let mut state = DeferredState::new(registry).unwrap();
180        let statement = state
181            .register(Node::value(FixturePrecompile::tag(), [ZERO; 8]).unwrap())
182            .unwrap();
183        state.log_statement(statement).unwrap();
184        PrecompileWitness::new(state).unwrap()
185    }
186
187    #[test]
188    fn singleton_construction_rejects_true_and_retains_execution_root() {
189        assert!(matches!(
190            PrecompileWitness::new(DeferredState::default()),
191            Err(PrecompileWitnessError::TrueRoot)
192        ));
193
194        let state = framework_state(1);
195        let root = state.root();
196        let witness = PrecompileWitness::new(state).unwrap();
197
198        assert_eq!(witness.roots(), &[root]);
199    }
200
201    #[test]
202    fn merge_rejects_empty_input() {
203        assert!(matches!(
204            PrecompileWitness::merge(Vec::new()),
205            Err(PrecompileWitnessError::EmptyMerge)
206        ));
207    }
208
209    #[test]
210    fn merge_preserves_order_and_compacts_the_first_state() {
211        let mut first_state = framework_state(1);
212        let orphan = first_state.register(Node::chunks(alloc::vec![[ZERO; 8]]).unwrap()).unwrap();
213        let first = PrecompileWitness::new(first_state).unwrap();
214        let second = singleton(2);
215        let first_root = first.roots()[0];
216        let second_root = second.roots()[0];
217
218        let ordered = PrecompileWitness::merge(alloc::vec![first.clone(), second.clone()]).unwrap();
219        let reversed = PrecompileWitness::merge(alloc::vec![second, first]).unwrap();
220
221        assert_eq!(ordered.roots(), &[first_root, second_root]);
222        assert_eq!(reversed.roots(), &[second_root, first_root]);
223        assert!(ordered.state().get_node(&orphan).is_none());
224        assert!(reversed.state().get_node(&orphan).is_none());
225        assert_eq!(ordered.state().num_elements(), reversed.state().num_elements());
226        assert_eq!(ordered.state().remaining_elements(), reversed.state().remaining_elements());
227    }
228
229    #[test]
230    fn merge_preserves_duplicate_singleton_roots() {
231        let witness = singleton(1);
232        let root = witness.roots()[0];
233
234        let merged = PrecompileWitness::merge(alloc::vec![witness.clone(), witness]).unwrap();
235
236        assert_eq!(merged.roots(), &[root, root]);
237    }
238
239    #[test]
240    fn merge_rejects_an_already_merged_input_during_prevalidation() {
241        let merged = PrecompileWitness::merge(alloc::vec![singleton(1), singleton(2)]).unwrap();
242
243        let error = PrecompileWitness::merge(alloc::vec![singleton(3), fixture_witness(), merged])
244            .unwrap_err();
245
246        assert!(matches!(error, PrecompileWitnessError::NonSingleton));
247    }
248
249    #[test]
250    fn one_element_merge_remains_singleton() {
251        let witness = singleton(1);
252        let root = witness.roots()[0];
253
254        let merged = PrecompileWitness::merge(alloc::vec![witness]).unwrap();
255
256        assert_eq!(merged.roots(), &[root]);
257    }
258
259    #[test]
260    fn merge_rejects_excessive_root_count() {
261        let witnesses = alloc::vec![singleton(1); MAX_PRECOMPILE_ROOTS + 1];
262
263        assert!(matches!(
264            PrecompileWitness::merge(witnesses),
265            Err(PrecompileWitnessError::TooManyRoots {
266                roots,
267                max: MAX_PRECOMPILE_ROOTS,
268            }) if roots == MAX_PRECOMPILE_ROOTS + 1
269        ));
270    }
271}
miden_core/deferred/witness.rs

miden_core/deferred/
witness.rs
