本章将展示如何在信号列表中交换两个信号（signals）。这是排序算法中一个重要的子例程。更一般地说，列表是构建更有趣功能（如哈希函数或在 CPU 中模拟内存）的基本构建块，因此我们必须学习如何更新它们的值。

交换列表中的两个元素是程序员最早学到的知识之一，典型的解决方案如下所示：

Copy
# s and t are indexes of array arr
def swap(arr, s, t):
  temp = arr[s];
  arr[s] = arr[t];
  arr[t] = temp;
  return arr

然而，在 ZK（零知识）电路中，这项操作可能会异常棘手。

• 首先，我们无法直接对信号数组进行索引。为此，我们需要使用 Quin selector。
• 其次，我们不能“写入”信号数组中的信号，因为信号是不可变的（immutable）。

相反，我们需要创建一个新数组，并将旧值复制到新数组中，同时遵循以下条件：

• 如果我们位于索引 s，则写入 arr[t] 的值
• 如果我们位于索引 t，则写入 arr[s] 的值
• 否则，写入原始值

我们对新数组的每一次写入都是一个条件操作。

前面的章节已经解释过了 Quin selector —— 为了节省空间，我们不会在这里重复这些代码。

Circom 中的 Swap

下面的组件将交换索引 s 和索引 t 处的元素，并返回一个新数组。（以下代码中存在一个 bug，试着把它找出来！答案将在后文揭晓。）

Copy
template Swap(n) {
  signal input in[n];
  signal input s;
  signal input t;
  signal output out[n];
  
  // we do not check that
  // s < n or t < n
  // because the Quin selector
  // does that

  // get the value at s
  component qss = QuinSelector(n);
  qss.idx <== s;
  for (var i = 0; i < n; i++) {
    qss.in[i] <== in[i];
  }

  // get the value at t
  component qst = QuinSelector(n);
  qst.idx <== t;
  for (var i = 0; i < n; i++) {
    qst.in[i] <== in[i];
  }
  
  // qss.out holds in[s]
  // qst.out holds in[t]

  component IdxEqS[n];
  component IdxEqT[n];
  component IdxNorST[n];
  signal branchS[n];
  signal branchT[n];
  signal branchNorST[n];
  for (var i = 0; i < n; i++) {
    IdxEqS[i] = IsEqual();
    IdxEqS[i].in[0] <== i;
    IdxEqS[i].in[1] <== s;

    IdxEqT[i] = IsEqual();
    IdxEqT[i].in[0] <== i;
    IdxEqT[i].in[1] <== t;

    // if IdxEqS[i].out + IdxEqT[i].out
    // equals 0, then it is not i ≠ s and i ≠ t
    IdxNorST[i] = IsZero();
    IdxNorST[i].in <== IdxEqS[i].out + IdxEqT[i].out;

    // if we are at index s,
    // write in[t]
    // if we are at index t,
    // write in[s]
    // else write in[i]
    branchS[i] <== IdxEqS[i].out * qst.out;
    branchT[i] <== IdxEqT[i].out * qss.out;
    branchNorST[i] <== IdxNorST[i].out * in[i];
    out[i] <==  branchS[i] + branchT[i] + branchNorST[i];
  }
}

请注意，最后的条件语句

Copy
branchS[i] <== IdxEqS[i].out * qst.out;
branchT[i] <== IdxEqT[i].out * qss.out;
branchNorST[i] <== IdxNorST[i].out * in[i];
out[i] <==  branchS[i] + branchT[i] + branchNorST[i];

不能写成

Copy
out[i] <==  IdxEqS[i].out * qst.out + IdxEqT[i].out * qss.out + IdxNorST[i].out * in[i]

因为这会导致非二次约束错误（non-quadratic constraints error，即在约束中存在不止一次乘法运算）。

寻找 Bug

上面的代码中有一个 bug —— 在向下滚动之前，你能发现它吗？

代码中的 Bug

上述代码的问题在于，它没有考虑到 s 的值可能等于 t 的值（s == t）的情况。在这种情况下，写入该索引的值将会变成该索引处的值加上它自身。

修复问题

为了防止这种情况发生，我们需要显式地检测是否 s == t，并将 branchS 或 branchT 其中之一乘以零，以避免数值翻倍。换句话说，如果针对 s 和 t 的开关都处于激活状态，那么最终的值将是 s + t。但这不是我们想要的结果，我们希望通过任意选择 branchS 或 branchT（它们的值相同）来确保该值实际上保持不变：

Copy
template Swap(n) {
  signal input in[n];
  signal input s;
  signal input t;
  signal output out[n];

  // NEW CODE to detect if s == t
  signal sEqT;
  sEqT <== IsEqual()([s, t]);

  // get the value at s
  component qss = QuinSelector(n);
  qss.idx <== s;
  for (var i = 0; i < n; i++) {
    qss.in[i] <== in[i];
  }

  // get the value at t
  component qst = QuinSelector(n);
  qst.idx <== t;
  for (var i = 0; i < n; i++) {
    qst.in[i] <== in[i];
  }

  component IdxEqS[n];
  component IdxEqT[n];
  component IdxNorST[n];
  signal branchS[n];
  signal branchT[n];
  signal branchNorST[n];
  for (var i = 0; i < n; i++) {
    IdxEqS[i] = IsEqual();
    IdxEqS[i].in[0] <== i;
    IdxEqS[i].in[1] <== s;

    IdxEqT[i] = IsEqual();
    IdxEqT[i].in[0] <== i;
    IdxEqT[i].in[1] <== t;

    // if IdxEqS[i].out + IdxEqT[i].out
    // equals 0, then it is not i ≠ s and i ≠ t
    IdxNorST[i] = IsZero();
    IdxNorST[i].in <== IdxEqS[i].out + IdxEqT[i].out;

    // if we are at index s, write in[t]
    // if we are at index t, write in[s]
    // else write in[i]
    branchS[i] <== IdxEqS[i].out * qst.out;
    branchT[i] <== IdxEqT[i].out * qss.out;
    branchNorST[i] <== IdxNorST[i].out * in[i];
    
    // multiply branchS by zero if s equals T
    out[i] <==  (1-sEqT) * (branchS[i]) + branchT[i] + branchNorST[i];
  }
}

结论

在 Circom 中进行任何数组操作都需要创建一个新数组，并将旧值复制到新数组中（发生更新的位置除外）。

通过在循环中使用这种模式，我们可以执行对列表进行排序、模拟栈和队列等数据结构，甚至更改 CPU 或 VM 状态等操作。我们将在后面的章节中看到相关的例子。