2018-03-24

Bitcoin Cashのブロック伝搬速度を10倍にするGrapheneで使われているInvertible Bloom Lookup Tables(IBLT)について調べてみた

Bitcoin Cashのブロック伝搬速度を10倍にするという話もあるGrapheneでも使われている Invertible Bloom Lookup Tables(以下、IBLT)について調べました。

背景

IBLTはもともと集合一致などで使われるデータ構造です。ブロックチェーンに限った技術ではありませんが、ここではGrapheneでも導入として話される内容で述べます。

まず、マイナーがBTCやBCHのブロックをマイニングする際には、各マイナーノードが持つmempoolから一定のポリシー(feeが高い順など)に基づき、ユーザのトランザクション(以下、tx)を選びます。

ところが各マイナーが持っているmempoolは完全に同期しておらず、マイナーは新しいブロックを見つけたら(マイニングに成功したら)、そのブロックに含んでいるtxもブロードキャストする必要があります。Grapheneはこの「ブロックに含まれるtxを伝搬するコスト」を下げたいことがモチベーションとなります。

仮に完全にmempoolが同期できており、同じポリシーでtxを選ぶならtxをブロードキャストする必要もありません。例えば、「feeが高い順にtotal block sizeがxxMBまで」というポリシーに基づいて、同期されたmempoolからtxを選べば、新しいブロックに含まれるtxは確定できるため、わざわざ伝達してあげる必要もありません。

しかし、上述の通り、mempoolは完全に同期できてはいません。とはいえ、各マイナーが持つmempoolはほとんど同じです。この前提のときに効率的にmempoolという集合の差分を伝え、集合一致させる技術がIBLTです。

BloomFilterとIBLT

IBLTは、BloomFilterと多数の類似性を持つため、BloomFiterと比較し、IBLTをみていきます。まず、一般的なBloomFilterでは、以下の操作をサポートします。

keyのInsert
kyeのGet

counting BloomFilterでは、空間効率性を少々犠牲にし、

keyのDelete

も可能にします。

※BloomFilterについては、以前の記事や実装(と要素技術)を参照ください。

対して、IBLTでは、以下の操作をサポートします。

(key, value)のInsert
(key)のGet
(key, value)のDelete
ListEntries

特筆すべきはListEntriesで、IBLTに含まれるkey-value pairを列挙することができます。 ListEntriesの利用方法を見るために、 Bitcoin block propagation with IBLT, Part I: infographicを参考にブロックチェーンでどのようにIBLTが使われるのか見てみたいと思います。リンク先の図を見ながらだとわかりやすいと思います。

IBLTを使った集合一致

集合一致までの流れを箇条書きで記載します。

マイナーは、複数のtxを含めたブロックを生成
各txをkey-value pairとしてIBLTに割り当てる
k個のハッシュ関数でkeyに対するハッシュ値を計算し、ハッシュ値をindexと思って各txをIBLTのcellに格納
3.で作成したIBLTをブロードキャスト
IBLTを受け取ったマイナーは自分のmempoolから1.のminerと同じポリシーでtxを選ぶ（ただし、mempoolは完全に同期しているわけでないので、同じtxが選ばれるとは限らない）
選んだtxたちに対して、2.,3.と同じ操作で、受信側のマイナーでもIBLTを作成
ListEntriesによって3.のIBLTのkey-value pairを列挙し、6.のIBLTからDeleteしていく
7.の操作で選んだtxの差分が得られる

Grapheneでは、上記を効率的に行うために、BloomFilterを差分を計算する補助として使っています。BloomFilterは、false-positiveはあってもfalse-negativeは原理的にないので、受信側でIBLTを作る時のフィルタとして使っているようです。

長くなってしまったので、IBLTのデータ構造やサポートされる各操作の実装は次回の記事にまとめます。

References

2018-03-17

Atom gotestsでレシーバがあったときにテストが自動生成されないバグを直した話

Atom gotestsでレシーバがあったときにテストが生成されないバグを直した話

少し前に以下のツイートをし、Atom pluginのgotestsを使ってユニットテストの自動生成をしてました。

goのテスト自動生成ツール。めっちゃ便利。すごい。https://t.co/15Fd5sq2VI
— さいぺ (@cipepser) 2018年2月25日

ところがタイトルにあるように、レシーバがあるようなfuncでは、テストが自動生成されませんでした。

実際にテストを生成しているのはcweillのgotestsで、 (例ですが)以下のようにコマンドラインで実行すると、レシーバありでも問題なく、テストが生成されました。

❯ gotests -w -only=Hello ./hello.go

ご想像の通りplugin側に問題があったので、修正しました。 PRを送り、無事マージされたので同じような問題で困っている方がいれば最新版へアップデートして、利用してみてください。

References

2018-03-11

【Golang】gobで変数をファイルに保存する

gobは、Go専用のバイナリシリアライズフォーマットです。シリアライズフォーマットとしては、Protocol Buffers¹がデファクトでしょうし、Go専用のgobは他の言語で扱えず、使い勝手としても難しいところです。しかし、Goしか使っていないような環境で、変数をファイルに保存したい場合などでは便利なので、備忘メモとしてもまとめたいと思います。

考え方は、Gobs of data - The Go Blog やencoding/gobでinterface{}をシリアライズするがとても参考になりました。

また、Redditでも議論されているように、structのsliceをdeep copyしたいときの手段としてgobが有用そうです。

概要

gobは、encoding/gobに標準パッケージとして用意されています。使う際も NewEncoder(w io.Writer)とNewDecoder(r io.Reader)が用意されているので、jsonを扱うときと同じ要領で扱うことができます。

今回は、以下で定義したPerson型の変数をファイルへ保存、ファイルから復元してみます。

type Person struct {
    Name string
    Age  int
}

ファイルへ保存

package main

import (
    "encoding/gob"
    "log"
    "os"
)

type Person struct {
    Name string
    Age  int
}

func main() {
    p := Person{
        "Alice",
        20,
    }

    f, err := os.Create("./save.txt")
    if err != nil {
        log.Fatal(err)
    }
    defer f.Close()
    enc := gob.NewEncoder(f)

    if err := enc.Encode(p); err != nil {
        log.Fatal(err)
    }
}

ファイルから復元

package main

import (
    "encoding/gob"
    "fmt"
    "log"
    "os"
)

type Person struct {
    Name string
    Age  int
}

func main() {
    f, err := os.Open("./save.txt")
    if err != nil {
        log.Fatal(err)
    }
    defer f.Close()

    var q Person
    dec := gob.NewDecoder(f)
    if err := dec.Decode(&q); err != nil {
        log.Fatal("decode error:", err)
    }

    fmt.Println(q) // {Alice 20}
}

References

（2018/03/11）投稿時は、gRPCと記載していましたが、シリアライズフォーマットとしてはProtocol Buffersが正しいため訂正します。↩

2018-03-05

Visual Studio Codeをインストールするときにやったこと

AtomからVScodeに移行したメモです。自分しか使ってないようなkey-bindとかもありますが、同じように設定に困ったら参考にしてください。

カラーテーマ

Atom One Dark Theme

表示関連

goのソースコードのみタブを半角スペース2つへ

    "[go]": {
        "editor.insertSpaces": true,
        "editor.tabSize": 2,
        "editor.autoIndent": false
    }

全角スペースを強調

以下パッケージをインストール

EvilInspector

半角スペースを強調

表示 → 空白文字の表示の切り替え

折り返し

    "editor.wordWrap": "on"

key-bind系

パッケージ

エディタの分割

defaultのまま

{
  "key": "ctrl+alt+cmd+[IntlYen]",
  "command": "workbench.action.splitEditor"
}

cmd+cでESCされてしまう(vimパッケージによる)

ショートカットを削除

{
  "key": "",
  "command": "extension.vim_cmd+c"
}

行を跨いて左右の移動ができない(vimパッケージによる)

ショートカットを削除

{
  "key": "",
  "command": "extension.vim_left"
}

{
  "key": "",
  "command": "extension.vim_right"
}

go to def

ショートカットを変更

定義へ

{
  "key": "cmd+d",
  "command": "editor.action.goToDeclaration",
  "when": "editorHasDefinitionProvider && editorTextFocus && !isInEmbeddedEditor"
}

定義から戻る

{
  "key": "shift+cmd+d",
  "command": "workbench.action.navigateBack"
}

置換

ショートカットを変更

{
  "key": "shift+cmd+f",
  "command": "editor.action.startFindReplaceAction"
}

移動

ショートカットを変更

行頭へ

{
  "key": "ctrl+a",
  "command": "cursorLineStart",
  "when": "editorTextFocus"
}

行末へ

{
  "key": "ctrl+e",
  "command": "cursorLineEnd",
  "when": "editorTextFocus"
}

Go関連

パッケージ

Go for Visual Studio Code

合わせて必要なパッケージをターミナルからインストールしておく。

go get -u -v github.com/nsf/gocode
go get -u -v github.com/rogpeppe/godef
go get -u -v github.com/zmb3/gogetdoc
go get -u -v github.com/golang/lint/golint
go get -u -v github.com/lukehoban/go-outline
go get -u -v sourcegraph.com/sqs/goreturns
go get -u -v golang.org/x/tools/cmd/gorename
go get -u -v github.com/tpng/gopkgs
go get -u -v github.com/newhook/go-symbols
go get -u -v golang.org/x/tools/cmd/guru
go get -u -v github.com/cweill/gotests/...
go get github.com/derekparker/delve/cmd/dlv

go tests generate

ショートカットを登録

{
  "key": "shift+cmd+g",
  "command": "go.test.generate.function"
}

go testsの実行(*_test.goで以下コマンドを実行)

{
  "key": "f5",
  "command": "go.test.file"
}

go testsのcoverageを表示

{
    "go.buildFlags": ["-cover"]
}

markdown

preview

{
  "key": "ctrl+shift+m",
  "command": "markdown.showPreviewToSide",
  "when": "editorLangId == 'markdown'"
}

previewと本文が一緒に動かないようにしたい

{
    "markdown.preview.scrollPreviewWithEditorSelection": false
}

ターミナル

ターミナルへ移動

{
  "key": "ctrl+cmd+t",
  "command": "workbench.action.terminal.focusPrevious"
}

ターミナルのカーソルを縦棒(|)にする

{
    "terminal.integrated.cursorStyle": "line"
}

その他

メッセージボックスを消す

f:id:cipepser:20180305164959p:plain

以下ショートカットを追加

    {
        "key": "escape",
        "command": "workbench.action.closeMessages",
        "when": "globalMessageVisible"
    }

最後に

最終的なkeybindings.jsonとsettings.jsonは、Githubに上げてあります。

References

2018-02-24

ブロックチェーンアプリケーション開発の教科書を読んでハマったところメモ

ブロックチェーンアプリケーション開発の教科書 / 加嵜長門(著), 篠原航(著), 丸山弘詩(編集)を読みました。

仮想通貨の基礎知識、事例：1-5章
Ethereumのスマートコントラクト実装：6-8章
今現在議論となっているトピック、これからブロックチェーンがどうなっていくのか：9-11章

上記の構成になっており、仮想通貨界隈で議論されているトピックについて網羅的に記載されています。トピックの多さにびっくりしました。
特にエンジニアの方で、「ブロックチェーンや仮想通貨盛り上がってるけど何をしたらいいのかよくわからない」という場合はとりあえず本書を読んでおけばよいなという感じです。

そしてなんといっても本書のメインである「Ethereumのスマートコントラクト実装：6-8章」はひたすら丁寧に記載されています。各行の処理やこの関数で何をしてるのかなど。
まさに自分もライトニングネットワークというような用語となんとなくの意味はわかるものの、スマートコントラクトの実装などになるとさっぱりという状態だったので、本書を読むべきタイミングで読めたことをうれしく思います。

とても良かったのでおすすめしたいのですが、バージョン違いなどで本書通りでは動作しない箇所がありました。自分で手を動かしてハマってしまったところをメモ代わりに残します。途中でハマり投げ出したくなった方の一助になればと思います。

version

上述の通り、本書が書かれたタイミングからバージョンが上がってしまったことによるハマりどころもあるのかと思うので、本記事でもバージョンを記載しておきます。良くも悪くも発展途上のため、今後のアップデートなどで動作が変わると思うのでご注意ください。

geth

geth-darwin-amd64-1.8.1-1e67410e

npmのバージョン

> npm version
{ 'dapps-token': '1.0.0',
  npm: '5.6.0',
  ares: '1.13.0',
  cldr: '32.0.1',
  http_parser: '2.7.0',
  icu: '60.2',
  modules: '59',
  napi: '2',
  nghttp2: '1.29.0',
  node: '9.5.0',
  openssl: '1.0.2n',
  tz: '2017c',
  unicode: '10.0',
  uv: '1.19.1',
  v8: '6.2.414.46-node.18',
  zlib: '1.2.11' }

truffle

> truffle version
Truffle v4.0.6 (core: 4.0.6)
Solidity v0.4.19 (solc-js)

コマンド6.1.4.3: Gethの初期化処理

genesis.jsonでtypoしてしまったため、一度実行に失敗しました。キャッシュもっているのか修正後も以下のようにFatalとなってうまくいきませんでした。一度genesis.jsonを消してから再実行したら成功しました。

# geth --datadir ~/geth/private_net init ~/geth/private_net/genesis.json
Fatal: Failed to read genesis file: open ~/geth/private_net/genesis.json: no such file or directory

コード8.2.3.1: トークンのコントラスト

StandardToken.solがimportできませんでした。

truffle(develop)> test
Error: Could not find zeppelin-solidity/contracts/token/StandardToken.sol

本文とStandardToken.solのPATHが変わっているのでDappsToken.solを修正します。

// DappsToken.sol
pragma solidity ^0.4.18;
import "zeppelin-solidity/contracts/token/ERC20/StandardToken.sol";

上記に伴って、DappsToken.sol中のDappsTokenの引数もuintからuint256に変更します。また、totalSupplyもERC20/BasicToken.sol中でtotalSupply_となっているので修正します。

// DappsToken.sol
contract DappsToken is StandardToken {
  string public name = "DappsToken";
  string public symbol = "DTKN";
  uint public decimals = 18;
  
  function DappsToken(uint256 initialSupply) public {
    totalSupply_ = initialSupply;
    balances[msg.sender] = initialSupply;
  }
}

8-2 ERC20準拠のトークン作成のファイル位置

慣れれば当然なのでしょうが、本節で書いた各ファイルの配置は、 dapps-tokenをカレントディレクトリとして以下です。

./contracts/DappsToken.sol(コード8.2.3.1)
./migrations/2_deploy_dapps_token.js
./test/DappsTokens.js

Ropstenネットワークへのデプロイ

コード8.3.2.14の通りにgasを設定しても以下のエラーメッセージが出てきて、デプロイできませんでした。

> truffle migrate --network ropsten
Using network 'ropsten'.

Running migration: 2_deploy_dapps_token.js
  Deploying DappsToken...
  ... <hash>
Error encountered, bailing. Network state unknown. Review successful transactions manually.
Error: The contract code couldn't be stored, please check your gas amount.

truffleの公式ドキュメントや githubのissue、 StackExchange あたりを読んでも、同じエラーメッセージなのに解決策がマチマチで、ここで一番ハマりました。自分の場合は、2_deploy_dapps_token.jsのgasと同じく truffle.jsのgasも以下のように設定することでうまくいきました。

// truffle.js
module.exports = {
  networks: {
    ropsten: {
      provider: function() {
        return new HDWalletProvider(
          mnemonic,
          "https://ropsten.infura.io/" + accessToken
        );
      },
      network_id: 3,
      gas: 2000000
    }
  }
};

Tips

truffleを終了させる

truffle(develop)> .exit

truffle migrateをやり直すとき

コンパイル結果がbuild配下にあるので、削除したほうが無難です。

> rm -R build

Refs

ブロックチェーンアプリケーション開発の教科書

作者: 加嵜長門,篠原航,丸山弘詩
出版社/メーカー: マイナビ出版
発売日: 2018/02/01
メディア: 単行本（ソフトカバー）
この商品を含むブログ (1件) を見る

2018-02-17

【Golang】Disjoint-set algorithmによる無向グラフのcycle detectを実装する

Cycle in Undirected Graph Graph Algorithmを視聴したので、Disjoint set algorithmによるcycle detect実装してみます。

Disjoint set algorithmでは、以下3つの操作を使うことでcycle detectを行います。

MakeSet
- 各nodeだけの集合を作る(初期化)
Union
- 2つの集合を結合する
FindSet
- edgeを入力に、そのedgeの両端のnodeが含まれる集合を返す

Algorithm

アルゴリズムは以下となります。

MakeSetにより、各nodeの集合を作る
edgeを順番に選ぶ
FindSetにより、2.で選んだedgeの両端のnodeが含まれる集合を見つける
3.で見つけた2つの集合が同じか、異なるかを判定する
- 同じ: cycleあり
- 異なるかつ全edgeを探索終了: cycleなし

Cycle in Undirected Graph Graph Algorithmの動画では、図を交えた説明がされているので、詳しくは動画を御覧ください。

実装

本体だけ抜き出すと実装は以下のようになります。

func DisjointSetAlgorithm(g *graph) bool {
    d, err := g.NewDisjointSet()
    if err != nil {
        panic(err)
    }

    for _, e := range g.GetEdges() {
        F, T := d.FindSet(e)
        if F.Equal(T) {
            return true
        }
        d = d.Union(F, T)
    }
    return false
}

FindSetやUnionの実装はこちら

References

2018-02-10

【Golang】reflect.DeepEqualでsliceとmapを組み合わせて比較する

先日、集合や族を扱うパッケージを書いていたところ、mapやsliceが混じった構造でどのようにEqualを実装するかで少しハマりました。reflect.DeepEqualの実装を見て解決したので備忘として整理します。

ちょうどGoで違うmapであることをテストするでも、同じような課題に遭遇された方がいたようです。

考え方

まず、mapのEqualを実装するときに定義する2つのmapが等しいは、大きく以下の2つになると思います。

中身の要素が同じmapは、等しい(ポインタが異なることは気にしない)
中身が同じでも、ポインタが異なれば、等しくない

それぞれ、以下のように比較できます。

1. 中身の要素が同じmapは、等しい(ポインタが異なることは気にしない)

この場合は、中身を比較すればいいので、reflect.DeepEqualで簡潔に書くことができます。

2. 中身が同じでも、ポインタが異なれば、等しくない

こちらは中身を見る必要はなく、ポインタだけを比較します。

コード

上記それぞれ実装すると以下のようになります。

package main

import (
    "fmt"
    "reflect"
)

func main() {
    m1 := map[int]int{
        1: 1,
        2: 2,
    }
    m2 := map[int]int{
        1: 1,
        2: 2,
    }

    fmt.Printf("%p\n%p\n", m1, m2)
  // 0x10444240
  // 0x10444260

    fmt.Print("1: ")
    if reflect.DeepEqual(m1, m2) {
        fmt.Println("same")
    } else {
        fmt.Println("different")
    }
  // 1: same

    fmt.Print("2: ")
    if reflect.ValueOf(m1).Pointer() == reflect.ValueOf(m2).Pointer() {
        fmt.Println("same")
    } else {
        fmt.Println("different")
    }
  // 2: different
}

https://play.golang.org/p/tlVEfsHYojr

mapとsliceの組み合わせ

単純なmapの比較は、上記のDeepEqualを使う場合が多いのですが、今回ハマったのは、以下のように集合Setと集合族Familyを扱おうとしたときです。
※今回実装したかったのは、要素が同じ集合族は同じ(上記の1.のパターン)と見なしたかったため、1.のパターンのみを考えます。

type Set map[int]struct{}
type Family []Set

以下のようにSetの順番が異なる集合族の比較をするとdifferentが返ってきます。

package main

import (
    "fmt"
    "reflect"
)

type Set map[int]struct{}
type Family []Set

func main() {
    f1 := Family{
        Set{1: struct{}{}, 2: struct{}{}},
        Set{3: struct{}{}, 4: struct{}{}, 5: struct{}{}},
    }

    f2 := Family{
        Set{3: struct{}{}, 4: struct{}{}, 5: struct{}{}},
        Set{1: struct{}{}, 2: struct{}{}},
    }

    if reflect.DeepEqual(f1, f2) {
        fmt.Println("same")
    } else {
        fmt.Println("different")
    }
  // different
}

https://play.golang.org/p/euz02m_InVS

この理由はreflect.DeepEqualの実装を見るとわかります。内部実装のdeepValueEqualでは、型ごと（今回だとsliceとmap)に比較方法が異なります。
sliceの比較は以下のようになっており、 順序も含めた比較 が行われます。

for i := 0; i < v1.Len(); i++ {
  if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) {
    return false
  }
}

このため、上記の例では{1,2}と{3,4,5}を格納した順序が違い、differentとなりました。
mapはもともと順序を意識させないデータ構造のため、DeepEqualで比較すれば十分です。

ワークアラウンド

sliceを用いたまま、上記を解決するためには、なんらかの形で順序を揃えてあげる必要があります。今回、自分が解決したかった問題では、Family中のSetは互いに素という条件があったため、集合中の最大要素でソートすることで解決を図りました。

package main

import (
    "fmt"
    "reflect"
    "sort"
)

type Set map[int]struct{}
type Family []Set

func main() {
    f1 := Family{
        Set{1: struct{}{}, 2: struct{}{}},
        Set{3: struct{}{}, 4: struct{}{}, 5: struct{}{}},
    }

    f2 := Family{
        Set{3: struct{}{}, 4: struct{}{}, 5: struct{}{}},
        Set{1: struct{}{}, 2: struct{}{}},
    }

    f1 = mySort(f1)
    f1 = mySort(f2)

    if reflect.DeepEqual(f1, f2) {
        fmt.Println("same")
    } else {
        fmt.Println("different")
    }
}
// same

func mySort(f Family) Family {
    sort.Slice(f, func(i, j int) bool {
        var maxi, maxj int
        for k := range f[i] {
            if k > maxi {
                maxi = k
            }
        }
        for k := range f[j] {
            if k > maxj {
                maxj = k
            }
        }
        return maxi < maxj
    })

    return f
}

https://play.golang.org/p/CdHW_gKPxrS