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
43    /// for. It is one of the main contributing factors to the length of the
44    /// FRI domain.
45    pub fn padded_height(&self) -> Result<usize, ProofStreamError> {
46        let mut log_2_padded_heights = ProofStream::try_from(self)?
47            .items
48            .into_iter()
49            .filter_map(|item| item.try_into_log2_padded_height().ok());
50
51        let log_2_padded_height = log_2_padded_heights
52            .next()
53            .ok_or(ProofStreamError::NoLog2PaddedHeight)?;
54        if log_2_padded_heights.next().is_some() {
55            return Err(ProofStreamError::TooManyLog2PaddedHeights);
56        }
57
58        Ok(1 << log_2_padded_height)
59    }
60}
61
62/// Contains the public information of a verifiably correct computation.
63/// A corresponding [`Proof`] is needed to verify the computation.
64/// One additional piece of public information not explicitly listed in the
65/// [`Claim`] is the `padded_height`, an upper bound on the length of the
66/// computation. It is derivable from a [`Proof`] by calling
67/// [`Proof::padded_height()`].
68#[derive(
69    Debug, Clone, Eq, PartialEq, Hash, Serialize, Deserialize, GetSize, BFieldCodec, Arbitrary,
70)]
71pub struct Claim {
72    /// The hash digest of the program that was executed. The hash function in
73    /// use is [`Tip5`].
74    pub program_digest: Digest,
75
76    /// The version of the Triton VM instruction set architecture the
77    /// [`program_digest`][digest] is about, as well as of the STARK proof
78    /// system in use. See also: [`CURRENT_VERSION`].
79    ///
80    /// [digest]: Self::program_digest
81    pub version: u32,
82
83    /// The public input to the computation.
84    pub input: Vec<BFieldElement>,
85
86    /// The public output of the computation.
87    pub output: Vec<BFieldElement>,
88}
89
90impl Claim {
91    /// Create a new Claim.
92    ///
93    /// Assumes the version to be [`CURRENT_VERSION`]. The version can be
94    /// changed with method [`about_version`][Self::about_version].
95    pub fn new(program_digest: Digest) -> Self {
96        Self {
97            program_digest,
98            version: CURRENT_VERSION,
99            input: vec![],
100            output: vec![],
101        }
102    }
103
104    #[must_use]
105    pub fn about_program(program: &Program) -> Self {
106        Self::new(program.hash())
107    }
108
109    #[must_use]
110    pub fn with_input(mut self, input: impl Into<Vec<BFieldElement>>) -> Self {
111        self.input = input.into();
112        self
113    }
114
115    #[must_use]
116    pub fn with_output(mut self, output: Vec<BFieldElement>) -> Self {
117        self.output = output;
118        self
119    }
120
121    #[must_use]
122    pub fn about_version(mut self, version: u32) -> Self {
123        self.version = version;
124        self
125    }
126}
127
128#[cfg(test)]
129#[cfg_attr(coverage_nightly, coverage(off))]
130mod tests {
131    use assert2::assert;
132    use proptest::collection::vec;
133    use proptest::prelude::*;
134    use proptest_arbitrary_interop::arb;
135    use rand::prelude::*;
136    use test_strategy::proptest;
137
138    use crate::prelude::*;
139    use crate::proof_item::ProofItem;
140
141    use super::*;
142
143    impl Default for Claim {
144        /// For testing purposes only.
145        fn default() -> Self {
146            Self::new(Digest::default())
147        }
148    }
149
150    #[test]
151    fn claim_accepts_various_types_for_public_input() {
152        let _claim = Claim::default()
153            .with_input(bfe_vec![42])
154            .with_input(bfe_array![42])
155            .with_input(PublicInput::new(bfe_vec![42]));
156    }
157
158    #[proptest]
159    fn decode_proof(#[strategy(arb())] proof: Proof) {
160        let encoded = proof.encode();
161        let decoded = *Proof::decode(&encoded).unwrap();
162        prop_assert_eq!(proof, decoded);
163    }
164
165    #[proptest]
166    fn decode_claim(#[strategy(arb())] claim: Claim) {
167        let encoded = claim.encode();
168        let decoded = *Claim::decode(&encoded).unwrap();
169        prop_assert_eq!(claim, decoded);
170    }
171
172    #[proptest(cases = 10)]
173    fn proof_with_no_padded_height_gives_err(#[strategy(arb())] root: Digest) {
174        let mut proof_stream = ProofStream::new();
175        proof_stream.enqueue(ProofItem::MerkleRoot(root));
176        let proof: Proof = proof_stream.into();
177        let maybe_padded_height = proof.padded_height();
178        assert!(maybe_padded_height.is_err());
179    }
180
181    #[proptest(cases = 10)]
182    fn proof_with_multiple_padded_height_gives_err(#[strategy(arb())] root: Digest) {
183        let mut proof_stream = ProofStream::new();
184        proof_stream.enqueue(ProofItem::Log2PaddedHeight(8));
185        proof_stream.enqueue(ProofItem::MerkleRoot(root));
186        proof_stream.enqueue(ProofItem::Log2PaddedHeight(7));
187        let proof: Proof = proof_stream.into();
188        let maybe_padded_height = proof.padded_height();
189        assert!(maybe_padded_height.is_err());
190    }
191
192    #[proptest]
193    fn decoding_arbitrary_proof_data_does_not_panic(
194        #[strategy(vec(arb(), 0..1_000))] proof_data: Vec<BFieldElement>,
195    ) {
196        let _proof = Proof::decode(&proof_data);
197    }
198
199    #[test]
200    fn current_proof_version_is_still_current() {
201        let program = triton_program! {
202            pick 11 pick 12 pick 13 pick 14 pick 15
203            read_io 5 assert_vector halt
204        };
205        let claim = Claim::about_program(&program).with_input(program.hash());
206
207        let input = claim.input.clone().into();
208        let non_determinism = NonDeterminism::default();
209        let (aet, _) = VM::trace_execution(program, input, non_determinism).unwrap();
210
211        let mut rng = StdRng::seed_from_u64(4742841043836029231);
212        let proof = Prover::default()
213            .set_randomness_seed_which_may_break_zero_knowledge(rng.random())
214            .prove(&claim, &aet)
215            .unwrap();
216
217        insta::assert_snapshot!(
218            Tip5::hash(&proof),
219            @"09201244033942307448,\
220              02199220141408935358,\
221              14798078607418975656,\
222              16178332457365390929,\
223              00369058580658580912",
224        );
225    }
226}
triton_vm/proof.rs

triton_vm/
proof.rs
