WebsiteTwitterTelegramDiscord
Search…
⌃K
Links

Field Simulation

The Zei library provides an implementation of field simulation (and its constraint systems), which is able to simulate Ristretto scalar field in the BLS12-381 scalar field. As follows, we assume that

Data structure​​

The field simulation scheme consists of two data structures: simulated field (
SimFr\mathsf{SimFr}
) and simulated multiplication result (
SimFrMul\mathsf{SimFrMul}
), described as follows.
  • Simulated field (
    SimFr\mathsf{SimFr}
    ): It consists of
    66
     limbs in the BLS12-381 scalar field. The number of bits in each limb in the standard representation is
    43434343
     bits. Associated with each simulated field element is the number of additions over the normal form.
  • Simulated multiplication result (
    SimFrMul\mathsf{SimFrMul}
    ): It consists of
    1313
     limbs in the BLS12-381 scalar field. Associated with each simulation multiplication result element is the product of the the number of additions over the normal form.

Operations for
SimFr\mathsf{SimFr}
:​​

The implementation of
SimFr\mathsf{SimFr}
 in the Zei library supports a restricted set of operations, as follows:
  • ​
    Sub(a,b):=c\mathsf{Sub}(\mathsf{a}, \mathsf{b}) := \mathsf{c}
    :
    • This is a restricted subtraction, where
      b\mathsf{b}
       must satisfy the following requirements:
      • Either,
        bb
         is already in the reduced format. That is, each non-top limb has at most
        4343
         bits, and the top limb has at most
        3838
         bits, and the actual number being represented is strictly smaller than the Ristretto scalar field size;
      • Or,
        bbbb
         is in an almost reduced format. That is, each non-top limb has at most
        4343
         bits, and the top limb has at most
        3838
         bits, and the actual number being represented can be larger than the Ristretto scalar field size (in other words, to represent number
        xx
        , it can be
        p+xp + x
        ).
    • Let the limbs of the Ristretto scalar field subtraction pad be
      r_limbs\mathsf{r\_limbs}
      , which is a constant
      SimFr\mathsf{SimFr}
       element where each limb has one more bit than the reduced format, and the actual number it represents is multiplies of
      pp
      . In our case, it is
      3p3p
      .
    • For
      i=0,1,...,5i= 0, 1, ..., 5
      :
      • ​
        c.limb[i]:=a.limbs[i]+r_limbs[i]−b.limbs[i]\mathsf{c.limb[i] := a.limbs[i] + r\_limbs[i] - b.limbs[i]}
        ​
    • Set
      res.num_of_additions_over_normal_form\mathsf{res.num\_of\_additions\_over\_normal\_form}
       as follows:
      • If
        a\mathsf{a}
         is in the reduced format, set it to be
        33
        ​
      • If
        a\mathsf{a}
         is in the almost reduced format, set it to be
        44
        ​
      • If
        a\mathsf{a}
         has
        num_of_additions_over_normal_form\mathsf{num\_of\_additions\_over\_normal\_form}
         of
        xx
        , set it to be
        x+3x + 3
        ​
  • ​
    Mul(a,b):=c\mathsf{Mul}(\mathsf{a, b}) := \mathsf{c}
    :
    • For
      i=0,1,...,5i= 0, 1, ...,5
       and
      j=0,1,...,5j = 0, 1, ..., 5
      :
      • ​
        c.limbs[i+j]+=a.limbs[i]⋅b.limbs[j]\mathsf{c.limbs[i + j] \mathrel{+=} a.limbs[i] \cdot b.limbs[j]}
        ​
    • Set
      waw_a
       to be as follows:
      • If
        a\mathsf{a}
         is in the reduced format, set it to be
        00
        ​
      • If
        a\mathsf{a}
         is in the almost reduced format, set it to be
        11
        ​
      • If
        a\mathsf{a}
         has
        num_of_additions_over_normal_form\mathsf{num\_of\_additions\_over\_normal\_form}
         of
        xx
        , set it to be
        xx
        ​
    • Set
      wbw_b
       to be as follows:
      • If
        b\mathsf{b}
         is in the reduced format, set it to be
        00
        ​
      • If
        b\mathsf{b}
         is in the almost reduced format, set it to be
        11
        ​
      • If
        b\mathsf{b}
         has
        num_of_additions_over_normal_form\mathsf{num\_of\_additions\_over\_normal\_form}
         of
        xx
        , set it to be
        xx
        ​
    • ​
      res.prod_of_num_of_additions:=(wa+1)⋅(wb+1)\mathsf{res.prod\_of\_num\_of\_additions} := (w_a + 1)\cdot (w_b + 1)
      .

Operations for
SimFrMul\mathsf{SimFrMul}
:​​

The implementation of
SimFrMul\mathsf{SimFrMul}
 is to allow computation over the multiplied results. Similarly, it supposes a restricted set of operations, as follows:
  • ​
    Add(a,b):=c\mathsf{Add}(\mathsf{a, b}) := \mathsf{c}
    :
    • For
      i=0,1,...,11i=0,1, ..., 11
      :
      • ​
        res.limb[i]:=a.limbs[i]+b.limbs[i]\mathsf{res.limb[i] := a.limbs[i] + b.limbs[i]}
        ​
    • Set
      c.prod_of_num_of_addition:=a.prod_of_num_of_addition+b.prod_of_num_of_addition\mathsf{c.prod\_of\_num\_of\_addition} := \mathsf{a.prod\_of\_num\_of\_addition} + \mathsf{b.prod\_of\_num\_of\_addition}
      ​
  • ​
    Sub(a,b):=c\mathsf{Sub}(\mathsf{a, b}) := \mathsf{c}
    :
    • This is a restricted subtraction. It only allows
      b\mathsf{b}
       in the reduced format, almost reduced format, or with
      num_of_additions_over_normal_form\mathsf{num\_of\_additions\_over\_normal\_form}
       smaller or equal to
      44
      ​
    • Let the limbs of the Ristretto scalar field subtraction pad be
      r_limbs\mathsf{r\_limbs}
      ​
    • For
      i=0,1,...,11i = 0, 1, ..., 11
      :
      • ​
        res.limb[i]:=a.limbs[i]+4∗r_limbs[i]−b.limbs[i]\mathsf{res.limb[i] := a.limbs[i] + 4 * r\_limbs[i] - b.limbs[i]}
        ​
    • Increment
      res.prod_of_num_of_additions\mathsf{res.prod\_of\_num\_of\_additions}
       by
      1212
      ​
    • ​
      Zero(x):=b∈{0,1}\mathsf{Zero(x)} := b\in\{0,1\}
      :
      • This only allows
        x\mathsf{x}
         with
        prod_of_num_of_additions\mathsf{prod\_of\_num\_of\_additions}
         smaller than
        3232
        ​
      • Find
        k\mathsf{k}
         such that the actual number of
        x\mathsf{x}
         is
        kp\mathsf{k}p
        . Note that we can enforce that
        k<32p\mathsf{k}< 32 p
        ​
      • Let the limbs of the Ristretto scalar field subtraction pad be
        r_limbs\mathsf{r\_limbs}
        ​
      • Let the limb representations of be
        k_limb\mathsf{k\_limb}
         and check that:
        • The non-top limb has at most
          4343
           bits
        • The top limb has at most
          38+538 + 5
           bits
      • Compute
        rk_limb\mathsf{rk\_limb}
         by multiplying the limbs of
        r_limb\mathsf{r\_limb}
         and
        k_limb\mathsf{k\_limb}
        , according to the
        SimFr.Mul\mathsf{SimFr}.\mathsf{Mul}
         algorithm. Note that
        rk_limb\mathsf{rk\_limb}
         has 11 limbs
      • Create six groups, as follows:
        • ​
          left[0]:=x[0]+243⋅x[1]\mathsf{left}[0] := \mathsf{x}[0] + 2^{43}\cdot \mathsf{x}[1]
          ,
          right[0]:=rk_limb[0]+243⋅rk_limb[1]\mathsf{right}[0] := \mathsf{rk\_limb}[0] + 2^{43}\cdot \mathsf{rk\_limb}[1]
          ​
        • ​
          left[1]:=x[2]+243⋅x[3]\mathsf{left}[1] := \mathsf{x}[2] + 2^{43}\cdot \mathsf{x}[3]
          ,
          right[1]:=rk_limb[2]+243⋅rk_limb[3]\mathsf{right}[1] := \mathsf{rk\_limb}[2] + 2^{43}\cdot \mathsf{rk\_limb}[3]
          ​
        • ​
          left[2]:=x[4]+243⋅x[5]\mathsf{left}[2] := \mathsf{x}[4] + 2^{43}\cdot \mathsf{x}[5]
          ,
          right[2]:=rk_limb[4]+243⋅rk_limb[5]\mathsf{right}[2] := \mathsf{rk\_limb}[4] + 2^{43}\cdot \mathsf{rk\_limb}[5]
          ​
        • ​
          left[3]:=x[6]+243⋅x[7]\mathsf{left}[3] := \mathsf{x}[6] + 2^{43}\cdot \mathsf{x}[7]
          ,
          right[3]:=rk_limb[6]+243⋅rk_limb[7]\mathsf{right}[3] := \mathsf{rk\_limb}[6] + 2^{43}\cdot \mathsf{rk\_limb}[7]
          ​
        • ​
          left[4]:=x[8]+243⋅x[9]\mathsf{left}[4] := \mathsf{x}[8] + 2^{43}\cdot \mathsf{x}[9]
          ,
          right[4]:=rk_limb[8]+243⋅rk_limb[9]\mathsf{right}[4] := \mathsf{rk\_limb}[8] + 2^{43}\cdot \mathsf{rk\_limb}[9]
          ​
        • ​
          left[5]:=x[10]\mathsf{left}[5] := \mathsf{x}[10]
          ,
          right[5]:=rk_limb[10]\mathsf{right}[5] := \mathsf{rk\_limb}[10]
          ​
      • Initialize
        carry_in:=0\mathsf{carry\_in} := 0
         and
        accumulated_extra:=0\mathsf{accumulated\_extra} := 0
        ​
      • For
        i=0,1,...,5i = 0, 1, ..., 5
        :
        • Let
          nn
           be the number of limbs in this group (i.e., one if
          i=5i = 5
          , two otherwise)
        • ​
          pad:=243(n+1)+n+5\mathsf{pad} := 2^{43(n+1) + n + 5}
          ​
        • ​
          accumulated_extra:=accumulated_extra+pad\mathsf{accumulated\_extra} := \mathsf{accumulated\_extra} + \mathsf{pad}
          ​
        • ​
          new_accumulated_extra:=accumulated_extra/243n\mathsf{new\_accumulated\_extra} := \mathsf{accumulated\_extra} / 2^{43n}
          ​
        • ​
          remainder:=accumulated_extra%243n\mathsf{remainder} := \mathsf{accumulated\_extra} \% 2^{43n}
          ​
        • ​
          carry:=(left[i]+pad+carry_in−right[i])/243n\mathsf{carry} := (\mathsf{left}[i] + \mathsf{pad} + \mathsf{carry\_in} - \mathsf{right}[i])/2^{43n}
          ​
        • Check
          left[i]+pad+carry_in−right[i]=243n⋅carry+remainder\mathsf{left}[i] + \mathsf{pad} + \mathsf{carry\_in} - \mathsf{right}[i] = 2^{43n}\cdot\mathsf{carry} + \mathsf{remainder}
          ​
        • ​
          accumulated_extra:=new_accumulated_extra\mathsf{accumulated\_extra} := \mathsf{new\_accumulated\_extra}
          ​
        • ​
          carry_in:=carry\mathsf{carry\_in} := \mathsf{carry}
          ​
        • If
          i=5i = 5
          :
          • Check
            carry_in\mathsf{carry\_in}
             has at most
            5+43∗25 + 43 * 2
             bits
        • Otherwise:
          • Check
            carry_in=accumulated_extra\mathsf{carry\_in} = \mathsf{accumulated\_extra}
            ​
Previous
Delegated Schnorr
Next
TurboPlonk
Last modified 4mo ago