🕌

【デザインパターン】秘匿したい値の所有を証明するコミットメントスキームについて ~Pedersen Commitmentを添えて~

serinuntius2022/12/02に公開

はじめに

こんにちは〜、本記事は Ethereum Advent Calendar 2022 の3日目の記事です。

ブロックチェーンというかスマートコントラクトを書いているときに、秘密の値を扱いたいときはないでしょうか?

例えば、投票であったり、ゲームだったり、プライバシーを重視した何かであったり・・・。
そしてその値は後から開示して良い場合と、ずっと開示したくない場合があります。

そういう場合のデザインパターンとして、コミットメントスキームと呼ばれるものがあります。本記事ではコミットメントスキームの1つである、Pedersen Commitment を試しながら、簡単なアプリケーションを作ってみたいと思います。
また著者は暗号学の専門家ではないため、DYOR & Verifyお願いします。

コミットメントスキームとは?

ビットコミットメント、コミットメント方式とは、暗号理論におけるプロトコルである。ビットコミットメントを用いることで、ユーザーは値を秘密裏にコミットすることができる。また、ユーザーは後にコミットされた値を明らかにすることが可能である。 コミットメント方式を想像するには以下の喩えが有効である。送信者は値を書いた紙を箱に入れカギを掛け、その箱を受信者に送る。箱の中身は受信者には見えないし、送信者が鍵を送らなければ錠前を開けることもできない。また受信者が箱を持っているので送信者が箱の中身を改ざんすることも不可能である。コミットメント方式は暗号プロトコルと密接な関係を持っている。とくにゼロ知識証明やマルチパーティ計算、また電子マネーや電子投票 に用いられている。 ビットコミットメント - Wikipedia

らしいです。この記事では ビットコミットメント = コミットメントスキーム として扱います。

コミットメントスキームでは

  • 秘匿性
    • コミットする前の値が受信者がわからない
  • 束縛性
    • コミットする前の値を後から変更できない

という性質が大事になってきます。

送信者がある値を秘匿された値に変換し受信者に公開することをコミットという。
逆に秘匿された値を復元できるような付加的な情報を受信者に公開することをデコミットという。

ハッシュ関数を利用したコミットメント

ハッシュ関数も乱数(ソルト)と組み合わせると 秘匿性束縛性 を手に入れることができます。
もし、乱数を使わない場合は、レインボーテーブルのような攻撃ができてしまいます。ソルト(乱数)が必要になるわけですね。

例えばジャンケンの手をコミットしたいとすると、次のような感じになるでしょう。

ぐー、ちょき、ぱーをそれぞれ0, 1, 2とする。
暗号論的擬似乱数生成器 を用いて、ソルトを生成します。

Unixな環境で、bashで試してみましょう。

# 256bitな値をbase64エンコードしてsaltとして利用。
alice $ SALT=$(dd if=/dev/urandom bs=256 count=1 2> /dev/null | base64)

# 試しに出力してみる
alice $ echo $SALT
bLs98qz0Jg0L2Oonn/hW8fXZmQXY/MHd9hKoFprcozTuJDyPWGCFpLLsYrmpv0f24FhZ6TEk869srbgASl+vFMKC7iv8FyDbvz4o2drbYHfdaPIw81zGQWdEx1GvzBUMoELio2ofS7ZnMs89pSKLm+tO894ztAo3GREY9aelxB0HJbqM8J4/4xN3QSCfrO0WkiZ7jDFCYuv3hixOgdO8npc+FV3dsBEBY5TY+G2r962lkQD/bjZWfM+evQepfitDdaITkBeCsP6fORTgft1DbIZ2Gh58WcDSS0/HD/141gdSg0DRXhZhDxza/B7/1isfTAIWTTY6DPZf92DVI4UgCg==

# sha256を使って0(ぐー)とソルトでハッシュにかけてみる
# 3974...がコミットされた値
alice $ echo 0.$SALT | shasum -a 256
39749134deefba1ff722519b7635513ccd70c75fc4ba991b53732d5da7642287 

# bobになりきって、コミットされた値をaliceから受け取る
bob $ COMMIT=39749134deefba1ff722519b7635513ccd70c75fc4ba991b53732d5da7642287

# 当たり前だけど、COMMITだけでは、bobは何の手を出されたかわからない。
# デコミットして、じゃんけんの手を知りたいのでaliceに手とsaltを教えてもらう
bob $ HAND=0
bob $ SALT=bLs98qz0Jg0L2Oonn/hW8fXZmQXY/MHd9hKoFprcozTuJDyPWGCFpLLsYrmpv0f24FhZ6TEk869srbgASl+vFMKC7iv8FyDbvz4o2drbYHfdaPIw81zGQWdEx1GvzBUMoELio2ofS7ZnMs89pSKLm+tO894ztAo3GREY9aelxB0HJbqM8J4/4xN3QSCfrO0WkiZ7jDFCYuv3hixOgdO8npc+FV3dsBEBY5TY+G2r962lkQD/bjZWfM+evQepfitDdaITkBeCsP6fORTgft1DbIZ2Gh58WcDSS0/HD/141gdSg0DRXhZhDxza/B7/1isfTAIWTTY6DPZf92DVI4UgCg==

# 本当にグーだったのかコミットされた値になるかverifyする
bob $ echo $HAND.$SALT | shasum -a 256
39749134deefba1ff722519b7635513ccd70c75fc4ba991b53732d5da7642287 
# ^^^ aliceが事前にコミットしていた値と正しいので、確かにぐー(0)を出していたとわかる

これは対話形式でやりましたが、スマートコントラクト(Solidity)を用いてじゃんけんをするのであれば、以下のような記事を参考にするといいでしょう。
Exploring Commit-Reveal Schemes on Ethereum

Pedersen Commitmentとは?

Pedersen Commitmentとは照明者がある値を公開したり変更したりすることなく、コミットできる暗号アルゴリズムです。

加法準同型暗号の1つで、暗号化したまま値を足し算(加法)できるという特徴があります。離散対数を用いて非対称性を得ているようです。

c(x,r) + c(x', r') = (x + x')P + (r + r')Q = c(x + x', r + r')

(a, b, c, d)の中身を知らなくても

Enc(a) = Enc(b) + Enc(c) + Enc(d)

を確認すれば、

a = b + c + d

が成り立つ。

RustでPedersen Commitmentを見てみよう

最近Rustがお気に入りなので、Rustで書いていきましょう!

依存関係はこんな感じです。

# Cargo.toml
[dependencies]
grin_secp256k1zkp = { git = "https://github.com/mimblewimble/rust-secp256k1-zkp.git"}

main.rs はこんな感じです。

use secp256k1zkp::{pedersen::Commitment, rand::thread_rng, ContextFlag, Secp256k1, SecretKey};

fn main() {
    let secp = Secp256k1::with_caps(ContextFlag::Commit);

    fn commit(value: u64, blinding: &SecretKey) -> Commitment {
        let secp = Secp256k1::with_caps(ContextFlag::Commit);
        secp.commit(value, blinding.clone()).unwrap()
    }

    // blindするための秘密鍵を生成
    let blind_alice = SecretKey::new(&secp, &mut thread_rng());
    let blind_bob = SecretKey::new(&secp, &mut thread_rng());

    // 3をコミット(暗号化されてるので、これだけ渡されても何かわからない)
    let commit_alice = commit(3, &blind_alice);

    // 2をコミット(暗号化されてるので、これだけ渡されても何かわからない)
    let commit_bob = commit(2, &blind_bob);

    println!("{:?}", commit_alice);
    println!("{:?}", commit_bob);

    // blindを足しておく
    let blind_c = secp
        .blind_sum(vec![blind_alice, blind_bob], vec![])
        .unwrap();

    // blind_cで5をコミット
    let commit_c = commit(5, &blind_c);

    // 暗号化された状態でコミットメントを加算する
    let commit_d = secp
        .commit_sum(vec![commit_alice, commit_bob], vec![])
        .unwrap();

    // 等しい!(すごい!)
    assert_eq!(commit_c, commit_d);
}

Rustでプライバシーを考慮した残高がわからないコインを書いてみよう!

#[test]
fn private_coin() {
    let secp = Secp256k1::with_caps(ContextFlag::Commit);

    let alice_blind = SecretKey::new(&secp, &mut thread_rng());
    let alice_blind2 = SecretKey::new(&secp, &mut thread_rng());
    let bob_blind = SecretKey::new(&secp, &mut thread_rng());

    // 最初のコイン発行量のコミット
    let genesis_commit = secp.commit(5, alice_blind.clone()).unwrap();
    // aliceが受け取るお釣りのコミット
    let otsuri_commit = secp.commit(3, alice_blind2.clone()).unwrap();

    // これをbobに渡す a2 - a1
    let alice_sum_blind = secp
        .blind_sum(vec![alice_blind2], vec![alice_blind])
        .unwrap();

    // bobが受け取る数量をcommit. aliceに渡す
    let transfer_commit = secp.commit(2, bob_blind.clone()).unwrap();

    // bobがblind_sum (a2 - a1 + b1)
    let bob_blind_sum = secp
        .blind_sum(vec![alice_sum_blind, bob_blind], vec![])
        .unwrap();

    // お釣り + 送る量 - 最初に発行したコイン量 = 0 のコミットを合算
    let all_commit = secp
        .commit_sum(vec![otsuri_commit, transfer_commit], vec![genesis_commit])
        .unwrap();

    let zero_commit = secp.commit(0, bob_blind_sum).unwrap();

    assert_eq!(zero_commit, all_commit);
}

実際にSolidityでPedersen Commitmentの検証をしてみよう

ちょっと間に合わなかったので、ここは宿題とします笑笑

間に合わせたかったのですが、すみません。

Solidityっぽい疑似言語でコントラクトを書いてみたよ。こんな感じになるかもね!

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.13;

import "./zkp/PedersenCommitment.sol";

// これは疑似コードであり、solidityではありません。

contract PrivateCoin is PedersenCommitment {
    
    /// @param change_commit お釣りの量のコミット(送信者のblindでコミット) blind => b1
    /// @param to_amount_commit 送る量のコミット(受信者のblindでコミット) blind => b2
    /// @param input_commit 受信者が最初に持っていた量のコミット(送信者のblindでコミット) blind => b3
    /// @param receiver_blind_sum 全てのblindのsum(b2 - b1 + b3)
    function transfer(change_commit, to_amount_commit, input_commit, receiver_blind_sum) external {
        // お釣り + 送る量 - 持ってる量 = 0になるようなcommitを加算する
        let commit = commit_sum([change_commit, to_amount_commit], [input_commit]);

        // 全部のblindのsumで0にコミットする
        let zero_commit = commit(0, receiver_blind_sum);

        // ここがイコールになっていれば、成功
        assert(commit, zero_commit);
    }
}

問題です!!(唐突)

もしこの疑似コードが正しく動いていたとしても、このコードには脆弱性があります。それはなんでしょうか?
その脆弱性をパブリックにせずにTwitterのDMまで教えてください!

まとめ

Pedersen Commitmentを初めて使ってみましたが、著者の頭が硬すぎて残高の秘匿をしながらblinding factorをやり取りするのに苦労しました。

Pedersen Commitment以外にもコミットメントスキームは多数あり、自分が知っているだけでも

  • KZGコミットメント
  • Merkle Tree(ハッシュ関数使ってるから当たり前と言えば当たり前だけど)

等があります。

本当はMerkle TreeとZKP使って不必要に情報を開示せずに、所有を証明するパターンもやりたかったのですが、時間の都合上そこまでいけませんでした。

Ethereumアドベントカレンダーという割にただの暗号学の話になってしまいましたが、引き続き濃い内容の記事を見たい方はいいねTwitterのフォローをお願いします!

no plan株式会社について

謝辞

この記事を書くにあたってコードを書いていたら、よくわからない事象にぶち当たりTwitterに投稿していたら、安土神に助けていただきました。この場で感謝を送りたいと思います。
https://twitter.com/techmedia_think/status/1598224092666023937?s=20&t=zdk_3HVqnuEm8K7DjO998w

参考文献

Discussion

ログインするとコメントできます