Quin Selector 是一种设计模式，它允许我们将一个 signal（信号）用作 signal 数组的索引。

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

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

Copy
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,9,14,20] 和 [0,0,1,0] 之间进行内积计算，结果为 14。

如果 index 等于所需的索引，每个“开关”就会变成 0 或 1。

Copy
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
  signal prod[n];
  
  // prod = 1 * in[i] if i == index else 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 的范围检查，因此我们建议读者参考该模板，上述示例正是基于该模板编写的：

Copy
// out is the sum of 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 idx;
  signal output out;
  
  // Ensure that idx < choices
  component lessThan = LessThan(252);
  lessThan.in[0] <== idx;
  lessThan.in[1] <== choices;
  lessThan.out === 1;

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

  // For each item, check whether its index equals the input idx.
  for (var i = 0; i < choices; i ++) {
    eqs[i] = IsEqual();
    eqs[i].in[0] <== i;
    eqs[i].in[1] <== idx;

    // eqs[i].out is 1 if the idx matches. As such, at most one input to
    // calcTotal is not 0.
    calcTotal.in[i] <== eqs[i].out * in[i];
  }

  // Returns 0 + 0 + 0 + item
  out <== calcTotal.out;
}

作为一种优化，component lessThan = LessThan(252); 这一步实际上不需要 252 位来确保 idx 小于 choices。根据具体的应用场景，我们可以使用更少的位数来进行比较，从而节省底层生成的约束数量。

Circomlib 中的 Quin Selector 实现

Circomlib 库中的 multiplexer 实现了与 Quin Selector 相同的功能。不过，它索引的是一个二维数组并返回一个一维数组。例如，给定数组 in = [[5,5],[6,6],[7,7]] 且 idx = 1，它将返回 [6, 6]。

该 component 具有以下输入和输出：

Copy
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 的值，而是生成一个在目标索引处为 1、其余全为 0 的“掩码（mask）”，并将该掩码与输入相乘。例如，如果 sel = 1，它会生成掩码 [0,1,0] 并将输入与该掩码相乘。

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

Copy
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）”，这早于以太坊 Dark Forest 的实现。感谢 0xerhant 指出这一点。