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

ストレージ

上級

Ori Pomerantz

2021年12月30日

17 分の読書

はじめに

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

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

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

仕組み

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

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

(opens in a new tab)

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

(opens in a new tab)

実装

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

オフチェーンコード

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

マークルルートの作成

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

1const ethers = require("ethers")
2

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]
8

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

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

ここでは、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)))
5

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

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

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

警告: 暗号技術は見た目以上に難解です。 この記事の最初のバージョンでは、ハッシュ関数hash(a^b)を使用していました。 これは、好ましくない手法でした。aとbの正しい値を知っていれば、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
4

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

(opens in a new tab)

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
14
すべて表示

この関数は、現在のレイヤーで値のペアをハッシュ化すると、マークルツリーを 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}
10
すべて表示

ルートを得るには、残っている値が 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
19
すべて表示

ハッシュ化は、(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
8

オンチェーンコード

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

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

コードの作成には、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
15
すべて表示
 コピー

マークルルート用の 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    }
8
 コピー

この関数は、ペアのハッシュを生成します。 JavaScrip コードのhashとpairHashを 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
15
すべて表示
 コピー

数学的表記では、マークルプルーフの検証は次のようになります。 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 などの分散型ストレージで最もよく使用されています。