This is an old version of this page. You can view the most recent version or browse the history.

12 exp

用于处理EXP指令以及电路中的exp运算的子电路

设计

Witness、Column设计

Witness设计


#[derive(Clone, Debug, Serialize)]
pub struct Row {
    // type of row, one of zero, one, base2 or arbitrary
    pub tag: Tag,
    // base of exp
    pub base_hi: U256,
    pub base_lo: U256,
    // index of exp
    pub index_hi: U256,
    pub index_lo: U256,
    // count of index
    pub count: U256,
    // whether count is equal or large than 2**128
    pub is_high: U256,
    // exp res
    pub power_hi: U256,
    pub power_lo: U256,
}

#[derive(Clone, Copy, Debug, Default, Serialize, EnumIter, EnumString)]
pub enum Tag {
    #[default]
    Zero,
    One,
    Base2,
    Arbitrary0, // index & 1 = 0
    Arbitrary1, // index & 1 = 1
}

Circuit Column 设计


#[derive(Clone)]
pub struct ExpCircuitConfig<F: Field> {
    q_enable: Selector,
    /// the operation tag, zero,one,arbitrary,base2
    pub tag: BinaryNumberConfig<Tag, LOG_NUM_EXP_TAG>,
    /// base hi , base lo
    pub base: [Column<Advice>; EXP_NUM_OPERAND],
    /// index hi, index lo
    pub index: [Column<Advice>; EXP_NUM_OPERAND],
    /// power hi, power lo
    pub power: [Column<Advice>; EXP_NUM_OPERAND],
    /// count
    pub count: Column<Advice>,
    /// is_high
    pub is_high: Column<Advice>,
    /// IsZero chip for column count
    pub count_is_zero: IsZeroWithRotationConfig<F>,
    /// for chip to determine whether count is 128
    pub count_is_128: IsZeroConfig<F>,
    /// for chip to determine whether count is 256
    pub count_is_256: IsZeroConfig<F>,
    /// arithmetic table for lookup
    arithmetic_table: ArithmeticTable,
}

Witness生成算法设计

    pub fn from_operands(
        base: U256,
        index: U256,
    ) -> (U256, Vec<Self>, Vec<arithmetic::Row>, Vec<arithmetic::Row>)

入参: base为底数,index为指数
返回参数: exp运算结果,exp生成witness row 数组(exp rows),使用的乘法电路运算生成的witness row(mul rows),使用的加法电路运算生成的witness row(add rows)
算法:
- 生成Tag::Zero 行,将其添加到exp rows中
- 若index == 0,则直接返回
- 生成Tag::One 行, 将其添加到exp rows中
- 计算index对2的除法和取模运算,记商为div,余数为rem
  - 如果rem == 0, 则生成 Tag::Arbitrary0 Row,将其添加到exp rows中；其中 index hi/lo = (Tag::Zero row )的index hi/lo ；power hi/lo = (Tag::Zero row)的power hi/lo；
  - 如果rem == 1, 则生成 Tag::Arbitrary1 Row,将其添加到exp rows中；其中 index hi/lo = (Tag::Zero row 与 Tag::One row)的index hi/lo 之和,调用加法电路生成add row,将其添加到add rows中；power hi/lo = (Tag::Zero row 与 Tag::One row)的 power hi/lo之积,调用乘法电路生成mul row ,将其添加到mul rows中；
- 若div == 0,则直接返回
- 循环对 div 做2的除法和取模运算,记商为div,余数为rem
  - 若div == 0 且 rem == 0, 则中断循环
  - 否则:
    - 生成Tag::Base2 Row,将其添加到exp rows中；其中index hi/lo = (exp rows中的两行前的row)的 index hi/lo * 2 ,调用乘法电路生成mul row,将其添加到mul rows中；power hi/lo = (exp rows中的两行前的row)的 power hi/lo 的平方,调用乘法电路生成mul row,将其添加到mul rows中；count = (exp rows中的前一行的row)的count + 1；
      - 若count == 0 ,则is_high = 0
      - 若count == 128 ,则is_high = 1
      - 否则 is_high = (exp rows中的两行前的row)的is_high
    - 生成Tag::Arbitrary0/Tag::Arbitrary1 Row；其中count = (exp rows中的前一行的row)的count, is_high = (exp rows中的前一行的row)的is_high
      - 若rem == 0 , 则生成Tag::Arbitrary0 Row,将其添加到exp rows中；其中index hi/lo = (exp rows中的两行前的row)的 index hi/lo；power hi/lo = (exp rows中的两行前的row)的 power hi/lo
      - 若rem == 1 , 则生成Tag::Arbitrary1 Row,将其添加到exp rows中；其中index hi/lo = (exp rows中的两行前的row)的 index hi/lo + (exp rows中的前一行的row)的index hi/lo, 调用加法电路生成add row,将其添加到add rows中；power hi/lo = (exp rows中的两行前的row)的 power hi/lo * (exp rows中的前一行的row)的 power hi/lo,调用乘法电路生成mul row,将其添加到mul rows中
- 去exp rows中最后一行的power hi/lo, 将power hi << 128 + power lo作为最终的power value, return (power value,exp rows, mul rows, add rows)

门约束

Tag 约束

若当前行的Tag为ZERO,则前一行的Tag也为ZERO
若当前行的Tag为BASE2,则前一行的Tag必为ARBITRARY0 or ARBITRARY1
若当前行的Tag为ARBITRARY0 or ARBITRARY1,则前一行的Tag为ONE or BASE2

Count约束

若当前行的Tag为ZERO,则count为0
若当前行的Tag为BASE2,则count为前一行的count+1
若当前行的Tag为ARBITRARY0 or ARBITRARY1,则count等于前一行的count
count不等于256

Is_high约束

若当前行的count为0,则is_high为0
若当前行的count为128,则is_high为1
若当前行的count不为0和128,则is_high等于前一行的is_high

Index/Power约束

若当前行的Tag为ZERO,则index为0,power为1,则index
若当前行的Tag为ONE,则index为1,power为BASE(底数)
若当前行的Tag为ARBITRARY0,则index等于前两行index,power等于前两行的power
若当前行的Tag为BASE2,且count为128,则index hi为1,index lo为0

Lookup约束

Tag为BASE2,Index运算lookup

若Tag为BASE2时,index 等于两行前的index * 2,若count为128时,则index hi为1,index为0

Tag为BASE2,Power运算lookup

若Tag为BASE2时,power为两行前的power的平方

Tag为ARBITRARY1,Index运算lookup

若Tag为ARBITRARY1,index为两行前的index + 一行前的index

Tag为ARBITRARY1,Power运算lookup

若Tag为ARBITRARY1,power为两行前的power * 一行前的power