R1CS
R1CS is rank-1 constraint system.
R1CSは$ (a, b, c) $ a_i(x)
$ s*a * s*b = s*c
$ S = \left(\begin{array}{ccc}s_1 & s_2 & s_3 \end{array} \right)
$ A_1 = \left(\begin{array}{ccc}a_{1,1} \\ a_{1,2} \\ a_{1,3} \end{array} \right)
とした時に
$ SA * SB - SC = 0
になることが問題を解いたことになリマス。
SAやSB, SCはスカラ値になります。
Sは数字、変数、入力、出力のベクトル。
例）$ S = \left(\begin{array}{ccc} ~one & x & ~out & sym_1 & y & sym_2 \end{array} \right)
flatteningされたgates
code:js
sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5
一つ目の式 sym_1=x*xは以下のようになります。
$ A_1 = \left(\begin{array}{ccc}0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{array} \right)$ B_1 = \left(\begin{array}{ccc}0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{array} \right)$ C_1 = \left(\begin{array}{ccc}0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{array} \right)
という風にやっていくと、問題をS, A, B, Cベクトルに変換できることはわかると思います。
そしてこれを満たすSは(1, 3, 35, 9, 27, 30)ですね。
結果はこれですね（縦じゃなくて横に並べてます）
A
(0, 1, 0, 0, 0, 0)
(0, 0, 0, 1, 0, 0)
(0, 1, 0, 0, 1, 0)
(5, 0, 0, 0, 0, 1)
B
(0, 1, 0, 0, 0, 0)
(0, 1, 0, 0, 0, 0)
(1, 0, 0, 0, 0, 0)
(1, 0, 0, 0, 0, 0)
C
(0, 0, 0, 1, 0, 0)
(0, 0, 0, 0, 1, 0)
(0, 0, 0, 0, 0, 1)
(0, 0, 1, 0, 0, 0)
コードを読む
該当コードも示します
こちらのsignalsが上記の$ S = \left(\begin{array}{ccc} ~one & x & ~out & sym_1 & y & sym_2 \end{array} \right)と思われます。
初期状態でoneだけ入っています。
おそらくoriginal codeを解析し、signalsが全て入り切ったところで
buildConstraintsでR1CSを作るのだと思います。
code:js
function fillLC(dst, src) {
if (src.type != "LINEARCOMBINATION") throw new Error("Constraint is not a LINEARCOMBINATION");
for (let s in src.values) {
const v = src.valuess.toString(); const id = ctx.signalName2Idxs; }
}