Edited at
HaskellDay 18

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

More than 1 year has passed since last update.

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

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


  • ウォレットの作成

  • Bitcoinの送金

  • 残高の確認

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

完成したコードはGitHubにもアップロードしているのでそちらも参照してみて下さい。

https://github.com/lotz84/bitcoin-spv-wallet


Bitcoinネットワーク

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

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


Bitcoinの国の挨拶: version, verack

知ってる人に会ったらまずは挨拶をしますよね?同じようにBitcoinネットワークに繋いだらまずはハンドシェイクを行います。ハンドシェイクはお互いにversionというメッセージを送ってverackというメッセージを返す、それだけです。

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


基本的なデータ型

実際にバイナリメッセージでハンドシェイクを行う前にいくつかの準備をしておきましょう。まずBitcoinプロトコルでの数値は基本的にリトルエンディアンで扱われます。なのでリトルエンディアンでエンコードされる数値の型を定義しておきましょう。バイナリを取り扱うライブラリにはbinaryを使用します。


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)の型を定義してみましょう。var_intは最初の1バイトで数値の長さが指定されており、0xFDより小さければそのままの数値を、0xFDであればuint16_tを、0xFEであればuint32_tを、0xFFであればuint64_tの数値が後に続きます。


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)を定義しましょう。これはまず文字列の長さを表すvar_intがあってその後に文字列が続きます。


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プロトコルにはよくあります。これも型として切り出しておきましょう。


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のVectorを使って固定長文字列を表す型を定義しておきましょう。


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


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

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


Bitcoinプロトコルの基礎

Bitcoinプロトコルのメッセージはヘッダーとペイロードから構成されています。ペイロードの部分はメッセージによって変わってきますがヘッダーは全てのメッセージに共通で以下のようになっています。

項目

説明

magic
uint32_t
ネットワーク毎に固有の値

commandName
char[12]
メッセージの名前("verack"等)

payloadSize
uint32_t
ペイロードのバイト数

checksum
char[4]
チェックサム

参考: Bitcoin Developer Reference - Message Headers

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


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メッセージのペイロードを定義してみましょう。


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"


NetAddrNetwork Addressを表す型で以下のようになっています。


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プロトコルの中で唯一ビッグエンディアンで扱われる数値です。

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


src/Bitcoin/Types.hs

class Message a where

commandName :: ByteString

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


src/Bitcoin/Protocol/Verack.hs

data Verack = Verack

deriving (Show, Generic)

instance Binary Verack

instance Message Verack where
commandName = "verack"


verackメッセージにはペイロードがないのでとても簡素な実装になっています。

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


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

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

hash256はハッシュ関数のsha256を2回適用したものでcryptoniteを使って以下のように定義しています。


src/Bitcoin/Hash.hs

sha256 :: ByteString -> ByteString

sha256 bs = convert (Crypto.hash bs :: Digest SHA256)

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


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


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の実装を参考にしています。

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


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 ""

$ 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

sendheadersBIP130で追加されたメッセージです。Bicoinプロトコルでデータを送る際はまず送るデータの種類とヘッダーだけが入ったinvメッセージを送って欲しい情報だけ精査してgetdataメッセージとして送り返してもらった後にデータを送るのが基本です。新しくマイニングされたブロックの情報も当然この手順に従って送信されます。さらに新しくブロックがマイニングされた時はそのブロックがマイニングされたチェーンの一連のヘッダー情報も同時にリクエストします。

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


sendcmpct

sendcmpctBIP152で追加されたメッセージです。Bitcoinネットワーク上でブロックの情報を効率よく伝播させるための仕組みです。以下の記事で詳しく解説されているので参照してみて下さい。

Block受信時に重複したトランザクションの受信を抑制するCompact Block(BIP-152)


ping

pingはノードと正常につながっているかどうかを確認するために使われるメッセージです。pingを受け取ったらメッセージの中にnonceが入っているのでpongの中に受け取ったnonceを入れて送り返しましょう。


getheaders

getheadersは持っているブロックチェーンのブロックヘッダーの情報を送って欲しい時に送るメッセージです。 ブロックの情報が欲しい時はgetblocksというメッセージも使われますがgetheadersはヘッダーの情報しか含まれていない分getblocksよりも多くの情報を受け取ることができます。


feefilter

feefilterは一定以上の手数料しか払っていないトランザクションは送ってこなくていいという意思を表明するためのメッセージでBIP133で提案されました。手数料が極端に低いトランザクションを大量に処理することになって効率が落ちることを防ぐために用意されています。


addr

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


Bitcoinの財布を自分で作る: Secp256k1

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

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

トランザクションの構造


説明

version


バージョン情報

TxIn
TxIn1
Outpoint
使用するトランザクションのTxOutへの参照

ScriptSig
OutPointが指すTxOutが自分への送金であることを証明するスクリプト

...

TxOut
TxOut1
Value
送金する金額

ScriptPubKey
送金先の人にしか証明できないスクリプト

...

lock_time


このトランザクションが有効になる時間

txメッセージの構造をざっくりと表にしてみました。誰から送られてきたお金を(TxIn)誰に送金するのか(TxOut)という情報が含まれているのがわかると思います。このトランザクションを受け取ったノードはどのように検証作業を行うのでしょうか。いろいろと確認項目はありますが、一番大事なのはTxInに指定されているScriptSig(Unlocking Script)が正しく参照しているTxOutのScriptPubKey(Locking Script)を解錠できているかということです。

ScriptSig, ScriptPubKeyの例としてP2PKHを見てみましょう。これはScriptPubKeyとして

OP_DUP OP_HASH160 <PubkeyHash> OP_EQUALVERIFY OP_CHECKSIG

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

<Sig> <PubKey>

のようなスクリプトを使用するものです。<PubKeyHash>は自分が持つ公開鍵をハッシュ化したもの、<PubKey>は自分の公開鍵、<Sig>は自分の秘密鍵を使ってトランザクションを署名したもので、OP_DUPなどのOP_から始まる命令はあらかじめ定義されているBitcoinプロトコルで使える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と呼ばれる楕円曲線暗号が使われています。


app/Wallet.hs

-- | Secp256k1の秘密鍵を生成する

genSecKey :: IO SecKey
genSecKey = do
bs <- getRandomBytes 32
case secKey bs of
Just sk -> pure sk
Nothing -> genSecKey

cryptoniteのgetRandomBytesを使ってランダムな文字列を生成し、secp256k1のsecKeyを使ってそれがSecp256k1の秘密鍵として使えるか判定して、秘密鍵が生成されるまで繰り返しています。作った秘密鍵はそのまま保存しても構いませんが簡便のためWIFと呼ばれる形式に変換して保存します。


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を利用しています。

WIFへの変換手順

No.
手順

1
WIFに変換する秘密鍵
0C28FCA386C7A227600B2F...

2
先頭にネットワークを表す1バイトの文字を付ける

EF0C28FCA386C7A227600B2FE50B7CAE...

3
Hash256に適用する
507A5B8DFED0FC6FE88017...

4
先頭4バイトの文字を取る
507A5B8D

5
2と3を結合する
EF0C28FCA386C7A227600B2F...507A5B8D

6
Base58でエンコードする
5HueCGU8rMjxEXxiPuD5BDku4MkFqe...

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


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アドレスと呼ばれる読みやすい公開鍵のフォーマットが定められています。

-- | 公開鍵を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と呼ばれるハッシュ関数に適用するものです。以下のように実装しています。


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


ウォレットの作成

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


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も後を見越して少し修正しておきます。


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

実行してみます。

$ 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


ウォレットへの送金

Bitcoinアドレスを作ったのでさっそく送金してみましょう。Faucetという仕組みを利用してTestnetのBitcoinを手に入れます。利用するFaucetはBitcoin Testnet Sandboxです。

image.png

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

Sent! TX ID: 247b3712423da29dcdcf1819e53e1eb0da4bd117a7205fb90b5014d881a14df2

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

image.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の仕様を参考に型を定義してみましょう。


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という仕様に使われるデータです。ですがまだ取引所や普及しているウォレットの対応が進んでいないためSegwitの送金トランザクションはあまり見かけません。大手取引所Coinbaseが対応を進めていたり、iOSで普及しているBreadが来年1月に対応するらしいので来年から徐々にSegwitのトランザクションが増えていくのではないでしょうか。エンジニア的な視点からすると双方向ペイメントチャネルシュノア署名MASTなどの実装が容易になるためSegwitの普及は進んで欲しいと思っています。


TxInの作成

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

次にTxInを作ります。TxInにはOutPointという使いたいBitcoinが送られてきたトランザクションのTxOutを指定するデータがあります。今はまだ必要なデータをブロックチェーンから取得できているわけではないので先ほどのBitcoin Testnet Explorerを利用して必要な情報を取ってきましょう。さっきのトランザクションのページにアクセスしてAdvanced Detailというボタンを押して出てきた画面の中の</> API Callをクリックします。すると以下のURLでトランザクションの情報がJSONで取得できると思います。

https://api.blockcypher.com/v1/btc/test3/txs/247b3712423da29dcdcf1819e53e1eb0da4bd117a7205fb90b5014d881a14df2?limit=50&includeHex=true

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

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


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. いくら手数料を支払うのか

の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)。P2SHのScriptPubKeyは以下のようになっています。

OP_HASH160 [20-byte-hash-value] OP_EQUAL

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


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を取る関数で以下のように定義しています。


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の中で使用しているスクリプトは以下のように定義しています。


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が詳しいです。


署名の作成

さて次は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には署名の検証方法の詳しい手順が解説してある図があってとても参考になります。署名を作成するコードを見てみましょう。


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からコピーしてきました。hashTypehashTypeCode署名の作成手順の種類を表すコードでここではSIGHASH_ALLを表す0x00000001を指定しています(リトルエンディアンなので0x01から始まっています)。


Txの作成・送金

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

まずはinvgetdataメッセージの型を実装してみましょう。


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



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を送信するプログラムを実装してみましょう。


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の一連のコードを改めて載せておきます。


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を呼んで実行してみましょう。

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

$ 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からアドレスの情報を確認しましょう。トランザクションが増えて2 Transactionsになっていれば無事送信完了です。あとはブロックに取り込まれてConfirmされるのを待ちましょう。


番外編: トランザクション作成のためのデバッグ方法

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


TP's Go Bitcoin Tests

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


rejectメッセージ

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


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メッセージを使います。仕様を元にGetBlocksの型を定義してみましょう。


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メッセージでブロックの情報が返ってきます。しかしこのブロックの情報はブロックヘッダとブロックに含まれる全てのトランザクションの情報が含まれておりTestnetとはいえ1250000を超えるブロックが存在するので全てのブロックを取得するのは非効率的です。関心があるのは自分のアドレスに関係するトランザクションだけです。Bitcoinプロトコルではこんな時のために特定のトランザクションだけに関連する情報を受け取る機能が存在します。それがSPV(Simple Payment Verification)と呼ばれる仕組みです。SPVではブロックの全ての情報を受け取るのではなく関心のあるトランザクションだけが入ったブロックを受け取ります。しかしこれだけではそのトランザクションが本当にそのブロックに含まれているものかがわからないので、同時にマークルパスと呼ばれるハッシュのリストも受け取ります。


Merkle tree

マークルパスについて理解するためにマークル木を説明します。例えばブロックの中に5個のトランザクションが含まれていたときマークル木は以下のように構成されます。

# 1段目

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を結合してハッシュ化

木にするとこんな感じ。



要するにトランザクションのハッシュを一列に並べて2つずつ結合してハッシュ化するという操作を1つのハッシュになるまで繰り返します。端っこが一つ余った時は同じものを複製してハッシュ化します。Bitcoinプロトコルではブロックに含まれる全てのトランザクションでマークル木を作り、最後一つになったハッシュをマークルルート(merkle_root)としてブロックヘッダに保存しています。

SPVでは例えば前述の例でH1とH5が検索条件にマッチして返ってきたとするとH2, H34のハッシュ値も返ってきます。



これだけのハッシュがあれば再び結合して1つのハッシュ値を作り、それをマークルルートと比較することで本当にそのブロックに含まれるトランザクションかどうかを判定することができます。


Bloom filter

そもそもどうやって接続先のノードにトランザクションを制限する条件を送るのでしょうか?例えば自分のアドレスに関係するトランザクションだけを送ってもらおうとして自分のアドレスを直接渡してしまうと、そのアドレスとノードが紐付けられて匿名性が下がるという危険があります。そこでBitcoinプロトコルではこのプライバシーの低下をある程度緩和するためにBloom filterを送るという方法が採用されています。

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に「りんご」を適用して出てきた全ての数字に対応するビット配列の要素が1になっていることを確かめればいいでしょう。例えば「みかん」を使って調べると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というメッセージを使って送ります。さっそく型に写して実装してみましょう。


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を参考にしました)。つぎにnHashFuncsnTweakでハッシュ関数を生成します。ハッシュ関数の生成方法はBIP37にかかれている通り、

nHashNum * 0xFBA4C795 + nTweak

を初期値としてnHashFuncs個のMurmur3のハッシュ関数を生成します。Murmur3の実装にはmurmur3というライブラリを使用しています。

このfilternHashFuncsnTweakの3つを送れば接続先のノードでも同じBloom filterを生成してくれてマッチしたトランザクションだけを送り返してくれるという仕組みです。Bloom filterの検証手順は以下の通りです。


  1. トランザクションIDを検証

  2. それぞれのTxOutのスクリプトのデータを一つずつ検証

  3. それぞれのTxInのOutPointを検証

  4. それぞれのTxInのスクリプトのデータを一つずつ検証

  5. 以上でマッチしなければトランザクションを送らない

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

nFlags
挙動

0
何も更新しない

1
scriptPubKeyのいずれかの要素にマッチしたらそのOutPointをBloom filterに追加する

2
P2PKかMultiSigの時のみ1と同様にBloom filterを更新する

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


merkleblock

さて、filterloadでBloom filterを設定したらいよいよ必要なトランザクションだけを含んだブロックを受け取る準備ができました。このブロックはmerkleblockメッセージで送られてきます。merkleblockメッセージを受け取るまでの手順は以下の通りです。

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


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文字とってきてハッシュ化するというズボラなことをしていますw

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


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ネットワークに繋げるときは基本的に周りは敵だらけだと思いましょうw

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


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にはトランザクションのハッシュもそうでないハッシュも一緒に含まれています。ここから関心のあるトランザクションのハッシュを取り出すにはtotalTransactionsflagsを使ってマークルツリーを探索しなければなりません。

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

Flag
TX IDのノード
それ以外のノード

0
先頭のハッシュをこのノードのTXIDとする。このトランザクションはマッチしたものではない。
先頭のハッシュをこのノードのハッシュとする。これより下のノードは探索しない

1
先頭のハッシュをこのノードのTXIDとする。このトランザクションはマッチしたものである。
このノードのハッシュは計算されるべきものなので、まず左のノードから深さ優先で探索を進め、次に右のノードを探索し、最後にそれぞれのハッシュを結合してハッシュ化したものをこのノードのハッシュとする。

参考: Bitcoin Developer Reference - Parsing A MerkleBlock Message

(リンク先にめっっっちゃわかりやすいGIFがあるので是非見て下さい)

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


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を参考に実装しています。


UTXO

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


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として残しておいた箇所を実装します。


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。今回は細かいところまでは実装しませんでしたが本気でクライアントを作る時はこのルールに従った検証を行うのが必須でしょう。

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


あとがき

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

まずは第三位! トランザクションの送信

送れない!送れない!ちゃんと署名してるのに!あ、hashTypeCodeつけるの忘れてた…(6時間経過)

次に第二位! filterload

ドキュメントによって!書かれてるfilterの仕様が違う!!

Bitcoin wiki - filterloadのfilterの型は?(?って何!?)

Bitcoin Developer Refernceはfilterの前にvar_intがついてる(こっちが正解)

(8時間経過)

そして第一位! merkleblock

マークルパスって全部のハッシュが返ってくるんじゃないの!?順番にハッシュ関数を適用すればいいだけだと思ってた/(^o^)\

最終的にBitcoin Developer ReferenceのGIFに救われました。

結論、Bitcoin Developer Referenceは神!(12時間経過)

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


:books: 参考文献