Zenn
no plan incテックブログPublicationへの投稿
🙌

Plonky2というゼロ知識証明アルゴリズムで実装されているEVMの証明をチラ見してみる

serinuntius
2022/12/19に公開
Ethereum
ゼロ知識証明
plonky2
tech

はじめに

この記事はRust Advent Calendar 2022の19日目の記事です。

本当はCosmWASMで残高を秘匿するコインを作って紹介しようと思ったのですが、実装が間に合いませんでした 🙏

Rustと個人的な興味であるクリプトがマッチしていそうな分野の「ゼロ知識証明」の Plonky2 のEVMについてチラ見していきたいと思います。

投稿が遅れてしまって申し訳ないです。

ゼロ知識証明とは？

ゼロ知識証明とは、秘密を知っていることを秘密を教えることなく、第三者に秘密を知っていると証明できる仕組みのことです。
ここではあまり深入りしませんが、zkRollupを作る上で大切な特徴があります。それは、大量の計算を正しく行ったことを証拠を見るだけで検証できるということです。 zkRollupの回路内で計算してること

以降ZKPとします。

EthereumとEVMとは？

Ethereumはスマートコントラクトを実装しているブロックチェーンの1つです。
EVMは、Ethereumに採用されているVMのことです。

Plonky2とは？

mir-protocolが開発した再帰的なZKPを高速化するツールです。

シンプルな送金txについて見てみる

シンプルな新しいアドレスへの送金テストがあったので、そちらに日本語で適当にコメントを入れていきます。

/// Test a simple token transfer to a new address.
#[test]
fn test_simple_transfer() -> anyhow::Result<()> {
    init_logger();

    let all_stark = AllStark::<F, D>::default();
    let config = StarkConfig::standard_fast_config();

    // アドレスを定義しています。
    let sender = hex!("2c7536e3605d9c16a7a3d7b1898e529396a65c23");
    let to = hex!("a0a0a0a0a0a0a0a0a0a0a0a0a0a0a0a0a0a0a0a0");

    // keccakとはEthereumでよく使われるハッシュ関数です。
    let sender_state_key = keccak(sender);
    let to_state_key = keccak(to);
    let sender_nibbles = Nibbles::from(sender_state_key);
    let to_nibbles = Nibbles::from(to_state_key);
    let value = U256::from(100u32);

    // アカウントを初期化しています。
    let sender_account_before = AccountRlp {
        nonce: 5.into(),
        balance: eth_to_wei(100_000.into()),
        storage_root: PartialTrie::Empty.calc_hash(),
        // code_hashが空ってことはEOAを表しているのかも
        code_hash: keccak([]),
    };

    // EthereumではBitcoinのようなシンプルなMerkle Treeではなく、Merkle Patricia Trieという木構造が利用されています。
    // https://docs.rs/eth_trie_utils/0.3.0/eth_trie_utils/partial_trie/enum.PartialTrie.html
    let state_trie_before = PartialTrie::Leaf {
        nibbles: sender_nibbles,
        // RLPエンコードとは、Recursive Length Prefixの略で、Ethereumでよく目にします。
        // >RLPは高度に最小化したシリアライゼーションフォーマットで、ネストされたByte配列を保存する目的のためにある。
        // >protobufやBSONなどとは違って、BooleanやFloat、DoubleやIntegerさえ定義しない
        // だそうです。
        value: rlp::encode(&sender_account_before).to_vec(),
    };
    let tries_before = TrieInputs {
        state_trie: state_trie_before,
        transactions_trie: PartialTrie::Empty,
        receipts_trie: PartialTrie::Empty,
        storage_tries: vec![],
    };

    // Generated using a little py-evm script. py-evmで事前にスクリプトを書いたようです。
    let txn = hex!("f861050a8255f094a0a0a0a0a0a0a0a0a0a0a0a0a0a0a0a0a0a0a0a0648242421ba02c89eb757d9deeb1f5b3859a9d4d679951ef610ac47ad4608dc142beb1b7e313a05af7e9fbab825455d36c36c7f4cfcafbeafa9a77bdff936b52afb36d4fe4bcdd");

    let block_metadata = BlockMetadata::default();

    let inputs = GenerationInputs {
        signed_txns: vec![txn.to_vec()],
        tries: tries_before,
        contract_code: HashMap::new(),
        block_metadata,
    };

    let mut timing = TimingTree::new("prove", log::Level::Debug);

    // ZKのprove(証明)をここでやっています。EVMが正しい挙動をしているという証明をしています。
    let proof = prove::<F, C, D>(&all_stark, &config, inputs, &mut timing)?;
    timing.filter(Duration::from_millis(100)).print();

    // txの後で期待する動作を定義しています。
    let expected_state_trie_after = {
        // 送金したので、残高が減っている
        let sender_account_after = AccountRlp {
            balance: sender_account_before.balance - value, // TODO: Also subtract gas_used * price. まだガスプライスの計算は行なっていないようでうs。
            // nonce: sender_account_before.nonce + 1, // TODO: まだnonceがうまく動いていないようでうs。
            ..sender_account_before
        };
        let to_account_after = AccountRlp {
            balance: value,
            ..AccountRlp::default()
        };

        let mut children = std::array::from_fn(|_| PartialTrie::Empty.into());
        children[sender_nibbles.get_nibble(0) as usize] = PartialTrie::Leaf {
            nibbles: sender_nibbles.truncate_n_nibbles_front(1),
            value: rlp::encode(&sender_account_after).to_vec(),
        }
        .into();
        children[to_nibbles.get_nibble(0) as usize] = PartialTrie::Leaf {
            nibbles: to_nibbles.truncate_n_nibbles_front(1),
            value: rlp::encode(&to_account_after).to_vec(),
        }
        .into();
        PartialTrie::Branch {
            children,
            value: vec![],
        }
    };

    // ZK Proofのstate rootと素で計算した送金後のステートルートを比較する
    assert_eq!(
        proof.public_values.trie_roots_after.state_root,
        expected_state_trie_after.calc_hash()
    );

    // proof(証拠)のverify(検証)もやっておく
    verify_proof(all_stark, proof, &config)
}

まとめ

駆け足でしたが、ざっくり証明の過程と証明について見れました。
Proveの中身を見ると大変なことになりそうですね。

明日は@namn1125さんです、お願いします！

no plan株式会社について

外部リンク・参考文献

no plan incテックブログ
no plan incテックブログPublication

Discussion