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

// Copyright 2023 RISC Zero, Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

use crate::{
    core::log2_ceil,
    hal::{Buffer, Hal},
    prove::merkle::MerkleTreeProver,
    INV_RATE, QUERIES,
};

/// A PolyGroup represents a group of polynomials, all of the same maximum
/// degree, as well as the evaluation of those polynomials over some domain that
/// is larger than that degree by some invRate. Additionally, it includes a
/// dense Merkle tree, where each entry is a single point of the domain, and the
/// leaf hash is a simple linear hash of all of the values at that point.  That
/// is, if we have 100 polynomials evaluated on 2^16 points, the merkle tree has
/// 2^16 entries, each being a hash of 100 values.  The size of the domain is
/// always a power of 2 so that we can use NTTs.
///
/// The primary purpose of the PolyGroup is for use in the DEEP-ALI protocol,
/// which basically needs 4 methods during proof generation, specifically we
/// need to: 1) Resolve queries (i.e. make MerkleColProofs)
/// 2) Do evaluation of the polynomials at 'randomly' chosen points
/// 3) Mix the polynomials via a random set of linear coefficients
/// 4) Access the raw values in the evaluation domain to 'evaluate' the
/// constraint polynomial
///
/// The poly group holds 3 buffers:
/// 1) The per-polynomial coefficients, used for evaluation + mixing
/// 2) The points evaluated on the domain in question (for the 'col' part of
/// merkle proofs) 3) The Merkle tree itself.
///
/// PolyGroups are constructed from two basic sources: steps of a computations,
/// and a single higher degree polynomial that has been split into lower degree
/// parts.  In the case of computations, the resulting steps must be padded
/// (possibly with randomized data), which is presumed to be done by the caller.
/// The constructor additionally 'shifts' the polynomial so that f(x) -> f(3*x),
/// which means that the normal NTT evaluation domain does not reveal anything
/// about the original datapoints (i.e. is zero knowledge) so long as the number
/// of queries is less than the randomized padding.
pub struct PolyGroup<'a, H: Hal> {
    pub coeffs: &'a H::BufferElem,
    pub count: usize,
    pub evaluated: H::BufferElem,
    pub merkle: MerkleTreeProver<H>,
}

impl<'a, H: Hal> PolyGroup<'a, H> {
    #[tracing::instrument(name = "PolyGroup", skip_all, fields(name = _name))]
    pub fn new(
        hal: &H,
        coeffs: &'a H::BufferElem,
        count: usize,
        size: usize,
        _name: &'static str,
    ) -> Self {
        assert_eq!(coeffs.size(), count * size);
        let domain = size * INV_RATE;
        let evaluated = hal.alloc_elem("evaluated", count * domain);
        hal.batch_expand(&evaluated, &coeffs, count);
        hal.batch_evaluate_ntt(&evaluated, count, log2_ceil(INV_RATE));
        hal.batch_bit_reverse(&coeffs, count);
        let merkle = MerkleTreeProver::new(hal, &evaluated, domain, count, QUERIES);
        PolyGroup {
            coeffs,
            count,
            evaluated,
            merkle,
        }
    }
}