triton_vm/
proof.rs

1use arbitrary::Arbitrary;
2use get_size2::GetSize;
3use isa::program::Program;
4use serde::Deserialize;
5use serde::Serialize;
6use twenty_first::prelude::*;
7
8use crate::error::ProofStreamError;
9use crate::proof_stream::ProofStream;
10
11/// A version tag for the combination of Triton VM's
12/// [instruction set architecture (ISA)][isa] as well as the
13/// [STARK proof system][crate::stark::Stark].
14/// This version changes whenever either of the two changes.
15///
16/// # Rationale
17///
18/// A change in the ISA might give a [`Program`] a new meaning, and an existing
19/// proof might erroneously attest to the “new” program's graceful halt. By
20/// bumping this version when changing the ISA, the old proof is surely invalid
21/// under the new version. If the program's meaning has not changed, or the new
22/// meaning is accepted, a new proof can be generated.
23///
24/// A change in the STARK proof system generally means that the verifier has to
25/// perform different operations to verify a proof. This means that existing
26/// proofs about some program _should_ be accepted as valid, but (generally) are
27/// not. This version helps to make the discrepancy explicit.
28///
29/// Note that proofs remain valid for their matching versions indefinitely.
30///
31/// This version is separate from the crate's semantic version to allow software
32/// upgrades with no semantic changes to both, the ISA and the proof system.
33pub const CURRENT_VERSION: u32 = 0;
34
35/// Contains the necessary cryptographic information to verify a computation.
36/// Should be used together with a [`Claim`].
37#[derive(Debug, Clone, Eq, PartialEq, Serialize, Deserialize, GetSize, BFieldCodec, Arbitrary)]
38pub struct Proof(pub Vec<BFieldElement>);
39
40impl Proof {
41    /// Get the height of the trace used during proof generation.
42    /// This is an upper bound on the length of the computation this proof is for.
43    /// It is one of the main contributing factors to the length of the FRI domain.
44    pub fn padded_height(&self) -> Result<usize, ProofStreamError> {
45        let mut log_2_padded_heights = ProofStream::try_from(self)?
46            .items
47            .into_iter()
48            .filter_map(|item| item.try_into_log2_padded_height().ok());
49
50        let log_2_padded_height = log_2_padded_heights
51            .next()
52            .ok_or(ProofStreamError::NoLog2PaddedHeight)?;
53        if log_2_padded_heights.next().is_some() {
54            return Err(ProofStreamError::TooManyLog2PaddedHeights);
55        }
56
57        Ok(1 << log_2_padded_height)
58    }
59}
60
61/// Contains the public information of a verifiably correct computation.
62/// A corresponding [`Proof`] is needed to verify the computation.
63/// One additional piece of public information not explicitly listed in the [`Claim`] is the
64/// `padded_height`, an upper bound on the length of the computation.
65/// It is derivable from a [`Proof`] by calling [`Proof::padded_height()`].
66#[derive(
67    Debug, Clone, Eq, PartialEq, Hash, Serialize, Deserialize, GetSize, BFieldCodec, Arbitrary,
68)]
69pub struct Claim {
70    /// The hash digest of the program that was executed. The hash function in use is [`Tip5`].
71    pub program_digest: Digest,
72
73    /// The version of the Triton VM instruction set architecture the
74    /// [`program_digest`][digest] is about, as well as of the STARK proof system
75    /// in use. See also: [`CURRENT_VERSION`].
76    ///
77    /// [digest]: Self::program_digest
78    pub version: u32,
79
80    /// The public input to the computation.
81    pub input: Vec<BFieldElement>,
82
83    /// The public output of the computation.
84    pub output: Vec<BFieldElement>,
85}
86
87impl Claim {
88    /// Create a new Claim.
89    ///
90    /// Assumes the version to be [`CURRENT_VERSION`]. The version can be changed
91    /// with method [`about_version`][Self::about_version].
92    pub fn new(program_digest: Digest) -> Self {
93        Self {
94            program_digest,
95            version: CURRENT_VERSION,
96            input: vec![],
97            output: vec![],
98        }
99    }
100
101    #[must_use]
102    pub fn about_program(program: &Program) -> Self {
103        Self::new(program.hash())
104    }
105
106    #[must_use]
107    pub fn with_input(mut self, input: impl Into<Vec<BFieldElement>>) -> Self {
108        self.input = input.into();
109        self
110    }
111
112    #[must_use]
113    pub fn with_output(mut self, output: Vec<BFieldElement>) -> Self {
114        self.output = output;
115        self
116    }
117
118    #[must_use]
119    pub fn about_version(mut self, version: u32) -> Self {
120        self.version = version;
121        self
122    }
123}
124
125#[cfg(test)]
126mod tests {
127    use assert2::assert;
128    use proptest::collection::vec;
129    use proptest::prelude::*;
130    use proptest_arbitrary_interop::arb;
131    use rand::prelude::*;
132    use test_strategy::proptest;
133
134    use crate::prelude::*;
135    use crate::proof_item::ProofItem;
136
137    use super::*;
138
139    impl Default for Claim {
140        /// For testing purposes only.
141        fn default() -> Self {
142            Self::new(Digest::default())
143        }
144    }
145
146    #[test]
147    fn claim_accepts_various_types_for_public_input() {
148        let _claim = Claim::default()
149            .with_input(bfe_vec![42])
150            .with_input(bfe_array![42])
151            .with_input(PublicInput::new(bfe_vec![42]));
152    }
153
154    #[proptest]
155    fn decode_proof(#[strategy(arb())] proof: Proof) {
156        let encoded = proof.encode();
157        let decoded = *Proof::decode(&encoded).unwrap();
158        prop_assert_eq!(proof, decoded);
159    }
160
161    #[proptest]
162    fn decode_claim(#[strategy(arb())] claim: Claim) {
163        let encoded = claim.encode();
164        let decoded = *Claim::decode(&encoded).unwrap();
165        prop_assert_eq!(claim, decoded);
166    }
167
168    #[proptest(cases = 10)]
169    fn proof_with_no_padded_height_gives_err(#[strategy(arb())] root: Digest) {
170        let mut proof_stream = ProofStream::new();
171        proof_stream.enqueue(ProofItem::MerkleRoot(root));
172        let proof: Proof = proof_stream.into();
173        let maybe_padded_height = proof.padded_height();
174        assert!(maybe_padded_height.is_err());
175    }
176
177    #[proptest(cases = 10)]
178    fn proof_with_multiple_padded_height_gives_err(#[strategy(arb())] root: Digest) {
179        let mut proof_stream = ProofStream::new();
180        proof_stream.enqueue(ProofItem::Log2PaddedHeight(8));
181        proof_stream.enqueue(ProofItem::MerkleRoot(root));
182        proof_stream.enqueue(ProofItem::Log2PaddedHeight(7));
183        let proof: Proof = proof_stream.into();
184        let maybe_padded_height = proof.padded_height();
185        assert!(maybe_padded_height.is_err());
186    }
187
188    #[proptest]
189    fn decoding_arbitrary_proof_data_does_not_panic(
190        #[strategy(vec(arb(), 0..1_000))] proof_data: Vec<BFieldElement>,
191    ) {
192        let _proof = Proof::decode(&proof_data);
193    }
194
195    #[test]
196    fn current_proof_version_is_still_current() {
197        let program = triton_program! {
198            pick 11 pick 12 pick 13 pick 14 pick 15
199            read_io 5 assert_vector halt
200        };
201        let claim = Claim::about_program(&program).with_input(program.hash());
202
203        let input = claim.input.clone().into();
204        let non_determinism = NonDeterminism::default();
205        let (aet, _) = VM::trace_execution(program, input, non_determinism).unwrap();
206
207        let mut rng = StdRng::seed_from_u64(4742841043836029231);
208        let proof = Prover::default()
209            .set_randomness_seed_which_may_break_zero_knowledge(rng.random())
210            .prove(&claim, &aet)
211            .unwrap();
212
213        insta::assert_snapshot!(
214            Tip5::hash(&proof),
215            @"09201244033942307448,\
216              02199220141408935358,\
217              14798078607418975656,\
218              16178332457365390929,\
219              00369058580658580912",
220        );
221    }
222}
triton_vm/proof.rs

triton_vm/
proof.rs
