在进行诸如幂、阶乘或计算 Fibonacci 数列等迭代计算时，我们需要在特定点之后“停止计算”。

例如，如果我们正在计算 $x^7$，我们会将 $x$ 自身相乘七次。然而，在算术电路中是不可能实现条件停止的。因为电路具有固定大小（底层的 R1CS 具有固定的行数且你无法更改它），所以它们必须足够大，以便涵盖我们想要计算的每一个指数。

因此，解决方案是计算达到某个上限的所有可能值，该上限要大于我们在实际中预期计算的值。然后我们使用 Quin selector 来挑选所需的值。

本章将展示使用阶乘和 Fibonacci 数列实现此过程的示例，并将计算幂作为练习。

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

这些序列在每一步只有一种可能的计算（例如将前两个状态相加，或将前一个状态乘以某个数字）。然而，如果在每个状态中加入条件分支，那么我们就具备了状态计算所需的所有组件。

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

阶乘示例

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

其中 $!$ 是阶乘，$p$ 是默认的有限域模数。

要在诸如 Python 等传统编程语言中计算阶乘，代码将如下所示：

Copy
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 这样的算术化表示，我们需要从 0 开始计算阶乘，直到我们打算支持的某个上限。

例如，如果我们知道我们永远不需要计算超过 99 的阶乘，那么我们必须计算从 0 到 99（含）的所有阶乘。如果我们想为 80 的阶乘生成证明，我们仍然需要计算从 0 到 99 的阶乘，但是我们使用一个 Quin selector 来返回 80 的计算结果。

这里有一个不包含 if 语句且具有固定长度循环的 Python 示例：

Copy
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] * i) % p
  
  return ans[x]

从某种意义上说，我们正在创建一个长度为 100 的数组，并将该索引的阶乘值填充进去。然后，我们将使用 Quin selector 来“选择”我们关心的阶乘。

将其转换为 Circom 非常直观：

Copy
include "./node_modules/circomlib/circuits/multiplexer.circom";
include "./node_modules/circomlib/circuits/comparators.circom";

template factorial(n) {
  signal input in;
  signal output out;

  // precompute factorials from 0 to n
  signal factorials[n+1];

  // compute the factorials
  factorials[0] <== 1;
  for (var i = 1; i <= n; i++) {
    factorials[i] <== factorials[i - 1] * i;
  }

  // ensure that in < n
  signal inLTn;
  inLTn <== LessThan(252)([in, n]);
  inLTn === 1;
  
  // select the factorial of interest
  component mux = Multiplexer(1, n);
  mux.sel <== in;

  // assign factorials into the multiplexer
  for (var i = 0; i < n; i++) {
    mux.inp[i][0] <== factorials[i];
  }

  out <== mux.out[0];
}

component main = factorial(100);

/*
  INPUT = { "in": "3" }
*/

一个不安全的实现

许多刚接触 Circom 的工程师通常会使用一种“直觉”的解决方案，这种方案避免了二次约束的任何问题，并会写出如下代码：

Copy
pragma circom 2.1.8;

include "./node_modules/circomlib/circuits/comparators.circom";

template factorial(n) {
  signal input in;
  signal output out;

  signal factorials[n + 1];

  // compute the factorials
  var acc = 1;
  for (var i = 1; i < n; i++) {
    acc = acc * i;
  }
  
  out <-- acc;
}

component main = factorial(100);

尽管 out 将得到正确的答案，但完全没有使用 <== 或 === 运算符意味着该电路没有任何约束。

在上面的代码中，程序员编写了能够正确计算阶乘的代码，但并没有对其施加约束。

模 p 下的 Fibonacci 示例

在阶乘示例中，我们必须将 factorials 的第 0 个条目“硬编码”为 1，因为 0! = 1。在 Fibonacci 数列中，前两个数字都是 1，之后的所有数字都是序列中前两个数字的和。因此，对于 Fibonacci 代码，我们硬编码前两个值，然后计算其余部分。

下面的电路计算直到第 n 个数字的 Fibonacci 数列（模 p），然后输出我们感兴趣的第 “in” 个 Fibonacci 数。

Copy

include "./node_modules/circomlib/circuits/multiplexer.circom";
include "./node_modules/circomlib/circuits/comparators.circom";

template Fibonacci(n) {
  assert(n >= 2); // so we don't break the hardcoding

  signal input in; // compute the kth Fibonacci number
  signal output out;

  // precompute Fibonacci sequence from
  // 0 to n
  signal fib[n + 1];

  // compute the factorials
  fib[0] <== 1;
  fib[1] <== 1;
  
  for (var i = 2; i < n; i++) {
    fib[i] <== fib[i - 1] + fib[i - 2];
  }

  // ensure that in < n
  signal inLTn;
  inLTn <== LessThan(252)([in, n]);
  inLTn === 1;

  // select the fibonacci number 
  // of interest
  component mux = Multiplexer(1, n);
  mux.sel <== in;

  // assign Fibonacci into
  // the Quin Selector
  for (var i = 0; i < n; i++) {
    mux.inp[i][0] <== fib[i];
  }

  out <== mux.out[0];
}

component main = Fibonacci(99);

/*
  INPUT = {"in": 5}
*/

像往常一样，重要的是要显式约束 Fibonacci 数列的每一次更新，而不是仅仅在一个不受约束的循环中计算结果。

练习：

完成 Circom Puzzles 中的 pow 练习。