ZK 中有状态计算简介

在执行诸如幂、阶乘或计算斐波那契数列之类的迭代计算时，我们需要在某个点“停止计算”。

例如，如果我们计算 $x^7$，我们会将 $x$ 乘以自身七次。但是，条件停止在算术电路中是不可能的。由于电路的大小是固定的（底层 R1CS 具有固定数量的行，你不能更改它），它们必须足够大，以适应我们关心的每个指数的计算。

因此，解决方案是计算直到某个大于我们期望在实践中计算的限制的每个可能值。然后我们使用 Quin 选择器来选择所需的值。

本章展示了一个使用阶乘、斐波那契数列来执行此操作的示例，并将计算幂作为练习留给读者。

我们可以将这些计算中的每一个都视为一个状态机，它经历一个固定的状态转换一定的次数（其中迭代次数在证明时确定，而不是烘焙到电路中）。

这些序列在每个步骤中只有一个可能的计算（例如，加上前两个状态，或将前一个状态乘以某个数字）。但是，如果我们在每个状态添加条件分支，那么我们就拥有了有状态计算所需的所有组件。

在本章中，我们只展示只有一个可能的状态变化且状态变化的次数可变的示例。在接下来的章节中，我们将展示如何使状态转换本身有条件，即具有多个可能的状态转换。

阶乘示例

我们现在展示如何编写一个电路，以证明我们正确计算了

$$ y =x!\pmod p $$

其中 $!$ 是阶乘，$p$ 是默认的字段模数。

要在传统的编程语言（例如 Python）中计算阶乘，代码如下：

def factorial_mod_p(x, p):
  if x == 0:
    return 1

  acc = 1
  for i in range(1, x+1):
    acc = (acc * i) % p

  return acc

但是，如果直接转换为 Circom，上面的代码会有一些问题：

• Circom 不支持 if 语句，因此 if x == 0: return 0 行将无法编译。
• Circom 不支持未知迭代次数的循环。由于 x 决定了循环的值，因此这也无法编译。Circom 在底层编译为 R1CS，并且底层 R1CS 需要具有固定的大小，并且不能基于输入的值来更改大小。

为了使代码与诸如 R1CS 之类的算术化表示形式兼容，我们需要计算从零到我们打算支持的某个上限的阶乘。

例如，如果我们知道我们永远不需要计算超过 99 的阶乘，那么我们必须计算从 0 到 99（包括 0 到 99）的每个阶乘。如果我们想为 80 的阶乘创建一个证明，我们仍然需要计算从 0 到 99 的阶乘，但是我们使用 Quin 选择器来返回 80 的结果。

这是一个没有 if 语句和固定长度循环的 Python 示例：

def factorial_mod_p(x, p):

  assert x < 100
  # allocate the array
  ans = [0] * 100
  ans[0] = 1 # 0! = 1

  for i in range(1, 100):
      ans[i] = (ans[i-1]...