frontend/layouter/nodes/
fiat_shamir_challenge.rs

1//! The FiatShamirChallengeNode is a node that represents when the verifier has
2//! to send challenges to the prover, which it samples via the Fiat-Shamir
3//! transformation.
4//!
5//! Currently, when the circuit builder is generating a circuit, the actual
6//! challenge is not sampled yet, so this node serves as a placeholder for an
7//! indeterminate that will later be populated by the challenge that the
8//! verifier sapmles.
9//!
10//! For example, one use-case for this node is in LogUp circuits, where the
11//! denominator of the left-hand-side terms of the logup summation equation
12//! contains an indeterminate, which is later replaced with a random challenge
13//! sampled via FiatShamir. In that case, we would use the
14//! [FiatShamirChallengeNode] while building the circuit.
15use ark_std::log2;
16
17use shared_types::Field;
18
19use super::{CircuitNode, NodeId};
20use crate::layouter::builder::CircuitMap;
21use remainder::{
22    circuit_layout::CircuitLocation,
23    input_layer::fiat_shamir_challenge::FiatShamirChallengeDescription, layer::LayerId,
24};
25
26#[derive(Debug, Clone)]
27/// The node representing the random challenge that the verifier supplies via
28/// Fiat-Shamir.
29pub struct FiatShamirChallengeNode {
30    id: NodeId,
31    num_vars: usize,
32}
33
34impl CircuitNode for FiatShamirChallengeNode {
35    fn id(&self) -> NodeId {
36        self.id
37    }
38
39    fn sources(&self) -> Vec<NodeId> {
40        vec![]
41    }
42
43    fn get_num_vars(&self) -> usize {
44        self.num_vars
45    }
46}
47
48impl FiatShamirChallengeNode {
49    /// Constructor for a [FiatShamirChallengeNode].
50    pub fn new(num_challenges: usize) -> Self {
51        Self {
52            id: NodeId::new(),
53            num_vars: log2(num_challenges) as usize,
54        }
55    }
56
57    /// Generate a [FiatShamirChallengeDescription], which is the
58    /// circuit description for a [FiatShamirChallengeNode].
59    pub fn generate_circuit_description<F: Field>(
60        &self,
61        circuit_map: &mut CircuitMap,
62    ) -> FiatShamirChallengeDescription<F> {
63        let layer_id = LayerId::next_fiat_shamir_challenge_layer_id();
64        let fsc_layer = FiatShamirChallengeDescription::new(layer_id, self.get_num_vars());
65        circuit_map.add_node_id_and_location_num_vars(
66            self.id,
67            (CircuitLocation::new(layer_id, vec![]), self.get_num_vars()),
68        );
69        fsc_layer
70    }
71}
72
73#[cfg(test)]
74mod test {
75    use crate::layouter::builder::{CircuitBuilder, LayerVisibility};
76    use shared_types::Fr;
77
78    use remainder::{
79        mle::evals::MultilinearExtension,
80        prover::helpers::test_circuit_with_runtime_optimized_config,
81    };
82
83    #[test]
84    fn test_verifier_challenge_node_in_circuit() {
85        let mut builder = CircuitBuilder::<Fr>::new();
86
87        let input_a_data = MultilinearExtension::new(vec![
88            Fr::from(1),
89            Fr::from(2),
90            Fr::from(9),
91            Fr::from(10),
92            Fr::from(13),
93            Fr::from(1),
94            Fr::from(3),
95            Fr::from(10),
96        ]);
97
98        let verifier_challenge_node = builder.add_fiat_shamir_challenge_node(8);
99
100        let input_layer = builder.add_input_layer("Input Layer", LayerVisibility::Public);
101        let input_a = builder.add_input_shred("input a", input_a_data.num_vars(), &input_layer);
102
103        let product_sector = builder.add_sector(input_a - verifier_challenge_node);
104
105        let difference_sector = builder.add_sector(&product_sector - &product_sector);
106        builder.set_output(&difference_sector);
107
108        let mut circuit = builder.build_with_layer_combination().unwrap();
109        circuit.set_input("input a", input_a_data);
110
111        let provable_circuit = circuit.gen_provable_circuit().unwrap();
112
113        test_circuit_with_runtime_optimized_config(&provable_circuit);
114    }
115}
frontend/layouter/nodes/fiat_shamir_challenge.rs

frontend/layouter/nodes/
fiat_shamir_challenge.rs
