Rubyでブロックチェーンを実装してみる

Bitcoinの技術的な入門書として有名な本はおそらくMastering Bitcoinでしょう。Bitcoinライクなブロックチェーンの技術的な解説が非常に詳しくされており、ブロックチェーンを学ぶ人にとってはもはや登竜門的な本になっています。

しかし、Mastering Bitcoinを読んでも実際にブロックチェーンそのものを実装することはありません。ブロックチェーンを学ぶ者として、「1度くらい実装した方がいいよな〜」と思っていました。
そんな時に以下の記事を見つけました。

- [Swiftでブロックチェーンを実装してみる](https://qiita.com/shu223/items/ebe59325f36fbf25e3d6#fn1)

この記事はPythonで実装された記事[^1]に触発されて、Swiftでブロックチェーンを実装してみたとのことだったので、私は、Swiftではなく、Rubyで書いてみることにしました。
[^1]: [ブロックチェーンを作ることで学ぶ 〜ブロックチェーンがどのように動いているのか学ぶ最速の方法は作ってみることだ〜](https://qiita.com/hidehiro98/items/841ece65d896aeaa8a2a)
（上記の記事を参考に、自分なりにアレンジしながら実装してみました）

## 1. ブロックチェーンを作る

### ブロックチェーンを書く
まずは、雛形となるBlockchainを定義します。

```ruby:block_chain.rb
class BlockChain

  def initialize
    # ブロックチェーンを納めるための最初の空のリスト
    @blocks = []
    # ジェネシス・ブロックをブロックチェーンの最初に追加する
    @blocks << BlockChain.get_genesis_block()
  end

  # ブロックチェーンの最後のブロックを返す
  def last_block
  end

  # 新しいブロックを作る
  def next_block transactions
  end

  # 作ったブロックをチェーンに追加する
  def add_block new_block
  end

  def get_genesis_block
    Block.create_genesis_block
  end
end
```
ジェネシス・ブロックはブロックチェーンを初期化するときに生成することにする。

### トランザクションの雛形を定義する

```ruby:transaction.rb
require_relative 'transaction_input'
require_relative 'transaction_output'

class Transaction
  attr_reader :tx_id, :inputs, :outputs

  def initialize args
    @inputs = args[:inputs]
    @outputs = args[:outputs]
    @tx_id = args[:tx_id]

  end

  # create coinbase transaction
  def self.new_coinbase_transaction
  end
end
```
今回は、通常のトランザクションはクラスの初期化で生成し、マイニング報酬やジェネシス・ブロック生成時のトランザクションはnew_coinbase_transactionメソッドとして定義しました。
（本来であれば、transactionとは別に複数のトランザクションをまとめたtransactions = []という配列を用意して、そこにtransactionをappendしていくべきだと思いますが、今回は1ブロックに対して、1トランザクションとしました。）

また、今後UTXO形式のトランザクションを実装することを想定し、inputとoutputは別ファイルで定義します。

```ruby:transaction_input.rb
class Input
  attr_reader :tx_id, :v_out, :script_sig

  def initialize args
    # tx_id: 前の出力の参照
    # v_out: トランザクション内の出力のインデックスを格納
    # script_sig: ScriptPubKeyで使われるデータを提供するスクリプト（今は任意のユーザのアドレス）
    @tx_id = args[:tx_id]
    @v_out = args[:v_out]
    @script_sig = args[:script_sig]
  end
end
```

```ruby:transaction_output.rb
class Output
  attr_reader :value, :script_pubkey

  def initialize args
    @value = args[:value]
    @script_pubkey = args[:script_pubkey]
  end
end
```

### ブロックとはどのようなものか

```ruby:block.rb
class Block
  attr_reader :hash, :height, :transactions, :timestamp, :nonce, :previous_hash

  def initialize args
    @hash = args[:hash]
    @height = args[:height]
    # TODO: merkle root
    @transactions = args[:transactions]
    @timestamp = args[:timestamp]
    @nonce = args[:nonce]
    @previous_hash = args[:previous_hash]
  end

  # ジェネシス・ブロックを作成する
  def create_genesis_block
  end
end
```
これを自分で実際に書いてからMastering Bitcoinを読むとブロックの構造が非常に分かりやすいです。

### 新しいブロックを作る

```ruby:block_chain.rb
  def next_block transactions
    height = last_block.height + 1
    timestamp = Time.now.to_i
    previous_hash = last_block.hash
    # TODO: transactions → merkle_root
    pow = ProofOfWork.new(
      timestamp: timestamp,
      previous_hash: previous_hash,
      transactions: transactions)

    nonce, hash = pow.do_proof_of_work

    block = Block.new(
      hash: hash,
      height: height,
      transactions: transactions,
      timestamp: timestamp,
      nonce: nonce,
      previous_hash: previous_hash
    )
  end
```
nonceとblockのhashはProof of Workの結果から取得することにしています。
実際は、Proof of Workにmerkle rootのハッシュ値を使っていますが、今は簡略化して、transactionsを使うことにしています。

これに伴い、last_blockメソッドを実装します。

```ruby:block_chain.rb
  # ブロックチェーンの最後のブロックを返す
  def last_block
    @blocks.last
  end
```

ジェネシス・ブロックを生成するためのメソッドを実装します。

```ruby:block.rb
    # ジェネシス・ブロックを作成する
    def create_genesis_block
      address = "62e907b15cbf27d5425399ebf6f0fb50ebb88f18"
      timestamp = Time.parse("2009/1/3").to_i
      previous_hash = '0'
      genesis_coinbase_data = "The Times 03/Jan/2009 Chancellor on brink of second bailout for banks"
      transactions = [Transaction.new_coinbase_transaction(address, genesis_coinbase_data)]

      pow = ProofOfWork.new(
        timestamp: timestamp,
        previous_hash: previous_hash,
        transactions: transactions
      )

      nonce, hash = pow.do_proof_of_work
      Block.new(
        hash: hash,
        height: 0,
        transactions: transactions,
        timestamp: timestamp,
        nonce: nonce,
        previous_hash: previous_hash
      )
    end
```

続いて、new_coinbase_transactionメソッドを実装します。

```ruby:transaction.rb
  # create coinbase transaction
  def self.new_coinbase_transaction to, data
    # mining reward
    subsidy = 50
    if data == nil
      data = "Reward to #{to}"
    end

    tx_in = [Input.new(
    # tx_id = nil or "" ?
      tx_id: nil,
      v_out: -1,
      script_sig: data
    )]

    tx_out = [Output.new(
      value: subsidy,
      script_pubkey: to
    )]

    tx = Transaction.new(
      tx_id: calculate_hash_for_tx(tx_in, tx_out),
      inputs: tx_in,
      outputs: tx_out
    )
    tx
  end
```

トランザクションを生成するときにインプットとアウトプットからトランザクションのハッシュ値を計算するので、そのためのメソッドを実装します。ビットコインではSHA-256が使われています。

```ruby:transaction.rb
  def self.calculate_hash_for_tx tx_in, tx_out
    Digest::SHA256.hexdigest({
      tx_in: tx_in,
      tx_out: tx_out
    }.to_json)
  end
```
### Proof of Workを理解する

では、いよいよブロックのハッシュ値を決めるProof of Workについて見ていきます。
今回は以下のように実装してみました。

```ruby:proof_of_work.rb
class ProofOfWork
  attr_reader :timestamp, :transactions, :previous_hash

  def initialize args
    @timestamp = args[:timestamp]
    @transactions = args[:transactions]
    @previous_hash = args[:previous_hash]
  end

  def calc_hash_with_nonce(nonce=0)
    sha = Digest::SHA256.hexdigest({
      timestamp: @timestamp,
      transactions: @transactions,
      previous_hash: @previous_hash,
      nonce: nonce
    }.to_json)
    sha
  end

  # TODO: difficulty
  def do_proof_of_work(difficulty = '0000')
    nonce = 0

    loop do
      hash = calc_hash_with_nonce nonce
      if hash.start_with? difficulty
        return [nonce, hash]
      else
        nonce += 1
      end
    end
  end
end
```

かなり、簡略化してあると思います。
timestamp, transactions, previous_hashを使って、do_proof_of_workのメソッドを実行し、ハッシュ値を計算し、difficulty（今回は、先頭が0000で始まる）を満たすnonceを見つける計算をしています。

##2. マイナーはどうやってブロックを受け取るか
これで、最低限の実装はできました。しかし、今のままだと、ブロックに含まれているprevious_hashと一つ前のブロックのハッシュ値が等しいのかなどといったチェックがないままブロックが追加されてしまします。

そこで、minerクラスを用意して、生成したブロックを受け取ったマイナーがそのブロックが正しいものかを確認できるようにします。[^2]

[^2]: これ以降の実装は[Rubyでブロックチェーンを理解しよう!!](https://qiita.com/g_ryotaro/items/3b321309d0eea7d42bf2)を参考にさせていただきました。

```ruby:miner.rb
require 'openssl'
class Miner
  attr_reader :name, :block_chain
  def initialize args
    @name = args[:name]
    @rsa = OpenSSL::PKey::RSA.generate(2048)
    @block_chain = BlockChain.new
  end

  def accept receive_block_chain
  end

  def add_new_block
  end
end
```

acceptメソッドでブロックチェーンにブロックを追加/ブロックチェーンを受け入れるか判断し、add_new_blockでブロックを追加します。

新しいブロックの条件は以下の通りです。

* 前のブロックのindexの次のindexと等しい
* 前のブロックのhashは新しいブロックのprevious_hashと等しい
* hashの計算方法が誤ってないか確認
ブロックチェーンとして正しいか
* 最初のブロックから検証していき条件を満たすか確認していきます

まず、acceptメソッドから実装します。

```ruby:miner.rb
  def accept receive_block_chain
    puts "#{@name} checks received block chain. Size: #{@block_chain.size}"
    if receive_block_chain.size > @block_chain.size
      if BlockChain.is_valid_chain? receive_block_chain
        puts "#{@name} accepted received blockchain"
        @block_chain = receive_block_chain.clone
      else
        puts "Received blockchain invalid"
      end
    end
  end
```

最終的にBlockChainクラスのis_valid_chain?メソッドでチェックします。

```ruby:block_chain.rb
  def is_valid_new_block? new_block, previous_block
    if previous_block.height + 1 != new_block.height
      puts "invalid height"
      return false
    elsif previous_block.hash != new_block.previous_hash
      puts "invalid hash: previous hash"
      return false
    elsif calculate_hash_for_block(new_block) != new_block.hash
      puts "invalid hash: hash"
      puts calculate_hash_for_block(new_block)
      puts new_block.hash
      return false
    end
    true
  end

  def is_valid_chain? block_chain_to_validate
    return false if block_chain_to_validate.blocks[0] != BlockChain.get_genesis_block()
    tmp_blocks = [block_chain_to_validate.blocks[0]]
    block_chain_to_validate.blocks[1..-1].each.with_index(1) do |block, i|
      if block_chain_to_validate.is_valid_new_block?(block, tmp_blocks[i - 1])
        tmp_blocks << block
      else
        return false
      end
    end
  end
```

ブロックチェーンのサイズを取得するメソッドは以下の通りです。

```ruby:block_chain.rb
  def size
    @blocks.size
  end
```

これでブロックチェーンの実装は全て完成です！

##3. ブロックチェーンをシミュレーションする

main.rbを作成して、ブロックチェーンの動きをシミュレーションしてみます。

```ruby:main.rb
require_relative 'ruby_chain/block_chain'
require_relative 'ruby_chain/miner'

## blockchain simulator
$receive_block_chain = BlockChain.new

def create_miner args
  Thread.new {
    miner = Miner.new args
    3.times do
      sleep [1, 2, 3].sample
      miner.accept $receive_block_chain
      [1, 2, 3].sample.times.each do |i|
        miner.add_new_block
      end
      broadcast miner
    end
  }
end

def broadcast miner
  puts "#{miner.name} broadcasted"
  $receive_block_chain = miner.block_chain
end

puts "start"
th1 = create_miner name: "miner1"
th2 = create_miner name: "miner2"
th3 = create_miner name: "miner3"
[th1, th2, th3].each{|t| t.join}

puts "block chain result"

$receive_block_chain.blocks.each do |block|
  puts "*** Block #{block.height} ***"
  puts "hash: #{block.hash}"
  puts "previous_hash: #{block.previous_hash}"
  puts "timestamp: #{block.timestamp}"
  puts "transactions: #{block.transactions}"
  puts "nonce: #{block.nonce}"
  puts ""
end
```

実行結果

```
user1noMacBook-Pro:ruby_chain user1$ ruby main.rb 
start
miner3 checks received block chain. Size: 1
miner3 add new block: 000037f24bc12cb856d8d41931b58b756fcf4c311c8ac7f84a6b85e17566b0a9
miner2 checks received block chain. Size: 1
miner3 add new block: 0000479761a259652a83a9dfb9d468fa4fdd3b40ec4aed38354b5e927edf2fe3
miner3 broadcasted
miner3 checks received block chain. Size: 3
miner2 add new block: 0000af39e879aabf4a7394274b5efdee8ed595c7f76d4280aaeb4609cca4a493
miner1 checks received block chain. Size: 1
Received blockchain invalid
miner3 add new block: 0000b42d5ec726e5e0f06f2812e52508684edf0e8923c52ff724f2bd9d7c1620
miner3 broadcasted
miner3 checks received block chain. Size: 4
miner1 add new block: 0000e496e774622b0844c0bc9041e15996acc6cd52c02eba295b919a72ba9418
miner3 add new block: 000073c6a1c70faecacf8538f2eb2bd5efda918731e770c7217637e0b9dd473e
miner3 add new block: 00002b53565aa070a39300f599ac2b9025c26c7893590bc0de8dafca23990daa
miner3 add new block: 000026b13ee57295843aa44b9c55d1ed233c53b2c7046b1ff6041a4c9c3dbdf7
miner3 broadcasted
miner1 add new block: 0000a7b6096fca613f6fddc23d18e6361a78647000b1958e920007dba826c822
miner1 add new block: 00005147c6d5c9a4d0e7b45094ee87fb352f122f280ea50f405595fd46f6f9ae
miner1 broadcasted
miner2 add new block: 0000402cafbc8d15dc1749f8dcb72d8300ccf12721927113db08bd546685e0b0
miner2 add new block: 00000ea7e1edd5dd98076bd67a367c5c77fb448b586b6f2539cc529a2a63c626
miner2 broadcasted
miner1 checks received block chain. Size: 4
miner1 add new block: 00007d727a3f3a13fd45fbe6f7bd6ab6c35b532b6f54ec2032bbe02636a672a6
miner2 checks received block chain. Size: 4
miner2 add new block: 00003114a17f84578f6f03604dbcde0485c65db1b7e4c9361ece94b3c63fd29a
miner2 broadcasted
miner2 checks received block chain. Size: 5
miner2 add new block: 00005001d02cbe338406c8e977c94e7e1a3c5ae0cffeb5283fc1290acd029afc
miner2 broadcasted
miner1 add new block: 0000c224d520d8c3a7dbcf42208e2d5e32be24b63fa9bef00cbd30f0e778fa88
miner1 add new block: 00000d2cb16a232a3ff161f97e9061eecd708a70aa8f7e2f0b9bfdd1ce64f2e7
miner1 broadcasted
miner1 checks received block chain. Size: 7
miner1 add new block: 0000b891db7777ffc4145e31e1e3fd83fd8fa3fb20a215551f603ecfac6ab1ef
miner1 add new block: 00008d288b16b6759d75513e147129ca3a35de6ac6c4762d8e159a1e8f2e71f0
miner1 add new block: 0000f2b1a32b83471666848af759a313eba695ab9574f68be39b3874825b0846
miner1 broadcasted
block chain result
*** Block 0 ***
hash: 0000893344939a34a8039bf2e0b5b2e25553301c4b65e77a53f36590a423b354
previous_hash: 0
timestamp: 1230908400
transactions: [#<Transaction:0x007fae05861180 @inputs=[#<Input:0x007fae058615e0 @tx_id=nil, @v_out=-1, @script_sig="The Times 03/Jan/2009 Chancellor on brink of second bailout for banks">], @outputs=[#<Output:0x007fae05861568 @value=50, @script_pubkey="62e907b15cbf27d5425399ebf6f0fb50ebb88f18">], @tx_id="0daa08753fea5fc81dab845e8a358bc570faa49b0c77c28d9acc1d9607ad34ae">]
nonce: 7886

*** Block 1 ***
hash: 0000e496e774622b0844c0bc9041e15996acc6cd52c02eba295b919a72ba9418
previous_hash: 0000893344939a34a8039bf2e0b5b2e25553301c4b65e77a53f36590a423b354
timestamp: 1515663724
transactions: []
nonce: 80726

*** Block 2 ***
hash: 0000a7b6096fca613f6fddc23d18e6361a78647000b1958e920007dba826c822
previous_hash: 0000e496e774622b0844c0bc9041e15996acc6cd52c02eba295b919a72ba9418
timestamp: 1515663727
transactions: []
nonce: 113470

*** Block 3 ***
hash: 00005147c6d5c9a4d0e7b45094ee87fb352f122f280ea50f405595fd46f6f9ae
previous_hash: 0000a7b6096fca613f6fddc23d18e6361a78647000b1958e920007dba826c822
timestamp: 1515663732
transactions: []
nonce: 1654

*** Block 4 ***
hash: 00007d727a3f3a13fd45fbe6f7bd6ab6c35b532b6f54ec2032bbe02636a672a6
previous_hash: 00005147c6d5c9a4d0e7b45094ee87fb352f122f280ea50f405595fd46f6f9ae
timestamp: 1515663735
transactions: []
nonce: 91294

*** Block 5 ***
hash: 0000c224d520d8c3a7dbcf42208e2d5e32be24b63fa9bef00cbd30f0e778fa88
previous_hash: 00007d727a3f3a13fd45fbe6f7bd6ab6c35b532b6f54ec2032bbe02636a672a6
timestamp: 1515663736
transactions: []
nonce: 88586

*** Block 6 ***
hash: 00000d2cb16a232a3ff161f97e9061eecd708a70aa8f7e2f0b9bfdd1ce64f2e7
previous_hash: 0000c224d520d8c3a7dbcf42208e2d5e32be24b63fa9bef00cbd30f0e778fa88
timestamp: 1515663738
transactions: []
nonce: 36690

*** Block 7 ***
hash: 0000b891db7777ffc4145e31e1e3fd83fd8fa3fb20a215551f603ecfac6ab1ef
previous_hash: 00000d2cb16a232a3ff161f97e9061eecd708a70aa8f7e2f0b9bfdd1ce64f2e7
timestamp: 1515663741
transactions: []
nonce: 136172

*** Block 8 ***
hash: 00008d288b16b6759d75513e147129ca3a35de6ac6c4762d8e159a1e8f2e71f0
previous_hash: 0000b891db7777ffc4145e31e1e3fd83fd8fa3fb20a215551f603ecfac6ab1ef
timestamp: 1515663743
transactions: []
nonce: 105883

*** Block 9 ***
hash: 0000f2b1a32b83471666848af759a313eba695ab9574f68be39b3874825b0846
previous_hash: 00008d288b16b6759d75513e147129ca3a35de6ac6c4762d8e159a1e8f2e71f0
timestamp: 1515663745
transactions: []
nonce: 12591
```

実装は以上です。

##4. まとめ
今回はRubyでBitcoinライクなブロックチェーンを実装しました。
ブロックの構造やProof of Workなど、文章を読めば、何となく理解したつもりになってしまいますが、やはり実際に手を動かして実装してみると、理解はより深まりますね。

ソースコードは以下のリポジトリにあります。プルリク大歓迎です。
https://github.com/shiki-tak/ruby_chain

しかし、まだ実装できず、やり残していることもいくつかあります。それは以下の2点です。

### UTXO形式のトランザクション
今回はジェネシス・ブロックを作成するときだけ具体的なトランザクションを作成し、残りは全て空のトランザクションを格納しました。
しかし、Bitcoinライクなブロックチェーンを実装するのであれば、やはりUTXOの実装は外せません。Go言語で実装されている例があったので、参考にしながら今後実装してみます。[^3]
[^3]: [Building Blockchain in Go](https://jeiwan.cc/posts/building-blockchain-in-go-part-1/)

### ウォレットの実装
現在の実装ではトランザクションに直接addressが格納されるようになっています。これもウォレットから作ったaddressが入るようにしてみたいです。

以上のような課題はありますが、最小限の実装だけなら、比較的簡単にできます。
ブロックチェーンに興味がある人はぜひ、自分の得意な言語で実装してみてはいかがでしょうか？