1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

use lambdaworks_math::{
    field::{
        element::FieldElement,
        traits::{IsField, IsSubFieldOf},
    },
    traits::AsBytes,
};

/// The functionality of a transcript to be used in the STARK Prove and Verify protocols.
pub trait IsTranscript<F: IsField> {
    /// Appends a field element to the transcript.
    fn append_field_element(&mut self, element: &FieldElement<F>);
    /// Appends a bytes to the transcript.
    fn append_bytes(&mut self, new_bytes: &[u8]);
    /// Returns the inner state of the transcript that fully determines its outputs.
    fn state(&self) -> [u8; 32];
    /// Returns a random field element.
    fn sample_field_element(&mut self) -> FieldElement<F>;
    /// Returns a random index between 0 and `upper_bound`.
    fn sample_u64(&mut self, upper_bound: u64) -> u64;
    /// Returns a field element not contained in `lde_roots_of_unity_coset` or `trace_roots_of_unity`.
    fn sample_z_ood<S: IsSubFieldOf<F>>(
        &mut self,
        lde_roots_of_unity_coset: &[FieldElement<S>],
        trace_roots_of_unity: &[FieldElement<S>],
    ) -> FieldElement<F>
    where
        FieldElement<F>: AsBytes,
    {
        loop {
            let value: FieldElement<F> = self.sample_field_element();
            if !lde_roots_of_unity_coset
                .iter()
                .any(|x| x.clone().to_extension() == value)
                && !trace_roots_of_unity
                    .iter()
                    .any(|x| x.clone().to_extension() == value)
            {
                return value;
            }
        }
    }
}