在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 处，
    // 写入 in[t]
    // 如果我们在索引 t 处，
    // 写入 in[s]
    // 否则写入 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];
  }
}

请注意，最终的条件语句

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];

不能写成

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

因为这会产生非二次约束错误（约束中存在多个乘法）。

找出错误

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

代码中的错误

上面代码的问题在于它没有考虑到 s 处的值可能等于 t 处的值 (s == t)。在这种情况下，写入索引的值将是该索引处的值与其自身相加的结果。

修复问题

为了防止这种情况，我们需要明确检测 s == t，并将 branchS 或 branchT 中的一个乘以零，以避免使值加倍。换句话说，如果 s 和 t 的开关都处于活动状态，则结果值将为 s + t。但我们不希望这样，我们希望通过任意选择 branchS 或 branchT 来有效地保持值不变（它们将具有相同的值）：

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

  // 新代码，用于检测 s == t
  signal sEqT;
  sEqT <== IsEqual()([s, t]);

  // 获取 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];
  }

  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 处，则写入 in[t]
    // 如果我们在索引 t 处，则写入 in[s]
    // 否则写入 in[i]
    branchS[i] <== IdxEqS[i].out * qst.out;
    branchT[i] <== IdxEqT[i].out * qss.out;
    branchNorST[i] <== IdxNorST[i].out * in[i];

    // 如果 s 等于 T，则将 branchS 乘以零
    out[i] <==  (1-sEqT) * (branchS[i]) + branchT[i] + branchNorST[i];
  }
}

结论

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

通过在循环中使用这种模式，我们可以执行诸如排序列表、建模堆栈和队列之类的数据结构，甚至可以更改 CPU 或 VM 的状态。我们将在以下章节中看到这些示例。

• 原文链接： rareskills.io/post/circo...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～