在Circom中交换数组中的两个条目

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

在列表中交换两个项目是程序员首先学习的事情之一，一个典型的解决方案如下所示：

## s 和 t 是数组 arr 的索引
def swap(arr, s, t):
  temp = arr[s];
  arr[s] = arr[t];
  arr[t] = temp;
  return arr

然而，在 ZK 电路中，此操作可能非常棘手。

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

相反，我们需要创建一个新数组并将旧值复制到新数组，但须满足以下条件：

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

我们对新数组进行的每次写入都是有条件的操作。

Quin selector 在上一章中解释过——为了节省空间，我们这里不再重复代码。

在 Circom 中交换

下面的组件将交换索引 s 处的项目与索引 t 处的项目，并返回一个新数组。（以下代码存在错误，尝试找到它！答案稍后给出。）

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

  // 我们不检查
  // s < n 或 t < n
  // 因为 Quin selector
  // 做了这件事

  // 获取 s 处的值
  component qss = QuinSelector(n);
  qss.idx <== s;
  for (var i = 0; i < n; i++) {
    qss.in[i] <== in[i];
  }

  // 获取 t 处的值
  component qst = QuinSelector(n);
  qst.idx <== t;
  for (var i = 0; i < n; i++) {
    qst.in[i] <== in[i];
  }

  // qss.out 保存 in[s]
  // qst.out 保存 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;

    // 如果 IdxEqS[i].out + IdxEqT[i].out
    // 等于 0，则它不是 i ≠ s 且 i ≠ t
    IdxNorST[i] = IsZero();
    IdxNorST[i].in <== IdxEqS[i].out + IdxEqT[i].out;

    // 如果我们在索引 s 处，...