triton_vm/
proof_item.rs

1use arbitrary::Arbitrary;
2use strum::Display;
3use strum::EnumCount;
4use strum::EnumDiscriminants;
5use strum::EnumIter;
6use twenty_first::prelude::*;
7
8use crate::error::ProofStreamError;
9use crate::error::ProofStreamError::UnexpectedItem;
10use crate::fri::AuthenticationStructure;
11use crate::table::AuxiliaryRow;
12use crate::table::MainRow;
13use crate::table::QuotientSegments;
14
15/// A `FriResponse` is an `AuthenticationStructure` together with the values of
16/// the revealed leaves of the Merkle tree. Together, they correspond to the
17/// queried indices of the FRI codeword (of that round).
18#[derive(Debug, Clone, Eq, PartialEq, Hash, BFieldCodec, Arbitrary)]
19pub struct FriResponse {
20    /// The authentication structure of the Merkle tree.
21    pub auth_structure: AuthenticationStructure,
22
23    /// The values of the opened leaves of the Merkle tree.
24    pub revealed_leaves: Vec<XFieldElement>,
25}
26
27macro_rules! proof_items {
28    ($($variant:ident($payload:ty) => $in_fiat_shamir_heuristic:literal, $try_into_fn:ident,)+) => {
29        #[derive(
30            Debug,
31            Display,
32            Clone,
33            Eq,
34            PartialEq,
35            Hash,
36            EnumCount,
37            EnumDiscriminants,
38            BFieldCodec,
39            Arbitrary,
40        )]
41        #[strum_discriminants(name(ProofItemVariant))]
42        // discriminants' default derives: Debug, Copy, Clone, Eq, PartialEq
43        #[strum_discriminants(derive(Display, EnumIter, BFieldCodec, Arbitrary))]
44        pub enum ProofItem {
45            $( $variant($payload), )+
46        }
47
48        impl ProofItem {
49            /// Whether a given proof item should be considered in the
50            /// Fiat-Shamir heuristic.
51            ///
52            /// The Fiat-Shamir heuristic is sound only if all elements in the
53            /// (current) transcript are considered. However, certain elements
54            /// indirectly appear more than once. For example, a Merkle root is
55            /// a commitment to any number of elements. If the Merkle root is
56            /// part of the transcript, has been considered in the Fiat-Shamir
57            /// heuristic, and assuming collision resistance of the hash
58            /// function in use, none of the committed-to elements have to be
59            /// considered in the Fiat-Shamir heuristic again. This also extends
60            /// to the authentication structure of these elements, et cetera.
61            pub const fn include_in_fiat_shamir_heuristic(&self) -> bool {
62                match self {
63                    $( Self::$variant(_) => $in_fiat_shamir_heuristic, )+
64                }
65            }
66
67            $(
68            pub fn $try_into_fn(self) -> Result<$payload, ProofStreamError> {
69                match self {
70                    Self::$variant(payload) => Ok(payload),
71                    _ => Err(UnexpectedItem {
72                        expected: ProofItemVariant::$variant,
73                        got: self,
74                    }),
75                }
76            }
77            )+
78        }
79
80        impl ProofItemVariant {
81            pub fn payload_static_length(self) -> Option<usize> {
82                match self {
83                    $( Self::$variant => <$payload>::static_length(), )+
84                }
85            }
86
87            /// See [`ProofItem::include_in_fiat_shamir_heuristic`].
88            pub const fn include_in_fiat_shamir_heuristic(self) -> bool {
89                match self {
90                    $( Self::$variant => $in_fiat_shamir_heuristic, )+
91                }
92            }
93
94            /// Can be used as “reflection”, for example through `syn`.
95            pub const fn payload_type(self) -> &'static str {
96                match self {
97                    $( Self::$variant => stringify!($payload), )+
98                }
99            }
100        }
101    };
102}
103
104proof_items!(
105    MerkleRoot(Digest) => true, try_into_merkle_root,
106    Log2PaddedHeight(u32) => true, try_into_log2_padded_height,
107    OutOfDomainMainRow(Box<MainRow<XFieldElement>>) => true, try_into_out_of_domain_main_row,
108    OutOfDomainAuxRow(Box<AuxiliaryRow>) => true, try_into_out_of_domain_aux_row,
109    OutOfDomainQuotientSegments(QuotientSegments) => true, try_into_out_of_domain_quot_segments,
110    FriPolynomial(Polynomial<'static, XFieldElement>) => true, try_into_fri_polynomial,
111
112    // For performance reasons (only!), the following items are not included in
113    // the Fiat-Shamir heuristic. The resulting proof system is still sound if
114    // (and only if!) the prover has already committed to the item in question
115    // in some other fashion.
116    //
117    // Before including additional items in the section below, make certain that
118    // the prover is _actually_ committed to the item in some other fashion.
119    // An oversight will lead (and has led) to soundness vulnerabilities. If you
120    // are unsure, better err on the side of performance degradation than on the
121    // side of an unsound verifier.
122    //
123    // Ideally, write down the argument right above the item; bonus points if
124    // you write down a proof instead. This helps in making assumptions (more)
125    // explicit.
126
127    // 1. An authentication structure is only valid with respect to some
128    //    `MerkleRoot`.
129    // 2. Merkle roots alter the Fiat-Shamir state, committing the prover.
130    // 3. For every authentication structure we supply, the corresponding Merkle
131    //    root is integrated into the proof stream first.
132    // 4. The verifier samples the indices the prover should open.
133    AuthenticationStructure(AuthenticationStructure) => false, try_into_authentication_structure,
134
135    // 1. A (main, aux, or quotient-segment) row is only hashed in full, never
136    //    partially.
137    // 2. All rows of a table are put into a Merkle tree.
138    // 3. The root of that tree is integrated into the proof stream before
139    //    any row is revealed.
140    // 4. The verifier dictates which rows to reveal.
141    MasterMainTableRows(Vec<MainRow<BFieldElement>>) => false, try_into_master_main_table_rows,
142    MasterAuxTableRows(Vec<AuxiliaryRow>) => false, try_into_master_aux_table_rows,
143    QuotientSegmentsElements(Vec<QuotientSegments>) => false, try_into_quot_segments_elements,
144
145    // 1. The Merkle root of the tree of the codeword is integrated into the
146    //    proof stream before the codeword is sent.
147    FriCodeword(Vec<XFieldElement>) => false, try_into_fri_codeword,
148
149    // Since a `FriResponse` is both, an authentication structure and some
150    // revealed elements, the arguments of `AuthenticationStructure` and the
151    // tables' rows apply.
152    FriResponse(FriResponse) => false, try_into_fri_response,
153);
154
155#[cfg(test)]
156#[cfg_attr(coverage_nightly, coverage(off))]
157pub(crate) mod tests {
158    use std::collections::HashSet;
159
160    use assert2::assert;
161    use assert2::let_assert;
162    use proptest::prelude::*;
163    use strum::IntoEnumIterator;
164
165    use crate::proof::Proof;
166    use crate::proof_stream::ProofStream;
167    use crate::shared_tests::LeavedMerkleTreeTestData;
168    use crate::tests::proptest;
169    use crate::tests::test;
170
171    use super::*;
172
173    #[macro_rules_attr::apply(proptest)]
174    fn serialize_fri_response_in_isolation(leaved_merkle_tree: LeavedMerkleTreeTestData) {
175        let fri_response = leaved_merkle_tree.into_fri_response();
176        let encoding = fri_response.encode();
177        let_assert!(Ok(decoding) = FriResponse::decode(&encoding));
178        prop_assert_eq!(fri_response, *decoding);
179    }
180
181    #[macro_rules_attr::apply(proptest)]
182    fn serialize_fri_response_in_proof_stream(leaved_merkle_tree: LeavedMerkleTreeTestData) {
183        let fri_response = leaved_merkle_tree.into_fri_response();
184        let mut proof_stream = ProofStream::new();
185        proof_stream.enqueue(ProofItem::FriResponse(fri_response.clone()));
186        let proof: Proof = proof_stream.into();
187
188        let_assert!(Ok(mut proof_stream) = ProofStream::try_from(&proof));
189        let_assert!(Ok(proof_item) = proof_stream.dequeue());
190        let_assert!(Ok(fri_response_) = proof_item.try_into_fri_response());
191        prop_assert_eq!(fri_response, fri_response_);
192    }
193
194    #[macro_rules_attr::apply(proptest)]
195    fn serialize_authentication_structure_in_isolation(
196        leaved_merkle_tree: LeavedMerkleTreeTestData,
197    ) {
198        let auth_structure = leaved_merkle_tree.auth_structure;
199        let encoding = auth_structure.encode();
200        let_assert!(Ok(decoding) = AuthenticationStructure::decode(&encoding));
201        prop_assert_eq!(auth_structure, *decoding);
202    }
203
204    #[macro_rules_attr::apply(proptest)]
205    fn serialize_authentication_structure_in_proof_stream(
206        leaved_merkle_tree: LeavedMerkleTreeTestData,
207    ) {
208        let auth_structure = leaved_merkle_tree.auth_structure;
209        let mut proof_stream = ProofStream::new();
210        proof_stream.enqueue(ProofItem::AuthenticationStructure(auth_structure.clone()));
211        let proof: Proof = proof_stream.into();
212
213        let_assert!(Ok(mut proof_stream) = ProofStream::try_from(&proof));
214        let_assert!(Ok(proof_item) = proof_stream.dequeue());
215        let_assert!(Ok(auth_structure_) = proof_item.try_into_authentication_structure());
216        prop_assert_eq!(auth_structure, auth_structure_);
217    }
218
219    #[macro_rules_attr::apply(test)]
220    fn interpreting_a_merkle_root_as_anything_else_gives_appropriate_error() {
221        let fake_root = Digest::default();
222        let item = ProofItem::MerkleRoot(fake_root);
223        assert!(let Err(UnexpectedItem{..}) = item.clone().try_into_authentication_structure());
224        assert!(let Err(UnexpectedItem{..}) = item.clone().try_into_fri_response());
225        assert!(let Err(UnexpectedItem{..}) = item.clone().try_into_master_main_table_rows());
226        assert!(let Err(UnexpectedItem{..}) = item.clone().try_into_master_aux_table_rows());
227        assert!(let Err(UnexpectedItem{..}) = item.clone().try_into_out_of_domain_main_row());
228        assert!(let Err(UnexpectedItem{..}) = item.clone().try_into_out_of_domain_aux_row());
229        assert!(let Err(UnexpectedItem{..}) = item.clone().try_into_out_of_domain_quot_segments());
230        assert!(let Err(UnexpectedItem{..}) = item.clone().try_into_log2_padded_height());
231        assert!(let Err(UnexpectedItem{..}) = item.clone().try_into_quot_segments_elements());
232        assert!(let Err(UnexpectedItem{..}) = item.clone().try_into_fri_codeword());
233        assert!(let Err(UnexpectedItem{..}) = item.try_into_fri_polynomial());
234    }
235
236    #[macro_rules_attr::apply(test)]
237    fn proof_item_payload_static_length_is_as_expected() {
238        assert!(let Some(_) =  ProofItemVariant::MerkleRoot.payload_static_length());
239        assert!(let Some(_) =  ProofItemVariant::Log2PaddedHeight.payload_static_length());
240        assert_eq!(None, ProofItemVariant::FriCodeword.payload_static_length());
241        assert_eq!(None, ProofItemVariant::FriResponse.payload_static_length());
242    }
243
244    #[macro_rules_attr::apply(test)]
245    fn can_loop_over_proof_item_variants() {
246        let all_discriminants: HashSet<_> = ProofItemVariant::iter()
247            .map(|variant| variant.bfield_codec_discriminant())
248            .collect();
249        assert_eq!(ProofItem::COUNT, all_discriminants.len());
250    }
251
252    #[macro_rules_attr::apply(test)]
253    fn proof_item_and_its_variant_have_same_bfield_codec_discriminant() {
254        assert_eq!(
255            ProofItem::MerkleRoot(Digest::default()).bfield_codec_discriminant(),
256            ProofItemVariant::MerkleRoot.bfield_codec_discriminant()
257        );
258        assert_eq!(
259            ProofItem::Log2PaddedHeight(0).bfield_codec_discriminant(),
260            ProofItemVariant::Log2PaddedHeight.bfield_codec_discriminant()
261        );
262        assert_eq!(
263            ProofItem::FriCodeword(vec![]).bfield_codec_discriminant(),
264            ProofItemVariant::FriCodeword.bfield_codec_discriminant()
265        );
266    }
267
268    #[macro_rules_attr::apply(test)]
269    fn proof_item_variants_payload_type_has_expected_format() {
270        assert_eq!("Digest", ProofItemVariant::MerkleRoot.payload_type());
271    }
272}
triton_vm/proof_item.rs

triton_vm/
proof_item.rs
