GoでCount-min sketchを実装する

この記事は Go Advent Calendar 2019 の2日目の記事です。

f:id:cipepser:20191119213339j:plain

こんにちは!さいぺです。
サムネのGopherくんは最近趣味で描いたものを、せっかくなので載せました。 オリジナルのThe Go gopherGopherくん)は、Renée Frenchによってデザインされました。

さて、以下の動画を見てMiniSketchなるデータ構造があることを知りました。

動画中のMiniSketchでは集合のreconcileまで述べられていますが、今回はCount-min sketchを実装します。より具体的には、指定した要素がいくつ追加されたのかを返すデータ構造を実装します。

Count-min sketchとは

Count-min sketchは、追加された要素の数を記憶するデータ構造です。
BloomFilterに似た確率的データ構造で、BloomFilterが要素の有無をboolで返すのに対して、Count-min sketchは追加された要素の数をintで返します。
偽陽性を許容することで、追加された要素の数を得るための最悪計算量が O(1)、メモリサイズを固定にできます。

アルゴリズム

k個のハッシュ関数k個のテーブルを利用します。
各テーブルのフィールドは0に初期化されています。 それぞれのハッシュ関数とテーブルは1:1で対応しており、要素を追加する際にフィールドの値をインクリメントします。

ハッシュ関数の数k=3、テーブルのサイズN=10として、二つの要素 e_1 e_2を追加する例を考えます。3つの各テーブルのindexは0始まりで図示しています。

f:id:cipepser:20191201030221p:plain

1つ目の要素 e_1に対して、3つのハッシュ値を計算し、該当するフィールド(中段図の赤字)をインクリメントします。

続けて、2つ目の要素 e_2に対して、3つのハッシュ値を計算し、該当するフィールド(下段図の赤字)をインクリメントします。

要素がいくつ追加されたのか知りたいときも同じような手順をとります。
例えば上記の例で e_2がいくつ追加されたのか知りたいとします。 このとき要素 e_2に対する3つのハッシュ値を計算します(図中の中段から下段に移動したときと同じ)。該当するフィールドの値を参照すると121が得られます(下段図の赤字)。この3つの数字のうち、最小(min)の値を要素が追加された数として返すのがCount-min sketchです(今回の例では1を返す)。
 h_2(e_1) h_2(e_2)が衝突しましたが、ハッシュ関数を3つ用意したことで、衝突していない残り2つの値が正しい答えとして、追加された要素の数を表現できていることがわかります。

実装

アルゴリズムが理解できたところで実装に移ります。 本記事ではポイントを絞って説明しますが、実装した一式はGitHubにあるので興味がある方はご覧ください。

github.com

データ構造

まずSketch型を以下のように定義します。 ここでkハッシュ関数の数、Nは各テーブルのサイズです。

type Sketch [k][N]int

Addの実装

k個のハッシュ関数は、Double-hash法で用意します。 Double-hash法については、以前の記事で触れていますのでご参照ください。

cipepser.hatenablog.com

今回はDouble-hash法をこのように実装していますが、Sketchのアルゴリズムとは直接関係ないので本記事では省略します。

要素をSketchに追加するためのメソッドAddの実装は以下のようになります。

func (s *Sketch) Add(elem string) error {
    for i := 0; i < k; i++ {
        h, err := util.DoubleHashing(elem, i, N)
        if err != nil {
            return err
        }
        s[i][h] += 1
    }

    return nil
}

k個のテーブルそれぞれに紐づくハッシュ関数があるので、要素のハッシュ値を計算します。 そのハッシュ値ををテーブルのindexだと思って、対応するフィールドをインクリメントするだけです。

Countの実装

要素がいくつ追加されたのかを得るためのメソッドCountの実装は以下です。

func (s *Sketch) Count(elem string) (int, error) {
    min := math.MaxInt64

    for i := 0; i < k; i++ {
        h, err := util.DoubleHashing(elem, i, N)
        if err != nil {
            return 0, err
        }

        if s[i][h] < min {
            min = s[i][h]
        }
    }

    return min, nil
}

Addと同じくk個のハッシュ値を計算します。 k個のハッシュ値のうち最小のものを、追加された要素の数として返します。

動作を確認する

実際に動かしてみましょう。 以下のようにaeをそれぞれ15個追加します。 なお、ハッシュ関数の数k=3、テーブルのサイズN=10としています。

elements := []string{
    "a",
    "b", "b",
    "c", "c", "c",
    "d", "d", "d", "d",
    "e", "e", "e", "e", "e",
}

要素を追加する操作はこんな感じです。

for _, e := range elements {
    err := s.Add(e)
    if err != nil {
        panic(err)
    }
}

uniques := []string{"a", "b", "c", "d", "e"}として、すべての要素がいくつずつ追加されたのか出力させてみます。

for _, e := range uniques {
    cnt, err := s.Count(e)
    if err != nil {
        panic(err)
    }
    fmt.Println(e, ":", cnt)
}

実行結果です。しっかり追加した要素の数を取得できていますね。

❯ go run main.go
a : 1
b : 2
c : 3
d : 4
e : 5

ハッシュ衝突させてみる

ハッシュ衝突させてみたかったので、要素の数を増やしたところghで衝突しました。

elements := []string{
    "a",
    "b", "b",
    "c", "c", "c",
    "d", "d", "d", "d",
    "e", "e", "e", "e", "e",
    "f", "f", "f", "f", "f", "f",
    "g", "g", "g", "g", "g", "g", "g",
    "h", "h", "h", "h", "h", "h", "h", "h",
}

以下のようにg(7個)とh(8個)で15となりました。

❯ go run main.go
a : 1
b : 2
c : 3
d : 4
e : 5
f : 6
g : 15
h : 15

最後に

偽陽性はありますが、データ構造自体のサイズを固定できるのは魅力的です。 今回はテーブルサイズをかなり小さくしたので比較的容易にハッシュ衝突しましたが、もう少し大きなNを選べば十分実用的でしょう。1
今回はベンチマークまで取れていないのでkNを大きくしたときにどうなるか調べるのもおもしろそうです。 あとはMiniSketchでの集合をreconcileもいずれ実装したいです。

References


  1. 本当は偽陽性確率がどれくらいに抑えられるかも本記事に間に合わせたかった

Go1.13のError wrappingを触ってみる

2019年9月3日にGo 1.13がリリースされました。 リリースノートを見ていて、Error wrappingが気になったので触ってみます。

何はともあれ、ドキュメントを見てみます。 errorsのドキュメントを確認すると、以下4つの関数が存在します。

func As(err error, target interface{}) bool
func Is(err, target error) bool
func New(text string) error
func Unwrap(err error) error

Newはただのコンストラクタなのでいいとして、残り3つは挙動を確認します。

Isを使ってみる

順番が前後しますが、Isから見ていきましょう。 Go1.12以前では、以下のような(if err != nil)エラーハンドリングをしていたと思います。

package main

import (
    "errors"
    "fmt"
)

var (
    MyError = myError()
)

func myError() error { return errors.New("myErr") }

func simpleError() error {
    return MyError
}

func main() {
    err := simpleError()
    if err != nil {
        fmt.Println(err) // myError
    }
}

もしくは、switch文を用いて以下のようにするパターンもありますね。
※以降では、main以外の共通部分は省略します。

func main() {
    err := simpleError()
    if err != nil {
        switch err {
        case MyError:
            fmt.Println("MyError:", err) // MyError: myErr
        default:
            fmt.Println("default:", err)
        }
    }
}

Isを用いると以下のように(if errors.Is(err, MyError))なります。

func main() {
    err := simpleError()
    if errors.Is(err, MyError) {
        fmt.Println(err) // myError
    }
}

Isの使い方はわかりましたが、Isの何が嬉しいのでしょうか。 本アップデートの名前にもあるようにwrapしたときに活きてきます。

ドキュメントにあるように、wrapするには%wを使います。 例えば、以下のような実装になります。

func wrappedError() error {
    err := simpleError()
    return fmt.Errorf("%w", err)
}

実際にwrappedErrorを用いて、wrapしたときのerrの型を見てみましょう。

func main() {
    err = simpleError()
    fmt.Printf("%T", err) // *errors.errorString

    fmt.Println()

    err := wrappedError()
    fmt.Printf("%T", err) // *fmt.wrapError
}

wrapする前は*errors.errorString型だったものが、*fmt.wrapError型になっていることがわかります。
先ほどのswitch文の例を実行してみると、MyErrorのエラーを捕まえることができなくなってしまいました。

func main() {
    err := wrappedError() // wrappedErrorに変わったことに注意
    if err != nil {
        switch err {
        case MyError:
            fmt.Println("MyError:", err)
        default:
            fmt.Println("default:", err) // default: myErr
        }
    }
}

そこでIsの登場です。

func main() {
    err := wrappedError()
    if errors.Is(err, MyError) {
        fmt.Printf(err.Error()) // myErr
    }
}

こちらはMyErrorを捉えられています。

Asを使ってみる

次にAsについてです。 個人的に最近はパーサーを書くことが多いので、以下のような例を用意しました。 Parseに失敗したときのエラーをハンドリングする例です。 返ってきたerrInvalidCharに型キャストして、エラーハンドリングしています。

package main

import (
    "errors"
    "fmt"
)

type InvalidChar struct {
    // other fields
    err error
}

func (ic *InvalidChar) Error() string {
    ic.err = errors.New("INVALID CHARACTER")
    return fmt.Errorf("%w", ic.err).Error()
}

func Parse() error {
    return &InvalidChar{}
}

func main() {
    err := Parse()
    if ierr, ok := err.(*InvalidChar); ok {
        fmt.Println(ierr) // INVALID CHARACTER
    }
}

Asを用いると以下のようになります。

func main() {
    err := Parse()
    var ierr *InvalidChar
    if errors.As(err, &ierr) {
        fmt.Println(ierr) // INVALID CHARACTER
    }
}

ここまでは、Isの例と同じなので本例でもwrappedErrorを実装します。

func wrappedError() error {
    err := Parse()
    return fmt.Errorf("%w", err)
}

wrapされたerrをGo1.12以前の方法で扱おうとすると以下のようにチェックをすり抜けます。

func main() {
    err := wrappedError()
    if ierr, ok := err.(*InvalidChar); ok {
        fmt.Println(ierr) // 何も出力されない
    }
}

以下のようにAsを用いれば、正しくハンドリングすることができます。

func main() {
    err := wrappedError()
    var ierr *InvalidChar
    if errors.As(err, &ierr) {
        fmt.Println(ierr) // INVALID CHARACTER
    }
}

Unwrapを触ってみる

最後にUnwrapです。 例はAsで用いたものと同じです。

func main() {
    err := wrappedError()
    fmt.Printf("Type:%T\nValue:%v\n", err, err)
    // Type:*fmt.wrapError
    // Value:INVALID CHARACTER

    err = errors.Unwrap(err)
    fmt.Printf("Type:%T\nValue:%v\n", err, err)
    // Type:*main.InvalidChar
    // Value:INVALID CHARACTER

    err = errors.Unwrap(err)
    fmt.Printf("Type:%T\nValue:%v\n", err, err)
    // Type:<nil>
    // Value:<nil>
}

wrapされたエラーを順番にUnwrapしていくことができ、最後にはnilになります。

所感

  • 標準ライブラリや外部ライブラリのエラーをwrapできるようになったのはありがたい
  • Go1.13以降で開発されたライブラリを用いることも考慮し、安全に倒すためにIsAsでエラーハンドリングしたほうがよさそう
  • エラー型が多くなってきたときにswitch文が使えないのが微妙

3つ目について、Go1.13からは今までのエラーハンドリングが機能しなくなるかもしれない - Qiitaでも言及されています。 以下のようにUnwrapする案も考えましたが、多段でwrapした際にうまく動かなくなるので実用的ではないでしょう。。。

func main() {
    err := wrappedError()
    switch errors.Unwrap(err).(type) {
    case *InvalidChar:
        fmt.Println("InvalidChar:", err) // InvalidChar: INVALID CHARACTER
    default:
        fmt.Println("default:", err)
    }
}

References

Rustでprotobufのゼロ値がどうやって実現されているか

以前、以下の記事たちを書きました。

cipepser.hatenablog.com

cipepser.hatenablog.com

Rustで0byteを読み込むとどうなるのか(Option型になるのか)気になったので検証してみます。

0byteをrust-protobufで読み込む

protobufを読み込むコードは、Golangで出力したprotobufバイナリをRustで読み込む - 逆さまにしたとほぼ同じです。一点変更しているのは、読み込むファイル名で、main.rsgo_user.binzero.binに変更しました。

ちなみに.protoの定義は以下の通りです。

syntax = "proto3";
package user;

message User {
  string name = 1;
  int32 age = 2;
}

空ファイルを作成し、それを読み込んだ実行結果は以下の通りです。 Goでいうゼロ値でデコードできています。

❯ touch zero.bin

❯ cargo run
Name:
Age: 0

というのもproto3の仕様に以下のように書いてあるのです。

Unknown fields are well-formed protocol buffer serialized data representing fields that the parser does not recognize. For example, when an old binary parses data sent by a new binary with new fields, those new fields become unknown fields in the old binary.

つまりprotobufでは、unknow fieldsも含めて仕様化されており、パーサーは値が存在しないのか、フィールドが定義されていないのかは区別できないのです。
ゼロ値ならバイナリにすらエンコードされないので、送るデータそのものを無くすことができる効率性があります。

protocで生成したコードの実装

protobufの仕様からGoのゼロ値のようにデフォルト値が使われることがわかりました。 もう一歩踏み込んで、protoc --rustoutでgenerateした実装を見ていきましょう。

わかりやすところで、Golangで出力したprotobufバイナリをRustで読み込む - 逆さまにしたで利用した以下のgetメソッドの実装を見ていきます。

println!("Name: {}", u.get_name());
println!("Age: {}", u.get_age());

protoc --rustoutでgenerateした実装を確認すると、以下のようになっています。

pub fn get_name(&self) -> &str {
    &self.name
}

pub fn get_age(&self) -> i32 {
    self.age
}

返り値がOptionに包まれていないですね。 Goの場合はゼロ値がありますが、Rustではどうやって実現されているんでしょうか。 ということでnewの実装をみてみます。

impl User {
    pub fn new() -> User {
        ::std::default::Default::default()
    }
}

予想通りですが、defaultが使われています。
なお、Userの定義でもDefaultがattributeに含まれています。

#[derive(PartialEq,Clone,Default)]
pub struct User {
    // message fields
    pub name: ::std::string::String,
    pub age: i32,
    // special fields
    pub unknown_fields: ::protobuf::UnknownFields,
    pub cached_size: ::protobuf::CachedSize,
}

References

実践Rust入門を読んだ

実践Rust入門 言語仕様から開発手法まで, κeen, 河野達也, 小松礼人を読みました。本書の特徴は以下の3つでしょう。

  • 2018 Editionに対応している
  • FFIについて日本語で書かれた書籍
  • 実践 を意識した内容になっている

本記事では、特に3つ目の実践的という観点で感想を述べようと思います。

Rustの言語仕様という観点で言えば、プログラミングRustのほうが網羅性は高いでしょう。 しかし、Rustは入門のハードルがとても高い言語です。1

個人的な経験でいえば、mapfilterでさえHaskellを勉強していなかったら、とっつきにくかったんじゃないかと思います。他言語の経験が豊富であればまだしも、いきなりRustを始めると挫折してしまうでしょう。 だからこそ、本書のような実践的な入門書は重要だと思います。「あれもこれもやらなきゃいけない」とならずに、実際に利用されるトピックから取り組めるのはとても良いことだと思います。

また、わかってる人からすると当たり前だけど初学者はわからないというようなことが、言語化されていたのもよかったです。例えばP.151では、桁あふれのメソッドについて

  • 検査付き演算: checked_
  • 飽和演算: saturating_
  • ラッピング演算: wrapping_
  • 桁あふれ演算: overflowing_

のprefixがつく、と言及されていました。他にもP.169のボックス化されたスライスでは、

使う機会はあまりなさそうですが、

と書かれていたりして、力の抜きどころもわかって良かったです。 プログラミングRustを読んでいると網羅性が高いのはいいんですが、これはいつ使うんだろう?となることがあるのでこういう配慮は助かります。

他にも、プログラミングRustにも載っている内容ではあるものの、Stringstrの違いは最初にわからなくなりがちなところなので、メモリ表現が図解されているのもわかりやすいと思います。
また、ユニット型()がサイズゼロだと知ってるとcollectionでSet作りたいときに()使えば良さそうと思えるのも良かったです。以前、GoでSetライブラリを自作しようとしたときにstruct{}{}だらけになったのでRustのほうが同じサイズゼロで実装するのにきれいに書けますね。 2

いいところばかりなのもあれなので、気になったところも述べます。 内容ではないですが、誤植が気になりました。 例えば、ch07_10_closures.rslet lookup = || assert!(s1.find('d').is_some()); に閉じカッコがないなど、コンパイルが通らないエラーは潰し込んでほしかったなと。 とはいえ、誤植はrust-jpのslackでも報告、対応してくださっているので、大きな問題はなかったです。 また、GitHubのコードは問題なく動くのでこちらも見ながら進めれば大丈夫でした。

構成で気になったのが、P.271の最後です。ここはgrowを実装する前だと動かないので、初学だと動かなくてちょっと困るかもと思いました。newしただけだとサイズ0しかヒープに領域確保してないので、動かないと思います。一度読み飛ばして、growを実装後に、戻ってくれば実行できるので、順序が逆だとわかりやすそうです。

また、本書でもマクロが使われているので、簡単な紹介くらいあるともっと良かったかと思います。

特に良かった章

最後に、個人的に勉強になった・楽しかった章の感想を残します。

第7章 所有権システム

Rust特有の概念である所有権やライフタイムについて第1部の中で特に実践的な章でした。 簡易版のVecを実際に自分の手で実装することで、利用頻度の高いVecの内部実装がイメージできるのは大きいと思います。 また、CopyとClone、RcとArc、FnとFnMutとFnOnceの違いが書かれていて、頭の中が整理できました。

第9章 パーサを作る

本書で一番読みたかった章です。 再帰下降パーサはmonkeyで実装したことがありましたが、Annotationをつけたことがなかったのと、エラー処理をちゃんとできるのはとても楽しかったです。

第10章 パッケージを作る

パッケージの作成、CI、crate.ioへの公開と一通り触れてよかったです。特にcrate.ioへの公開は初めてだったので勉強になりました。

第11章 Webアプリケーション、データベース接続

リクエストの受付からDBへの接続、レスポンスを返すところまで一式という章です。 Futuresに振れることができたのも大きな収穫でした。 また、CLIがこんなに簡単に書けるのかという驚きもありました。

References

実践Rust入門[言語仕様から開発手法まで]

実践Rust入門[言語仕様から開発手法まで]

プログラミングRust

プログラミングRust


  1. 本書の「はじめに」でも学習コストが高いことに言及されています

  2. RustはCollectionがstdにありますが。

Rustでsliceをシャッフルする

メモ書きです。

O'Reilly Japan - プログラミングRustを読んでいたら rand::Rng - Rustでsliceのシャッフルができるとあったので試したところrand::Rng::shuffleがdeprecatedになっていました。 SliceRandom::shuffleを使った例を残します。

Cargo.tomlは以下のとおりです。

[dependencies]
rand = "0.6.5"

実装例

use rand::seq::SliceRandom;

fn main() {
    let mut v = vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

    let mut rng = rand::thread_rng();
    v.shuffle(&mut rng);
    println!("{:?}", v); // [3, 4, 7, 6, 2, 0, 5, 9, 1, 8] 
}

deprecatedな実装

use rand::Rng;

fn main() {
    let mut v = vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

    let mut rng = rand::thread_rng();
    rng.shuffle(&mut v);
    println!("{:?}", v);
}
❯ cargo run
warning: use of deprecated item 'rand::Rng::shuffle': use SliceRandom::shuffle instead
 --> src/main.rs:7:9
  |
7 |     rng.shuffle(&mut v);
  |         ^^^^^^^
  |
  = note: #[warn(deprecated)] on by default

    Finished dev [unoptimized + debuginfo] target(s) in 0.64s
     Running `target/debug/rust-shuffle-slice`
[1, 2, 4, 8, 3, 5, 7, 0, 9, 6]

References

メモリをダンプして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ポインタ - 簡潔なQas_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,
}

またRawVecraw_vec.rsで実装されています。

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

このようにVec<T>lencapを持ちます。

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

// (再掲)
[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]
}

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

文字列まわり

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

  • [char]Vec<char>
  • [&str]Vec<&str>
  • StringVec<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]

lencap3(うしろ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]

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

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

f:id:cipepser:20190317174507p:plain

References

プログラミングRust

プログラミングRust

BLS署名について

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

cipepser.hatenablog.com

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

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


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