halo2ccs/
query.rs

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
// Reference to a cell, relative to the current row
use halo2_proofs::plonk::Any;
use halo2_proofs::plonk::FixedQuery;
use halo2_proofs::plonk::{AdviceQuery, InstanceQuery, Selector};
use std::cmp::Ordering;
use std::hash::Hash;

// I use this Ord impl for witness deduplication.
// Cells with greater ordering will get deduplicated into cells with less ordering.
// If there was a copy constraint between an advice cell and an instance cell,
//   the former will get deduplicated into the latter.
// If there was a copy constraint between an advice cell and a fixed cell,
//   the former will get deduplicated into the latter.

/// Column type. Basically halo2_proofs::plonk::Any but with some variants added.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub enum VirtualColumnType {
    LookupInput,
    Selector,
    Fixed,
    Instance,
    Advice,
}

impl From<Any> for VirtualColumnType {
    fn from(value: Any) -> Self {
        match value {
            Any::Instance => VirtualColumnType::Instance,
            Any::Advice => VirtualColumnType::Advice,
            Any::Fixed => VirtualColumnType::Fixed,
        }
    }
}

// Cell position in a Plonkish table.
// Unlike Query, which represents a cell position *relative* to the current row, this struct represents an absolute position in the Plonkish table.

// column_index will be assigned for each column_type, starting from 0.
// For example if we had 1 instance column and 1 advice column, column_index of both will be 0.
// if we had 0 instance column and 2 advice column, first column_index is 0, second column_index is 1.

// This feels unintuitive but Halo2's internal works that way so I didn't bother to change it.

/// Cell position in a Plonkish table.
/// column_index will be assigned for each column_type, starting from 0.
/// For example if we had 1 instance column and 1 advice column, column_index of both will be 0.
/// if we had 0 instance column and 2 advice column, first column_index is 0, second column_index is 1.
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
pub struct AbsoluteCellPosition {
    pub column_type: VirtualColumnType,
    pub column_index: usize,
    pub row_index: usize,
}

// I use this Ord impl for witness deduplication.
// Cells with greater ordering will get deduplicated into cells with less ordering.
impl Ord for AbsoluteCellPosition {
    fn cmp(&self, other: &Self) -> Ordering {
        match self.column_type.cmp(&other.column_type) {
            Ordering::Equal => match self.column_index.cmp(&other.column_index) {
                Ordering::Equal => self.row_index.cmp(&other.row_index),
                ordering => ordering,
            },
            ordering => ordering,
        }
    }
}

impl PartialOrd for AbsoluteCellPosition {
    fn partial_cmp(&self, other: &AbsoluteCellPosition) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

#[derive(Debug, Clone, Copy)]
pub(crate) enum Query {
    Fixed(FixedQuery),
    Advice(AdviceQuery),
    Instance(InstanceQuery),
    Selector(Selector),
    LookupInput(usize), // the index of lookup constraint
}

impl Query {
    // As I said Query is a reference to a cell *relative* to the current row.
    // This method converts that relative reference to an absolute cell position, given the current row.
    pub(crate) fn cell_position(self, at_row: usize, table_height: usize) -> AbsoluteCellPosition {
        match self {
            Query::Selector(query) => AbsoluteCellPosition {
                column_type: VirtualColumnType::Selector,
                column_index: query.0,
                row_index: at_row,
            },
            Query::Fixed(query) => AbsoluteCellPosition {
                column_type: VirtualColumnType::Fixed,
                column_index: query.column_index,
                row_index: (at_row as i32 + query.rotation.0).rem_euclid(table_height as i32)
                    as usize,
            },
            Query::Instance(query) => AbsoluteCellPosition {
                column_type: VirtualColumnType::Instance,
                column_index: query.column_index,
                row_index: (at_row as i32 + query.rotation.0).rem_euclid(table_height as i32)
                    as usize,
            },
            Query::Advice(query) => AbsoluteCellPosition {
                column_type: VirtualColumnType::Advice,
                column_index: query.column_index,
                row_index: (at_row as i32 + query.rotation.0).rem_euclid(table_height as i32)
                    as usize,
            },
            Query::LookupInput(index) => AbsoluteCellPosition {
                column_type: VirtualColumnType::LookupInput,
                column_index: index,
                row_index: at_row,
            },
        }
    }
}

impl PartialEq for Query {
    fn eq(&self, other: &Self) -> bool {
        // This implementation only cares about the information CCS+ cares about.
        // I want QueryA == QueryB to hold every time when QueryA and QueryB is essentially the same query, ignoring Halo2's menial internal data.
        // For example query.index is just data Halo2 internally uses to keep track of queries.
        // So this impl ignores query.index

        match (self, other) {
            (Self::Fixed(lhs), Self::Fixed(rhs)) => {
                lhs.rotation == rhs.rotation && lhs.column_index == rhs.column_index
            }
            (Self::Advice(lhs), Self::Advice(rhs)) => {
                lhs.rotation == rhs.rotation && lhs.column_index == rhs.column_index
            }
            (Self::Instance(lhs), Self::Instance(rhs)) => {
                lhs.rotation == rhs.rotation && lhs.column_index == rhs.column_index
            }
            (Self::Selector(lhs), Self::Selector(rhs)) => lhs.0 == rhs.0,
            (Self::LookupInput(lhs), Self::LookupInput(rhs)) => lhs == rhs,
            _ => false,
        }
    }
}