译自 halo2 book:https://zcash.github.io/halo2/design/implementation/fields.html

域(Fields)

我们在 halo2 中使用的 Pasta 曲线被设计为高度 2-adic 的,这意味着每个域(field)中都存在一个较大的 $2^{S}$ 乘法子群(multiplicative subgroup)。也就是说,我们可以写成 $p - 1 \equiv 2^{S} \cdot T$ ,其中 $T$ 为奇数。对于 Pallas 和 Vesta, $S = 32$ ;这有助于简化域的实现。

Sarkar 平方根算法(基于表的变体)

我们使用来自 Sarkar2020 的一种技术来在 halo2 中计算平方根(square roots)。该算法背后的直觉是:我们可以把任务拆分为在每个乘法子群中分别计算平方根。

假设我们想求 $u$ 模某个 Pasta 素数 $p$ 的平方根,其中 $u$ 是 $Z_{p}^{\times}$ 中的一个非零平方数(square)。我们定义一个 $2^{S}$ 阶单位根(root of unity) $g = z^{T}$ ,其中 $z$ 是 $Z_{p}^{\times}$ 中的一个非平方数(non-square),并预计算以下各表:

$g t ab = g^{0} (g^{2^{8}})^{0} (g^{2^{16}})^{0} (g^{2^{24}})^{0} g^{1} (g^{2^{8}})^{1} (g^{2^{16}})^{1} (g^{2^{24}})^{1} ... ... ... ... g^{2^{8} - 1} (g^{2^{8}})^{2^{8} - 1} (g^{2^{16}})^{2^{8} - 1} (g^{2^{24}})^{2^{8} - 1}$

$in v t ab = [(g^{- 2^{24}})^{0} (g^{- 2^{24}})^{1} ... (g^{- 2^{24}})^{2^{8} - 1}]$

令 $v = u^{(T - 1) /2}$ 。我们便可定义 $x = uv \cdot v = u^{T}$ ,它是 $2^{S}$ 乘法子群中的一个元素。

令 $x_{3} = x, x_{2} = x_{3}^{2^{8}}, x_{1} = x_{2}^{2^{8}}, x_{0} = x_{1}^{2^{8}} .$

i = 0, 1

使用 $in v t ab$ ,我们查找 $t_{0}$ 使得 $x_{0} = (g^{- 2^{24}})^{t_{0}} ⟹ x_{0} \cdot g^{t_{0} \cdot 2^{24}} = 1.$

定义 $α_{1} = x_{1} \cdot (g^{2^{16}})^{t_{0}} .$

i = 2

查找 $t_{1}$ 使得 $α_{1} = (g^{- 2^{24}})^{t_{1}} ⟹ x_{1} \cdot (g^{2^{16}})^{t_{0}} = (g^{- 2^{24}})^{t_{1}} ⟹ x_{1} \cdot g^{(t_{0} + 2^{8} \cdot t_{1}) \cdot 2^{16}} = 1.$

定义 $α_{2} = x_{2} \cdot (g^{2^{8}})^{t_{0} + 2^{8} \cdot t_{1}} .$

i = 3

查找 $t_{2}$ 使得

$α_{2} = (g^{- 2^{24}})^{t_{2}} ⟹ x_{2} \cdot (g^{2^{8}})^{t_{0} + 2^{8} \cdot t_{1}} = (g^{- 2^{24}})^{t_{2}} ⟹ x_{2} \cdot g^{(t_{0} + 2^{8} \cdot t_{1} + 2^{16} \cdot t_{2}) \cdot 2^{8}} = 1.$

定义 $α_{3} = x_{3} \cdot g^{t_{0} + 2^{8} \cdot t_{1} + 2^{16} \cdot t_{2}} .$

最终结果

查找 $t_{3}$ 使得

$α_{3} = (g^{- 2^{24}})^{t_{3}} ⟹ x_{3} \cdot g^{t_{0} + 2^{8} \cdot t_{1} + 2^{16} \cdot t_{2}} = (g^{- 2^{24}})^{t_{3}} ⟹ x_{3} \cdot g^{t_{0} + 2^{8} \cdot t_{1} + 2^{16} \cdot t_{2} + 2^{24} \cdot t_{3}} = 1.$

令 $t = t_{0} + 2^{8} \cdot t_{1} + 2^{16} \cdot t_{2} + 2^{24} \cdot t_{3}$ 。

现在我们可以写出 $x_{3} \cdot g^{t} = 1 ⟹ ⟹ ⟹ ⟹ x_{3} u v^{2} uv uv \cdot g^{t /2} = = = = g^{- t} g^{- t} v^{- 1} \cdot g^{- t} v^{- 1} \cdot g^{- t /2} .$

对右端(RHS)取平方,我们观察到 $(v^{- 1} g^{- t /2})^{2} = v^{- 2} g^{- t} = u .$ 因此, $u$ 的平方根就是 $uv \cdot g^{t /2}$ ;其中第一部分我们在前面已经计算过,第二部分可以利用 $g t ab$ 中的查找,通过三次乘法计算得到。

Keyboard shortcuts