p3-sumcheck 0.8.0

Sumcheck protocol engine (product polynomials, SVO, HVZK masks)
Documentation 
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

//! Random table/spec fixtures.

use alloc::vec;
use alloc::vec::Vec;

use p3_baby_bear::BabyBear;
use p3_field::{Field, PackedValue};
use p3_util::{log2_ceil_usize, log2_strict_usize};
use rand::rngs::SmallRng;
use rand::{RngExt, SeedableRng};

use crate::layout::Table;
use crate::{OpeningBatch, OpeningRequest, PointSchedule, TableShape, TableSpec};

pub type F = BabyBear;

pub fn table_point_schedule(width: usize, extra_points: Vec<OpeningRequest>) -> PointSchedule {
    let mut point_schedule = Vec::with_capacity(extra_points.len() + 1);
    point_schedule.push(OpeningBatch::new((0..width).collect(), Vec::new()));
    point_schedule.extend(extra_points);
    point_schedule
}

pub fn random_point_schedule(rng: &mut SmallRng, width: usize, num_points: usize) -> PointSchedule {
    table_point_schedule(
        width,
        (1..num_points)
            .map(|_| {
                // Sample a direct-opening subset and a successor-view subset independently.
                // Each filter keeps the columns of one side distinct.
                // The two sides may overlap: one column opened both at the point and at its successor.
                let direct = (0..width)
                    .filter(|_| rng.random_bool(0.5))
                    .collect::<Vec<_>>();
                let successor = (0..width)
                    .filter(|_| rng.random_bool(0.5))
                    .collect::<Vec<_>>();
                // A batch must name at least one column on some side.
                if direct.is_empty() && successor.is_empty() {
                    OpeningBatch::new(vec![0], Vec::new())
                } else {
                    OpeningBatch::new(direct, successor)
                }
            })
            .collect(),
    )
}

pub fn random_table_specs(rng: &mut SmallRng, folding: usize) -> Vec<TableSpec> {
    let packing_log = log2_strict_usize(<F as Field>::Packing::WIDTH);
    loop {
        let num_points = rng.random_range(1..=5);
        let num_tables = rng.random_range(1..=5);
        let specs = (0..num_tables)
            .map(|_| {
                let num_variables = rng.random_range(1..=12);
                let width = rng.random_range(1..=5);
                TableSpec::new(
                    TableShape::new(num_variables, width),
                    random_point_schedule(rng, width, num_points),
                )
            })
            .collect::<Vec<_>>();

        if stacked_num_variables(&specs, folding) >= folding + packing_log {
            return specs;
        }
    }
}

pub fn stacked_num_variables(specs: &[TableSpec], folding: usize) -> usize {
    let total_evals = specs
        .iter()
        .map(|spec| spec.shape().width() << spec.shape().num_variables().max(folding))
        .sum::<usize>();
    log2_ceil_usize(total_evals)
}

pub fn table_specs_to_tables(specs: &[TableSpec]) -> Vec<Table<F>> {
    let mut rng = SmallRng::seed_from_u64(3);
    specs
        .iter()
        .map(|spec| Table::rand(&mut rng, spec.shape().width(), spec.shape().num_variables()))
        .collect()
}