BigInt 除法/模数事实证明，在构建约束方面，除法只比乘法稍微复杂一点。如果把 a / b 写成 (q, r) ，其中 q 是商， r 是余数，则只需约束 a = b * q + r 和 0 <= r 。虽然仍然需要用长除法来计算这些值以产生一个见证，但约束这个见证要简单得多，因为可以再次使用 BigInt 乘法约束。通过除法可以实现 a mod p 操作（也就是除以 p 后的余数），同时也可以用这个电路来建立加法、减法和乘法 mod p ！剩下的唯一操作是模逆运算，我们可以将其限制为 a_inv * a = 1 (mod p) 并重新使用乘法电路，此处可以用费马小定律 （Fermat&＃39;s Little Theorem ）来计算见证的 a_inv ，即 a ** (p - 2) = a_inv (mod p) 。再一次强调，我们可以在编写约束时把除法变成乘法。 ECC 操作 在这一节中，我们将讨论如何在一个非本机字段上将 BigInt 运算转变为椭圆曲线运算。下面的约束计数被应用到了我们的 v0.0.0 实现中 [5] 。在过去的几个月里，我们已经实现了进一步的优化，目前仍在整理和记录这些优化的过程中。 点加法和倍点在传统的计算模型中，模逆比模乘要昂贵得多。因此，点加和倍点通常是以 Jacobian 形式进行的，它是以牺牲更多的模乘为代价来消除模逆运算。在我们的设置中，模逆和模乘消耗相同数量的约束，所以我们使用更有效的 Weierstrass 形式的标准公式。这个例子也能够说明 zkSNARKs 编程如何为性能优化创造一个新的机制。 标量乘法
实现 ECDSAPrivToPub 需要将 secp256k1 上的基点 G 与私钥 d_A （一个标量）进行标量乘法 d_A * G 。这方面的标准算法是倍点-加，它使用 d_A 的二进制表示：
def double_and_add(bits): res = O // O is the additive identity on secp256k1 for i in [0, ..., 255]: res = res + res // doubling on secp256k1 if bits[i] == 1: res = res + G // addition of unequal points on secp256k1 return res
对于一个 256-bit 的私钥，在最坏的情况下，需要 256 个点加和点乘，以转化为 9037920 个约束。由于基点 G 在我们的设定中是已知和固定的，我们可以通过预先计算和缓存 G 的 2 次方的倍数来减少点操作的数量，然后再通过与私钥二进制数相对应的 G 的缓存倍数之和来计算出公钥。
Gpow[256] = precompute_G_powers() // Gpow[i] = (2 ** i) * G def cached_double_and_add(bits): let res = O // O is the additive identity on secp256k1 for i in [0, ..., 255]: if bits[i] == 1: res = res + Gpow[i] // addition of unequal points on secp256k1 return res
这种缓存的倍点-加最多需要 256 个点加，无需倍点，将约束的数量减少到了 3733697 个。在我们的实现中，我们使用缓存版的窗口法（Windowed Method) 来进一步减少点加的数量。也就是说，我们将私钥的二进制数字分成大小为 stride 的组，缓存 G 的倍数对应于一个组中二进制数为非零的数字，并将 G 表示为缓存的椭圆曲线点之和：
// Gpow[i][j] = j * (2 ** (i * stride)) * G for j = 1, ..., 2**stride - 1Gpow[ceil(256 / stride)][2 ** stride] = precompute_G_powers(stride) def cached_windowed(bits, stride): let res = O // O is the additive identity on secp256k1 for i in [0, ..., ceil(256 / stride) - 1]: j = bits[i * stride] + ... + bits[(i + 1) * stride - 1] * 2**(stride - 1) if j != 0: res = res + Gpow[i][j] // addition of unequal points on secp256k1 return res
![[大整数乘法] java代码实现](https://img1.php1.cn/3cd4a/24c6f/9f3/0133bb25da242824.jpeg)
京公网安备 11010802041100号