ブロックチェーン技術ブログ

ブロックチェーンと英語、数学に関するブログ

Ethereum入門1 <アカウント、トランザクション、ブロック、ガス>

ブロックチェーン Ethereum

Ethereumは、Bitcoinと同様に仮想通貨の一種です.
仮想通貨とは、ブロックチェーンの分散台帳に記録された交換可能な電子データです.

仮想通貨は、仲介業者を介することなく、当事者間で送金や商品の売買をおこなうことができます.
また、特定の団体が中央主権的に管理するのはではなく、各団体・個人が分散してノードを動かすことで管理しています.

Ethereum

Ethereumは、トランザクションによって状態を更新するステートマシンです.
アカウントや残高を保持するだけでなく、ステートを更新するコントラクトコードの実行をおこなうことが可能です.

Ethereumでは、トランザクションを実行するのにガスと呼ばれる手数料を支払う必要があります.
これは、不正なコードあるいは不備のあるコードがEVMのネットワークを浪費するのを防ぐためです.

コンセンサスメカニズムには、Proof of Stakeを採用しています.
仮想通貨をブロックチェーン上で管理するためには、全てのノードが同一のブロックチェーンに同意している必要があります.
ブロックチェーンに新たにブロックを追加するときのルールを定めたものがコンセンサスメカニズムです.

Ethereumは、コンセンサスメカニズムにProof of Work(PoW)を使用していましたが、2020年12月1日からProof of Stake(PoS)を採用しています.

PoSは、各バリデータがEther(Ethereum上の通貨)をステーク(賭け金)として、ブロックの検証や新たなブロックの作成をおこないます.
バリデータは、ブロックを検証・作成することによって、報酬を得ることができます.
しかし、バリデータが不正な行動をとったもしくはブロックの作成時にオフラインであった場合、ステークの全部あるいは一部を消失します.

Ether (ETH)

Ethereum上の通貨が Ether です.

また、wei や gwei といった単位が使われます.
1wei = 10^{-18} ETH
1gwei = 10^{-9} ETH ※グウェイと呼ばれます

アカウント

Ethereumには、外部アカウント(Externally-owned Account)とコントラクトアカウント(Contract Account)の２種類があります.

外部アカウントは、秘密鍵を持つ人によって管理されているアカウントです.
コントラクトアカウントは、EVMにデプロイされた送金などの様々なアクションをおこなうコードのアカウントです.

  • 外部アカウント・コントラクトアカウント 共通

    • ETHの保持・送金が可能

  • 外部アカウント

  • コントラクトアカウント

    • 作成(デプロイ)するのに、ガスを消費する
    • 外部コントラクトから呼び出されて、コントラクトコードを実行する
    • アドレスは、コントラクトアカウントを作成した人のアドレスとnonce(トランザクションに含まれるカウンター)から生成される

トランザクション

トランザクションは、外部アカウントによって送信されます.
また、EVM上でトランザクションを実行するのに、ガスを消費します.

トランザクションには、以下の３種類があります.

ガス

ガスは、Ethereum上でトランザクションを実行するに必要な計算量の単位です.
ガスが大きければ大きいほど、トランザクションの実行に必要な計算量が多くなります.

単純な送金の場合、gas limitは 21,000です.

トランザクションの実行に必要な手数料(ETH)は、以下の式で計算されます.
gas limit * (base fee + priority fee)

パラメータ名 説明
base fee 1ガスあたりの最低価格
priority fee 1ガスあたりのマイナーへのチップ
max fee 手数料の上限 (base fee + priority feeを含めた値)

max fee を設定することで、ブロックを作成するまでbase feeがわからないことによって、もしくはコントラクコードの無限ループ等によって、指定した値より多くの手数料を払うことを避けることができます.
(base feeは、直前のブロックのガスの合計と新しく追加するブロックのガスの合計の割合によって決まるので、トランザクション送信時に正確な金額がわからない)

例) アリスがボブに1ETHを送金する (この時 base fee: 20 gwei, priority fee: 3 gwei)

単純な送金であるため、gas limitは21,000です.

21,000 * (20 + 3) = 483,000 gwei (0.000483 ETH)

アリスのアカウントから、1.000483 ETH が差し引かれます.
ボブのアカウントに、1 ETH が送金されます.

21,000 * 20 = 42,000 gwei (0.00042 ETH) が消失します. 21,000 * 3 = 6,300 gwei (0.000062 ETH) がマイナーにチップとして支払われます.

ブロック

ブロックは、複数のトランザクションをまとめたものです.
ブロックを順に繋いでいくことで、ブロックチェーンを構成します.

また、ブロックは、直前のブロックのハッシュ値を含んでいます.
Ethereumでは、ブロックチェーンのデータ構造に、マークルパトリシアツリーを利用し、ブロックやトランザクションの改ざんを検知できるようにしています.

ブロック追加の流れ

  1. バリデータの中から、ブロックを作成する人(プロポーザー)がランダムに選ばれる
  2. プロポーザーがトランザクションを任意の並び順で選択して、まとめる
  3. まとめたトランザクションを順に実行してコミットして、ステートを更新する
  4. トランザクションと更新されたステートをまとめてブロックを作成する
  5. 他のバリデータがブロックのトランザクションを実行して、検証する
  6. 検証に成功した場合、ブロックチェーンに追加する

ブロックに含まれるトランザクションのガス使用量の合計をブロックサイズと呼びます.

ブロックサイズには、上限がありその数は 3 * 10^{7} ガス です.
ブロックサイズが大きすぎる場合、ブロック内のトランザクションを実行するのに必要な計算リソースが大きくなり、一部のバリデータのみ実行可能となってしまいます.

デジタル署名 < ECDSA署名 >

ブロックチェーン 暗号技術 数学

デジタル署名は、"ある人がデータを作成したこと"あるいは"あるデータに同意したこと"を保証する仕組みです.
ブロックチェーンでは、トランザクションが送信者本人によって作成されたものであることを示すために利用されます.

デジタル署名には、公開鍵暗号の技術が応用されています.

デジタル署名は、鍵生成、署名、検証の3つのアルゴリズムからなります.

  1. 鍵生成
    デジタル署名では、公開鍵暗号技術を利用した署名鍵(秘密鍵)と検証鍵(公開鍵)のペアを利用します.
    事前に、署名鍵と検証鍵のペアを作成しておきます.

  2. 署名
    署名者が署名対象のメッセージと自身の署名鍵から、デジタル署名を生成します.

  3. 検証
    署名者の検証鍵を用いて、署名対象のメッセージとデジタル署名から、検証をおこないます.
    正しい署名の場合、検証に成功します.

デジタル署名の図

　署名者　　　　　　　　　　　　　　　　 検証者

メッセージ　　　　　　→　　　　　　　　メッセージ
　　↓　　　　　　　　　　　　　　　　　　　↓
  署名　　→　　デジタル署名　　→　検証 (署名者の検証鍵を使用)　
(自身の署名鍵を使用)　　 　　　　　　　　↓
　　　　　　　　　　　　　　　　　　　成功 or 失敗

署名のサイズは、メッセージのサイズによらず一定です.
また、暗号と異なり、署名からメッセージを計算することはできません.

楕円曲線

楕円曲線について簡単にみていきましょう.

楕円曲線Eは、y^{2}=x^{3}+ax+b を満たす、3次曲線です.
体として有限体 F_p が用いられます.

楕円曲線上の点G(ベースポイント)に対して、加法を定義できます.
このときに、G + G + ... + G = nG = O となる、nが存在します.
また、n が G の位数となります.

楕円曲線暗号では、nG から n を求めるのが困難であるという仮定を利用します.

ECDSA署名

ECDSAは、楕円曲線を利用した署名アルゴリズムです.
BitcoinやEthereumでも使用されています.

事前に以下の情報を共有しておきます.

パラメータ 説明
a, b 楕円曲線の係数
p 有限体F_pの素数
Gx, Gy ベースポイントのx座標, y座標
n Gの位数

鍵生成

Q = dG を計算して、署名鍵と検証鍵を生成します.
署名鍵: d
検証鍵: G

署名

  1. \lbrack 1, n-1 \rbrack の乱数kを選ぶ
  2. kG = (x_1, y_1)から、r = x_1\pmod n を計算します
    r = 0 の場合、乱数を取り直して、再度 r を計算します
  3. e = Hash(m)
  4. s = k^{-1} (e+dr)\pmod n を計算する
  5. (r, s) がmに対する署名となる

検証

  1. r, s が \lbrack 1, n-1 \rbrackの範囲でなければ、失敗とする
  2. e = Hash(m)
  3. w = s^{-1}\pmod n
  4. u_1=ew\pmod n, u_2=rw\pmod n を計算する
  5. u_1G + u_2Q = X = (x_1, y_1)
  6. v = x_1 \pmod n
  7. v = r の場合、署名の検証に成功

公開鍵暗号 < RSA暗号 >

ブロックチェーン 暗号技術 数学

公開鍵暗号では、暗号化と復号で異なる鍵を使います.
また、事前に鍵を共有する必要がなく、公開鍵は他のユーザが見えるようにしておきます.
秘密鍵のみ漏洩しないように管理する必要があります.

ブロックチェーンで使用するディジタル署名でも、公開鍵暗号の仕組みが利用されています.

暗号は、トラップドア付きの一方向関数です.
暗号文から平文を計算するのは困難ですが、鍵を利用することで暗号文から平文を計算することができます.

公開鍵暗号の暗号化・復号化の図

　　暗号化 (公開鍵を使用)
平文　⇄　暗号文
　　 復号 (秘密鍵を使用)

公開鍵暗号には以下の性質が求められます

  • 強秘匿性
    暗号文から平文の情報を一部でも得ることが困難である性質.

  • 識別不可能性
    二つの平文とどちらかの暗号文が与えられたときに、それがどちらの平文の暗号文であるか特定が困難である性質.

  • 頑強性
    ある平文と暗号文のペアと別の平文と暗号文のペアに何の関係もない性質.
    平文と暗号文のペアが与えられて、その平文の一部を変えた場合、暗号文が予測できないものでなければいけません.

RSA暗号

RSA暗号は、巨大な素数の素因数分解が困難である性質を利用した暗号です.

暗号化・復号に以下のパラメータを利用します.

事前に2素数 p, q を用意し、暗号化・復号に使用するパラメータをそれぞれ以下とします.
n = pq
L を p-1 と q-1 の最小公倍数
e を L と互いに素な数
d を ed ≡ 1 (mod L) を満たす数

また、公開鍵、秘密鍵を以下のように定義します.
公開鍵: e, n
秘密鍵: d

暗号化、復号はそれぞれ以下の手順でおこないます.
m を 平文とします.

暗号化 c= m^{e}\pmod n

復号 m= c^{d}\pmod n

実際に p, q, e, d に値を割り当てて、確認してみましょう.
p = 5
q = 11
n = 55
L = (5 - 1) * (11 - 1) = 40
e = 3
d = 27 ( 3 * 27 ≡ 1 (mod 40) )

メッセージ m = 4 とします.

c=4^{3}\pmod {55} = 9

m=9^{27}\pmod {55} = 4

暗号文(c=9) が 平文(m=4) に復号されたことが確認できます.

指数が大き場合は、中国剰余定理とラグランジュの定理を使用して、以下のように計算できます.
3^{54}\pmod {5} = 3^{52} * 3^{2} \pmod{5} = 9 \pmod{5} = 4
3^{54}\pmod {11} = 3^{50} * 3^{4} \pmod{11} = 81 \pmod{11} = 4

↑ 9^{27} = 3^{54} を使用し式を簡略化した

したがって、 9^{27}\pmod {55} = 4
(5で割ったときに余りが4になり、11で割ったときに余りが4になる、55より小さな整数は4)

暗号学的ハッシュ関数 < SHA-2, SHA3 >

ブロックチェーン

暗号学的ハッシュ関数は、任意のメッセージ(入力値)に対して、固定長の数値を生成します.
メッセージに識別子を付与することで、メッセージの認証等に利用されます.

例) SHA-1 を使用したハッシュ値

  1. 入力値が abc
    => a9993e364706816aba3e25717850c26c9cd0d89d

  2. 入力値が 01234567890123456789012345678901234567890123456789
    => 9578f951955d37f20b601c26591e260c1e5389bf

SHA1は、20バイト(数値40桁)のハッシュ値を生成します.
メッセージが3文字の場合と40文字の場合で、ハッシュ値の長さが同じになっていることがわかります.

暗号学的ハッシュ関数には、以下の性質が求められます.

  • 現像困難性
    ハッシュ値から現像(入力値のメッセージ)を求めることが困難である性質.

  • 第二現像困難性
    あるメッセージに対して、ハッシュ値が一致するメッセージを見つけることが困難である性質.

  • 衝突困難性
    ハッシュ値が一致するメッセージの組を見つけることが困難である性質.
    第二現像困難性との違いは、特定のメッセージに対してだけでなく、任意のメッセージに対して、ハッシュ値の一致が困難である必要があります.

SHA-2

SHA-2は、ハッシュ値の長さを224、256、384、512から選ぶことができます.

SHA256では、入力データを512ビットごとのブロックに分割して、全体が512ビットの倍数になるようにパディングします.
8個の32ビットの整数からなる内部状態を準備しておきます.

圧縮関数を利用して、先頭のブロックと内部状態を混ぜ合わせて、内部状態を更新します.
2番目以降のブロックに対して、更新された内部状態と混ぜ合わせる処理を順番に繰り返します.
最終的な内部状態をハッシュ値として出力します.

このハッシュの構成を MD(マークル・ダンガード)構造といいます.

SHA-3

SHA-2と同様、ハッシュ値の長さを224、256、384、512から選ぶことができます.

SHA-3-256では、入力データを1088ビットのブロックに分割します.
全体が1088の倍数になるように、余りのブロックにパディングします.
先頭のブロックから内部状態を生成し、その値に対して置換関数を適用し、内部状態を更新します.
2番目以降のブロックに対して、置換関数を適用し、内部状態を順に更新します.
最終的な内部状態の先頭256ビットを適用したものがハッシュ値となります.

大きな内部状態にブロックを取り込むことから、このハッシュの構成法はスポンジ構造といいます.

また、EthereumではSHA-3のオリジナルである Keccak が使用されています.

ブロックチェーンのデータ構造 < マークルツリーとマークルパトリシアツリー >

ブロックチェーン データ構造

BitcoinやEthereumといった仮想通貨では、ブロックチェーンのデータを複数のノードで分散管理をしています.
その際に、ブロックチェーンの改ざんを検知できるように、データを保持する必要があります.

Bitcoin、Ethereumではそれぞれマークルツリー、マークルパトリシアツリーを利用してデータを管理しています.

マークルツリー、マークルパトリシアツリーを順番にみていきましょう.

マークルツリー

マークルツリーでは、まず各リーフノードのハッシュを取得します.
2組のハッシュ値を結合したものを次のハッシュの入力値とする操作を繰り返して、最終的に1つのルートハッシュを出力します.

マークルツリーは、データが正しさ(改ざんされていないこと)を検証する用途で利用されます.
もし、データの一部が改ざんされていた場合、ルートハッシュが異なる値となります.

https://upload.wikimedia.org/wikipedia/commons/9/95/Hash_Tree.svg Merkle tree - Wikipedia から引用

上の図で、L1のデータがマークルツリーに含まれることを検証してみましょう。
まず L1 のハッシュを Hash 0-0 と比較します.
次に Hash 0-0 と Hash 0-1 を結合した文字列のハッシュ を Hash 0 と比較して検証します.
最後に、 Hash 0 と Hash 1 を結合した値のハッシュ を ルートハッシュ(Top Hash) と比較して検証します. 全てのノードのハッシュを再計算することなく、効率的にデータの検証がおこなえます.

マークルパトリシアツリーの前に、トライ木とパトリシア木をみてみましょう.

トライ

複数の文字列を保持するツリー構造です.
文字列がルートノードからのパスになっています.

https://upload.wikimedia.org/wikipedia/commons/b/be/Trie_example.svg

Trie - Wikipedia から引用

上の図で、文字列 "to" を検索してみましょう.
ルートノードから "t" のパスを辿って、t のノードに到達する.
t のノードから "o" のパスを辿って、to のノードに到達する.

トライはシンプルなデータ構造です.
ただし、文字列の長さだけノードが必要になるという欠点があります.
そのため、文字列の検索、追加、更新のパフォーマンスが良くありません.

より効率的にキーを保持できるようにしたのが、次に紹介するパトリシアツリーです.

パトリシアツリー

パトリシアツリーでは、複数の文字列で共通するパスの部分を1つのノードで保持するようにしました.
また、リーフノードで、パスを複数文字保持できます.

例) "leaf" と "leave" を保持する
トライの場合、root, l, e, a, f, v, e のノード必要になります.
パトリシアツリーの場合、共通文字列 "lea" と 残りの文字列 "f", "ve" の3つのノードだけで済みます.

root
|
lea
/ \
f ve

https://upload.wikimedia.org/wikipedia/commons/a/ae/Patricia_trie.svg

Radix tree - Wikipedia から引用

Ethereum は、複数のトランザクションからブロックを作成した後に、順にトランザクションを実行して状態を更新していきます.
そのため、マークルツリーのデータの改ざんを検知するのに加えて、データの更新に適したデータ構造が必要です.

マークルパトリシアツリー

マークルパトリシアツリーは、マークルツリーのデータの改ざんを検知する機能とパトリシアツリーのデータを効率よく検索、追加、更新する機能を持ったデータ構造です.

各ノードがそれぞれハッシュ値を持ち、ルートノードのハッシュが一意に定まります.

マークルパトリシアツリーは、以下のノードからなります.

ノードの種類 説明
NULL 空文字を表す
ブランチ [1 2 3 ... e f バリュー] の形式で、1~fの数字とバリューの計17種類の要素からなる
1 ~ f には参照先のノードのハッシュが入る
リーフ [パス バリュー] の形式
エクステンション [パス 参照先のノードのハッシュ] の形式
パスの共通部分を集約する

※ 今回はわかりやすさを優先して、キーのハッシュ処理やバリューのエンコード処理、パスの先頭にフラグをつける処理等を省略しました.

以下のキー・バリューのペアを順番に追加する例をみてみましょう.

キー バリュー
1020 One
820 Two
10251 Three
102 Four

まず、[1020, One] を追加します.

ルートノードの直下に、Hash1のノードが追加されました.
下の表で、左の列がハッシュ値で、右の列がハッシュの入力値となります.
Hash1 は、[1020, One] を入力値としたハッシュです.
Root は、Hash1 を入力値としたハッシュです.

Root Hash1
Hash1 [1020, One]

次に、[820, Two] を追加します.

ルートノードからの分岐が2パターン(1と8)あるので、ブランチノードを追加します.
Hash1 だったノードは、Hash4 が親になり、パスが 020 となります.
Root は、ハッシュの入力値が Hash4 に更新されました.
このように、ノードの追加によって、ルートハッシュが更新されていきます.

Root Hash4
Hash4 [N, Hash2, N, N, N, N, N, N, Hash3, N, N, N, N, N, N, N, N]
Hash3 [20, Two]
Hash2 [020, One]

続いて、(10251, Three) を追加します.

ここで、キー 10251 を検索してみましょう.
まずは、Root から Hash9 へ移動します.
キーの先頭文字は 1 なので、Hash8 に移動します.
Hash8 はブランチノードなので分岐することなく、Hash7に移動します.
ここまで、102 のパスを辿ってきたので、残りパスの 51 です.
5 のパスから Hash6 に移動します.
末尾の文字の 1 をパスに持ち、リーフノードである Hash6 に到達することができました.

Root Hash9
Hash9 [N, Hash8, N, N, N, N, N, N, Hash3, N, N, N, N, N, N, N, N]
Hash8 [02, Hash7]
Hash7 [Hash5, N, N, N, N, Hash6, N, N,N, N, N, N, N, N, N, N, N]
Hash6 [1, Three]
Hash5 [, One]
Hash3 [20, Two]

最後に、(102, Four) を追加します.

直前に Hash7 であったのノードの V のところに Four が追加されました.
それにより、Root のハッシュが更新されました.
また、Hash3, Hash5, Hash6 はそのままです.
マークルパトリシアツリーでは、ノードのデータによってルートハッシュを一意に出力すると同時に、効率的なノードの検索、追加、更新を可能にします.

Root Hash12
Hash12 [N, Hash11, N, N, N, N, N, N, Hash3, N, N, N, N, N, N, N, N]
Hash11 [02, Hash10]
Hash10 [Hash5, N, N, N, N, Hash6, N, N,N, N, N, N, N, N, N, N, Four]
Hash6 [1, Three]
Hash5 [, One]
Hash3 [20, Two]

以下のリンクから、Ethereumでの厳密なマークルパトシアツリーを確認できます.

ethereum.org