Quin Selector(选择器)

Quin Selector 是一种设计模式，允许我们使用一个信号作为信号数组的索引。

作为前提，我们假设读者已经阅读了 Circom 中的条件语句章节。

以下代码无法编译，但它说明了我们想要完成的目标：

template ArraySelect(n) {

  signal input in[n];
  signal input index;

  signal output out;

  // won't compile -- non-quadratic constraints
  // 无法编译 -- 非二次约束
  out <== in[index];
}

为了在 Circom 中表达条件，我们将期望的分支乘以 1，其他的乘以 0，然后将所有分支相加。归零的分支不会对总和产生任何影响。Quin selector 遵循相同的逻辑：我们将期望的索引乘以 1，其余的乘以 0，然后对结果求和。

例如，假设我们的输入数组是 in = [5,9,14,20]。选择索引 2 处的项目意味着我们计算：

$$ 5\cdot0+9\cdot0+\boxed{14\cdot1}+20\cdot0=14 $$

换句话说，我们计算 [5,9,14,20] 和 [0,0,1,0] 之间的内积，结果为 14。

如果 index 等于期望的索引，则每个“switch”变为 0 或 1。

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

template ArraySelect(n) {

  signal input in[n];
  signal input index;
  signal output out;

  component eqs[n];

  // prod keeps a running product
  // prod 保持运行乘积
  signal prod[n];

  // prod = 1 * in[i] if i == index else 0
  // 如果 i == index 则 prod = 1 * in[i] 否则为 0
  for (var i = 0; i < n; i++) {
    eqs[i] = IsEqual();
    eqs[i].in[0] <== i;
    eqs[i].in[1] <== index;

    prod[i] <== eqs[i].out * in[i];
  }

  // sum the result
  // 对结果求和
  var sum;
  for (var i = 0; i < n; i++) {
    sum += prod[i];
  }

  out <== sum;
}

上面的代码没有约束索引小于数组的大小。如果索引超出范围，则代码将返回 0 作为结果。DarkForest 中的 Quin Selector 实现 包括对 index 的范围检查，因此我们将读者引用到该模板，以上示例基于该模板：

// out is the sum of in
// out 是 in 的总和
template CalculateTotal(n) {
  signal input in[n];
  signal output out;

  signal sums[n];

  sums[0] <== in[0];

  for (var i = 1; i < n; i++) {
      sums[i] <== sums[i-1] + in[i];
  }

  out <== sums[n-1];
}

template QuinSelector(choices) {
  signal input in[choices];
  signal input index;
  signal output out;

  // Ensure that index < choices
  // 确保 index < choices
  component lessThan = LessThan(252);
  lessThan.in[0] <== index;
  lessThan.in[1] <== choices;
  lessThan.out === 1;

  component calcTotal = CalculateTotal(choices);
  component eqs[choices];

  // For each item, check whether its index equals the input index.
  // 对于每个项目，检查其索引是否等于输入索引。
  for (var i = 0; i < choices; i ++) {
    eqs[i] = IsEqual();
    eqs[i].in[0] <== i;
    eqs[i].in[1] <== index;

    // eqs[i].out is 1 if the index matches. As such, at most one input to
    // 如果索引匹配，则 eqs[i].out 为 1。因此，最多一个输入到
    // calcTotal is not 0.
    // calcTotal 不为 0。
    calcTotal.in[i] <== eqs[i].out * in[i];
  }

  // Returns 0 + 0 + 0 + item
  // 返回 0 + 0 + 0 + 项目
  out <== calcTotal.out;
}

作为一种优化，步骤 component lessThan = LessThan(252); 不需要 252 位来确保 index 小于 choices。根据我们的应用程序，我们可以使用更少的位数来进行比较，并节省在底层生成的约束数量。

Circomlib 中 Quin Selector 的实现

Circomlib 库中的 multiplexer 完成了与 Quin Selector 相同的事情。但是，它索引一个二维数组并返回一个一维数组。例如，给定数组 in = [[5,5],[6,6],[7,7]] 和 index = 1，它将返回 [6, 6]。

该组件具有以下输入和输出：

template Multiplexer(wIn, nIn) {
  signal input inp[nIn][wIn];
  signal input sel;
  signal output out[wIn];

  // ...
}

使用示例 in = [[5,5],[6,6],[7,7]]，wIn 将为 2，nIn 将为 3。信号 sel 是要选择的索引；例如，如果 sel = 1，则 out = [6,6]。

Multiplexer 不是循环遍历数组并检查索引是否 IsEqual 到 sel 值，而是生成一个所有为零的“mask”，在期望的索引处为 1，并将该 mask 与输入相乘。例如，如果 sel = 1，它将生成 mask [0,1,0] 并将输入乘以该 mask。

以下是使用 Circomlib 的 multiplexer 的示例：

include "circomlib/multiplexer.circom";

template MultiplexerExample(n) {
  signal input in[n];
  signal input k;
  signal output out;

  component mux = Multiplexer(1, n);

  for (var i = 0; i < n; i++) {
    mux.inp[i][0] <== in[i];
  }
  mux.sel <== k;

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

component main = MultiplexerExample(4);

/* INPUT = {
  "in": [3, 7, 9, 11],
  "k": "1"
} */

历史记录

该算法在 xjsnark 论文 中被称为“Linear Scan”，该论文早于 eth Dark Forest 的实现。感谢 0xerhant 指出这一点。

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