winter_fri/prover/
channel.rs

1// Copyright (c) Facebook, Inc. and its affiliates.
2//
3// This source code is licensed under the MIT license found in the
4// LICENSE file in the root directory of this source tree.
5
6use alloc::vec::Vec;
7use core::marker::PhantomData;
8
9use crypto::{ElementHasher, Hasher, RandomCoin};
10use math::FieldElement;
11
12// PROVER CHANNEL TRAIT
13// ================================================================================================
14
15/// Defines an interface for a channel over which a prover communicates with a verifier.
16///
17/// The prover uses this channel to send commitments to FRI layer polynomials to the verifier, and
18/// then to draw a random value α from the channel after each commitment is sent. The prover then
19/// uses this α to construct the next FRI layer.
20///
21/// In the interactive version of the protocol, the verifier chooses α uniformly at random from
22/// the entire field. In the non-interactive version, the α is drawn pseudo-randomly based on the
23/// commitments the prover has written into the channel up to this point.
24pub trait ProverChannel<E: FieldElement> {
25    /// Hash function used by the prover to commit to polynomial evaluations.
26    type Hasher: ElementHasher<BaseField = E::BaseField>;
27
28    /// Sends a layer commitment to the verifier.
29    ///
30    /// A layer commitment is the commitment string of a vector commitment to the vector of
31    /// evaluations of a polynomial at a given layer. The vector commitment is built by
32    /// first transposing evaluations into a two-dimensional matrix where each row contains
33    /// values needed to compute a single value of the next FRI layer, and then computing
34    /// the hash of each row to get one entry of the vector being committed to. Thus, the number
35    /// of elements grouped into a single leaf is equal to the `folding_factor` used for FRI layer
36    /// construction.
37    fn commit_fri_layer(&mut self, layer_root: <Self::Hasher as Hasher>::Digest);
38
39    /// Returns a random α drawn uniformly at random from the entire field.
40    ///
41    /// The prover uses this α to build the next FRI layer.
42    ///
43    /// While in the interactive version of the protocol the verifier send a random α to the
44    /// prover, in the non-interactive version, the α is pseudo-randomly generated based on the
45    /// values the prover previously wrote into the channel.
46    fn draw_fri_alpha(&mut self) -> E;
47}
48
49// DEFAULT PROVER CHANNEL IMPLEMENTATION
50// ================================================================================================
51
52/// Provides a default implementation of the [ProverChannel] trait.
53///
54/// Though this implementation is intended primarily for testing purposes, it can be used in
55/// production use cases as well.
56pub struct DefaultProverChannel<E, H, R>
57where
58    E: FieldElement,
59    H: ElementHasher<BaseField = E::BaseField>,
60    R: RandomCoin<BaseField = E::BaseField, Hasher = H>,
61{
62    public_coin: R,
63    commitments: Vec<H::Digest>,
64    domain_size: usize,
65    num_queries: usize,
66    _field_element: PhantomData<E>,
67}
68
69impl<E, H, R> DefaultProverChannel<E, H, R>
70where
71    E: FieldElement,
72    H: ElementHasher<BaseField = E::BaseField>,
73    R: RandomCoin<BaseField = E::BaseField, Hasher = H>,
74{
75    /// Returns a new prover channel instantiated from the specified parameters.
76    ///
77    /// # Panics
78    /// Panics if:
79    /// * `domain_size` is smaller than 8 or is not a power of two.
80    /// * `num_queries` is zero.
81    pub fn new(domain_size: usize, num_queries: usize) -> Self {
82        assert!(domain_size >= 8, "domain size must be at least 8, but was {domain_size}");
83        assert!(
84            domain_size.is_power_of_two(),
85            "domain size must be a power of two, but was {domain_size}"
86        );
87        assert!(num_queries > 0, "number of queries must be greater than zero");
88        DefaultProverChannel {
89            public_coin: RandomCoin::new(&[]),
90            commitments: Vec::new(),
91            domain_size,
92            num_queries,
93            _field_element: PhantomData,
94        }
95    }
96
97    /// Draws a set of positions at which the polynomial evaluations committed at the first FRI
98    /// layer should be queried.
99    ///
100    /// The positions are pseudo-randomly generated based on the values the prover has written
101    /// into this channel and a PoW nonce.
102    ///
103    /// # Panics
104    /// Panics if the specified number of unique positions could not be drawn from the specified
105    /// domain. Both number of queried positions and domain size are specified during
106    /// construction of the channel.
107    pub fn draw_query_positions(&mut self, nonce: u64) -> Vec<usize> {
108        self.public_coin
109            .draw_integers(self.num_queries, self.domain_size, nonce)
110            .expect("failed to draw query position")
111    }
112
113    /// Returns a list of FRI layer commitments written by the prover into this channel.
114    pub fn layer_commitments(&self) -> &[H::Digest] {
115        &self.commitments
116    }
117}
118
119impl<E, H, R> ProverChannel<E> for DefaultProverChannel<E, H, R>
120where
121    E: FieldElement,
122    H: ElementHasher<BaseField = E::BaseField>,
123    R: RandomCoin<BaseField = E::BaseField, Hasher = H>,
124{
125    type Hasher = H;
126
127    fn commit_fri_layer(&mut self, layer_root: H::Digest) {
128        self.commitments.push(layer_root);
129        self.public_coin.reseed(layer_root);
130    }
131
132    fn draw_fri_alpha(&mut self) -> E {
133        self.public_coin.draw().expect("failed to draw FRI alpha")
134    }
135}
winter_fri/prover/channel.rs

winter_fri/prover/
channel.rs
