メインコンテンツへスキップ

オフラインデータの完全性のためのマークルプルーフ

ストレージ
上級
Ori Pomerantz
2021年12月30日
16 分の読書 minute read

はじめに

すべてのデータは、イーサリアムストレージに保存することが理想的です。このストレージは、数千ものコンピューターに保存され、非常に高い可用性(データは検閲されない)と完全性(データは不正に変更されない)を備えていますが、32バイトワードを保存するのに通常2万ガスがかかります。 執筆時点で、そのコストは$6.60に相当します。 1バイトごとに21セントかかるため、多くの用途には高すぎます。

この問題を解決するために、イーサリアムのエコシステムではデータを保存する多くの分散型の方法が開発されました。 通常、これらは可用性と価格のトレードオフを伴います。 しかしながら、一般に完全性は保証されます。

この記事では、ブロックチェーンにデータを保存することなくデータ完全性を確保する方法としてマークルプルーフ(opens in a new tab)を使用する方法を学びます。

仕組み

理論上、チェーン上にデータのハッシュだけを保存し、トランザクション内で必要なすべてのデータを送信することができます。 しかし、これでもまだ高すぎます。 1バイトのデータのトランザクションのコストは約16ガスで、現時点では0.5セントです。つまり、1キロバイトあたり約 $5になります。 1メガバイトでは $5000になり、データをハッシュ化するコストを差し引いても、多くの用途にはまだ高すぎます。

これを解決するには、異なるデータのサブセットを繰り返しハッシュ化します。そうすることで、データを送信する必要が無い場合は、ハッシュを送信するだけで済むようになります。 これを行うには、次のようなマークルツリーを使用します。このツリーは、それぞれのノードがその下のノードのハッシュとなるデータ構造を持ちます。

マークルツリー

チェーン上に保存する必要があるのは、ルートハッシュのみとなります。 特定の値を証明するには、ルートのハッシュを得るために、その値と結合させる必要があるハッシュをすべて提供します。 例えば、Cを証明するには、DH(A-B)H(E-H)を提供します。

Cの値の証明

実装

サンプルコードはこちらで入手できます(opens in a new tab)

オフチェーンコード

この記事では、オフチェーン計算にJavaScriptを使用します。 ほとんどの分散型アプリケーションには、JavaScriptのオフチェーンコンポーネントがあります。

マークルルートの作成

最初に、マークルルートをチェーンに提供する必要があります。

1const ethers = require("ethers")

ethersパッケージのハッシュ関数を使用します(opens in a new tab)

1// The raw data whose integrity we have to verify. The first two bytes a
2// are a user identifier, and the last two bytes the amount of tokens the
3// user owns at present.
4const dataArray = [
5 0x0bad0010, 0x60a70020, 0xbeef0030, 0xdead0040, 0xca110050, 0x0e660060,
6 0xface0070, 0xbad00080, 0x060d0091,
7]

各エントリを単一の256ビット整数にエンコードすると、JSONを使用した場合などよりも読みにくいコードになります。 しかし、これによりコントラクト内のデータを取得するための処理量が大幅に削減され、ガス代も大幅に削減されます。 チェーン上でJSONを読み取ることができますが(opens in a new tab)、回避できるのであれば避けるべきです。

1// The array of hash values, as BigInts
2const hashArray = dataArray

ここでは、256ビット値のデータで始めるので、処理は必要ありません。 文字列型のようなより複雑なデータ構造を使用する場合は、まずデータをハッシュ化してハッシュ配列を取得する必要があります。 これは、ユーザーが他のユーザーの情報を知っていても知らなくても構わないことを前提にしているためでもあります。 さもなければ、ユーザー1がユーザー0の値がわからないように、ユーザー2がユーザー3の値がわからないように、というようなハッシュ化をしなければならなくなります。

1// Convert between the string the hash function expects and the
2// BigInt we use everywhere else.
3const hash = (x) =>
4 BigInt(ethers.utils.keccak256("0x" + x.toString(16).padStart(64, 0)))

ethersのハッシュ関数は、0x60A7などの16進数のJavaScript文字列を受け取ることを想定しており、同じ構造の別の文字列で応答します。 ただし、コードの他の部分では、BigIntを使う方が簡単なため、16進数文字列に変換してから、もう一度BigIntに戻します。

1// ペアの対称ハッシュのため、順序が逆でも構いません。
2const pairHash = (a, b) => hash(hash(a) ^ hash(b))

この関数は対称(a xor(opens in a new tab) bのハッシュ)です。 そのため、マークルプルーフを確認するときに、計算された値の前と後のどちらにプルーフの値を配置すべきかについて考慮する必要はありません。 マークルプルーフの確認はオンチェーンで行われるので、必要な処理が少ないほど良いとされます。

警告: 暗号技術は見た目以上に難解です。 この記事の最初のバージョンでは、ハッシュ関数hash(a^b)を使用していました。 これは、好ましくない手法でした。abの正しい値を知っていれば、b' = a^b^a'を使用して目的のa'の値を証明できるからです。 この関数では、hash(a') ^ hash(b')が既知の値(ルートに向かう経路上の隣のブランチ)と等しくなるようにb'を計算する必要があり、これは非常に困難です。

1// The value to denote that a certain branch is empty, doesn't
2// have a value
3const empty = 0n

値の数が2の整数乗ではない時は、空のブランチを処理する必要があります。 このプログラムでは、ゼロをプレースホルダーとして配置する方法を使っています。

ブランチが欠けているマークルツリー

1// Calculate one level up the tree of a hash array by taking the hash of
2// each pair in sequence
3const oneLevelUp = (inputArray) => {
4 var result = []
5 var inp = [...inputArray] // To avoid over writing the input // Add an empty value if necessary (we need all the leaves to be // paired)
6
7 if (inp.length % 2 === 1) inp.push(empty)
8
9 for (var i = 0; i < inp.length; i += 2)
10 result.push(pairHash(inp[i], inp[i + 1]))
11
12 return result
13} // oneLevelUp
すべて表示

この関数は、現在のレイヤーで値のペアをハッシュ化すると、マークルツリーを1レベル「登り」ます。 これは効率性を追求した実装ではないことに留意してください。入力のコピーを避け、ループ内で適切なタイミングで単にhashEmptyを加えることもできますが、このコードは読みやすさを重視して最適化されています。

1const getMerkleRoot = (inputArray) => {
2 var result
3
4 result = [...inputArray] // Climb up the tree until there is only one value, that is the // root. // // If a layer has an odd number of entries the // code in oneLevelUp adds an empty value, so if we have, for example, // 10 leaves we'll have 5 branches in the second layer, 3 // branches in the third, 2 in the fourth and the root is the fifth
5
6 while (result.length > 1) result = oneLevelUp(result)
7
8 return result[0]
9}
すべて表示

ルートを得るには、残っている値が1つしかないところまで登ります。

マークルプルーフの作成

マークルプルーフは、マークルルートを得るために、証明される値と一緒にハッシュ化する値です。 証明する値は、他のデータから入手することが多いため、コードの一部としてではなく、別に提供することをお勧めします。

1// A merkle proof consists of the value of the list of entries to
2// hash with. Because we use a symmetrical hash function, we don't
3// need the item's location to verify the proof, only to create it
4const getMerkleProof = (inputArray, n) => {
5    var result = [], currentLayer = [...inputArray], currentN = n
6
7    // Until we reach the top
8    while (currentLayer.length > 1) {
9        // No odd length layers
10        if (currentLayer.length % 2)
11            currentLayer.push(empty)
12
13        result.push(currentN % 2
14               // If currentN is odd, add with the value before it to the proof
15            ? currentLayer[currentN-1]
16               // If it is even, add the value after it
17            : currentLayer[currentN+1])
18
すべて表示

ハッシュ化は、(v[0],v[1])(v[2],v[3])のように行っていきます。 したがって、偶数の値の場合はその次の値、基数の値の場合は1つ前の値が必要です。

1        // Move to the next layer up
2        currentN = Math.floor(currentN/2)
3        currentLayer = oneLevelUp(currentLayer)
4    }   // while currentLayer.length > 1
5
6    return result
7}   // getMerkleProof

オンチェーンコード

最後は、証明を確認するコードです。 オンチェーンコードは、Solidity(opens in a new tab)で書かれています。 ガス代が比較的高価なため、ここでは最適化がかなり重要になります。

1//SPDX-License-Identifier: Public Domain
2pragma solidity ^0.8.0;
3
4import "hardhat/console.sol";
コピー

コードの作成には、Hardhat開発環境(opens in a new tab)を使用しました。この環境では、開発している間もSolidityからコンソール出力(opens in a new tab)を得ることができます。

1
2contract MerkleProof {
3    uint merkleRoot;
4
5    function getRoot() public view returns (uint) {
6      return merkleRoot;
7    }
8
9    // Extremely insecure, in production code access to
10    // this function MUST BE strictly limited, probably to an
11    // owner
12    function setRoot(uint _merkleRoot) external {
13      merkleRoot = _merkleRoot;
14    }   // setRoot
すべて表示
コピー

マークルルート用のset関数とget関数が書かれています。 プロダクションシステムにおいて、誰でもマークルルートを更新できるようにすることは、非常に好ましくない手法です。 ここでは、サンプルコードをシンプルにするために、あえて行っています。 データの完全性が重要なシステムでは、行わないでください

1    function hash(uint _a) internal pure returns(uint) {
2      return uint(keccak256(abi.encode(_a)));
3    }
4
5    function pairHash(uint _a, uint _b) internal pure returns(uint) {
6      return hash(hash(_a) ^ hash(_b));
7    }
コピー

この関数は、ペアのハッシュを生成します。 JavaScripコードのhashpairHashをSolidityコードに変換したものです。

注: これも読みやすさを重視して最適化されています。 関数定義(opens in a new tab)によると、データをbytes32(opens in a new tab)の値として保存することで、変換を回避できる場合があります。

1    // Verify a Merkle proof
2    function verifyProof(uint _value, uint[] calldata _proof)
3        public view returns (bool) {
4      uint temp = _value;
5      uint i;
6
7      for(i=0; i<_proof.length; i++) {
8        temp = pairHash(temp, _proof[i]);
9      }
10
11      return temp == merkleRoot;
12    }
13
14}  // MarkleProof
すべて表示
コピー

数学的表記では、マークルプルーフの検証は次のようになります。 H(proof_n, H(proof_n-1, H(proof_n-2, .. H(proof_1, H(proof_0, value))...))). これをこのコードで実装しています。

マークルプルーフとロールアップを混在させない

マークルプルーフは、ロールアップでは、うまく機能しません。 ロールアップでは、すべてのトランザクションデータはL1(レイヤー1)に書き込まれ、処理はL2(レイヤー2)で行われるためです。 マークルプルーフをトランザクションで送信するのにかかるコストは、1レイヤーあたり平均638ガスです(現在のコールデータ1バイトは、ゼロでなければ16ガス、ゼロであれば4ガスかかります)。 1024ワードのデータがある場合、マークルプルーフには10レイヤー、つまり合計で6380ガスが必要になります。

Optimism(opens in a new tab)の例を見ると、L1への書き込みには約100gweiのガス代がかかり、L2では0.001gweiのガス代がかかります(これは通常の価格であり、混雑とともに上昇する可能性があります) 。 したがって、L1の1回分のガス代で、L2では10万ガスを処理に使えることになります。 ストレージを上書きしないと仮定すると、L1の1回のガス代でL2のストレージに約5ワード書き込めるということになります。 単一のマークルプルーフの場合、1024ワードすべてをストレージに書き込むことができ(トランザクションで提供されるのではなく、最初からチェーン上で計算できると仮定した場合)、依然としてほとんどのガスが残ります。

まとめ

実際に、マークルツリーを自身で実装することはないかもしれません。 よく知られている監査済みのライブラリを使用できるため、基本的には独自の暗号論的プリミティブを実装しないことをお勧めします。 しかし、マークルプルーフをよく理解し、使いどころを判断できるようになっていただければと思います。

マークルプルーフは、完全性を保持しますが、可用性は保持しないことに注意してください。 データストレージにアクセスを拒否され、データストレージにアクセスするためのマークルツリーを構築することもできない場合でも、誰も自分の資産を奪うことはできないということを知っていると、ささやかな慰めとなります。 この特性により、マークルツリーは、IPFSなどの分散型ストレージで最もよく使用されています。

最終編集者: @nhsz(opens in a new tab), 2023年8月15日

このチュートリアルは役に立ちましたか?