作って学ぶBitcoin！ゼロから作るSPVウォレット

Bitcoinはもはや説明する必要がないくらいメジャーな存在になりました。その価格は2017/12/12現在で日本円にして200万円を超えており[^1]、技術的な知識を持っていない一般の人でも気軽に手に入れることができるようになりました。技術的な視点からみるとBitcoinそのものというよりもその基礎技術であるブロックチェーンが革命的なものであり単純な仮想通貨にとどまらない応用の可能性を秘めています。例えば[Ethereum](https://www.ethereum.org/)はブロックチェーン上にプログラム（スマートコントラクト）をデプロイして実行できる環境であり、今年の12月には[CryptoKitties](https://www.cryptokitties.co/)というEthereumブロックチェーン上に実装されたゲームが大人気になりました。[Lightning Network](https://lightning.network/)や[Plasma](https://plasma.io/)などなど技術的な話題に尽きないのが盛り上がりを見せるブロックチェーン界隈の面白いところでありますが、今回はそのブロックチェーンを支えるネットワーク、特にBitcoinのP2Pプロトコルに焦点をあててみたいと思います。エンジニアたるもの新しい技術が出てきたら一から自分で作ってみたくなるのが性分だと思いますが、Bitcoinやブロックチェーンの仕組みをわかりやすく解説した記事は見つかれど、ネットワークに参加できるノードの作り方説明している記事はあまり見かけません（[Mastering Bitcoin](https://www.bitcoinbook.info/translations/ja/book.pdf)は詳しく書かれています）。もちろん[bitcoin/bitcion](https://github.com/bitcoin/bitcoin)を始め実装はGitHubにいくらでも転がっているのでソースコード読めという話ではありますが、取っ掛かりとなる知識がないといささかつらいものがあると思います。そこで今回はBitcoinネットワークに繋がるウォレットを１から作っていきたいと思います。実際に手を動かしてBitcoinの言葉をしゃべることでその仕組がより正確に分かり理解が深まることは間違いないでしょう。

まず今回作るBitcoinウォレットについて簡単に説明します。作るのは

* ウォレットの作成
* Bitcoinの送金
* 残高の確認

という３つの機能を持った簡単なアプリケーションです。マイニングは行いませんし、フルノードでもありません。HDウォレットも実装しません。残高の確認にはSPV(Simplified Payment Verification)という軽量に動作する方式を使います。参加するネットワークは[Testnet](https://en.bitcoin.it/wiki/Testnet)と呼ばれる開発用に使われるBitcoinネットワークで実際の通貨は動かしません。

完成したコードはGitHubにもアップロードしているのでそちらも参照してみて下さい。
<https://github.com/lotz84/bitcoin-spv-wallet>

Bitcoinネットワーク
---------------------
<img src="https://qiita-image-store.s3.amazonaws.com/0/17134/cb51a35b-cc26-5b0d-0247-f9c37653a6f2.png" width=300/>

BitcoinネットワークはP2PネットワークなのでWebサイトのURLのように特定の繋ぎ先というものが存在しません。通常はこれまでに繋いだことのあるノードを覚えておいて再び参加する時はそこを訪ねるという方法を取りますが、最初に参加する時やしばらく時間を開けた時はこの方法ではうまく行きません。そこで[Fallback Node](https://en.bitcoin.it/wiki/Fallback_Nodes)と呼ばれる比較的安定して稼働しているノードが存在しており初回等はここに繋ぎに行きます[^2]。ノード間ではTCPでソケット通信が行われます。

これから具体的にどうやってBitcoinネットワークに参加して、どのようなプロトコルを使って情報をやり取りすればいいのか見ていきます。プログラムの実装は強い型を持ち安全なプログラムが書ける[Haskell](https://www.haskell.org/)を使って進めていきます。Haskellは2017/12/23現在時価総額6位の仮想通貨である[Cardano](https://www.cardanohub.org/en/home/)の開発にも使われていまし、[Haskoin](https://github.com/haskoin/haskoin)というBitcoinプロトコルの実装もあります。もしまだHaskellを知らなければぜひ入門してみて下さい！[^3]

Bitcoinの国の挨拶: version, verack
------------------------------------
知ってる人に会ったらまずは挨拶をしますよね？同じようにBitcoinネットワークに繋いだらまずはハンドシェイクを行います。ハンドシェイクはお互いに[version](https://en.bitcoin.it/wiki/Protocol_documentation#version)というメッセージを送って[verack](https://en.bitcoin.it/wiki/Protocol_documentation#verack)というメッセージを返す、それだけです。

<img src="https://qiita-image-store.s3.amazonaws.com/0/17134/03fc1a0b-ebfd-31e9-79e4-22d722f36bc7.png" width=300/>

ネットワークに参加したノードはこのハンドシェイクを通じてお互いのバージョンに関する情報を交換します。そしてこの情報交換が完了するまではそれ以上の通信は行われません。

### 基本的なデータ型

実際にバイナリメッセージでハンドシェイクを行う前にいくつかの準備をしておきましょう。まずBitcoinプロトコルでの数値は基本的に[リトルエンディアン](https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%B3%E3%83%87%E3%82%A3%E3%82%A2%E3%83%B3)で扱われます。なのでリトルエンディアンでエンコードされる数値の型を定義しておきましょう。バイナリを取り扱うライブラリには[binary](https://hackage.haskell.org/package/binary)を使用します。

```hs:src/Bitcoin/Types.hs
-- | リトルエンディアンで表されるWord32
newtype Word32le = Word32le Word32
  deriving (Show, Eq, Ord, Enum, Bounded, Num, Real, Integral)

instance Binary Word32le where
  put (Word32le x) = putWord32le x
  get = Word32le <$> getWord32le

-- | リトルエンディアンで表されるWord64
newtype Word64le = Word64le Word64
  deriving (Show, Eq, Ord, Enum, Bounded, Num, Real, Integral)

instance Binary Word64le where
  put (Word64le x) = putWord64le x
  get = Word64le <$> getWord64le

-- | リトルエンディアンで表されるInt32
newtype Int32le = Int32le Int32
  deriving (Show, Eq, Ord, Enum, Bounded, Num, Real, Integral)

instance Binary Int32le where
  put (Int32le x) = putInt32le x
  get = Int32le <$> getInt32le

-- | リトルエンディアンで表されるInt64
newtype Int64le = Int64le Int64
  deriving (Show, Eq, Ord, Enum, Bounded, Num, Real, Integral)

instance Binary Int64le where
  put (Int64le x) = putInt64le x
  get = Int64le <$> getInt64le
```

次にBitcoinプロトコルで可変長の数値を表す[Variable length integer(var_int)](https://en.bitcoin.it/wiki/Protocol_documentation#Variable_length_integer)の型を定義してみましょう。var_intは最初の1バイトで数値の長さが指定されており、`0xFD`より小さければそのままの数値を、`0xFD`であれば`uint16_t`を、`0xFE`であれば`uint32_t`を、`0xFF`であれば`uint64_t`の数値が後に続きます。

```hs:src/Bitcoin/Protocol/VarInt.hs
-- | Variable length integer
newtype VarInt = VarInt Word64
  deriving (Show, Eq, Ord, Enum, Bounded, Num, Real, Integral)

instance Binary VarInt where
  put x
    | x < 0xFD                                 =                  putWord8    (fromIntegral x)
    | (fromIntegral x) <= (maxBound :: Word16) = putWord8 0xFD >> putWord16le (fromIntegral x)
    | (fromIntegral x) <= (maxBound :: Word32) = putWord8 0xFE >> putWord32le (fromIntegral x)
    | otherwise                                = putWord8 0xFF >> putWord64le (fromIntegral x)
  get = VarInt <$> (getWord8 >>= getValue)
    where
      getValue size
        | size <  0xFD = pure (fromIntegral size)
        | size == 0xFD = fromIntegral <$> getWord16le
        | size == 0xFE = fromIntegral <$> getWord32le
        | otherwise    = fromIntegral <$> getWord64le
```

次はBitcoinプロトコルの可変長文字列である[Variable length string(var_str)](https://en.bitcoin.it/wiki/Protocol_documentation#Variable_length_string)を定義しましょう。これはまず文字列の長さを表す`var_int`があってその後に文字列が続きます。

```hs:src/Bitcoin/Protocol/VarStr.hs
import Prelude hiding (length)

-- | Variable length string
data VarStr = VarStr
  { length :: VarInt
  , string :: ByteString
  } deriving Show

instance Binary VarStr where
  put x = do
    put           $ length x
    putByteString $ string x
  get = do
    size <- get
    xs   <- getByteString (fromIntegral size)
    pure (VarStr size xs)

fromByteString :: ByteString -> VarStr
fromByteString bs = VarStr (fromIntegral $ BS.length bs) bs
```

var_strのように最初にvar_intがあってその後に複数個メッセージが続くようなパターンがBitcoinプロトコルにはよくあります。これも型として切り出しておきましょう。

```hs:src/Bitcoin/Protocol/VarList.hs
import Prelude hiding (length)
import qualified Prelude as P

-- | var_intの後にメッセージが複数続くパターン
data VarList a = VarList
  { length :: VarInt
  , elems  :: [a]
  } deriving Show

-- | IsListのインスタンスにしておくとOverloadedLists拡張と併用することで
-- | リストリテラルを使ってVarListの値を作ることができる。
instance IsList (VarList a) where
  type Item (VarList a) = a
  fromList xs = VarList (fromIntegral $ P.length xs) xs
  toList = elems

instance Binary a => Binary (VarList a) where
  put x = do
    put       $ length x
    mapM_ put $ elems  x
  get = do
    size <- get
    es   <- replicateM (fromIntegral size) get
    pure (VarList size es)
```

Bitcoinプロトコルでは`char[32]`のように長さの指定された固定長文字列もよく出てきます。型で長さを表すことができる[vector-sized](https://hackage.haskell.org/package/vector-sized)のVectorを使って固定長文字列を表す型を定義しておきましょう。

```hs:src/Bitcoin/Types.hs
-- | char[n]のような固定長文字列
newtype Chars n = Chars (Vector n Word8)
  deriving (Show, Eq, Ord)

instance forall n. KnownNat n => Binary (Chars n) where
  put (Chars x) = mapM_ put $ Vector.toList x
  get = (Chars . fromJust . Vector.fromList) <$> (replicateM (fromInteger $ natVal (Proxy @n)) get)

toChars :: forall n. KnownNat n => ByteString -> Chars n
toChars bs = Chars . fromJust . Vector.fromList . take (fromInteger $ natVal (Proxy @n)) $ (BS.unpack bs ++ repeat 0x00)

toByteString :: Chars n -> ByteString
toByteString (Chars cs) = BS.pack $ Vector.toList cs
```

型から長さの情報を取り出すことができるので`put`や`get`の引数に長さを明示的に取らなくても実装できているところがポイントです :bulb: 

さて、せっせとBinaryのインスタンスを定義するのはこれで終わりです。これ以降に出てくるプロトコルの型のBinaryインスタンスは基本的に全て今までに定義した型から自動的に導出することができます。

### Bitcoinプロトコルの基礎

Bitcoinプロトコルのメッセージは[ヘッダーとペイロード](https://en.bitcoin.it/wiki/Protocol_documentation#Message_structure)から構成されています。ペイロードの部分はメッセージによって変わってきますがヘッダーは全てのメッセージに共通で以下のようになっています。

|     項目    |    型    |                説明        |
|:-----------:|:--------:|:--------------------------|
|    magic    | uint32_t | ネットワーク毎に固有の値       |
| commandName | char[12] | メッセージの名前("verack"等) |
| payloadSize | uint32_t | ペイロードのバイト数          |
|   checksum  | char[4]  | チェックサム                |
参考: [Bitcoin Developer Reference - Message Headers](https://bitcoin.org/en/developer-reference#message-headers)

これをHaskellの型にそのまま変換すると以下のようになります。

```hs:src/Bitcoin/Protocol/MessageHeader.hs
-- | 全てのメッセージに共通するヘッダー
data MessageHeader = MessageHeader
  { magic       :: Word32le
  , commandName :: Chars 12
  , payloadSize :: Word32le
  , checksum    :: Chars 4
  } deriving (Show, Generic)

instance Binary MessageHeader
```

BinaryのインスタンスはGenericを使って自動的に導出しています。このようにすればフィールドの上から順番に`put`又は`get`してくれるような実装になります。

それでは[version](https://en.bitcoin.it/wiki/Protocol_documentation#version)メッセージのペイロードを定義してみましょう。

```hs:src/Bitcoin/Protocol/Version.hs
-- | versionメッセージ
data Version = Version
  { version     :: Int32le  -- ノードで使われているプロトコルのバージョン番号
  , services    :: Word64le -- ノードがサポートしている機能を表すフラグ
  , timestamp   :: Int64le  -- UNIXタイムスタンプ（秒）
  , addrRecv    :: NetAddr  -- 受け手のネットワーク・アドレス
  , addrFrom    :: NetAddr  -- 送り手のネットワーク・アドレス
  , nonce       :: Word64le -- コネクションを特定するために使用されるランダムな値
  , userAgent   :: VarStr   -- ユーザーエージェント。see. BIP14
  , startHeight :: Int32le  -- ノードが持っているブロックの高さ
  , relay       :: Bool     -- 接続先ノードが受信したトランザクションを送っていいかどうか
  } deriving (Show, Generic)

instance Binary Version

instance Message Version where
  commandName = "version"
```

`NetAddr`は[Network Address](https://en.bitcoin.it/wiki/Protocol_documentation#Network_address)を表す型で以下のようになっています。

```hs:src/Bitcoin/Protocol/NetAddr.hs
-- | ネットワーク・アドレス
data NetAddr = NetAddr
  { services :: Word64le -- versionのserviceと同様
  , ip       :: Chars 16 -- IPアドレス
  , port     :: Word16   -- ポート番号
  } deriving (Show, Generic)

instance Binary NetAddr
```

`port`はBitcoinプロトコルの中で唯一ビッグエンディアンで扱われる数値です。

`Version`は`Message`のインスタンスになっています。`Message`はBitcoinプロトコルのメッセージのペイロードを表す型を表現し、機能としてはコマンド名が取得できるだけです。

```hs:src/Bitcoin/Types.hs
class Message a where
  commandName :: ByteString
```

verackメッセージの型も作りましょう。

```hs:src/Bitcoin/Protocol/Verack.hs
data Verack = Verack
  deriving (Show, Generic)

instance Binary Verack

instance Message Verack where
  commandName = "verack"
```

[verack](https://en.bitcoin.it/wiki/Protocol_documentation#verack)メッセージにはペイロードがないのでとても簡素な実装になっています。

それでは実際にTCPでソケット通信を行ってハンドシェイクをしてみましょう。ソケットプログラミングは[network](https://hackage.haskell.org/package/network)を使って実装していきます。まずは便利な関数を定義しておきましょう。

```hs:src/Bitcoin/Protocol.hs
-- | ソケットからBitcoinプロトコルのメッセージのペイロードを読み込む
recvMessage :: Binary msg => Socket -> Int -> IO msg
recvMessage sock size = decode . BL.fromStrict <$> recvAll sock size

-- | ソケットからBitcoinプロトコルのヘッダーを読み込む
recvMessageHeader :: Socket -> IO (ByteString, Int)
recvMessageHeader sock = do
  mh <- recvMessage sock 24 :: IO MessageHeader
  let name = toByteString $ MessageHeader.commandName mh
      size = fromIntegral $ MessageHeader.payloadSize mh
  putStrLn $ "Recv: " ++ BC.unpack name ++ " " ++ show size
  pure (name, size)

-- | 指定されたバイト数だけソケットからメッセージを読み込む
recvAll :: Socket -> Int -> IO ByteString
recvAll sock size = go [] sock size
  where
    go recieved _ 0 = pure . BS.concat $ reverse recieved
    go recieved sock size = do
      bs <- recv sock size
      go (bs:recieved) sock (size - BS.length bs)

-- | Bitcoinプロトコルのメッセージをソケットに書き込む
sendMessage :: forall msg. (Binary msg, Message msg) => Socket -> msg -> IO ()
sendMessage sock msg = do
  let header = createMessageHeader msg
      payload = encode msg
      size = BL.length payload
  send sock (BL.toStrict $ BL.concat [encode header, payload])
  putStrLn $ "Send: " ++ (BC.unpack $ commandName @msg) ++ " " ++ show size

-- | Bitcoinプロトコルのペイロードからヘッダーを作成する
createMessageHeader :: forall msg. (Binary msg, Message msg) => msg -> MessageHeader
createMessageHeader message =
  let payload = BL.toStrict $ encode message
   in MessageHeader
        0x0709110B -- Testnet magic value
        (toChars $ commandName @msg)
        (fromIntegral $ BS.length payload)
        (toChars $ hash256 payload)
```

`createMessageHeader`の実装にある`0x0709110B`はネットワーク毎に決まった値で以下のようになっています。

| Network    | Magic value |
|:-----------|------------:|
| Main       |  0xD9B4BEF9 |
| Testnet    |  0x0709110B |
参考: [Protocol documentation - Common structures](https://en.bitcoin.it/wiki/Protocol_documentation#Common_structures)

今回はTestnetを使用するので`0x0709110B`にしています。

`hash256`はハッシュ関数の`sha256`を2回適用したもので[cryptonite](https://hackage.haskell.org/package/cryptonite)を使って以下のように定義しています。

```hs:src/Bitcoin/Hash.hs
sha256 :: ByteString -> ByteString
sha256 bs = convert (Crypto.hash bs :: Digest SHA256)

hash256 :: ByteString -> ByteString
hash256 = sha256 . sha256
```

ハンドシェイクを行う関数を以下のように実装します。

```hs:src/Bitcoin/Protocol.hs
-- | 16進数表記された文字列をバイト列に変換する
readHex :: ByteString -> ByteString
readHex = either error id . convertFromBase Base16

-- | Bitcoinネットワークに繋げてハンドシェイクを行う
withBitcoinConnection :: ((Socket, Version) -> IO a) -> IO a
withBitcoinConnection between = bracket first (close . fst) between
  where
    first = do
      host <- hostAddress <$> getHostByName "testnet-seed.bitcoin.jonasschnelli.ch" -- Fallback Node
      sock <- socket AF_INET Stream defaultProtocol
      connect sock (SockAddrInet 18333 host)

      -- versionを送る
      unixtime <- getPOSIXTime
      let ip = readHex $ BS.concat ["00000000", "00000000", "0000FFFF", "7F000001"] -- 127.0.0.1
          addr = NetAddr 1 (toChars ip) 8333
          userAgent = VarStr 0 BS.empty
          version = Version 70015 1 (round unixtime) addr addr 0 userAgent 0 False
      sendMessage sock version

      -- versionを受け取ってverackを送り返す
      version <- handshake sock Nothing False
      pure (sock, version)

    -- versionとverackを受け取るまで処理を繰り返す
    handshake sock version verack = do
      case (version, verack) of
        (Just version, True) -> pure version
        _                    -> do
          (name, size) <- recvMessageHeader sock
          (version', verack') <- dispatch sock name size
          handshake sock (version <|> version') (verack || verack')

    -- 受信したメッセージに対応した処理を行う
    dispatch sock name size
      | "version" `BS.isPrefixOf` name = do
          version <- recvMessage sock size :: IO Version
          sendMessage sock Verack
          pure (Just version, False)
      | "verack" `BS.isPrefixOf` name = pure (Nothing, True)
      | otherwise = do
          recvMessage sock size :: IO ByteString
          pure (Nothing, False)
```

接続先のFallback Nodeは[bitcoinの実装](https://github.com/bitcoin/bitcoin/blob/master/src/chainparams.cpp#L232-L235)を参考にしています。

実際に動かしてみましょう。

```hs:app/Main.hs
main :: IO ()
main = withBitcoinConnection $ \(sock, _) -> do
  forever $ dispatch sock =<< recvMessageHeader sock
    where
      dispatch sock (name, size) =
        if size > 0
           then recvMessage sock size :: IO ByteString
           else pure ""
```

```shell
$ runhaskell Main.hs
Send: version 86
Recv: version 102
Send: verack 0
Recv: verack 0
Recv: sendheaders 0
Recv: sendcmpct 9
Recv: sendcmpct 9
Recv: ping 8
Recv: getheaders 1061
Recv: feefilter 8
Recv: addr 31
^C
```

ちゃんとハンドシェイクが行われていますね！versionとverackを交換した後にいくつかメッセージを受信しているのがわかると思います。一つずつ見ていきましょう。

#### sendheaders
[sendheaders](https://en.bitcoin.it/wiki/Protocol_documentation#sendheaders)は[BIP130](https://github.com/bitcoin/bips/blob/master/bip-0130.mediawiki)で追加されたメッセージです。Bicoinプロトコルでデータを送る際はまず送るデータの種類とヘッダーだけが入った[inv](https://en.bitcoin.it/wiki/Protocol_documentation#inv)メッセージを送って欲しい情報だけ精査して[getdata](https://en.bitcoin.it/wiki/Protocol_documentation#getdata)メッセージとして送り返してもらった後にデータを送るのが基本です。新しくマイニングされたブロックの情報も当然この手順に従って送信されます。さらに新しくブロックがマイニングされた時はそのブロックがマイニングされたチェーンの一連のヘッダー情報も同時にリクエストします。

<img src="https://qiita-image-store.s3.amazonaws.com/0/17134/7a0dad7e-ecf4-3de5-fffc-da666305ddb9.png" width=300/>

headersの情報からもinvに含まれるハッシュは計算できるので、新しいブロックの情報が来た時は先にheadersを送ってしまえば通信のコストを削減できます。sendheadersを送ることで自分のノードは先にheadersを送ってきても対応できるよということを表明することができるのです。sendheadersを送られた側はこの仕様に対応してもしなくても構いません。

<img src="https://qiita-image-store.s3.amazonaws.com/0/17134/4646a0b4-e19f-5b78-2d35-e2210c02bd28.png" width=300/>

#### sendcmpct
[sendcmpct](https://en.bitcoin.it/wiki/Protocol_documentation#sendcmpct)は[BIP152](https://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki)で追加されたメッセージです。Bitcoinネットワーク上でブロックの情報を効率よく伝播させるための仕組みです。以下の記事で詳しく解説されているので参照してみて下さい。
[Block受信時に重複したトランザクションの受信を抑制するCompact Block（BIP-152）](http://techmedia-think.hatenablog.com/entry/2016/07/03/170509)

#### ping
[ping](https://en.bitcoin.it/wiki/Protocol_documentation#ping)はノードと正常につながっているかどうかを確認するために使われるメッセージです。pingを受け取ったらメッセージの中にnonceが入っているので[pong](https://en.bitcoin.it/wiki/Protocol_documentation#pong)の中に受け取ったnonceを入れて送り返しましょう。

<img src="https://qiita-image-store.s3.amazonaws.com/0/17134/693f11e1-3011-9333-37d1-96ec9b9abec1.png" width=300/>

#### getheaders
[getheaders](https://en.bitcoin.it/wiki/Protocol_documentation#getheaders)は持っているブロックチェーンのブロックヘッダーの情報を送って欲しい時に送るメッセージです。 ブロックの情報が欲しい時は[getblocks](https://en.bitcoin.it/wiki/Protocol_documentation#getblocks)というメッセージも使われますがgetheadersはヘッダーの情報しか含まれていない分getblocksよりも多くの情報を受け取ることができます。

#### feefilter
[feefilter](https://en.bitcoin.it/wiki/Protocol_documentation#feefilter)は一定以上の手数料しか払っていないトランザクションは送ってこなくていいという意思を表明するためのメッセージで[BIP133](https://github.com/bitcoin/bips/blob/master/bip-0133.mediawiki)で提案されました。手数料が極端に低いトランザクションを大量に処理することになって効率が落ちることを防ぐために用意されています。

#### addr
[addr](https://en.bitcoin.it/wiki/Protocol_documentation#addr)は接続している別のノードの接続情報を教えてくれるメッセージです。今回はFallback Nodeにしか繋ぎませんが通常（特にSPVノード）は複数のノードに使ってデータをやり取りします。addrが来る度にコネクションを増やしたり、逆に接続が来る度にaddrを他のノードに送ることで健全なBitcoinネットワークの維持に貢献することができます。

Bitcoinの財布を自分で作る: Secp256k1
------------------------------
さて、無事にBitcoinネットワークに参加してハンドシェイクまで終えることができました。次は誰かからBitcoinを受け取って誰かに送金してみましょう。

誰かからBitcoinを送ってもらうには受け取るためのウォレットが必要です。どうすればウォレットを作ることができるでしょうか。そもそもウォレットって何でしょうか？ウォレットが何なのかを知るためにはBitcoinネットワークで送金ができる仕組みを知る必要があります。Bitcoinネットワークで誰かから誰かに送金が行われるということはブロックにそのトランザクションの情報が記載されることに他なりません。トランザクションは誰でも自由に作ってBitcoinネットワークに流すことができます。しかし勝手に作ったトランザクションをBitcoinネットワークに受け入れてもらうためにはそれが本当に自分のお金を送金しているトランザクションだということを証明できなければなりません。この証明方法を理解するためにトランザクションのデータ構造を詳しく見ていきましょう。

<table>
<tr>
  <th>トランザクションの構造</th>
  <th></th>
  <th></th>
  <th>説明</th>
</tr>
<tr>
  <td>version</td>
  <td></td>
  <td></td>
  <td>バージョン情報</td>
</tr>
<tr>
  <td rowspan=3>TxIn</td>
  <td rowspan=2>TxIn1</td>
  <td>Outpoint</td>
  <td>使用するトランザクションのTxOutへの参照</td>
</tr>
<tr>
  <td>ScriptSig</td>
  <td>OutPointが指すTxOutが自分への送金であることを証明するスクリプト</td>
</tr>
<tr>
  <td>...</td>
  <td></td>
  <td></td>
</tr>
<tr>
  <td rowspan=3>TxOut</td>
  <td rowspan=2>TxOut1</td>
  <td>Value</td>
  <td>送金する金額</td>
</tr>
<tr>
  <td>ScriptPubKey</td>
  <td>送金先の人にしか証明できないスクリプト</td>
</tr>
<tr>
  <td>...</td>
  <td></td>
  <td></td>
</tr>
<tr>
  <td>lock_time</td>
  <td></td>
  <td></td>
  <td>このトランザクションが有効になる時間</td>
</tr>
</table>

[tx](https://en.bitcoin.it/wiki/Protocol_documentation#tx)メッセージの構造をざっくりと表にしてみました。誰から送られてきたお金を（TxIn）誰に送金するのか（TxOut）という情報が含まれているのがわかると思います。このトランザクションを受け取ったノードはどのように検証作業を行うのでしょうか。[いろいろと確認項目はありますが](https://en.bitcoin.it/wiki/Protocol_rules#.22tx.22_messages)、一番大事なのはTxInに指定されているScriptSig(Unlocking Script)が正しく参照しているTxOutのScriptPubKey(Locking Script)を解錠できているかということです。
ScriptSig, ScriptPubKeyの例として[P2PKH](https://bitcoin.org/en/developer-guide#p2pkh-script-validation)を見てみましょう。これはScriptPubKeyとして

```
OP_DUP OP_HASH160 <PubkeyHash> OP_EQUALVERIFY OP_CHECKSIG
```

のようなスクリプトを、ScriptSigとして

```
<Sig> <PubKey>
```

のようなスクリプトを使用するものです。`<PubKeyHash>`は自分が持つ公開鍵をハッシュ化したもの、`<PubKey>`は自分の公開鍵、`<Sig>`は自分の秘密鍵を使ってトランザクションを署名したもので、`OP_DUP`などの`OP_`から始まる命令はあらかじめ定義されているBitcoinプロトコルで使える[Script](https://en.bitcoin.it/wiki/Script)です。これらの値は全てバイト列にエンコードされてtxメッセージの中に入っています。
役者が出揃ったのでトランザクションの検証方法について説明したいと思います。AさんがBさんに送ったBitcoinをBさんがCさんに送るケースを考えます。まずBさんはあらかじめウォレットとして公開鍵と秘密鍵を作成しておき、Aさんに公開鍵を教えて、その公開鍵を送金先に指定してトランザクションを作ってもらいます。その時のScriptPubKeyは以下のようになります。

```
OP_DUP OP_HASH160 <ハッシュ化されたBさんの公開鍵> OP_EQUALVERIFY OP_CHECKSIG
```

次にBさんはCさんへの送金トランザクションを作ります。この送金トランザクションのTxInには先程のAさんからBさんへの送金が指定されておりScriptSigには以下のように記載されています。

```
<Bさんの秘密鍵でこのトランザクションを署名したもの> <Bさんの公開鍵>
```

Bitcoinネットワークのノードがこのトランザクションを受け取った時にノードはTxInが正しいかを検証するためにそのScriptSigと参照しているTxOutのScriptPubKeyをこの順番に並べます。今の場合だと以下のようになります。

```
<Bさんの秘密鍵でこのトランザクションを署名したもの> <Bさんの公開鍵> OP_DUP OP_HASH160 <ハッシュ化されたBさんの公開鍵> OP_EQUALVERIFY OP_CHECKSIG
```

これを単純なスタックマシンを想定して前から順番に実行していきます。

1. `<Bさんの秘密鍵でこのトランザクションを署名したもの>` をスタックに積む
2. `<Bさんの公開鍵>` をスタックに積む
3. `OP_DUP`が来たのでスタックの先頭に詰まれているもの（今の場合だと`<Bさんの公開鍵>`）をコピーしてスタックに積む
4. `OP_HASH160`が来たのでスタックから一つデータを取り出してハッシュ化して再びスタックに積む
5. `<ハッシュ化されたBさんの公開鍵>`をスタックに積む
6. `OP_EQUALVERIFY`が来たのでスタックから2つ値を取り出して等しいかどうかを検証する
7. `OP_CHECKSIG`が来たのでスタックから2つ値を取り出して2つ目の値を署名とみなして最初の値で検証する

実行すると以上のようになり、確かに`<Bさんの秘密鍵でこのトランザクションを署名したもの>`はBさんにしか作れないのでBさん以外が送金することができなくなっていることがわかります。Bitcoinネットワークではこのように公開鍵と電子署名を使った仕組みでお金が使える人を制限しているので、それを持っていないと送金することができない秘密鍵のことを指してウォレットと呼ぶようになっています。

### 秘密鍵と公開鍵の作成

公開鍵暗号の秘密鍵がウォレットとだということがわかったので実際にこれを作ってみましょう。Bitcoinの公開鍵暗号には[Secp256k1](https://en.bitcoin.it/wiki/Secp256k1)と呼ばれる楕円曲線暗号が使われています。

```hs:app/Wallet.hs
-- | Secp256k1の秘密鍵を生成する
genSecKey :: IO SecKey
genSecKey = do
  bs <- getRandomBytes 32
  case secKey bs of
    Just sk -> pure sk
    Nothing -> genSecKey
```

[cryptoniteのgetRandomBytes](https://hackage.haskell.org/package/cryptonite-0.24/docs/Crypto-Random.html#t:MonadRandom)を使ってランダムな文字列を生成し、[secp256k1のsecKey](https://hackage.haskell.org/package/secp256k1-0.5.2/docs/Crypto-Secp256k1.html#v:secKey)を使ってそれがSecp256k1の秘密鍵として使えるか判定して、秘密鍵が生成されるまで繰り返しています。作った秘密鍵はそのまま保存しても構いませんが簡便のため[WIF](https://en.bitcoin.it/wiki/Wallet_import_format)と呼ばれる形式に変換して保存します。

```hs:app/Wallet.hs
-- | 秘密鍵をWIFに変換する
encodeWIF :: SecKey -> ByteString
encodeWIF sk =
  let xs = BS.concat [BS.singleton 0xEF, getSecKey sk]
      checksum = BS.take 4 . hash256 $ xs
   in encodeBase58 bitcoinAlphabet $ BS.concat [xs, checksum]
```

WIFは秘密鍵の先頭にネットワークの種類を示す1バイトの文字を付け（テストネットだと0xEF）、全体をHash256でハッシュ化して先頭4バイトを取ってきたものをチェックサムとして後ろにつけたものをBase58エンコードしたものです。Base58の実装には[base58-bytestring](https://hackage.haskell.org/package/base58-bytestring)を利用しています。

**WIFへの変換手順**

|No.   |手順  |例   |
|:----:|:----|:----|
|1|WIFに変換する秘密鍵|`0C28FCA386C7A227600B2F...`|
|2|先頭にネットワークを表す1バイトの文字を付ける|**`EF`**`0C28FCA386C7A227600B2FE50B7CAE...`|
|3|Hash256に適用する|`507A5B8DFED0FC6FE88017...`|
|4|先頭4バイトの文字を取る|`507A5B8D `|
|5|2と3を結合する|`EF0C28FCA386C7A227600B2F...507A5B8D`|
|6|Base58でエンコードする| `5HueCGU8rMjxEXxiPuD5BDku4MkFqe...`|

WIFから秘密鍵に戻す時は逆の操作を行えばいいでしょう

```hs:app/Wallet.hs
-- | WIFから秘密鍵に変換する
decodeWIF :: ByteString -> Maybe SecKey
decodeWIF wif = do
  xs <- decodeBase58 bitcoinAlphabet wif
  let l         = BS.length xs
      ys        = BS.take (l - 4) xs
      checksum  = BS.drop (l - 4) xs
      checksum' = BS.take 4 . hash256 $ ys
  guard  $ checksum == checksum'
  secKey $ BS.drop 1 ys
```

秘密鍵から公開鍵を作ることは簡単です。ですが公開鍵はそのままだととても長い文字列になってしまうのでBitcoinでは[Bitcoinアドレス](https://en.bitcoin.it/wiki/Address)と呼ばれる読みやすい公開鍵のフォーマットが定められています。

```hs
-- | 公開鍵をBitcoinアドレスに変換する
encodeBitcoinAddress :: PubKey -> ByteString
encodeBitcoinAddress pubKey =
  let xs = BS.concat [BS.singleton 0x6F, hash160 $ exportPubKey False pubKey]
      checksum = BS.take 4 . hash256 $ xs
   in encodeBase58 bitcoinAlphabet $ BS.concat [xs, checksum]
```

WIFの時とほとんど同じ手順ですね。違うのはネットワークを表す1バイトの文字と公開鍵をハッシュ関数に適用するところです。公開鍵に適用するハッシュ関数はHash160でこれはSHA256でハッシュ化した後に[RIPEMD-160](https://en.bitcoin.it/wiki/RIPEMD-160)と呼ばれるハッシュ関数に適用するものです。以下のように実装しています。

```hs:app/Bitcoin/Hash.hs
ripemd160 :: ByteString -> ByteString
ripemd160 bs = convert (Crypto.hash bs :: Digest RIPEMD160)

hash160 :: ByteString -> ByteString
hash160 = ripemd160 . sha256
```

Bitcoinアドレスの作り方はこちらのWikiにも詳しく載っています。 [Bitcoin wiki - Technical background of version 1 Bitcoin addresses](https://en.bitcoin.it/w/index.php?title=Technical_background_of_version_1_Bitcoin_addresses)

### ウォレットの作成
最後にウォレットを作成して保存・表示するアプリケーションを作ってみましょう。

```hs:app/Wallet.hs
-- | 秘密鍵を保存するファイルパス
secKeyFilePath :: FilePath
secKeyFilePath = "secret-key.der"

-- | ファイルから秘密鍵を取得する
getWalletSecretKey :: IO (Maybe SecKey)
getWalletSecretKey = do
  isExists <- doesFileExist secKeyFilePath
  if isExists
     then decodeWIF <$> BS.readFile secKeyFilePath
     else pure Nothing

-- | ウォレットのBitcoinアドレスを表示する
-- | もし秘密鍵が保存されて無ければ生成する
showWallet :: IO ()
showWallet = do
  secKey <- fix $ \loop -> do
    secKey <- getWalletSecretKey
    case secKey of
      Nothing -> do
        sk <- genSecKey
        BS.writeFile secKeyFilePath $ encodeWIF sk
        loop
      Just secKey -> pure secKey
  BS.putStrLn . encodeBitcoinAddress $ derivePubKey secKey
```

Mainも後を見越して少し修正しておきます。

```hs:app/Main.hs
main :: IO ()
main = do
  args <- getArgs
  if length args == 0
     then putStrLn "Please give subcommand wallet/send/balance."
     else case head args of
       "wallet"  -> showWallet
```

実行してみます。

```shell
$ runhaskell Main.hs wallet
mxMDYVc8B25SJvTeUtkU6r8ELkUpsNTDEj
```

無事Bitcoinアドレスが表示されました :tada: `secret-key.der` というファイルが出来上がってるのも確かめてみて下さい。ところでBitcoinアドレスは1から始まっているものをよく見かけると思いますが、今作ったものはmから始まっていますね。これはBitcoinアドレスを生成する時に先頭に追加する1バイトの文字がMainnetとTestnetでは違っていることが原因です。色んなアドレスのPrefixをまとめたWikiがあるので参照してみて下さい。[Bitcoin wiki - List of address prefixes](https://en.bitcoin.it/wiki/List_of_address_prefixes)

### ウォレットへの送金
Bitcoinアドレスを作ったのでさっそく送金してみましょう。[Faucet](https://qiita.com/satetsu888/items/0311a3ec0d7a2323ea4e)という仕組みを利用してTestnetのBitcoinを手に入れます。利用するFaucetは[Bitcoin Testnet Sandbox](https://testnet.manu.backend.hamburg/faucet)です。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/17134/150a12e9-8945-bc4f-fe9e-98a266819245.png)

使い方は、_Your TestNet Address_とプレースホルダーがあるところに先程生成したアドレスを貼り付けてreCAPTCHAにチェックをいれて右端にある_Give me some coins_と書かれたボタンをクリックするだけです。すると

```
Sent! TX ID: 247b3712423da29dcdcf1819e53e1eb0da4bd117a7205fb90b5014d881a14df2
```

と書かれた緑色の表示が出てくるのでこれで送金リクエストは完了です。生成されたトランザクションを確認してみましょう。[BlockCypherのBitcoin Testnet Explorer](https://live.blockcypher.com/btc-testnet/)を使ってトランザクションの情報を確認してみます。<https://live.blockcypher.com/btc-testnet/> にアクセスすると以下のような画面が出てくるので検索ボックスに先程作った送金のトランザクションID（TX ID）を入れて🔍ボタンをクリックします。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/17134/4dfb7955-b990-6c7f-ab25-d222f295c555.png)


すると以下のようなURLでトランザクションの情報が確認できると思います。
<https://live.blockcypher.com/btc-testnet/tx/247b3712423da29dcdcf1819e53e1eb0da4bd117a7205fb90b5014d881a14df2/>
送金してすぐに確認するとまだConfirmationsが0/6のままかもしれません。もしかするとブロックに取り込まれずに送金がなかったことになる可能性もありますのでConfirmationsは要チェックですが、Bitcoin Testnet Sandboxからの送金であればまず大丈夫だと思います。

Bitcoinを送る: tx
------------------
Testnetでの送金も成功したので今度はこっちからBitcoinを送金してみましょう。Bitcoin Testnet Sandbokでは

> We would like to get them back. Send left coins to 2N8hwP1WmJrFF5QWABn38y63uYLhnJYJYTF. Thank you.

として使わないBitcoinはここに返してねとアドレスが指定されているのでここに送り返すことにします。Bitcoinの送金を行うにはtxメッセージを送ればよかったので、[txの仕様](https://en.bitcoin.it/wiki/Protocol_documentation#tx)を参考に型を定義してみましょう。

```hs:app/Bitcoin/Protocol/Tx.hs
-- | トランザクションID
type TxId = Chars 32

-- | TxOutへの参照
data OutPoint = OutPoint
  { hash  :: TxId
  , index :: Word32le
  } deriving (Show, Generic)

instance Binary OutPoint

-- | トランザクションで使用するUTXO
data TxIn = TxIn
  { previousOutput  :: OutPoint
  , signatureScript :: VarStr
  , sequence        :: Word32le
  } deriving (Show, Generic)

instance Binary TxIn

-- | 送金情報
data TxOut = TxOut
  { value          :: Int64le
  , pkScript       :: VarStr
  } deriving (Show, Generic)

instance Binary TxOut

-- | トランザクション
data Tx = Tx
  { version  :: Int32le
  , txIn     :: VarList TxIn
  , txOut    :: VarList TxOut
  , lockTime :: Word32le
  } deriving (Show, Generic)

instance Binary Tx

instance Message Tx where
  commandName = "tx"

txId :: Tx -> TxId
txId = toChars . hash256 . BL.toStrict . encode
```

実は`txOut`, `lockTime`の間に`witness`というデータが入る可能性があるのですが今回は簡便のため対応していません。`witness`は今年の8月にアクティベートされた[Segwit](https://bitflyer.jp/ja-jp/glossary/segwit)という仕様に使われるデータです。ですがまだ取引所や普及しているウォレットの対応が進んでいないためSegwitの送金トランザクションは[あまり見かけません](http://segwit.party/charts/#)。大手取引所Coinbaseが[対応を進めていたり](https://twitter.com/coinbase/status/937500274863751168)、iOSで普及しているBreadが[来年1月に対応するらしい](https://www.reddit.com/r/Bitcoin/comments/7k48gp/breadwallet_will_implement_segwit_in_january_2018/)ので来年から徐々にSegwitのトランザクションが増えていくのではないでしょうか。エンジニア的な視点からすると[双方向ペイメントチャネル](http://techmedia-think.hatenablog.com/entry/2016/08/06/212453)・[シュノア署名](https://zoom-blc.com/schnorr-signature)・[MAST](https://zoom-blc.com/what-is-bitcoin-mast)などの実装が容易になるためSegwitの普及は進んで欲しいと思っています。

### TxInの作成

さて、自分のウォレットからBitcoin Testnet Faucetに送金するための`Tx`を作っていきましょう。まず`version`は現時点では1で、`lockTime`は特に設けないので0でいいでしょう。

次に`TxIn`を作ります。`TxIn`には`OutPoint`という使いたいBitcoinが送られてきたトランザクションの`TxOut`を指定するデータがあります。今はまだ必要なデータをブロックチェーンから取得できているわけではないので先ほどのBitcoin Testnet Explorerを利用して必要な情報を取ってきましょう。[さっきのトランザクションのページ](https://live.blockcypher.com/btc-testnet/tx/247b3712423da29dcdcf1819e53e1eb0da4bd117a7205fb90b5014d881a14df2/)にアクセスして`Advanced Detail`というボタンを押して出てきた画面の中の`</> API Call`をクリックします。すると以下のURLでトランザクションの情報がJSONで取得できると思います。
<https://api.blockcypher.com/v1/btc/test3/txs/247b3712423da29dcdcf1819e53e1eb0da4bd117a7205fb90b5014d881a14df2?limit=50&includeHex=true>

`OutPoint`を作るには`hash`と`index`が必要です。`hash`はトランザクションID、`index`は使いたい送金の記録が`TxOut`の何番目に記載されているかを指定します（先頭が0番目です）。今回の例だとJSONで確認すると1番目に自分のアドレスへの送金が来ているので0を指定します。

`TxId`を以下のように作ります。

```hs:app/Send.hs
  let -- TxInの作成
      outTxId  = toChars . BS.reverse $ readHex "247b3712423da29dcdcf1819e53e1eb0da4bd117a7205fb90b5014d881a14df2"
      outPoint = OutPoint outTxId 0x00
      txIn xs  = TxIn outPoint xs 0xFFFFFFFF
```

`outTxId`はTxIdを読み込んだ後に反転していることに注意しましょう。`signatureScript`の部分は関数の引数にして空けています。あとでトランザクションへの署名を行う時にここの値を入れ替えるためです。`sequence`は今は使われていないので`0xFFFFFFFF`固定にします[^4]。

### TxOutの作成

次に`TxOut`を作りましょう。`TxOut`を作るのに必要なのは誰に・いくら送るのかという情報です。いくら送るかを決めるために必要な情報は

1. いくら使えるのか
2. いくら送るのか
3. いくら手数料を支払うのか

の３つです。いくら使えるのかは`TxIn`の値を足し合わせればよく、今回は`200000000`(=2BTC)です（単位はsatoshi）。いくら送るのかは`20000000`(=0.2BTC)としましょう。手数料は`10000000`(=0.1BTC)支払うとします（実際はこんなに払わなくても良いですがテストのため簡単な数字にしています。まだこんなに払わなくても大丈夫です…）。

これらの情報から

* Faucetに`20000000`(=0.2BTC)を送る
* 自分に`17000000`(= 200000000 - 20000000 - 10000000)(= 1.7BTC)を送る

という送金を行えば良いことがわかります。そして送金トランザクションに記載されていない`10000000`が手数料としてマイナーに支払われることになります。送り先は以下のようになっていました。

* Faucetのアドレス: `2N8hwP1WmJrFF5QWABn38y63uYLhnJYJYTF`
* 自分のアドレス: `mxMDYVc8B25SJvTeUtkU6r8ELkUpsNTDEj`

自分のアドレスにはP2PKHを使って送ればいいですが、FaucetのアドレスはPrefixが2になっていて普通のアドレスでは無さそうですね。Testnetで2から始まるアドレスはスクリプトハッシュといってP2SH(to Script Hash)で使われるアドレスです。これはScriptPubKeyに解錠するためのスクリプトのハッシュ値を入れておいてScriptSigの中に実際のスクリプトを仕込ませることで、複雑なスクリプトでも送金しやすくなるように作られたものです([BIP16](https://github.com/bitcoin/bips/blob/master/bip-0016.mediawiki))。P2SHのScriptPubKeyは以下のようになっています。

```
OP_HASH160 [20-byte-hash-value] OP_EQUAL
```

ScriptSigにスクリプトを移した分ScriptPubKeyはP2PKHに比べて単純なスクリプトになっていますね。それでは実際に`TxOut`を作ってみましょう。

```hs:app/Send.hs
  secKey <- fromJust <$> getWalletSecretKey

  let -- TxOutの作成
      balance = 200000000
      amount  =  20000000
      fee     =  10000000

      toAddress        = "2N8hwP1WmJrFF5QWABn38y63uYLhnJYJYTF"
      toPubKeyHashed   = fromJust $ decodeAddress toAddress
      fromPubKey       = exportPubKey False $ derivePubKey secKey
      fromPubKeyHashed = hash160 fromPubKey

      lockingScript1 = VarStr.fromByteString $ BS.concat [op_hash160, op_pushdata toPubKeyHashed,  op_equal]
      lockingScript2 = VarStr.fromByteString $ BS.concat [op_dup, op_hash160, op_pushdata fromPubKeyHashed, op_equalverify, op_checksig]

      txOut1 = TxOut amount                   lockingScript1
      txOut2 = TxOut (balance - amount - fee) lockingScript2
```

`decodeAddress`はアドレスをBase58からデコードしてPrefixを取る関数で以下のように定義しています。

```hs:src/Bitcoin/Wallet.hs
-- | addressから元の文字列を取得する
decodeAddress :: ByteString -> Maybe ByteString
decodeAddress address =
  case decodeBase58 bitcoinAlphabet address of
    Nothing -> Nothing
    Just bs ->
      let l         = BS.length bs
          payload   = BS.take (l - 4) bs
          checksum  = BS.drop (l - 4) bs
          checksum' = BS.take 4 . hash256 $ payload
       in if checksum == checksum'
             then Just $ BS.drop 1 payload
             else Nothing
```

lockingScriptの中で使用しているスクリプトは以下のように定義しています。

```hs:src/Bitcoin/Protocol/Script.hs
op_pushdata :: ByteString -> ByteString
op_pushdata bs =
  let size = BS.singleton . fromIntegral $ BS.length bs
   in size `BS.append` bs

op_dup, op_equal, op_equalverify, op_hash160, op_checksig :: ByteString
op_dup         = BS.singleton 0x76
op_equal       = BS.singleton 0x87
op_equalverify = BS.singleton 0x88
op_hash160     = BS.singleton 0xA9
op_checksig    = BS.singleton 0xAC
```

スクリプトの仕様がどのようになっているかは[Bitcoin wiki - Script](https://en.bitcoin.it/wiki/Script)が詳しいです。

### 署名の作成
さて次は`TxIn`で保留にしていたScriptSigを作りましょう。`OutPoint`で指定している`TxOut`はP2PKHで送金されているのでそれに対応したスクリプトを書く必要があります。具体的には以下の様なものです。

```
<このトランザクションの署名> <自分の公開鍵>
```

さっそく署名を作りたいところですが署名する対象のトランザクションはこの署名が無いと完成しません。どうすればいいでしょうか？不動点を求めれば良いのでしょうか（冗談ですw）？実はScriptSigに入れる署名を作る際は署名するTxInのScriptSigをOutPointで参照しているTxOutのScriptPubKeyで置き換え、それ以外のTxInのScriptSigを空にしたトランザクションを用意して署名をつくります（このような手順だとScriptSigは署名に含まれないため悪意を持ったノードはScriptSigにデータを追加することでトランザクションIDを変更することができます。このような脆弱性はトランザクション展性と呼ばれており、SegwitはScriptSigを`witness`に隔離してScriptSigを空にする事によりこの脆弱性を解決しています）。[Bitcoin Wiki - OP_CHECKSIG](https://en.bitcoin.it/wiki/OP_CHECKSIG)には[署名の検証方法の詳しい手順が解説してある図](https://en.bitcoin.it/wiki/File:Bitcoin_OpCheckSig_InDetail.png)があってとても参考になります。署名を作成するコードを見てみましょう。

```hs:app/Send.hs
  let -- 署名の作成
      subscript    = VarStr.fromByteString $ readHex "76a914aa8e6d2c98a67feba1c8eaed8bf1c168fc3ff74588ac"
      _tx          = Tx 1 [txIn subscript] [txOut1, txOut2] 0x00
      hashType     = BS.singleton 0x01
      hashTypeCode = BS.pack [0x01, 0x00, 0x00, 0x00]
      sign         = exportSig . signMsg secKey . fromJust . msg . hash256 $ BS.concat [BL.toStrict $ encode _tx, hashTypeCode]
      signWithType = sign `BS.append` hashType
```

subscriptとして指定しているものは`OutPoint`で参照している`TxOut`のScriptPubKeyでBitcoin Testnet ExplorerのJSONからコピーしてきました。`hashType`と`hashTypeCode`は[署名の作成手順の種類を表すコード](https://en.bitcoin.it/wiki/OP_CHECKSIG#How_it_works)でここでは`SIGHASH_ALL`を表す`0x00000001`を指定しています（リトルエンディアンなので`0x01`から始まっています）。

### Txの作成・送金
`TxIn`, `TxOut`, 署名まで作成できたのであとはこれらを組み合わせるだけで`Tx`ができます。`Tx`を作成したあとは接続先のノードに`inv`を送って`getdata`で作成した`Tx`へのリクエストを受け取ってから`tx`メッセージを送信します。図とコードで見てみましょう。


<img src="https://qiita-image-store.s3.amazonaws.com/0/17134/c759827d-74c0-9550-d4e9-fa16f0b64bed.png" width=300/>

まずは[inv](https://en.bitcoin.it/wiki/Protocol_documentation#inv)と[getdata](https://en.bitcoin.it/wiki/Protocol_documentation#getdata)メッセージの型を実装してみましょう。

```hs:app/Bitcoin/Protocol/Inv.hs
-- | Inventoryのリスト
newtype Inv = Inv (VarList Inventory)
  deriving (Show, Generic)

instance Binary Inv

instance Message Inv where
  commandName = "inv"

-- | ハッシュとそれが示すデータの種類
data Inventory = Inventory
  { invType :: InvType
  , hash    :: Chars 32
  } deriving (Show, Generic)

instance Binary Inventory

-- | Inventoryに含まれるデータの種類
data InvType = ERROR              -- エラー
             | MSG_TX             -- トランザクション
             | MSG_BLOCK          -- ブロック
             | MSG_FILTERED_BLOCK -- マークルブロック
             | MSG_CMPCT_BLOCK    -- コンパクトブロック
             deriving (Show, Eq)

instance Binary InvType where
  put ERROR              = putWord32le 0
  put MSG_TX             = putWord32le 1
  put MSG_BLOCK          = putWord32le 2
  put MSG_FILTERED_BLOCK = putWord32le 3
  put MSG_CMPCT_BLOCK    = putWord32le 4

  get = do
    _type <- getWord32le
    pure $ case _type of
      0 -> ERROR
      1 -> MSG_TX
      2 -> MSG_BLOCK
      3 -> MSG_FILTERED_BLOCK
      4 -> MSG_CMPCT_BLOCK
```

```hs:src/Bitcoin/Protocol/GetData.hs
-- | データを要求する
newtype GetData = GetData (VarList Inventory)
  deriving (Show, Generic)

instance Binary GetData

instance Message GetData where
  commandName = "getdata"
```

invメッセージでデータの種類とそのハッシュ値がリストになって送られてくるので、必要なものをフィルターした後にgetdataメッセージで要求するというのが基本の流れです。それでは`Tx`を送信するプログラムを実装してみましょう。


```hs:app/Send.hs
  let -- Txの作成
      unlockingScript = VarStr.fromByteString $ BS.concat [op_pushdata signWithType, op_pushdata fromPubKey]
      tx              = Tx 1 [txIn unlockingScript] [txOut1, txOut2] 0x00
      txId            = Tx.txId tx
      inv             = Inv [Inventory MSG_TX txId]

  sendMessage sock inv
  forever $ dispatch sock tx txId =<< recvMessageHeader sock
    where
      dispatch sock tx txId (name, size)
        | "getdata" `BS.isPrefixOf` name = do
            (GetData getdata) <- recvMessage sock size :: IO GetData
            let isTx inv = Inv.invType inv == MSG_TX && Inv.hash inv == txId
                inv = filter isTx $ VarList.elems getdata
            if null inv
               then pure ()
               else sendMessage sock tx
        | otherwise = () <$ (if size > 0 then recvMessage sock size :: IO ByteString else pure "")
```

invを送信したあとにforeverでデータを読み込んでdispatchするコードをぐるぐる回しています。`getdata`で送信したトランザクションのリクエストが来たら`tx`を送信します。

出来上がった`app/Send.hs`の一連のコードを改めて載せておきます。

```hs:app/Send.hs
sendBitcoin :: IO ()
sendBitcoin = withBitcoinConnection $ \(sock, version) -> do
  let -- TxInの作成
      outTxId  = toChars . BS.reverse $ readHex "35ba3ed9c42b1441d7f6da40f7bd9f81747b74e8b6f1e8ea040163fdf36d48f0"
      outPoint = OutPoint outTxId 0x00
      txIn xs  = TxIn outPoint xs 0xFFFFFFFF

  secKey <- fromJust <$> getWalletSecretKey

  let -- TxOutの作成
      balance = 200000000
      amount  =  20000000
      fee     =  10000000

      toAddress        = "2N8hwP1WmJrFF5QWABn38y63uYLhnJYJYTF"
      toPubKeyHashed   = fromJust $ decodeAddress toAddress
      fromPubKey       = exportPubKey False $ derivePubKey secKey
      fromPubKeyHashed = hash160 fromPubKey

      lockingScript1 = VarStr.fromByteString $ BS.concat [op_hash160, op_pushdata toPubKeyHashed,  op_equal]
      lockingScript2 = VarStr.fromByteString $ BS.concat [op_dup, op_hash160, op_pushdata fromPubKeyHashed, op_equalverify, op_checksig]

      txOut1 = TxOut amount                   lockingScript1
      txOut2 = TxOut (balance - amount - fee) lockingScript2
let -- 署名の作成
      subscript    = VarStr.fromByteString $ readHex "76a914aa8e6d2c98a67feba1c8eaed8bf1c168fc3ff74588ac"
      _tx          = Tx 1 [txIn subscript] [txOut1, txOut2] 0x00
      hashType     = BS.singleton 0x01
      hashTypeCode = BS.pack [0x01, 0x00, 0x00, 0x00]
      sign         = exportSig . signMsg secKey . fromJust . msg . hash256 $ BS.concat [BL.toStrict $ encode _tx, hashTypeCode]
      signWithType = sign `BS.append` hashType


  let -- Txの作成
      unlockingScript = VarStr.fromByteString $ BS.concat [op_pushdata signWithType, op_pushdata fromPubKey]
      tx              = Tx 1 [txIn unlockingScript] [txOut1, txOut2] 0x00
      txId            = Tx.txId tx
      inv             = Inv [Inventory MSG_TX txId]

  sendMessage sock inv
  forever $ dispatch sock tx txId =<< recvMessageHeader sock
    where
      dispatch sock tx txId (name, size)
        | "getdata" `BS.isPrefixOf` name = do
            (GetData getdata) <- recvMessage sock size :: IO GetData
            let isTx inv = Inv.invType inv == MSG_TX && Inv.hash inv == txId
                inv = filter isTx $ VarList.elems getdata
            if null inv
               then pure ()
               else sendMessage sock tx
        | otherwise = () <$ (if size > 0 then recvMessage sock size :: IO ByteString else pure "")
```

`Main.hs`から`sendBitcoin`を呼んで実行してみましょう。

```hs
main :: IO ()
main = do
  args <- getArgs
  if length args == 0
     then putStrLn "Please give subcommand wallet/send/balance."
     else case head args of
       "wallet"  -> showWallet
       "send"    -> sendBitcoin
```

```shell
$ runhaskell Main.hs send
Send: version 86
Recv: version 104
Send: verack 0
Recv: verack 0
Send: inv 37           <-- invの送信
Recv: sendheaders 0
Recv: sendcmpct 9
Recv: sendcmpct 9
Recv: ping 8
Recv: addr 31
Recv: getheaders 1061
Recv: feefilter 8
Recv: getdata 37       <-- getdataの受信
Send: tx 255           <-- txの送信！
^C
```

無事送信が完了したらBitcoin Testnet Explorerから[アドレスの情報](https://live.blockcypher.com/btc-testnet/address/mxMDYVc8B25SJvTeUtkU6r8ELkUpsNTDEj/)を確認しましょう。トランザクションが増えて`2 Transactions`になっていれば無事送信完了です。あとはブロックに取り込まれてConfirmされるのを待ちましょう。

### 番外編: トランザクション作成のためのデバッグ方法
トランザクション作成の実装はとても大変です。特に署名周りは間違った内容を送っても何も言われずに伝播もされないことが多々あるので本当に大変です…。一回間違った内容を送ったら次からversionを送っただけで接続を切られるようになったなんてこともあります（しばらくしたらまた繋がりました）。そんな中で僕が実装する際に役に立ったデバッグの方法を２つ紹介したいと思います。

#### TP's Go Bitcoin Tests
[TP's Go Bitcoin Tests](http://gobittest.appspot.com/)のWebサイトに行くとBitcoin Addressや秘密鍵からWIFの生成などのツールがWeb上で試せます。自分の実装が不安になった時は答え合わせしてみるといいでしょう。

#### rejectメッセージ
間違った内容を送ったらまれに接続先のノードが丁寧に[reject](https://en.bitcoin.it/wiki/Protocol_documentation#reject)メッセージとしてエラー内容を送り返してくれることがあります（Parse errorとかです）。以下のような型を用意してrejectを受け取って中身を見れるようにしておくと実装の役に立つと思います。

```hs:src/Bitcoin/Protocol/Reject.hs
-- | 受け取ったメッセージをRejectした時のメッセージ
data Reject = Reject
  { message :: VarStr -- Rejectの種類
  , ccode   :: Word8  -- Reject code
  , reason  :: VarStr -- Reject 理由
  , _data   :: BL.ByteString -- TX IDとかブロックヘッダが入る
  } deriving Show

instance Binary Reject where
  put x = do
    put               $ message x
    put               $ ccode   x
    put               $ reason  x
    putLazyByteString $ _data   x

  get = Reject
    <$> get
    <*> get
    <*> get
    <*> getRemainingLazyByteString

instance Message Reject where
  commandName = "reject"
```

Bitcoinの残高を確認する: merkletree
----------------------------------
さて、新しく作ったウォレットにFaucetから2.0BTCを受け取ってFaucetに0.2BTCを送り返して手数料に0.1BTC払ったのでこのウォレットに残っている残高は1.7BTCですよね？これを手で計算すること無くブロックチェーンから調べる機能を実装してみましょう。
ブロックの情報を受け取る時は[getblocks](https://en.bitcoin.it/wiki/Protocol_documentation#getblocks)メッセージを使います。仕様を元に`GetBlocks`の型を定義してみましょう。

```hs:src/Bitcoin/Protocol/GetBlocks.hs
-- | ブロックの情報を要求する
data GetBlocks = GetBlocks
  { version            :: Int32le            -- プロトコルのバージョン
  , blockLocatorHashes :: VarList (Chars 32) -- 取得を開始するブロックのハッシュ
  , hashStop           :: Chars 32           -- 取得を終わるブロックのハッシュ
  } deriving (Show, Generic)

instance Binary GetBlocks

instance Message GetBlocks where
  commandName = "getblocks"

-- | 全てのブロック(500個まで)を取得する時に指定するハッシュ
zeroHash :: Chars 32
zeroHash = Chars . fromJust . Vector.fromList $ replicate 32 0
```

`getblocks`に応答して`inv`でブロックハッシュが返ってきて`getdata`で要求すると[block](https://en.bitcoin.it/wiki/Protocol_documentation#block)メッセージでブロックの情報が返ってきます。しかしこのブロックの情報はブロックヘッダとブロックに含まれる全てのトランザクションの情報が含まれておりTestnetとはいえ1250000を超えるブロックが存在するので全てのブロックを取得するのは非効率的です。関心があるのは自分のアドレスに関係するトランザクションだけです。Bitcoinプロトコルではこんな時のために特定のトランザクションだけに関連する情報を受け取る機能が存在します。それがSPV(Simple Payment Verification)と呼ばれる仕組みです。SPVではブロックの全ての情報を受け取るのではなく関心のあるトランザクションだけが入ったブロックを受け取ります。しかしこれだけではそのトランザクションが本当にそのブロックに含まれているものかがわからないので、同時にマークルパスと呼ばれるハッシュのリストも受け取ります。

### Merkle tree
マークルパスについて理解するために[マークル木](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E6%9C%A8)を説明します。例えばブロックの中に5個のトランザクションが含まれていたときマークル木は以下のように構成されます。

```
# １段目
H1 -- tx1のハッシュ値（Tx ID）
H2 -- tx2のハッシュ値（Tx ID）
H3 -- tx3のハッシュ値（Tx ID）
H4 -- tx4のハッシュ値（Tx ID）
H5 -- tx5のハッシュ値（Tx ID）

# 2段目
H12 -- H1とH2を結合してハッシュ化
H34 -- H3とH4を結合してハッシュ化
H55 -- H5とH5を結合してハッシュ化

# 3段目
H1234 -- H12とH34を結合してハッシュ化
H5555 -- H55とH55を結合してハッシュ化

# 4段目
H12345555 -- H1234とH5555を結合してハッシュ化
```

木にするとこんな感じ。
<img src="https://qiita-image-store.s3.amazonaws.com/0/17134/260cb3bb-748f-a053-f98b-43f6b64fe119.png" width=300/>
要するにトランザクションのハッシュを一列に並べて２つずつ結合してハッシュ化するという操作を１つのハッシュになるまで繰り返します。端っこが一つ余った時は同じものを複製してハッシュ化します。Bitcoinプロトコルではブロックに含まれる全てのトランザクションでマークル木を作り、最後一つになったハッシュをマークルルート([merkle_root](https://en.bitcoin.it/wiki/Protocol_documentation#block))としてブロックヘッダに保存しています。

SPVでは例えば前述の例でH1とH5が検索条件にマッチして返ってきたとするとH2, H34のハッシュ値も返ってきます。
<img src="https://qiita-image-store.s3.amazonaws.com/0/17134/9968a0e3-c3ad-bd3f-54a0-da919b3548fa.png" width=300/>
これだけのハッシュがあれば再び結合して１つのハッシュ値を作り、それをマークルルートと比較することで本当にそのブロックに含まれるトランザクションかどうかを判定することができます。

### Bloom filter
そもそもどうやって接続先のノードにトランザクションを制限する条件を送るのでしょうか？例えば自分のアドレスに関係するトランザクションだけを送ってもらおうとして自分のアドレスを直接渡してしまうと、そのアドレスとノードが紐付けられて匿名性が下がるという危険があります。そこでBitcoinプロトコルではこのプライバシーの低下をある程度緩和するために[Bloom filter](https://ja.wikipedia.org/wiki/%E3%83%96%E3%83%AB%E3%83%BC%E3%83%A0%E3%83%95%E3%82%A3%E3%83%AB%E3%82%BF)を送るという方法が採用されています。

Bloom filterについて簡単に説明すると、例えば0,1を値に取る長さ10のビット配列と1~10の値を出力するハッシュ関数が3つあったとします。

```
ビット配列: [0,0,0,0,0,0,0,0,0,0]
ハッシュ関数: H1, H2, H3
```

この時、「りんご」という単語にヒットするBloom filterを次のように作ります。まずH1に「りんご」を適用した結果が5だったとします。するとビット配列の5番目の要素を1にします。同様にH2, H3それぞれが2,6を出力したとするとビット配列の2番目と6番目の要素を1にします。

```
H1(りんご) = 5
H2(りんご) = 2
H3(りんご) = 6

ビット配列: [0,1,0,0,1,1,0,0,0,0]
```

このBloom filterに「りんご」の文字が含まれているかを確かめる時はH1, H2, H3に「りんご」を適用して出てきた全ての数字に対応するビット配列の要素が１になっていることを確かめればいいでしょう。例えば「みかん」を使って調べるとH1, H2, H3が4, 7, 2を出力したとします。するとこのBloom filterは2番目以外の4番目と7番目は0なので「みかん」という文字列は含まれていないことがわかります。
さらに「みかん」もこのBloom filterに追加してみましょう。それにはビット配列の2, 4, 7番目の要素を1にするだけで可能です。

```
H1(みかん) = 4
H2(みかん) = 7
H3(みかん) = 2

ビット配列: [0,1,0,1,1,1,1,0,0,0]
```

ところで「ぶどう」をこのBloom filterに入っているか試そうとしたらH1, H2, H3が5, 6, 7を出力したとします。この時ビット配列の5, 6, 7番目は1が入っているので「ぶどう」もBloom filterに含まれていると判定されてしまいます。このようにBloom filterには偽陽性（含まれていないものも含まれていると判定される可能性）があります。この誤った判定が発生する割合はビット配列の長さとハッシュ関数の個数で調整することができ、Bitcoinプロトコルはこの偽陽性を使ってプライバシーの低下を防いでいます（逆に偽陰性が無いので受け取ったトランザクションには関心のあるトランザクションが全て含まれていることが保証されています）。

### filterload
それでは実際にBloom filterを関心のあるトランザクションだけ受け取るようにしてみましょう。Bloom filterは[filterload](https://en.bitcoin.it/wiki/Protocol_documentation#filterload.2C_filteradd.2C_filterclear.2C_merkleblock)というメッセージを使って送ります。さっそく型に写して実装してみましょう。

```hs:src/Bitcoin/Protocol/Filterload.hs
-- | Bloom filterを設定する
data Filterload = Filterload
  { filter       :: VarList Word8 -- Bloom filterのビット配列
  , nHashFuncs   :: Word32le      -- ハッシュ関数の個数
  , nTweak       :: Word32le      -- ハッシュ関数を生成する乱数
  , nFlags       :: Word8         -- Bloom filterの更新方法
  } deriving (Show, Generic)

instance Binary Filterload

instance Message Filterload where
  commandName = "filterload"

-- | ビット配列の長さ、ハッシュ関数の個数、含める文字列からFilterloadを作る
filterload :: Word32 -> Word32 -> [ByteString] -> IO Filterload
filterload size nHashFuncs queries = do
  nTweak <- withSystemRandom $ asGenIO uniform
  let seeds = map (\n -> n * 0xFBA4C795 + nTweak) [0 .. nHashFuncs - 1]
      bits = do
        seed  <- seeds
        query <- queries
        pure $ murmur3 seed query `mod` size
      bitArray = accum
        (\e a -> e .|. shiftL 1 (fromIntegral $ 7 .&. a))
        (listArray (0, size `div` 8 - 1) (repeat 0))
        (map (\i -> (shiftR i 3, i)) bits)
  pure $ Filterload (fromList $ elems bitArray) (Word32le nHashFuncs) (Word32le nTweak) 1
```

まず`filter`にはビット配列が入ります。型としては`VarList Word8`で表しているため`filterload`関数ではビット演算を用いて0,1を制御しています（ここの実装は[bitcoin - GitHub](https://github.com/bitcoin/bitcoin/blob/master/src/bloom.cpp#L58-L69)を参考にしました）。つぎに`nHashFuncs`と`nTweak`でハッシュ関数を生成します。ハッシュ関数の生成方法は[BIP37](http://techmedia-think.hatenablog.com/entry/2016/02/12/221225)にかかれている通り、

```
nHashNum * 0xFBA4C795 + nTweak
```

を初期値として`nHashFuncs`個の[Murmur3](https://en.wikipedia.org/wiki/MurmurHash)のハッシュ関数を生成します。Murmur3の実装には[murmur3](https://hackage.haskell.org/package/murmur3)というライブラリを使用しています。
この`filter`と`nHashFuncs`と`nTweak`の３つを送れば接続先のノードでも同じBloom filterを生成してくれてマッチしたトランザクションだけを送り返してくれるという仕組みです。Bloom filterの検証手順は以下の通りです。

1. トランザクションIDを検証
2. それぞれのTxOutのスクリプトのデータを一つずつ検証
3. それぞれのTxInのOutPointを検証
4. それぞれのTxInのスクリプトのデータを一つずつ検証
5. 以上でマッチしなければトランザクションを送らない

例えばP2PKHを想定してハッシュ化した公開鍵をBloom filterに入れておけば2でマッチしてそのトランザクションを送り返してくれるでしょう。実際はさらにそのトランザクションのTxOutを使用したトランザクションも送り返してくれるようになると、いちいちBloom filterを更新する必要がなくなって便利ですよね。`Filterload`の`nFlags`を使用すればそういった動作を実現しくれます。

|nFlags|挙動|
|:----:|:----|
|0|何も更新しない|
|1|scriptPubKeyのいずれかの要素にマッチしたらそのOutPointをBloom filterに追加する|
|2|P2PKかMultiSigの時のみ1と同様にBloom filｔerを更新する|

filterload関数ではnFlagsを1に設定して見つけたトランザクションのOutPointは自動的にBloom filterに追加してくれるようにしています。

### merkleblock
さて、filterloadでBloom filterを設定したらいよいよ必要なトランザクションだけを含んだブロックを受け取る準備ができました。このブロックは[merkleblock](https://en.bitcoin.it/wiki/Protocol_documentation#filterload.2C_filteradd.2C_filterclear.2C_merkleblock)メッセージで送られてきます。merkleblockメッセージを受け取るまでの手順は以下の通りです。
<img src="https://qiita-image-store.s3.amazonaws.com/0/17134/3de65d22-4781-5fb4-4e02-d29bb5c3925f.png" width=300/>

merkleblockを受け取るにはinvで受け取ったInventoryに`MSG_BLOCK`が含まれていたら、それを`MSG_FILTERED_BLOCK`に変換してgetdataで送り返します。merkleblockの型の実装を見てみましょう。

```hs:src/Bitcoin/Protocol/Merkleblock.hs
-- | マークルブロック
data Merkleblock = Merkleblock
  { version           :: Int32le            -- バージョン
  , prevBlock         :: Chars 32           -- 前のブロックのハッシュ値
  , merkleRoot        :: Chars 32           -- マークルルート
  , timestamp         :: Word32le           -- UNIXTIMESTAMP
  , bits              :: Word32le           -- 難易度
  , nonce             :: Word32le           -- ノンス
  , totalTransactions :: Word32le           -- ブロックに含まれるトランザクションの総数
  , hashes            :: VarList (Chars 32) -- マークルパスを構築するためのハッシュ列
  , flags             :: VarList Word8      -- ークルパスを構築するためのフラグ列
  } deriving (Show, Generic)

instance Binary Merkleblock

instance Message Merkleblock where
  commandName = "merkleblock"

-- | ブロックハッシュを計算する
blockHash :: Merkleblock -> Chars 32
blockHash = toChars . hash256 . BS.take 80 . BL.toStrict . encode
```

versionからnonceまでのデータをHash256することでブロックハッシュが得られます。固定長のフィールドだけなので`blockHash`関数では80文字とってきてハッシュ化するというズボラなことをしていますｗ

それではいよいよ今までの関数を組み合わせて自分のアドレスに関係あるトランザクションだけを取ってくるプログラムを書きたいと思います。

```hs:app/Balance.hs
showBalance :: IO ()
showBalance = withBitcoinConnection $ \(sock, version) -> do
  secKey <- fromJust <$> getWalletSecretKey
  let fromPubKey       = exportPubKey False $ derivePubKey secKey
      fromPubKeyHashed = hash160 fromPubKey

      -- 簡便のため高さ1255000のブロックから取得する
      startBlockHash = toChars . BS.reverse $ readHex "000000006ba819bcaa50e6fb2fb89deb4ff894068cbaf4b4b9b7e89f24ccdc2f"
      leftBlocks = fromIntegral $ Version.startHeight version - 1255000

  -- Bloom filterの設定
  sendMessage sock =<< filterload 1024 10 [fromPubKeyHashed]

  -- スレッドを別に立てて受け取ったブロックとトランザクションをMapに記録していく
  blockMapTVar <- newTVarIO Map.empty
  txMapTVar    <- newTVarIO Map.empty
  forkIO . forever $ dispatch sock (blockMapTVar, txMapTVar) =<< recvMessageHeader sock

  -- 目標の個数まで500個ずつブロックを取得していく
  let loop n = do
        threadDelay 100000 -- sleep 0.1s
        blockMap <- readTVarIO blockMapTVar
        if Map.size blockMap >= leftBlocks
           then pure blockMap
           else
             if Map.size blockMap >= n
                then do
                  let latestBlockHash = Merkleblock.blockHash . maximumBy (compare `on` Merkleblock.timestamp) $ Map.elems blockMap
                  sendMessage sock $ GetBlocks 70015 [latestBlockHash] zeroHash
                  loop (n + 500)
                else loop n
  sendMessage sock $ GetBlocks 70015 [startBlockHash] zeroHash
  blockMap <- loop 500

  print $ Map.size blockMap

  -- TODO: UTXOを取り出して残高を計算する

    where
      dispatch sock (blockMapTVar, txMapTVar) (name, size)
        | "inv" `BS.isPrefixOf` name = do
            (Inv inv) <- recvMessage sock size :: IO Inv
            -- MSG_BLOCKを受け取ったらMSG_FILTERED_BLOCKに変換する
            let toFilteredBlock x = if Inv.invType x == Inv.MSG_BLOCK then Inv.Inventory Inv.MSG_FILTERED_BLOCK (Inv.hash x) else x
                inv' = map toFilteredBlock $ VarList.elems inv
                hashes = map Inv.hash inv'
            sendMessage sock (GetData $ fromList inv')
        | "merkleblock" `BS.isPrefixOf` name = do
            block <- recvMessage sock size :: IO Merkleblock
            atomically . modifyTVar blockMapTVar $ Map.insert (Merkleblock.blockHash block) block
        | "tx" `BS.isPrefixOf` name = do
            tx <- recvMessage sock size :: IO Tx
            atomically . modifyTVar txMapTVar $ Map.insert (Tx.txId tx) tx
        | "reject" `BS.isPrefixOf` name = print =<< (recvMessage sock size :: IO Reject)
        | otherwise =
            if size > 0
               then () <$ (recvMessage sock size :: IO ByteString)
               else pure ()
```

一気に載せてしまいましたがやってることをざっくりと説明すると

1. ウォレットの公開鍵を取得
2. 1255000からversionで取得した接続先のノードが持ってる高さまでのブロックの個数を計算
3. filterloadメッセージを送ってBloom filterを設定
4. メッセージを受信してブロックとトランザクションを記録していく処理を別スレッドで立てる
5. getblocksで500個ずつ目標値までブロックを取得する

高さ1255000のブロックから取得を開始してるのは高さ1から始めると時間がかかるからで1255000という数字は適当です。getblocksメッセージはhashStopに全て0を設定するとブロックを500個まで全て返してくれます。この実装はgetdataが全てのデータを返してくれることが前提となっていますが実際は接続先のノードにどのようないたずらをされても動くようなコードを書かなければいけません。Bitcoinネットワークに繋げるときは基本的に周りは敵だらけだと思いましょうｗ

それではMainから`showBalance`を呼ぶようにして実行してみましょう。

```hs:app/Main.hs
main :: IO ()
main = do
  args <- getArgs
  if length args == 0
     then putStrLn "Please give subcommand wallet/send/balance."
     else case head args of
       "wallet"  -> showWallet
       "send"    -> sendBitcoin
       "balance" -> showBalance
```

```
$ runhaskell Main.hs balance
Send: version 86
Recv: version 102
Send: verack 0
Recv: verack 0
Send: filterload 138  <-- Bloom filterの設定
Send: getblocks 69    <-- ブロックの取得リクエスト
Recv: sendheaders 0
Recv: sendcmpct 9
Recv: sendcmpct 9
Recv: ping 8
Recv: addr 31
Recv: getheaders 1061
Recv: feefilter 8
Recv: inv 18003       <-- 送ってくれるブロックのハッシュ
Send: getdata 18003   <-- ブロック送信の要求
Recv: merkleblock 119 <-- マークルブロック！
Recv: merkleblock 119
...
Recv: merkleblock 119
Recv: merkleblock 119
853
```

うまく受け取れましたね！

### マークルパスの検証
さて、受け取ったマークルブロックのhashesにはトランザクションのハッシュもそうでないハッシュも一緒に含まれています。ここから関心のあるトランザクションのハッシュを取り出すには`totalTransactions`と`flags`を使ってマークルツリーを探索しなければなりません。

探索方法は、まず`totalTransactions`からマークル木の形がわかります。そしてルートから始めて`flags`に従って以下のルールで探索していきます。

|Flag|TX IDのノード|それ以外のノード|
|:----:|:----|:----|
|0|先頭のハッシュをこのノードのTXIDとする。このトランザクションはマッチしたものではない。|先頭のハッシュをこのノードのハッシュとする。これより下のノードは探索しない|
|1|先頭のハッシュをこのノードのTXIDとする。このトランザクションはマッチしたものである。|このノードのハッシュは計算されるべきものなので、まず左のノードから深さ優先で探索を進め、次に右のノードを探索し、最後にそれぞれのハッシュを結合してハッシュ化したものをこのノードのハッシュとする。|
参考: [Bitcoin Developer Reference - Parsing A MerkleBlock Message](https://bitcoin.org/en/developer-reference#parsing-a-merkleblock-message)
（リンク先にめっっっちゃわかりやすいGIFがあるので是非見て下さい）

この手順に従えばBloom filterに一致したトランザクションとマークルルートを計算することができます。実装してみましょう。

```hs:src/Bitcoin/Protocol/Merkletree.hs
-- | Word8で表現されているFlagsをBoolのリストに変換する
unpack :: Word8 -> [Bool]
unpack w = map (==1) $ map (\b -> (w `div` 2^b) `rem` 2) [0..7]

-- | 特定のノード数を持つマークル木の特定の高さの幅を計算する
calcTreeWidth :: Word32le -> Int -> Int
calcTreeWidth nTransactions height = (fromIntegral nTransactions + (1 `shiftL` height) - 1) `shiftR` height

-- | マークルパスを検証しマッチしたトランザクションを取り出す
validate :: Merkleblock -> Maybe [Chars 32]
validate block =
  let hs = VarList.elems $ hashes block
      fs = concatMap unpack . VarList.elems $ flags block
      ctw = calcTreeWidth (totalTransactions block)
      height = ceiling $ logBase 2 (fromIntegral $ totalTransactions block)
      (root, (_, _, ms)) = State.runState (accum ctw height 0) (hs, fs, [])
   in if root == toByteString (merkleRoot block) -- マークルルートが一致することを確認する
         then Just ms
         else Nothing
  where
    accum :: (Int -> Int) -> Int -> Int -> State ([Chars 32], [Bool], [Chars 32]) ByteString
    accum ctw height pos = do
      (h:hs, f:fs, ms) <- State.get
      case (f, height == 0) of
        -- 表の手順に従って探索する
        (False, _)     -> State.put (hs, fs,   ms) >> pure (toByteString h)
        (True, True)   -> State.put (hs, fs, h:ms) >> pure (toByteString h)
        (True, False)  -> do
          State.put (h:hs, fs, ms)
          left <- accum ctw (height - 1) (2 * pos)
          -- 幅が奇数個しか無かったら端のノードを複製してハッシュを計算する
          if ctw (height - 1) > 2 * pos + 1
             then do
               right <- accum ctw (height - 1) (2 * pos + 1)
               pure $ hash256 (BS.concat [left, right])
             else pure $ hash256 (BS.concat [left, left])
```

[bitcoin - GitHubのmerkleblock.cpp](https://github.com/bitcoin/bitcoin/blob/master/src/merkleblock.cpp#L40-L58)を参考に実装しています。

### UTXO
マークルブロックからトランザクションを取り出すところまでできたので、あとは残高を計算するために未だ使用されていないトランザクションのTxOutを集める必要があります。Bitcoinの世界ではこの未だ使用されていないトランザクションのTxOutのことをUTXO(Unspent Transaction Output)と呼びます。UTXOを計算するために必要な関数を実装しておきます。

```hs:src/Bitcoin/Protocol/Tx.hs
-- | 与えられた公開鍵をP2PKHのアウトプットに持つTxOutのインデックスを取得する
-- | 存在しなければNothingとなる
findP2PkhIndex :: ByteString -> Tx -> Maybe Word32le
findP2PkhIndex pkh tx =
  let scripts     = map (VarStr.string . pkScript) . VarList.elems $ txOut tx
      p2PkhHeader = BS.concat [op_dup, op_hash160]
      isP2Pkh     = BS.isPrefixOf p2PkhHeader
      getPkh      = BS.take 20 . BS.drop (BS.length p2PkhHeader + 1)
   in (fromIntegral . snd) <$> (find ((pkh ==) . getPkh . fst) . filter (isP2Pkh . fst) $ zip scripts [0..])

-- | トランザクションが与えられたOutPointを持つか調べる
hasOutPoint :: OutPoint -> Tx -> Bool
hasOutPoint op tx = elem op . map previousOutput . VarList.elems $ txIn tx

-- | 与えられたインデックスのTxOutのvalueを取得する
valueAt :: Word32le -> Tx -> Int64le
valueAt index tx = value $ (VarList.elems $ txOut tx) !! (fromIntegral index)
```

これらを使ってTODOとして残しておいた箇所を実装します。

```hs:app/Balance.hs
  -- マークルブロックからトランザクションを取り出しまだデータを取得していないトランザクションを列挙する
  txMap <- readTVarIO txMapTVar
  let txs = concat . fromJust . sequence . map Merkleblock.validate $ Map.elems blockMap
      unknowns = filter (isNothing . flip Map.lookup txMap) txs

  -- データを取得していないトランザクションのデータを取得する
  sendMessage sock (GetData . fromList $ map (Inventory Inv.MSG_TX) unknowns)
  txMap <- fix $ \loop -> do
    threadDelay 100000 -- sleep 0.1s
    txMap <- readTVarIO txMapTVar
    if and $ map (isJust . flip Map.lookup txMap) unknowns
       then pure txMap
       else loop

  -- UTXOを計算する
  let txs = Map.elems txMap
      myTxs = do
        tx <- txs
        case findP2PkhIndex fromPubKeyHashed tx of
          Just index -> [(tx, index)]
          Nothing    -> []
      utxo = do
        (tx, index) <- myTxs
        let op = OutPoint (Tx.txId tx) index
        guard $ and (map (not . (hasOutPoint op)) txs)
        pure (tx, index)
      balance = sum $ map (\(tx, index) -> valueAt index tx) utxo
  putStrLn $ "残高: " ++ show balance
```

実行してみましょう。

```
$ runhaskell Main.hs balance
Send: version 86
Recv: version 102
Send: verack 0
Recv: verack 0
Send: filterload 138
Send: getblocks 69
...
Recv: merkleblock 119
Recv: merkleblock 119
Recv: merkleblock 119
Recv: merkleblock 119
Recv: merkleblock 119
856
Send: getdata 1
残高: Int64le 170000000
```

めでたく想定通りの `170000000` が表示されましたね :clap: 

実際にブロックやトランザクションを受け取った時は間違った情報を掴まされてあとで痛い目を見ないように検証のルールが定められています。[Bitcoin wiki - Protocol rules](https://en.bitcoin.it/wiki/Protocol_rules)。今回は細かいところまでは実装しませんでしたが本気でクライアントを作る時はこのルールに従った検証を行うのが必須でしょう。

あとは計算したUTXOを使って送り先と金額を指定するだけで送金できる機能を作れば簡単なSPVウォレットの機能は一通り実装できたかなと思います。これに関しては今までの内容とちょっとの努力で実装できるかなと思うので読者への課題とさせて下さい（ここで力尽きる…）

あとがき
-------
Bitcoinプロトコルについて一つ一つの概念は理解していたつもりでしたが実際に実装してみると思わぬところでつまづき乗り越えるたびにさらに理解が深まりました。ということでこの記事を書くにあたって躓いた実装ランキングを発表します！！！

まずは第三位！ **トランザクションの送信**！
送れない！送れない！ちゃんと署名してるのに！あ、hashTypeCodeつけるの忘れてた…（6時間経過）

次に第二位！ **filterload**！
ドキュメントによって！書かれてるfilterの仕様が違う！！
[Bitcoin wiki - filterload](https://en.bitcoin.it/wiki/Protocol_documentation#filterload.2C_filteradd.2C_filterclear.2C_merkleblock)のfilterの型は`?`（?って何!?）
[Bitcoin Developer Refernce](https://bitcoin.org/en/developer-reference#filterload)はfilterの前にvar_intがついてる（こっちが正解）
（8時間経過）

そして第一位！ **merkleblock**！
マークルパスって全部のハッシュが返ってくるんじゃないの!?順番にハッシュ関数を適用すればいいだけだと思ってた／(^o^)＼
最終的に[Bitcoin Developer ReferenceのGIF](https://bitcoin.org/en/developer-reference#parsing-a-merkleblock-message)に救われました。
結論、Bitcoin Developer Referenceは神！（12時間経過）

これからもHaskellで楽しいブロックチェーンライフを送っていきましょう(^^)/

:books: 参考文献
----------------
* [Bitcoin Wiki - Protocol documentation](https://en.bitcoin.it/wiki/Protocol_documentation)
* [Bitcoin Developer Guide](https://bitcoin.org/en/developer-guide)
* [Bitcoins the hard way: Using the raw Bitcoin protocol](http://www.righto.com/2014/02/bitcoins-hard-way-using-raw-bitcoin.html)
* [bitcoinのしくみ - Bitcoinウォレットを実装する](http://bitcoin.peryaudo.org/implement.html)
* [bitcoin/bitcoin: Bitcoin Core integration/staging tree](https://github.com/bitcoin/bitcoin)

[^1]: 2017/12/23現在では180万円まで下落しています。
[^2]: [How do Bitcoin clients find each other?](https://bitcoin.stackexchange.com/questions/3536/how-do-bitcoin-clients-find-each-other)
[^3]: こちらの記事がオススメです！ [Haskellらしさって？「型」と「関数」の基本を解説！【第二言語としてのHaskell】](https://employment.en-japan.com/engineerhub/entry/2017/08/25/110000)
[^4]: [What is TxIn's sequence?](https://bitcoin.stackexchange.com/questions/2025/what-is-txins-sequence)