2019-03-18

メモリをダンプしてRustのsliceとVecを理解する

タイトルの通りなんですが、RustのsliceやVecがしっくり来ていないので、メモリ上でどのように表現されているのかという観点で理解を深めようと思います。

環境

❯ cargo version
cargo 1.32.0

❯ rustc --version
rustc 1.33.0

また今回の環境ではusizeは8バイト長です。

println!("size of usize: {}", std::mem::size_of::<usize>());
// size of usize: 8

事前準備

メモリ上でどのように表現されているか確認するため、RustのSizedとfatポインタ - 簡潔なQのas_raw_bytesを利用します。引数xを*const Tでキャストして、生ポインタからstd::mem::size_of_val(x)で得たバイト長を読み出します。

fn as_raw_bytes<'a, T: ?Sized>(x: &'a T) -> &'a [u8] {
    unsafe {
        std::slice::from_raw_parts(
            x as *const T as *const u8,
            std::mem::size_of_val(x))
    }
}

結論

[T]はスタック領域に連続して表現される
Vec<T>はスタック領域に「実データへのポインタ」「len」「cap」を持つ
&strはスタック領域に「実データへのポインタ」「len」を持つ

具体例

`[i32]`

まずは[i32]（i32のslice）でメモリ上の内容を見てみましょう。

let a: [i32; 5] = [255, 256, 1023, 1024, 1025];
println!("{:x?}", as_raw_bytes(&a));

実行結果は以下のようになります。読みやすいように改行などの整形を入れています。以降でも同じように整形して読みやすくしています。

[ff, 0, 0, 0,
 0, 1, 0, 0,
ff, 3, 0, 0,
 0, 4, 0, 0,
 1, 4, 0, 0]

これだけだと分かりづらいので、as_raw_bytesの返り値の型が[u8]であることを考慮して0を補完します。

[ff, 00, 00, 00,
 00, 01, 00, 00,
 ff, 03, 00, 00,
 00, 04, 00, 00,
 01, 04, 00, 00]

リトルエンディアンで表現されていることに注意すれば、　

0d255 = 0x000000ff
0d256 = 0x00000100
0d1023 = 0x000003ff
0d1024 = 0x00000400
0d1025 = 0x00000401

となることがわかると思います。またヒープ領域へのポインタなどもなく、スタック領域に確保もされていることも確認できました。

`Vec<i32>`

次にVec<i32>を見ていきます。

let a: Vec<i32> = vec![1, 2, 3, 4];
println!("{:x?}", as_raw_bytes(&a));

結果は以下のようになりました。

[d0, 2c, c0, d5, a8, 7f, 00, 00,
 04, 00, 00, 00, 00, 00, 00, 00,
 04, 00, 00, 00, 00, 00, 00, 00]

ここでVec<T>の実装を見てみましょう。 vec.rsの実装は以下のようになっています。

#[stable(feature = "rust1", since = "1.0.0")]
pub struct Vec<T> {
    buf: RawVec<T>,
    len: usize,
}

またRawVecはraw_vec.rsで実装されています。

#[allow(missing_debug_implementations)]
pub struct RawVec<T, A: Alloc = Global> {
    ptr: Unique<T>,
    cap: usize,
    a: A,
}

このようにVec<T>はlenとcapを持ちます。

改めて結果を見てみると後半の4から始まる8バイト2行はlenとcapであることがわかります。

// (再掲)
[d0, 2c, c0, d5, a8, 7f, 00, 00,
 04, 00, 00, 00, 00, 00, 00, 00,
 04, 00, 00, 00, 00, 00, 00, 00]

最初の8バイトが実データへのポインタになっているのですが、本当にそうなっているか参照外しをして確認しましょう。

let a = vec![4, 1, 2, 3];

unsafe {
    let p = a.as_ptr();
    println!("{:?}", p); // 0x7feba05027c0
    println!("{:?}", *p); // 4 <- 先頭のデータ
    let data: &[u8] = std::slice::from_raw_parts(p, a.len());
    println!("{:?}", data); // [4, 1, 2, 3]
}

*pやdataの出力結果から、確かに実データへのポインタとなっていました。

文字列まわり

[i32]とVec<i32>を確認できたので、おまけとして文字列を扱う際に登場する以下3つのメモリ内容も確認してみます。

[char]、Vec<char>
[&str]、Vec<&str>
String、Vec<String>

`char`

[char]から見ていきましょう。

let a = ['a', 'b', 'c'];

println!("{:x?}", as_raw_bytes(&a));
// [61, 0, 0, 0, 62, 0, 0, 0, 63, 0, 0, 0]

[i32]と同じでスタック領域のみで表現されていることがわかります。ちなみに、char - Rustにあるようにcharは4バイト長です。

char is always four bytes in size.

次にVec<char>です。

let a = vec!['a', 'b', 'c'];

println!("{:x?}", as_raw_bytes(&a));
// [d0, 2c, 40, d7, ad, 7f, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0]

unsafe {
    let p = a.as_ptr();
    println!("{:?}", p);
    // 0x7fadd7402cd0

    println!("{:?}", *p);
    // 'a'

    let data = std::slice::from_raw_parts(p, a.len());
    println!("{:?}", data);
    // ['a', 'b', 'c']
}

as_raw_bytes(&a)の出力結果を整形します。

[d0, 2c, 40, d7, ad, 7f, 00, 00,
 03, 00, 00, 00, 00, 00, 00, 00,
 03, 00, 00, 00, 00, 00, 00, 00]

lenとcapが3（うしろ2行）で、1行目はヒープにある実データへのポインタになっています。実際、unsafeの中で参照外しを行うと'a'が得られるため、実データの先頭アドレスであったことがわかります。

`[&str]`

続けて[&str]です。

let a: [&str; 3] = ["a", "b", "c"];

println!("{:x?}", as_raw_bytes(&a));
// [82, 59, 85, 4, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 80, 59, 85, 4, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 81, 59, 85, 4, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]

今までとは様子が違いそうです。理解を深めるため、別の例をもうひとつ表示してみます。

let a: [&str; 3] = ["a", "ab", "abc"];

println!("{:x?}", as_raw_bytes(&a));
// [35, 77, 46, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 30, 77, 46, 1, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 32, 77, 46, 1, 1, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0]

上記2つの結果を見やすいように整形しました。

[82, 59, 85, 04, 01, 00, 00, 00,
 01, 00, 00, 00, 00, 00, 00, 00,
 80, 59, 85, 04, 01, 00, 00, 00,
 01, 00, 00, 00, 00, 00, 00, 00,
 81, 59, 85, 04, 01, 00, 00, 00,
 01, 00, 00, 00, 00, 00, 00, 00]

[35, 77, 46, 01, 01, 00, 00, 00,
 01, 00, 00, 00, 00, 00, 00, 00,
 30, 77, 46, 01, 01, 00, 00, 00,
 02, 00, 00, 00, 00, 00, 00, 00,
 32, 77, 46, 01, 01, 00, 00, 00,
 03, 00, 00, 00, 00, 00, 00, 00]

実は、str - Rustにあるように&strは実データへのポインタとlenで構成されます。

A &str is made up of two components: a pointer to some bytes, and a length.

今回の表示した対象は[&str]（&strのslice）です。[i32]の例でみたようにsliceはスタック領域に連続してデータを格納します。そして&strは上記の通り、実データへのポインタとlenで表現されます。これらの組み合わせで、ポインタ＋lenが3つ並ぶ結果となったのです。

念のため、3つの要素のうち最初の8バイトが実データへのポインタであることも確かめておきましょう。

let a = ["a", "ab", "abc"];

println!("{:x?}", as_raw_bytes(&a));
// [55, 8e, f9, 7, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 50, 8e, f9, 7, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 52, 8e, f9, 7, 1, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0]

unsafe {
    for i in 0..a.len() {
        println!("-------");
        let p = a[i].as_ptr();
        println!("{:?}", p);
        println!("{:?}", *p);
        let data = std::slice::from_raw_parts(p, a[i].len());
        println!("{:?}", data);
    }
    // -------
    // 0x107f98e55
    // 97
    // [97]
    // -------
    // 0x107f98e50
    // 97
    // [97, 98]
    // -------
    // 0x107f98e52
    // 97
    // [97, 98, 99]
}

確かに、3つに分かれた各要素の先頭8バイトが実データへのポインタになっていました。

`String`

続いてStringです。

let a: [String; 3] = [
    "a".to_string(),
    "ab".to_string(),
    "abc".to_string()];

println!("{:x?}", as_raw_bytes(&a));
// [90, 2c, c0, 4a, 9b, 7f, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, a0, 2c, c0, 4a, 9b, 7f, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, b0, 2c, c0, 4a, 9b, 7f, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0]

例によって整形します。

[90, 2c, c0, 4a, 9b, 7f, 00, 00,
 01, 00, 00, 00, 00, 00, 00, 00,
 01, 00, 00, 00, 00, 00, 00, 00,
 a0, 2c, c0, 4a, 9b, 7f, 00, 00,
 02, 00, 00, 00, 00, 00, 00, 00,
 02, 00, 00, 00, 00, 00, 00, 00,
 b0, 2c, c0, 4a, 9b, 7f, 00, 00,
 03, 00, 00, 00, 00, 00, 00, 00,
 03, 00, 00, 00, 00, 00, 00, 00]

[String]も[&str]と同じようにスタック領域に3つのStringが並んでいます。上述の通り&strは実データへのポインタとlenを持っていますが、Stringはこれに加えてcapを持ちます。ちょうどVecに対応しています。

そうとなれば実データを指しているのか確認したくなりますね。

let a: [String; 3] = [
    "a".to_string(),
    "ab".to_string(),
    "abc".to_string()];

println!("{:x?}", as_raw_bytes(&a));
// [90, 2e, 40, 6f, 8c, 7f, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, a0, 2e, 40, 6f, 8c, 7f, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, b0, 2e, 40, 6f, 8c, 7f, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0]

unsafe {
    for i in 0..a.len() {
        println!("-------");
        let p = a[i].as_ptr();
        println!("{:?}", p);
        println!("{:?}", *p);
        let data = std::slice::from_raw_parts(p, a[i].len());
        println!("{:?}", data);
    }
    // -------
    // 0x7f8c6f402e90
    // 97
    // [97]
    // -------
    // 0x7f8c6f402ea0
    // 97
    // [97, 98]
    // -------
    // 0x7f8c6f402eb0
    // 97
    // [97, 98, 99]
}

確かに実データへのポインタとなっていました。

続けて、Vec<String>です。

let a: Vec<String> = vec![
    "a".to_string(),
    "ab".to_string(),
    "abc".to_string()];

println!("{:x?}", as_raw_bytes(&a));
// [a0, 2d, c0, d0, d5, 7f, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0]

unsafe {
    let p = a.as_ptr(); // p: *const String
    println!("{:?}", p);
    // 0x7fd5d0c02da0

    println!("{:?}", *p);
    // "a"

    let data = std::slice::from_raw_parts(p, a.len()); // data: &[String]
    println!("{:?}", data);
    // ["a", "ab", "abc"]

    for i in 0..a.len() {
        println!("-------");
        let p = a[i].as_ptr(); // p: *const u8
        println!("{:?}", p);
        println!("{:?}", *p);
        let data = std::slice::from_raw_parts(p, a[i].len()); // data: &[u8]
        println!("{:?}", data);
    }
    // -------
    // 0x7fd5d0c02cd0
    // 97
    // [97]
    // -------
    // 0x7fd5d0c02ce0
    // 97
    // [97, 98]
    // -------
    // 0x7fd5d0c02cf0
    // 97
    // [97, 98, 99]
}

一番最初のas_raw_bytes(&a)の結果を整形します。

[a0, 2d, c0, d0, d5, 7f, 00, 00,
 03, 00, 00, 00, 00, 00, 00, 00,
 03, 00, 00, 00, 00, 00, 00, 00]

aはVec<String>型のため、実データへのポインタ、len、capを持つ結果となっていることがわかります。

a.as_ptr()(0x00007fd5d0c02da0)を参照外しすると"a"が得られました。 a[0].as_ptr()(0x00007fd5d0c02cd0)は違うアドレスですが、同じ"a"を参照しています。図にすると以下のようになります。

f:id:cipepser:20190317174507p:plain

References

プログラミングRust

作者: Jim Blandy,Jason Orendorff,中田秀基
出版社/メーカー: オライリージャパン
発売日: 2018/08/10
メディア: 単行本（ソフトカバー）
この商品を含むブログを見る

2019-02-26

BLS署名について

以下を書いたので、BLS署名についてもまとめておく。

cipepser.hatenablog.com

なお、本内容はブロックチェーン系プロジェクトで着目される暗号技術のP.22に書かれているBLS署名について自分なりに理解するためのメモである。¹

BLS署名はその名の通り、署名をどうやるかという話なので、以下3フェーズで考える。

鍵生成
署名
検証

鍵生成

$G_1, G_2$ は素数位数 $p$ の加法巡回群とする。

ハッシュ関数を以下のように定める。

$H: \lbrace 0, 1 \rbrace^* \to G_1$

$\lbrace 0, 1 \rbrace^*$ は任意長の入力を表している。後述の双線形写像を使うために、写像した先が $G_1$ になるようにする。

また、公開パラメータとして、 $Q \in G_2$ を選ぶ。

次に有限体 $\mathbb{F}_p$ から秘密鍵を以下のように選ぶ。

$s \in \mathbb{F}_p$

公開パラメータ $Q$ を生成元として、公開鍵を $sQ$ とする。 $sQ \in G_2$ であることに注意。

署名

メッセージ $m$ に対して、以下のように署名 $Sign$ を行う。

$Sign(s, m) = s H(m)$

$sH(m) \in G_1$ であることに注意。

検証

BLS署名における双線形性（ペアリング）について - 逆さまにしたで述べた以下の双線形写像 $e$ を使う。

$e: G_1 \times G_2 \to G_T$

ここで $G_T$ は素数位数 $p$ の乗法巡回群である。

検証する内容は以下。等号が成り立つなら正当な署名である。

$e(H(m), sQ) = e(Sign(s, m), Q)$

補足

署名の検証までであれば、上記で終わりなのでおまけ。 $e(H(m), sQ) = e(Sign(s, m), Q)$ を式展開して、ちゃんと成り立つことを確認する。

署名のところで記載したように $Sign(s, m) = s H(m)$ なので、

$(l.h.s) = e(sH(m), Q)$

である。あとは $s$ を第一引数から第二引数に移せることが言えれば、右辺と一致する。これについては、BLS署名における双線形性（ペアリング）について - 逆さまにしたで述べた通りなので、そちら参照（一番最後のところ）。

もうちょっと補足しておくと、 $H(m)$ を $G_1$ の元としたことで、 $sH(m) \in G_1$ である。同様に $Q \in G_2$ としたので、 $sQ \in G_2$ である。双線形写像 $e$ は $e: G_1 \times G_2 \to G_T$ となるような写像であることも理解しておくとよいと思う。

References

今回も記号を自分の理解に合わせて出典元と変えている箇所がある↩

2019-02-20

BLS署名における双線形性（ペアリング）について

ブロックチェーン系プロジェクトで着目される暗号技術のP.21-22を理解するために双線形性（ペアリング）について調べた。自分が理解するに至った軌跡をメモベースで残す。

余談だが、調べる過程で双線形写像（Bilinear maps）とペアリングの違いが気になった。個人的な印象としては、ペアリングは暗号分野寄りに使われる用語だと思ったが、Intro to Bilinear Mapsにも以下のように書いてあるので、本記事では大体同じものとして扱う。

Bilinear maps are called pairings because they associate pairs of elements from G1 and G2 with elements in Gt.

(拙訳) 双線形写像はペアリングとも呼ばれる。 G1とG2からの要素をGtでペアとして関連付けるからだ。

以下、調べた内容。¹

双線形とは何なのか

本節は、ブロックチェーン系プロジェクトで着目される暗号技術がベースとなっている。

双線形を定義するにあたり、まず2種類の楕円曲線の生成元を $P, Q$ とする。このとき、素数位数 $p$ の加法巡回群 $G_1, G_2$ は、以下のように表現できる。

$G_1 = \lbrace 0, P, 2P, ..., (p-1) P \rbrace$
$G_2 = \lbrace 0, Q, 2Q, ..., (p-1) Q \rbrace$

また、有限体 $\mathbb{F}_p$ と、位数 $p$ の乗法巡回群（ $1$ の $p$ 乗根の集合）として $G_T$ を定める。

このとき、 $a, b \in \mathbb{F}_p$ なる $a ,b$ に対して、写像 $e: G_1 \times G_2 \to G_T$ が以下を満たすことを双線形という。

$e(aP, bQ) = e(P, Q)^{ab}$

個人的に本記事を書く要因となったのが、ブロックチェーン系プロジェクトで着目される暗号技術P.22「正当性」における以下の数式。上記定義と表記が違ったので疑問に思って調べ始めた。なので本記事では下記数式が成立するところまでを追う。

$e(sH(m), Q) = e(H(m), sQ)$

ベクトル空間における線形性（その1）

本節は、双線形関数物理のかぎしっぽがベースになっている。

まず、復習として一変数関数に対する線形性を考える。これはベクトル空間 $V$ の $x, y \in V$ なる元に対して、写像 $\phi: V \to \mathbb{R}$ が以下を満たすことだった。

$\phi(x + y) = \phi(x) + \phi(y)$
$\phi(\alpha x) = \alpha \phi(x) , \alpha \in \mathbb{R}$

では、二変数ではどうなるか。ベクトル空間 $V$ の直積集合 $V \times V$ の元 $(x, y)$ に対して、写像 $\psi(x,y): V \times V \to \mathbb{R}$ が以下を満たすことを双線形という。

$\psi(\alpha x + \beta x, y) = \alpha \psi(x, y) + \beta \psi(x,y)$
$\psi(x, \alpha y + \beta y) = \alpha \psi(x, y) + \beta \psi(x,y)$

双線形関数物理のかぎしっぽ本文には、以下のように記載されているが、理解が及ばず腹落ちしなかった。

双線形関数は個々の変数に対して別々に線形性を持っていると言えそうです．これが双線形という名前の由来でもありますなるほど。確かにそう見える。

ベクトル空間における線形性（その2）

本節は、岸本研究室 - 双線形写像についてがベースとなっている。

上記議論では、理解が及ばなかったので、もう少しシンプルに考える。「ベクトル空間における線形性（その1）」の定義に比べて、式の数は多いが、以下で双線形を定義したほうがシンプルで、学習にあたっては、理解しやすかった。

双線形を定義する。ベクトル空間 $V$ を考え、 $x, x_1, x_2, y, y_1, y_2 \in V$ なる元を考える。このベクトル空間 $V$ に対して、 $f: V \times V \to \mathbb{R}$ なる写像 $f$ を定義する。また、 $c \in \mathbb{R}$ とする。このとき双線形は以下の性質を満たすことをいう。

$f(x_1 + x_2, y) = f(x_1, y) + f(x_2, y)$
$f(cx, y) = c f(x, y)$
$f(x, y_1 + y_2) = f(x, y_1) + f(x, y_2)$
$f(x, cy) = c f(x, y)$

こちらのほうが「ベクトル空間における線形性（その1）」で引用した個々の変数に対して別々に線形性を持っているというのが理解しやすいと思う。

双線形の例

「例示は理解の試金石」ということで双線形を満たす写像 $f$ の具体例を考えてみる。

双線形な例

$f(x, y) = xy$

「ベクトル空間における線形性（その2）」で定義した4式を一つずつ確かめていく。

$f(x_1 + x_2, y) = (x_1 + x_2) y = x_1 y + x_2 y = f(x_1, y) + f(x_2, y)$
$f(cx, y) = (cx)y = c xy = c f(x, y)$
$f(x, y_1 + y_2) = x(y_1 + y_2) = x y_1 + x y_2 = f(x, y_1) + f(x, y_2)$
$f(x, cy) = x(cy) = c xy = c f(x, y)$

となり、すべて満たすので双線形。

双線形じゃない例²

$f(x, y) = x + y$

実は最初にこれを念頭に考えていた。パッと見、線形性持ってそうだし。でも双線形じゃない。 4式中の一番上の式で双線形を満たさないことを確認する。

となり、左辺と右辺が一致しない。

BLS署名における双線形

話をベクトル空間から乗法巡回群で考えているBLS署名の話に戻す。それにあたり「ベクトル空間における線形性（その2）」で登場した双線形性の定義を再掲する。

$f(x_1 + x_2, y) = f(x_1, y) + f(x_2, y)$
$f(cx, y) = c f(x, y)$
$f(x, y_1 + y_2) = f(x, y_1) + f(x, y_2)$
$f(x, cy) = c f(x, y)$

これらはベクトル空間 $V$ と実数 $\mathbb{R}$ で考えていたので、乗法巡回群 $G_T$ と有限体 $\mathbb{F}_p$ で考え直す。Intro to Bilinear Mapsより双線形性の定義を引用すると、双線形性とは $e: G_1 \times G_2 \to G_T$ なる写像について、 $u \in G_1, v \in G_2, a, b \in \mathbb{Z}$ に対して、

$e(u^{a}, v^{b}) = e(u, v)^{ab}$

が成り立つことである。ただし、このとき $e$ は非退化である。また本式の表現方法にはIntro to Bilinear Mapsの7ページ目に書いてある以下の表記もある。

$\forall P \in G_1, \forall Q \in G_2, \forall a, b \in \mathbb{Z}$ に対して、

$e(aP, bQ) = e(P, Q)^{ab}$

いきなり上式が出てくると、ベクトル空間から乗法巡回群への議論で少し飛んでしまっているように感じられるので補足する。

4式のうち、上2式について対応を示す。³

$f(x_1 + x_2, y) = f(x_1, y) + f(x_2, y) \tag{1}$
$f(cx, y) = c f(x, y) \tag{2}$

式(2)から示す。 $e(aP, bQ) = e(P, Q)^{ab}$ において、 $a = c, b = 1$ とすると

$e(cP, Q) = e(P, Q)^{c}$

と表現できる。ここで $e(P, Q) \in G_T$ で $G_T$ が乗法巡回群であることを考えると自然な表記であろう。

次に式(1)を示す。 $P \in G_1$ で $G_1$ が加法巡回群であることを考えると

$e(P_1 + P_2, Q) = e(P_1, Q)e(P_2, Q)$

となることを示せればよい。ここで $P_1, P_2$ は $G_1$ の元であることから生成元 $P$ を用いて、

$P_1 = a_1 P$
$P_2 = a_2 P$

と表現できる。ここで $a_1, a_2 \in \mathbb{Z}$ である。これらを用いると

が得られる。

ここまでの議論は整数 $\mathbb{Z}$ 上のものだったが、有限体 $\mathbb{F}_p$ 上でも成り立つとして、

$\forall P \in G_1, \forall Q \in G_2, \forall a, b \in \mathbb{F}_p$ に対して、

$e(aP, bQ) = e(P, Q)^{ab}$

である。ここから $a, b$ が可換であることがわかるが、もう少し詳細に書いておく。

$c \in \mathbb{F}_p$ に対して、 $a = c, b = 1$ とすると

$e(cP, Q) = e(P, Q)^{c}$

である。同様に $a = 1, b = c$ とすると

$e(P, cQ) = e(P, Q)^{c}$

である。これらを合わせると

$e(cP, Q) = e(P, cQ)$

が得られる。これを使うとブロックチェーン系プロジェクトで着目される暗号技術のP.22では、以下の変形が成り立つことがわかる。

$e(sH(m), Q) = e(H(m), sQ)$

References

自分が理解しやすいように記号を変えているので出典元と異なる箇所がある↩
改行を含む数式にpreタグを使った。markdownでも&がエスケープされないようにならないかなー↩
$y$ については同様なので省略↩

2019-02-18

Raspberry Pi 3 Model b+でビットコインフルノードを構築する

背景

フルノードの重要性とLightning NetworkやProof of Stakeがノード運営インセンティブに与える影響 - YouTube やフルノードの重要性とフルノードが広がった世界について改めて考える - ビットコインダンジョン2.0 を読んで（見て）、ビットコインフルノードを立てたくなりました。
とはいえ以前、下記記事を書いたときに一度ノードを立てたことはあったので、二度目の構築です。

cipepser.hatenablog.com

前回はMacBook Pro上で構築したためストレージ容量を節約したかったので、当時の構築メモの通り、pruneモードで構築しました。
今回はフルノードです。 My first impressions of the Casa Bitcoin Node – The Startup – Medium のようにCasaもありかなぁと思ったいたのですが、Casaのホームページを見たら2019年2月7日時点で出荷に1ヶ月掛かるとありました。

1ヶ月は待てなかったので、Casaは諦め¹、以下のRaspberry Pi 3 Model b+²を購入しました。

ABOX Raspberry Pi 3 Model b+ ラズベリーパイ 3 b＋【2018新型】 MicroSDHCカード32G/NOOBSシステムプリインストール/カードリーダ /5V/3A スイッチ付電源/高品質HDMIケーブルライン/ヒートシンク /簡単に取り付けケース /日本語取扱説明書

出版社/メーカー: ABOX
メディア: Personal Computers
この商品を含むブログを見る

なお、HDD、モニタ、キーボード、マウスは家にあったものを流用したので、今回発生した費用は本セットの約1万円でした。

開封の儀

届いたやつです。開封し、基盤を取り出します。 f:id:cipepser:20190212175033j:plain f:id:cipepser:20190212175045j:plain

付属のmicroSDカードを挿します。

f:id:cipepser:20190212175057j:plain

BluetoothマウスのUSBを取り付けます。

f:id:cipepser:20190212175110j:plain

HDMIケーブルを挿します。

f:id:cipepser:20190212175124j:plain

外付けHDD（USBケーブル）を挿します。

f:id:cipepser:20190212175138j:plain

電源ケーブルを挿し、スイッチを入れます。

f:id:cipepser:20190212175150j:plain

今回のキットにはSDカードにOSが入っているので、Raspbianをインストールしました。

f:id:cipepser:20190212175205j:plain

キーボードはBluetoothキーボードしか持っていなかったので、ここでやっとペアリングです。

f:id:cipepser:20190212175227j:plain

Wi-Fiの設定も上図の赤い☓のところからいけます。

Bitcoin Coreのインストール

構築には、ラズパイでビットコインフルノードを動かしてみる(2017年） – Crypto Developer Blogを参考にさせていただきました。 2019年になりBitcoin Coreのバージョンも上がっており、コマンドが異なる部分もあるので、自分でやった手順を残します。³

まず、SWAP領域を拡張します。

# /etc/dphys-swapfile
CONF_SWAPSIZE=1000

# termitanl
$ sudo dphys-swapfile setup
$ sudo dphys-swapfile swapon

apt-getを最新の状態にします。

# termitanl
$ sudo apt-get update
$ sudo apt-get upgrade -y

ツール群をインストールします。

# termitanl
$ sudo apt-get install autoconf libevent-dev libtool libssl-dev libboost-all-dev libminiupnpc-dev -y
$ sudo apt-get install git -y
$ sudo apt-get install qt4-dev-tools libprotobuf-dev protobuf-compiler libqrencode-dev -y

Bitcoin Coreをインストールします。本記事時点で最新の0.17をインストールします。

# termitanl
$ mkdir ~/bin
$ cd ~/bin
$ git clone -b 0.17 https://github.com/bitcoin/bitcoin.git
$ cd bitcoin/
$ ./autogen.sh
$ ./configure --enable-upnp-default --disable-wallet
$ make -j2 # ここがとても長い
$ sudo make install

HDDのマウント

HDDの容量はどれくらいがいいのか見積もっておきましょう。ブロックチェーンサイズは、Blockchain Size - Blockchainで確認できます。グラフを引用すると以下のようになります。

f:id:cipepser:20190212174022p:plain

2019年2月10日現在で200GBを超えたくらいですね。ここ4年ほどは概ね線形にサイズが増加しており、約50GB/年くらいのスピードです。フルノードで運用することを考えると500GBくらいあれば5年くらいは大丈夫そうですね。

かなりバッファを見て（手元にあったHDDなだけ）1TBのHDDでマウントします。手順やハマった記録は以下記事参照。

cipepser.hatenablog.com

Bitcoin Coreの設定

マウント先に/volumes/BTC/blocksを作り、ここにデータを格納することにします。⁴

bitcoin.confに設定を書き込みます。どこにbitcoin.confを配置すべきかというと、Running Bitcoin - Bitcoin Wiki に以下のように書いてあるので、/volumes/BTC/blocksに配置します。

By default, Bitcoin (or bitcoind) will look for a file named 'bitcoin.conf' in the bitcoin data directory

デフォルトでは、bitcoinデータを格納するフォルダにあるbitcoin.confを見に行く

設定した内容は以下の通りです。

# bitcoin.conf
rpcuser=bitcoinrpc
rpcpassword=<PASSWORD>

# ~/.bashrc (追記分のみ)
PATH="$PATH:/home/pi/bin/bitcoin/src"
alias bitcoin-cli='bitcoin-cli -datadir=/volumes/BTC/blocks'

ラズパイでビットコインフルノードを動かしてみる(2017年） – Crypto Developer Blog のように設定すると、bashが~/.profileを読みにいってくれないので、~/.bashrcに集約しています。本当はaliasとか.bash_aliasesに書くべきかもしれないですが、どうせフルノード専用機にするので管理箇所を集約することにしました。

Bitcoin Coreの起動

以下で起動します。

# termitanl
$ bitcoind -datadir=/volumes/BTC/blocks -daemon

バックグラウンドで実行されているので同期がされていることをCLIで確認します。 v0.16.0でgetinfoは削除されてしまったので、getblockchaininfoを確認しましょう。

# termitanl
pi@raspberrypi:~ $ bitcoin-cli getblockchaininfo
{
  "chain": "main",
  "blocks": 181901,
  "headers": 563103,
  "bestblockhash": "000000000000075b5e5ee7573921a3b48e45ace6d9020af7777f32fd99737f14",
  "difficulty": 1591074.961847305,
  "mediantime": 1338165561,
  "verificationprogress": 0.009423622364504645,
  "initialblockdownload": true,
  "chainwork": "000000000000000000000000000000000000000000000012406bed1889e1f934",
  "size_on_disk": 1702373506,
  "pruned": false,
  "softforks": [
    {
      "id": "bip34",
      "version": 2,
      "reject": {
        "status": false
      }
    },
    {
      "id": "bip66",
      "version": 3,
      "reject": {
        "status": false
      }
    },
    {
      "id": "bip65",
      "version": 4,
      "reject": {
        "status": false
      }
    }
  ],
  "bip9_softforks": {
    "csv": {
      "status": "defined",
      "startTime": 1462060800,
      "timeout": 1493596800,
      "since": 0
    },
    "segwit": {
      "status": "defined",
      "startTime": 1479168000,
      "timeout": 1510704000,
      "since": 0
    }
  },
  "warnings": ""
}

blocksとheadersが一致したら同期完了です。

最新ブロックが「いつマイニングされたものなのか」を確認するなら、debug.logを見たほうがわかりやすいです。

$ tail -f /volumes/BTC/blocks/debug.log
2019-02-15T21:31:40Z UpdateTip: new best=000000000000000009bfca5a27f95c6212923139b0f43888d8581f49b3542fd4 height=338070 version=0x00000002 log2_work=81.95771 tx=56124782 date='2015-01-08T16:27:25Z' progress=0.150469 cache=497.6MiB(4300081txo)
2019-02-15T21:31:43Z UpdateTip: new best=00000000000000001177c70e7b05f9790c645202b6714b8dce38a10c1ddd9b0e height=338071 version=0x00000002 log2_work=81.957763 tx=56126029 date='2015-01-08T16:32:46Z' progress=0.150472 cache=497.6MiB(4300049txo)

同期開始（bitcoindの起動）は2019/02/15 12:20頃です。ルータで通信量を確認したところ、1日経過時点で40GB程度（その他の通信も込み）だったので、一週間くらい掛かりそうですね。。。気長に待ちます。

（2019/4/10追記） wimaxの3日10GB制限あり、かつ、途中で同期を停止していたタイミングもあったので参考になるかわかりませんが、4/10早朝にprogressが1となりました。制限ありの状況で2ヶ月くらい生活するとネットすら見れずかなりつらい日々でした。固定回線で同期しましょう。。。

References

自前で構築する分、こちらのほうが安い。需給もあると思いますが。↩
SDカードだけ違う安いショップもあったのですが、レビューでACアダプタの電圧が足りないようなレビューが多かったので割高でもこちらにしました。バッテリーが少ないようなエラーも出ないのでよかったです。↩
大きな流れは変わりません。2019年でも手順変わってないよくらいの感じで見てもらえるとうれしいです。↩
blocksの中にblocksディレクトリができてしまったので、別の名前のほうがよかった。反省。↩

2019-02-13

【Raspberry Pi】マウントするファイルシステムを間違えて起動できなくなった

ラズパイを買ったので RaspberryPi 3 にUSBの外付けHDD（NTFSフォーマット）を接続する - min117の日記を参考に、外付けHDDをマウントしたところ、ntfs-3gをインストール後rebootしたらラズパイの起動ができなくなりました。ファイルシステムに明るくないため、手こずりましたが、無事復旧したのでログを残します。

環境情報

Raspberry Pi 3 Model b+

pi@raspberrypi:~ $ lsb_release -a
No LSB modules are available.
Distributor ID:   Raspbian
Description:  Raspbian GNU/Linux 9.6 (stretch)
Release:  9.6
Codename: stretch

発生事象

etc/fstabに以下を追記後、再起動したら起動できなくなりました。

# etc/fstab
UUID="<MY UUID>"  /volumes/  ntfs-3g defaults,iocharset=utf8,umask=000 0 0

より具体的な事象は、raspi 3 が起動しなくなった。 - Raspberry Pi Forums と同じで、起動後、以下メッセージが出るもののctrl + DやEnterを押しても同メッセージが出続け、先に進めなくなりました。

You are in emergency mode, After loging in, type "jounalctl -xb"to view system logs,
"systemctl reboot" to rebott, "systemctl default" or ^D to try again to boot into defalult mode.

Cannot open access to console, the root account is locked. See sulongin(8) man page
for more details.

Press Enter to continue.

完全に/etc/fstabでファイルシステムの指定を間違えてしまい、起動できなくなってしまったパターンです。やらかしです。 /etc/fstabを戻そうにも起動すらできないので、Macで復旧します。

復旧

方針

幸い所有しているMacBook ProにSDカードスロットがあったので、VirtualBox上のUbuntuにSDカードを認識させる · Yoshi's Notesを参考にVirtualBoxでUbuntuを立ち上げて、/etc/fstabを編集できるようにします。

環境情報

# VirtualBox
バージョン 5.2.26 r128414 (Qt5.6.3)

SDカードを認識させるのにExtension Packが必要なので、Download VirtualBox (Old Builds)から自身のVirtualBoxのバージョンに合ったExtension Packをインストールします。なお、バージョンが異なるとインストールに失敗します。

UbuntuのOS情報は以下の通りです。

vagrant@vagrant-ubuntu-trusty-64:~$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=14.04
DISTRIB_CODENAME=trusty
DISTRIB_DESCRIPTION="Ubuntu 14.04.5 LTS"

復旧手順

Mac側

SDカードをMacに挿入します（MicroSDなので変換アダプタ使いました）。

Macからdiskutilを確認します。以下のように当環境では、SDカードは/dev/disk2で認識されていることが確認できます。

# Mac
❯ diskutil list
(中略)
/dev/disk2 (internal, physical):
   #:                       TYPE NAME                    SIZE       IDENTIFIER
   0:     FDisk_partition_scheme                        *31.9 GB    disk2
   1:             Windows_FAT_16 RECOVERY                1.7 GB     disk2s1
   2:                      Linux                         33.6 MB    disk2s5
   3:             Windows_FAT_32 boot                    72.4 MB    disk2s6
   4:                      Linux                         30.1 GB    disk2s7

mountコマンドでも確認したところ、/dev/disk2に関連するパーティションは以下の2つ(RECOVERYとboot)でした。

# Mac
❯ mount
(中略)
/dev/disk2s1 on /Volumes/RECOVERY (msdos, local, nodev, nosuid, noowners)
/dev/disk2s6 on /Volumes/boot (msdos, local, nodev, nosuid, noowners)

ディスクユーティリティからも以下のように確認できます。

f:id:cipepser:20190212161634p:plain f:id:cipepser:20190212161628p:plain

次にディスクユーティリティからRECOVERY/bootをマウント解除します。
（スクショを残し忘れましたが、上記2画面RECOVERY/bootの画面上部にマウント解除のボタンがあります）

続いて、VirtualBox vmdkファイルを作成し、権限を変更します。
（本当は777にしたくないですが、元記事と変えてハマるのも嫌なので、777で。。。）

# Mac
❯ sudo VBoxManage internalcommands createrawvmdk -filename ./sd-card.vmdk -rawdisk /dev/disk2
❯ sudo chmod 777 sd-card.vmdk
❯ sudo chmod 777 /dev/disk2

作成したvmdkファイルについて、VirtualBox上でハードディスクの追加を行います。

f:id:cipepser:20190212164933p:plain

既存のディスクを選択します。

f:id:cipepser:20190212164940p:plain

先ほど作成したsd-card.vmdkを開きます。

f:id:cipepser:20190212164945p:plain

ちなみにマウント解除したはずなんですが、少し時間を開けたら再度マウントされてしまっていて、以下のように失敗しました。

f:id:cipepser:20190212164811p:plain

慌てず、ディスクユーティリティから再度マウント解除すればOKです。

成功すると以下のようにsd-card.vmdkが認識されます。

f:id:cipepser:20190212165542p:plain

Ubuntu側

無事追加できたので、vagrant upしましょう。

参考までですが、一度以下のように起動に失敗しました。

❯ vagrant up
(中略)
==> default: Booting VM...
There was an error while executing `VBoxManage`, a CLI used by Vagrant
for controlling VirtualBox. The command and stderr is shown below.

Command: ["startvm", "84b91ede-c9fc-45bb-a45a-1f2dfbddee39", "--type", "headless"]

Stderr: VBoxManage: error: VD: error VERR_RESOURCE_BUSY opening image file '/Users/xxx/sd-card.vmdk' (VERR_RESOURCE_BUSY).
VBoxManage: error: Failed to open image '/Users/xxx/sd-card.vmdk' in read-write mode (VERR_RESOURCE_BUSY).
VBoxManage: error: AHCI: Failed to attach drive to Port1 (VERR_RESOURCE_BUSY)
VBoxManage: error: Details: code NS_ERROR_FAILURE (0x80004005), component ConsoleWrap, interface IConsole

こちらもRECOVERY/bootがMacにマウントされてしまっていることが原因なので、ディスクユーティリティから再度マウント解除すればOKです。

さて、vagrant sshしてからlsblkを実行し、Ubuntu上でSDカードが認識できたことを確認します。

vagrant@vagrant-ubuntu-trusty-64:~$ lsblk
NAME   MAJ:MIN RM   SIZE RO TYPE MOUNTPOINT
sda      8:0    0    40G  0 disk
└─sda1   8:1    0    40G  0 part /
sdb      8:16   0  29.7G  0 disk
├─sdb1   8:17   0   1.6G  0 part
├─sdb2   8:18   0     1K  0 part
├─sdb5   8:21   0    32M  0 part
├─sdb6   8:22   0    69M  0 part
└─sdb7   8:23   0  28.1G  0 part

sdbとして認識できていますね。これをマウントしていきます。ラズパイ上では何も考えずにntfs-3gにマウントしようとして失敗したので、今回はちゃんとファイルシステムのTYPEを確認します。

vagrant@vagrant-ubuntu-trusty-64:/volumes$ sudo blkid
/dev/sda1: LABEL="cloudimg-rootfs" UUID="xxx" TYPE="ext4"
/dev/sdb1: LABEL="RECOVERY" UUID="xxx" TYPE="vfat"
/dev/sdb5: LABEL="SETTINGS" UUID="xxx" TYPE="ext4"
/dev/sdb6: LABEL="boot" UUID="xxx" TYPE="vfat"
/dev/sdb7: LABEL="root" UUID="xxx" TYPE="ext4"

今回のゴールは「/etc/fstabを編集すること」なので、LABELがrootになっている/dev/sdb7を見ます。 TYPEはext4なので、ext4として/volumes/sdcard7にマウントします。
（/volumes/sdcard7が存在しないと思うので、事前にmkdirしておいてください）

vagrant@vagrant-ubuntu-trusty-64:/volumes$ sudo mount -t ext4 /dev/sdb7 /volumes/sdcard7

無事マウントできました。
今回のゴールであるetc/fstabが編集できます。以下記述を削除しましょう。

UUID="<MY UUID>"  /volumes/  ntfs-3g defaults,iocharset=utf8,umask=000 0 0

この状態でSDカードをラズパイに挿し、起動したら復旧しました。

`etc/fstab`を正しく設定する

復旧できたので正しい設定をしましょう。
先ほど同じようにラズパイ上でsudo blkidしてファイルシステムのTYPEを確認します。

$ sudo blkid
/dev/sda1: UUID="<MY UUID>" TYPE="vfat" PARTUUID="xxx"

vfatなので、ntfs-3gではなくvfatでマウントします。

# etc/fstab
UUID="<MY UUID>"  /volumes/  vfat defaults,iocharset=utf8,umask=000 0 0

これで再起動すれば、途中で止まることなく起動でき、/volumes/BTC/に外付けHDDがマウントされているはずです。

References

2019-02-04

haskell-ide-engineで ld: symbol(s) not found for architecture x86_64 のエラーが出る

vscode と haskell-ide-engine で Haskell 開発環境を構築する - Qiita をもとに環境構築を進めていたところ以下のエラーが出て、haskell-ide-engineをmakeすることができませんでした。

❯ make hie-8.6.3

(中略)

cabal-install-2.4.1.0: configure
Completed 19 action(s).

--  While building package cabal-install-2.4.1.0 using:
      /Users/cipepser/.stack/programs/x86_64-osx/ghc-8.6.3/bin/ghc --make -odir /private/var/folders/mc/3v_pttq16pdblh7vbqf4mvk80000gn/T/stack33371/cabal-install-2.4.1.0/.stack-work/dist/x86_64-osx/Cabal-2.4.0.1/setup -hidir /private/var/folders/mc/3v_pttq16pdblh7vbqf4mvk80000gn/T/stack33371/cabal-install-2.4.1.0/.stack-work/dist/x86_64-osx/Cabal-2.4.0.1/setup -i -i. -clear-package-db -global-package-db -package-db=/Users/cipepser/.stack/snapshots/x86_64-osx/nightly-2018-12-31/8.6.3/pkgdb -package-db=/Users/cipepser/hie/haskell-ide-engine/.stack-work/install/x86_64-osx/nightly-2018-12-31/8.6.3/pkgdb -hide-all-packages -package-id=Cabal-2.4.1.0-IaB5GUEm19R82R9cEdbB1D -package-id=base-4.12.0.0 -package-id=filepath-1.4.2.1 -package-id=process-1.6.3.0 -optP-include -optP/private/var/folders/mc/3v_pttq16pdblh7vbqf4mvk80000gn/T/stack33371/cabal-install-2.4.1.0/.stack-work/dist/x86_64-osx/Cabal-2.4.0.1/setup/setup_macros.h /private/var/folders/mc/3v_pttq16pdblh7vbqf4mvk80000gn/T/stack33371/cabal-install-2.4.1.0/Setup.hs /Users/cipepser/.stack/setup-exe-src/setup-shim-mPHDZzAJ.hs -main-is StackSetupShim.mainOverride -o /private/var/folders/mc/3v_pttq16pdblh7vbqf4mvk80000gn/T/stack33371/cabal-install-2.4.1.0/.stack-work/dist/x86_64-osx/Cabal-2.4.0.1/setup/setup -threaded
    Process exited with code: ExitFailure 1
    Logs have been written to: /Users/cipepser/hie/haskell-ide-engine/.stack-work/logs/cabal-install-2.4.1.0.log

    [1 of 2] Compiling Main             ( /private/var/folders/mc/3v_pttq16pdblh7vbqf4mvk80000gn/T/stack33371/cabal-install-2.4.1.0/Setup.hs, /private/var/folders/mc/3v_pttq16pdblh7vbqf4mvk80000gn/T/stack33371/cabal-install-2.4.1.0/.stack-work/dist/x86_64-osx/Cabal-2.4.0.1/setup/Main.o )
    [2 of 2] Compiling StackSetupShim   ( /Users/cipepser/.stack/setup-exe-src/setup-shim-mPHDZzAJ.hs, /private/var/folders/mc/3v_pttq16pdblh7vbqf4mvk80000gn/T/stack33371/cabal-install-2.4.1.0/.stack-work/dist/x86_64-osx/Cabal-2.4.0.1/setup/StackSetupShim.o )
    Linking /private/var/folders/mc/3v_pttq16pdblh7vbqf4mvk80000gn/T/stack33371/cabal-install-2.4.1.0/.stack-work/dist/x86_64-osx/Cabal-2.4.0.1/setup/setup ...
    clang-7: warning: argument unused during compilation: '-nopie' [-Wunused-command-line-argument]
    clang-7: warning: argument unused during compilation: '-nopie' [-Wunused-command-line-argument]
    ld: warning: ignoring file /Users/cipepser/.stack/snapshots/x86_64-osx/nightly-2018-12-31/8.6.3/lib/x86_64-osx-ghc-8.6.3/Cabal-2.4.1.0-IaB5GUEm19R82R9cEdbB1D/libHSCabal-2.4.1.0-IaB5GUEm19R82R9cEdbB1D.a, file was built for archive which is not the architecture being linked (x86_64): /Users/cipepser/.stack/snapshots/x86_64-osx/nightly-2018-12-31/8.6.3/lib/x86_64-osx-ghc-8.6.3/Cabal-2.4.1.0-IaB5GUEm19R82R9cEdbB1D/libHSCabal-2.4.1.0-IaB5GUEm19R82R9cEdbB1D.a
    Undefined symbols for architecture x86_64:
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziSetup_replDistPref_closure", referenced from:
          _s8sM_info in StackSetupShim.o
          _u8AR_srt in StackSetupShim.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziSetup_replVerbosity_closure", referenced from:
          _s8sZ_info in StackSetupShim.o
          _u8AT_srt in StackSetupShim.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziBuild_initialBuildSteps_closure", referenced from:
          _c8y6_info in StackSetupShim.o
          _u8AV_srt in StackSetupShim.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimple_defaultMainWithHooks_closure", referenced from:
          _s7o5_info in Main.o
          _s7o5_closure in Main.o
          _c8DE_info in StackSetupShim.o
          _u8EF_srt in StackSetupShim.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziUserHooks_replHook_closure", referenced from:
          _c8xN_info in StackSetupShim.o
          _c8y1_info in StackSetupShim.o
          _u8AW_srt in StackSetupShim.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimple_simpleUserHooks_closure", referenced from:
          _s7qo_info in Main.o
          _u7FE_srt in Main.o
          _c8xN_info in StackSetupShim.o
          _c8y1_info in StackSetupShim.o
          _s8u9_info in StackSetupShim.o
          _u8AW_srt in StackSetupShim.o
          _u8EE_srt in StackSetupShim.o
          ...
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziSetup_buildVerbosity_closure", referenced from:
          _s7p9_info in Main.o
          _u7Fs_srt in Main.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziUtils_installOrdinaryFiles_closure", referenced from:
          _r3TL_info in Main.o
          _r3TL_closure in Main.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziSetup_copyVerbosity_closure", referenced from:
          _s7pN_info in Main.o
          _u7Fv_srt in Main.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziSetup_copyDest_closure", referenced from:
          _s7q1_info in Main.o
          _u7Fx_srt in Main.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziLocalBuildInfo_absoluteInstallDirs_closure", referenced from:
          _s7nU_info in Main.o
          _u7wv_srt in Main.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziUtils_notice_closure", referenced from:
          _s7pm_info in Main.o
          _u7Fj_srt in Main.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziInstallDirs_NoCopyDest_closure", referenced from:
          _s7qn_info in Main.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziTypesziHookedBuildInfo_emptyHookedBuildInfo_closure", referenced from:
          _s8tV_info in StackSetupShim.o
          _u8EB_srt in StackSetupShim.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziUserHooks_UserHooks_con_info", referenced from:
          _c7xB_info in Main.o
          _c8DN_info in StackSetupShim.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziSetup_installVerbosity_closure", referenced from:
          _s7ql_info in Main.o
          _u7FA_srt in Main.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziInstallDirs_mandir_closure", referenced from:
          _s7nV_info in Main.o
          _u7ww_srt in Main.o
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziSimpleziFlag_fromFlag_closure", referenced from:
          _s7qk_info in Main.o
          _s7q0_info in Main.o
          _s7pM_info in Main.o
          _s7p8_info in Main.o
          _u7Fr_srt in Main.o
          _s8t0_info in StackSetupShim.o
          _s8sN_info in StackSetupShim.o
          ...
      "_Cabalzm2zi4zi1zi0zmIaB5GUEm19R82R9cEdbB1D_DistributionziTypesziLocalBuildInfo_buildDir_closure", referenced from:
          _s7nY_info in Main.o
          _s7pb_info in Main.o
          _s7pe_info in Main.o
          _u7wz_srt in Main.o
          _u7Fo_srt in Main.o
    ld: symbol(s) not found for architecture x86_64
    clang-7: error: linker command failed with exit code 1 (use -v to see invocation)
    `clang' failed in phase `Linker'. (Exit code: 1)
make: *** [cabal] Error 1

2019年1月末時点で、同じようなエラーでissueがいくつも立てられて（特にOSXで......）います。ワークアラウンドも様々なようなので、今回は自分が解消した方法を残します。

環境、ビルド対象

OS

システムのバージョン:  macOS Mojave 10.14.3 (18D42)
カーネルのバージョン: Darwin 18.2.0

haskell-ide-engine

ビルド対象のcommit: d9bcbf28408da4c42e54cfd5014cfc1cce3ca993

なお、Makefile中で指定されているようにcabalのバージョンは2.4.1.0です。

brew

念のため。

❯ brew --version
Homebrew 2.0.0
Homebrew/homebrew-core (git revision 175af; last commit 2019-02-02)
Homebrew/homebrew-cask (git revision 05a81; last commit 2019-02-02)

解決策

Build failed on MacOS with clang link error(ghc 8.4.4) · Issue #1058 · haskell/haskell-ide-engineに書いてあるとおり、別プロジェクトでインストールしていたbinutilsが悪さをしていたようです。unlinkしたところ、うまくいきました。

※ issueではghc 8.4.4ですが、8.6.3でも同じ方法で解決しました。

❯ brew unlink binutils
Unlinking /usr/local/Cellar/binutils/2.31.1_2... 120 symlinks removed
❯ rm -rf ~/.stack
❯ stack clean --full

stack cleanはrmの先にやってもいいかもしれないです。この状態で、make hie-8.6.3したらエラーが解消され、以下のようにhieがインストールできました。

❯ hie --version
Version 0.5.0.0, Git revision d9bcbf28408da4c42e54cfd5014cfc1cce3ca993 (2394 commits) x86_64 ghc-8.6.3

なお、後続のmake build-doc-8.6.3も問題なくビルドできました。

その他

Makefileのどのコマンドで失敗していたか

cabal:
    stack install cabal-install
    cabal update
    cabal install Cabal-2.4.1.0 --with-compiler=$(GHC)
.PHONY: cabal

ここのstack install cabal-installで冒頭のエラーとなっていました。

他にも試してもうまくいかなかった方法たち

hie-install-memo.md

References

2019-01-24

Writing A Compiler In Goを読んだ

Writing A Compiler In Goを読みました。

本書は、Writing An Interpreter In Go（邦訳：Go言語でつくるインタプリタ）の続編で、前作で開発したプログラミング言語MonkeyのコンパイラとVirtual Machine(以下、VM)を実装する内容となっています。

本書を読む前に、2018年後半にGo言語でつくるインタプリタを読み始めました。 Lexer、Parserを実装し、抽象構文木ASTを構築して、evalする流れを、自分の手でなぞり、ちゃんと動いたときには「Monkeyちゃん」と呼び出すほどに愛着が湧いていました。

これまで「すごそうだけどよくわからない」「いつか挑戦してみたい」と思っていた言語実装を一から自分の手でできたことに感動を覚え、「Lexerは他にも使えそうだな」と、12月にはGo2 Advent Calendar 2018 - Qiitaにて以下のようにProtocol Buffersのデコーダを書いていました。

cipepser.hatenablog.com

そんな折、続編である本書Writing A Compiler In Goの存在を知りました。 Turing Complete FMがとても好きなpodcastなのですが、2018年のセキュリティ・キャンプのCコンパイラを自作してみよう！でも多数の方がコンパイラを実装していて、本当にみんなすごいなぁと憧れを抱いていました。本書は、C言語ではないですが、コンパイラを実装できたことはとても嬉しかったです。

また、本書は現時点で邦訳が出ていません。個人的に初めて洋書を一冊完走することができた本にもなりました。初めての洋書でしたが、思いの外すらすらと読み進めることができました。理由としては以下がよかったです。

一文一文が短いので、どこを読んでいるのか迷子にならない
シンプルな言い回しなので、文意がわかる
わからなくてもコードを見れば何を言っているのかわかる
やたら文章のテンションが高く、勢いがある
「このテストは失敗して当然なんだ」のような応援が心強い

ちなみに、読むのにどれくらい時間が掛かるのか計測したところ26時間11分でした。実装中にtypoでハマったりしたので参考ですが。

f:id:cipepser:20190120123326p:plain

また、インタプリタと合わせて書いたコードの量は9289行でした。本書そのものがコメント（ドキュメント？）みたいなもので、コード中にはコメントがないので、処理そのものの行数だと考えると、気づけば結構書いたんだなぁと感慨深くもあります。

各章の所感

概要とメモベースで各章の所感を書きます。

第1章 Compilers & Virtual Machines

コンパイラ、VMとは何なのか、本書で実装するものが何なのかの説明。コードがなく（例示のみあり）、ひたすら説明。

初めての洋書だったこともあり、本章が一番つらかったかもしれない。

第2章 Hello Bytecode!

バイトコードとは何か。どうやって表現し、実装するかの概要説明。

スタックを実装して、OpCodeをVMに解釈させて実行させるまでを行う。 JVMなど聞いたことはあったVMやバイトコード、OpCodeがどういうものなのか、自分の手で実装することで掴めたのは大きかった。

第3章 Compiling Expressions

式をコンパイルする章。

まず中置式として四則演算のOpCodeから始まり、Booleanや比較演算子、前置式などを実装する。同じことを繰り返しやっていくので、よくわからなくても進めていくうちに前のほうもわかるようになる。繰り返し大事。

True/False/Nullをグローバルオブジェクトとして実装すると比較が楽（こうしないとrefrect.DeeqEqualを使うことになる）のも、勉強になった。

第4章 Conditionals

条件式をバイトコードで表現する。

条件が真のときとそうでないときで、スタックの飛ぶ先をJUMP命令として実装する。これがあのJUMP命令か！と謎の感動があった。

第5章 Keeping Track of Names

Identifier、もとい名前がついた変数や関数をバイトコードでどうやって表現するか

変数名を数字で置き換えることは知っていたが、実際に実装したことあるかないかは違うと思う。この章時点ではグローバル変数のみ実装。7章でScopeが実装される。

第6章 String, Array and Hash

章題の通り、String、Array、Hashを実装する。

同じような内容の繰り返しなので、復習を兼ねてサクサク進む。IndexをArrayとHashで同一の実装にできるのが気持ちいい。

第7章 Functions

おそらく本書の山場。関数や関数呼び出しを実装する。

個人的にはこの章が一番おもしろかったけど、同時に一番頭を使った。テストを一行一行追いかけて、スタック上がどうなっているか考えると理解できると思う。一番エッジケースを考慮しないといけないものこの章だったと思う。

関数内でローカル変数を実装するため、Scopeを定義する。関数の引数もローカル変数と同じように実装できるのがよい。 VMのほうではScopeと同様の概念をFrameと呼んでいた。

第8章 Built-in Functions

前作で登場した組み込み関数を実装する。

7章のScopeを組み込み関数用に特別に用意する。特に詰まることもなく進んだ。

第9章 Closures

クロージャを実装する。

7章でScopeの実装をしていたので、その延長ではあるものの自由変数の実装は興味深かかった。グローバル変数ではなく自由変数を扱うために、前章までで関数をOpConstantでスタックに積んでいたが、 OpClosureを使って、関数と一緒に自由変数もスタックに積む。これでうまく動くのかと懐疑的な気持ちだったが、テストが通る。すごい。

第10章 Taking Time

9章まででは関数を再帰で書けないので軽く修正を加える。

最後に、前作のevaluator v.s. vm (with compile)でベンチマーク。フィボナッチ数列の計算ベースで3倍程度速くなった。

Goコンパイラ本読了。
Goインタプリタ本で作ったevaluatorからコンパイルすることでフィボナッチ数列の計算ベースで3倍速くなった。 pic.twitter.com/J4PzdMg0Ju
— さいぺ (@cipepser) 2019年1月19日

最後に

思いは、本記事の序盤で語ってしまったので、多くは語りませんが、同じよう気持ちを持っている人には強く勧めます。もちろん最適化や実装方法にも別の方式があるなど、本書の範囲外となっていることも多数あります。（本書でも最適化よりわかりやすさ、学習を優先すると述べられている）しかし、入門書としてとても素晴らしい本だと思います。

なお、LexerやParserは、前作から引き続き利用するので、Go言語でつくるインタプリタから読むべきです。前作から合わせるとクロージャや第一級オブジェクト、リテラルなどイマイチ掴めていなかった概念を、実装することで理解を深めることができました。

あとTDD（Table Driven Tests）を実践できるのも、Goのプラクティスを知る上で役立つと思います。ただ、テストパターンはTypoで詰まると結構ハマる（1つのTypoで2時間くらい溶かしたりした）ので、コピペがおすすめです。（たぶんめんどくさくなるのもある）

本書は、Writing A Compiler In Go | Thorsten Ballで買えますが、eBookで買うとePub (iBook), Mobi (Kindle), PDF and HTMLで読めるのもよかったです。

References

Go言語でつくるインタプリタ

作者:Thorsten Ball
発売日: 2018/06/16
メディア: 単行本（ソフトカバー）

環境

事前準備

結論

具体例

[i32]

Vec<i32>

文字列まわり

char

[&str]

String

References

鍵生成

署名

検証

補足

References

双線形とは何なのか

ベクトル空間における線形性（その1）

ベクトル空間における線形性（その2）

双線形の例

双線形な例

双線形じゃない例2

BLS署名における双線形

References

背景

開封の儀

Bitcoin Coreのインストール

HDDのマウント

Bitcoin Coreの設定

Bitcoin Coreの起動

References

環境情報

発生事象

復旧

方針

環境情報

復旧手順

Mac側

Ubuntu側

etc/fstabを正しく設定する

References

環境、ビルド対象

OS

haskell-ide-engine

解決策

その他

Makefileのどのコマンドで失敗していたか

他にも試してもうまくいかなかった方法たち

References

各章の所感

第1章 Compilers & Virtual Machines

第2章 Hello Bytecode!

第3章 Compiling Expressions

第4章 Conditionals

第5章 Keeping Track of Names

第6章 String, Array and Hash

第7章 Functions

第8章 Built-in Functions

第9章 Closures

第10章 Taking Time

最後に

References

`[i32]`

`Vec<i32>`

`char`

`[&str]`

`String`

双線形じゃない例²

`etc/fstab`を正しく設定する