Search…
⌃K

# 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 (
$\mathsf{SimFr}$
) and simulated multiplication result (
$\mathsf{SimFrMul}$
), described as follows.
• Simulated field (
$\mathsf{SimFr}$
): It consists of
$6$
limbs in the BLS12-381 scalar field. The number of bits in each limb in the standard representation is
$4343$
bits. Associated with each simulated field element is the number of additions over the normal form.
• Simulated multiplication result (
$\mathsf{SimFrMul}$
): It consists of
$13$
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 $\mathsf{SimFr}$:​​

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

### Operations for $\mathsf{SimFrMul}$:​​

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