🐖

値を隠すってどういうこと？ど素人からのroad to zk 2

に公開
Rust
Solana
zk
tech

どうしたら値を隠せるのか

そもそも、数学的に値を隠すってどういうこと？　っていうのを考えていきたいと思います。

ということで問題です！！

(1,6) - ①　
(3,10) - ②

の２点を通る関数を求めてください。

このとき
y = ax + b - ③に値を代入して求めることができますよね。

③に①を代入して、
6 = a + b - ④

③に②を代入して、
10 = 3a + b - ⑤

となります。
このとき⑤から④をひくと
4 = 2aとなり、a=2。
a=2ということは、これを④に代入して、
6 = 2 + b
b=4となり、この２点を通る関数は
y = 2x + 4となります。

この関数を求めるためには２つの点が必要です。
１つの点だけでは、関数を求めることはできません。

そして、たとえばbになにか隠したい値を入れて、この関数の点を違う人に配布したらどうでしょうか。
点を受け取った人たち同士がその点を持ち寄らないと、そのbの値をみることができません。

これが、値を隠すということです！

わああ！！ぱちぱちぱち👏

中学生レベルの数学でこんな面白い数字の隠し方があるなんて！！
私はもうここで「ああ、そういうことなのか」と幸せになっていました。

おさらい

適当に関数を作って
y=x^2+3x
そこに秘密の値を足す。
y=x^2+3x+200(秘密の値)

それでつぎはここにx=1やx=2,x=3を放り込む。
すると(1,205),(2,210),(3,218)という値が手に入るので、この値をA子さんB男さんC美さんの三人に配布する。
そうするとA子さんB男さんC美さんの三人がこの値を持ち寄ると先ほどの関数y=x^2+3x+200が復元できて、秘密の値(200)が手に入る。ということになります。（これすごく中学校とかの活動とかでやると楽しそうだと思いませんか？）

と、ここまでの理解で十分zkなどで必須とされる知識のシャミアの秘密分散のエッセンスはつかめています！！（シャミアの秘密分散という名前は初出ですが、ぜひ頭の片隅に引っ掛けておいてください）
ので以上！　解散！

ということで以下はおまけです。
興味がある人はお付き合いください。

おまけ1 ー数学をもう少しつまんでみよう

２、３個数値を集めただけで復元できるとなるとセキュリティ的には心配です。

ということで実際にはこのようなすごく長い関数を使うことになります。

y=a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+...+a_nx^n

さきほどのa,bはここでは、あまりにも多いのでa_0,a_1...にさせてもらいました。これでいくつ増えても大丈夫です。

このa_1..というやつを係数と呼ばせてください。

そして、係数もすごく大きい値になります。乱数とかでランダムに吐き出した数値を使います。

こんな感じの雰囲気になります。(イメージ)
y = 1123140881350019452x^3 + 1063579634836364405x^2 + 944457141809054311x + (秘密の値）

これで隠し方はばっちりです！

でも次の問題はどうやってこれを復元するんですか・・・？
ということですよね。

最初に出てきた計算は一次関数、二次関数なので、連立方程式を組めば簡単なのですが、それが三次、四次...それ以上...。
先ほどまでのように連立方程式では到底解けません。

そこででてくるのが
ラグランジュ補間という魔法のような方法です。

L(x) = \sum_{j=0}^{n} y_j \prod_{\substack{0 \le m \le n \\ m \ne j}} \frac{x - x_m}{x_j - x_m}

もう見た目がいかつい・・・。
普通に学校数学しかやってなかったら、この人は初対面だと思います。
\prod<-この人
が、この子は、要するに「後の要素をぜんぶ掛け合わせてね」という意味です。

日本語で「この要素をこっからここまで掛けてね」と書くとちょっとめんどくさいから「一つの記号で表しちゃえ！」という便利な言葉なので、怖がらなくて大丈夫です。

ちなみに具体的な演算としてはこうなります。

L(x) = y_0 \frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)} + y_1 \frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)} + y_2 \frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}

ここまでくると、面倒なだけ！で絶対解けるので、頑張ろう！！！って気分になりますよね！
私は面倒なので、ここまできたら、あとはプログラミングに投げてしまいたいです。

ということでおまけ２でRustで実装していきたいと思います。

おまけ2 ーここまできたら実装したいよね？

秘密の値を隠してみよう

まずは、秘密の値を隠した関数を作って、配布するための点をつくるところからです！

pub fn split(secret: u128, k: usize, n: usize) -> Vec<Share> {
    assert!(k <= n, "k must be <= n");
    // まずは係数の配列を準備します。このkは次数＋１を入れます。
    // ３次式にしたい場合には、k=4で渡してください。
    let mut coeffs = vec![0u128; k];
    // ここに秘密の値をいれます。y切片と言ってもいいし、a_0項目です。
    coeffs[0] = secret;
    //　ここから係数を放り込みます。
    // 0番目は秘密の値なので、１番目から放り込んでいきましょう。
    for i in 1..k {
        // 係数は乱数が良いので、乱数を使ってほうりこんでください。
        coeffs[i] = random();
        // debugのときにわかりやすくしたいなら、乱数じゃなくて、
        // とりあえずiを放り込んでもいいかも
        // 以下のものを上記と差し替えて使って値を見るのもおすすめ
        // coeffs[i] = i as u128;
    }

    // ここのnは配布したい点の数だよ。k以下の数にしないと秘密は復元できない。
    (1..=n as u128)
        .map(|x|{
            let y = coeffs.iter().rev().fold(0u128, |acc, &c|{
                // ホーナー法
                // 人間が手計算するときとは違う方法でやるのが
                // ポイントでして・・・。イメージは以下のとおり。
                // 展開してみると納得するはず
                // x(x(x(a_3)+a_2)+a_1)+a_0
                // revっていうのは配列を逆から回すってことなんだけど、
                // ホーナー法の計算順番をみてくれると納得すると思う。
                add(mul(acc, x), c)
            });
            (x, y)
        }).collect()
}

これで配布する点の作成は終わり。
関数をつくるところもプログラムにやってもらうから、秘密を隠したい人が用意するのは、秘密の値と何次式にしたいかと配布したい数だけ。
小難しい計算とかは全部お任せしてしまったらOK。

秘密の値を復元してみよう

pub fn combine(shares: &[Share]) -> u128 {
    assert!(!shares.is_empty(), "shares is empty");

    let mut secret = 0u128;

    for (i, &(xi, yi)) in shares.iter().enumerate() {
        let mut num = 1u128;
        let mut den = 1u128;

        // ここの計算はラグランジュ補間
        for (j, &(xj, _)) in shares.iter().enumerate() {
            if i != j {
                // y切片のみ必要なので、xは不要!!!
                num = mul(num, sub(0, xj));
                // 公式通り
                den = mul(den, sub(xi, xj));
            }
        }
        let lagrange = mul(yi, div(num, den));
        secret = add(secret, lagrange)
    }
    secret
}

復元も先ほどのラグランジュ補間を使えばこのとおりです。

ということで以上です！
読んでくださってありがとうございます！

追記）Rust解説はほかにもいっぱいありそうなので、割愛しているけれど、ホーナー法とかあたりの書き方など、Rust解説があった方がいいものがあれば、解説もしていこうと思います！

追記２） 基本的な演算(mul,addなど）については有限体の実装となっているので、こちらの記事もご覧ください。

Discussion