仮想通貨の基礎知識、事例：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で比較すれば十分です。

References

2018-02-03

Golangでgraphパッケージを書いた

グラフ理論のアルゴリズムで遊ぶための前準備として、graphパッケージを自作してみました。
基本的な操作として、以下ができます。

無向グラフ/有向グラフの生成
頂点(Vertex)の追加/削除
辺(Edge)の追加/削除

How to Install

$ go get github.com/cipepser/goGraphAlgo/...

可視化もできるようにしているので、可視化したい場合は以下もインストールしてください。

$ brew install graphviz
$ go get github.com/awalterschulze/gographviz

How to Use

具体的な使い方を以下に示します。いずれもerrorを返すようにしているのて適宜エラーチェックをしてください。

無向グラフの生成

g := graph.NewGraph()

※内部でisDirectedフィールドを持っていますが、ゼロ値がfalseのためデフォルトで無向グラフになります。

有向グラフの生成

g := graph.NewGraph()
g.SetDir(true)

頂点(Vertex)の追加/削除

g.AddVertex(0) // vertex 0を追加
g.AddVertex(1) // vertex 1を追加
g.AddVertex(2) // vertex 2を追加

g.RemoveVertex(2) // vertex 2を削除
g.RemoveVertex(1) // vertex 1を削除

辺(Edge)の追加/削除

AddEdgeの第3引数はedgeの重み(int)になります。

// edgeを追加する前にvertexの追加が必要
g.AddVertex(0)
g.AddVertex(1)

g.AddEdge(0, 1, 3) // 0→1に重み3のedgeを追加

g.RemoveEdge(0, 1) // 0→1のedgeを削除

可視化

g.Visualize()

Example

簡単な有向グラフを作成し、可視化してみます。

package main

import (
    "github.com/cipepser/goGraphAlgo/graph"
)

func main() {

    g := graph.NewGraph()
    g.SetDir(true)

    g.AddVertex(0)
    g.AddVertex(1)
    g.AddVertex(2)
    g.AddVertex(3)

    g.AddEdge(0, 1, 0)
    g.AddEdge(0, 2, 0)
    g.AddEdge(0, 3, 0)
    g.AddEdge(2, 3, 0)

    if err := g.Visualize(); err != nil {
        panic(err)
    }

}

上記をmain.goとして実行(go run main.go)するとgv.dotファイルが生成されます。これを以下のようにgraphgizでpngにします。

$ go run main.go
$ dot -T png ./gv.dot -o ./gv.png
$ open ./gv.png

f:id:cipepser:20180127175606p:plain

最後に

今後はこのパッケージを使って、グラフ理論のアルゴリズムを実装していく予定です。 repoはこちら

References

2018-01-27

【Golang】LINE Notifyで画像を送る

先日の記事では、LINE Notifyでメッセージを送りました。今回は画像を送ってみます。
少し検索してみても、メッセージを送る記事ばかりで画像を送るのはあまりないですね。 LINE公式のSDKでもimageFileで検索しても、実装されていないようなので、自分で実装することにしました。

ハマったところ

LINE Notify API Documentにもやり方が書いてあるし、すぐできると思ったのですが、multipart/form-dataでハマりました。

LINE NotifyにSticker送信機能と画像アップロード機能が追加されましたに書いてあるようにcurlで以下のように画像を送信できます。

$ curl -X POST https://notify-api.line.me/api/notify
       -H 'Authorization: Bearer YOUR_PERSONAL_ACCESS_TOKEN'
       -F 'message=test'
       -F 'imageFile=@/PATH/TO/IMAGE/cony.jpg'

curlした結果をパケットキャプチャ取得して、http streamを見てみると以下のようになってるんですね。

Content-Type: multipart/form-data; boundary=------------------------1ac14b01bb1c4782

--------------------------1ac14b01bb1c4782
Content-Disposition: form-data; name="message"

test
--------------------------1ac14b01bb1c4782
Content-Disposition: form-data; name="imageFile"; filename="sample.jpg"
Content-Type: image/jpeg

(略)

LINE Notify API Documentのリクエスト方法にmultipart/form-dataが書いてあるのは、ここで使うためだったようです。

Content-Type application/x-www-form-urlencoded OR multipart/form-data

恥ずかしながら、multipart/form-dataを使ったことがなかったので、調べたところ [PRG]いまさら聞けないHTTPマルチパートフォームデータ送信にわかりやすく書いてありました。

Content-Typeのフォーマットは以下で、boundaryで指定される文字列によって区切ってあげることで、複数のデータをhttpリクエスト中に付与できるようになっています。

Content-Type: multipart/form-data; boundary=「バウンダリ文字列」\r\n

golangには、標準のmime/multipartパッケージがあるので、こちらを利用します。さらに今回は、imageFileと独自ヘッダを付けたいので、 net/textprotoパッケージも使います。

実装

実装は以下です。

package main

import (
    "bytes"
    "errors"
    "image/jpeg"
    "image/png"
    "io"
    "mime/multipart"
    "net/http"
    "net/textproto"
    "os"
    "path/filepath"
)

var (
    URL = "https://notify-api.line.me/api/notify"
)

func main() {
    msg := "send an image"
    filename := "./tmp.jpg"
    accessToken := "<YOUR ACCESS TOKEN>"
    f, err := os.Open(filename)
    if err != nil {
        panic(err)
    }
    defer f.Close()

    c := &http.Client{}

    var b bytes.Buffer
    w := multipart.NewWriter(&b)

    fw, err := w.CreateFormField("message")
    if err != nil {
        panic(err)
    }
    if _, err = fw.Write([]byte(msg)); err != nil {
        panic(err)
    }

    part := make(textproto.MIMEHeader)
    part.Set("Content-Disposition", `form-data; name="imageFile"; filename=`+filename)

    img, format, err := checkImageFormat(f, filename)
    if err != nil {
        panic(err)
    }

    if format == "jpeg" {
        part.Set("Content-Type", "image/jpeg")
    } else if format == "png" {
        part.Set("Content-Type", "image/png")
    } else {
        panic("LINE Notify supports only jpeg/png image format")
    }

    fw, err = w.CreatePart(part)
    if err != nil {
        panic(err)
    }

    io.Copy(fw, img)
    w.Close() // boundaryの書き込み
    req, err := http.NewRequest("POST", URL, &b)
    if err != nil {
        panic(err)
    }

    req.Header.Set("Content-Type", w.FormDataContentType())
    req.Header.Set("Authorization", "Bearer "+accessToken)

    resp, err := c.Do(req)
    if err != nil {
        panic(err)
    }

    if resp.StatusCode != 200 {
        panic("failed to send image, get http status code: " + resp.Status)
    }
}

// checkImageFormat validates an image file is not illegal and
// returns image as io.Reader and file format.
func checkImageFormat(r io.Reader, filename string) (io.Reader, string, error) {
    ext := filepath.Ext(filename)

    var b bytes.Buffer
    if ext == ".jpeg" || ext == ".jpg" || ext == ".JPEG" || ext == ".JPG" {
        ext = "jpeg"
        img, err := jpeg.Decode(r)
        if err != nil {
            return nil, "", err
        }

        if err := jpeg.Encode(&b, img, &jpeg.Options{Quality: 100}); err != nil {
            return nil, "", err
        }
    } else if ext == ".png" || ext == ".PNG" {
        ext = "png"
        img, err := jpeg.Decode(r)
        if err != nil {
            return nil, "", err
        }

        if err = png.Encode(&b, img); err != nil {
            return nil, "", err
        }
    } else {
        return nil, "", errors.New("Image format must be jpeg or png")
    }

    return &b, ext, nil
}

sdkにしたものはGithubに上げてあります。使い方はREADMEに記載しています(LINE -> 画像を送る)。

References

2018-01-20

歴代の年始め最初に発表されたCVE(1999〜2018)をスクレイピングする

Google スプレッドシートでのスクレイピングがとても便利なので、題材としてNISTから1999年以降毎年最初に発表されたCVE(CVE-yyyy-0001)の descriptionを抜き出してみました。

やり方

IMPORTXML関数を使うだけです。簡単かつ強力でした。
フォーマットはIMPORTXML(URL, XPATH)です。

XPATHの記法は以下を参考にしました。 XPATHは、Chromeの要素を検証からCopy XPathでうまくいく場合もありますが、 NISTのページではうまくいかず。ちゃんと理解するの大切ですね。

クローラ作成に必須！XPATHの記法まとめ

今回の場合は、以下の実装としました。

=IMPORTXML(URL,"//p[@data-testid='vuln-description']")

結果

ID	内容
CVE-1999-0001	ip_input.c in BSD-derived TCP/IP implementations allows remote attackers to cause a denial of service (crash or hang) via crafted packets.
CVE-2000-0001	RealMedia server allows remote attackers to cause a denial of service via a long ramgen request.
CVE-2001-0001	cookiedecode function in PHP-Nuke 4.4 allows users to bypass authentication and gain access to other user accounts by extracting the authentication information from a cookie.
CVE-2002-0001	Vulnerability in RFC822 address parser in mutt before 1.2.5.1 and mutt 1.3.x before 1.3.25 allows remote attackers to execute arbitrary commands via an improperly terminated comment or phrase in the address list.
CVE-2003-0001	Multiple ethernet Network Interface Card (NIC) device drivers do not pad frames with null bytes, which allows remote attackers to obtain information from previous packets or kernel memory by using malformed packets, as demonstrated by Etherleak.
CVE-2004-0001	Unknown vulnerability in the eflags checking in the 32-bit ptrace emulation for the Linux kernel on AMD64 systems allows local users to gain privileges.
CVE-2005-0001	Race condition in the page fault handler (fault.c) for Linux kernel 2.2.x to 2.2.7, 2.4 to 2.4.29, and 2.6 to 2.6.10, when running on multiprocessor machines, allows local users to execute arbitrary code via concurrent threads that share the same virtual memory space and simultaneously request stack expansion.
CVE-2006-0001	Stack-based buffer overflow in Microsoft Publisher 2000 through 2003 allows user-assisted remote attackers to execute arbitrary code via a crafted PUB file, which causes an overflow when parsing fonts.
CVE-2007-0001	The file watch implementation in the audit subsystem (auditctl -w) in the Red Hat Enterprise Linux (RHEL) 4 kernel 2.6.9 allows local users to cause a denial of service (kernel panic) by replacing a watched file, which does not cause the watch on the old inode to be dropped.
CVE-2008-0001	VFS in the Linux kernel before 2.6.22.16, and 2.6.23.x before 2.6.23.14, performs tests of access mode by using the flag variable instead of the acc_mode variable, which might allow local users to bypass intended permissions and remove directories.
CVE-2009-0001	Heap-based buffer overflow in Apple QuickTime before 7.6 allows remote attackers to cause a denial of service (application termination) and possibly execute arbitrary code via a crafted RTSP URL.
CVE-2010-0001	Integer underflow in the unlzw function in unlzw.c in gzip before 1.4 on 64-bit platforms, as used in ncompress and probably others, allows remote attackers to cause a denial of service (application crash) or possibly execute arbitrary code via a crafted archive that uses LZW compression, leading to an array index error.
CVE-2011-0001	Double free vulnerability in the iscsi_rx_handler function (usr/iscsi/iscsid.c) in the tgt daemon (tgtd) in Linux SCSI target framework (tgt) before 1.0.14, aka scsi-target-utils, allows remote attackers to cause a denial of service (memory corruption and crash) and possibly execute arbitrary code via unknown vectors related to a buffer overflow during iscsi login. NOTE: some of these details are obtained from third party information.
CVE-2012-0001	The kernel in Microsoft Windows XP SP2, Windows Server 2003 SP2, Windows Vista SP2, Windows Server 2008 SP2, R2, and R2 SP1, and Windows 7 Gold and SP1 does not properly load structured exception handling tables, which allows context-dependent attackers to bypass the SafeSEH security feature by leveraging a Visual C++ .NET 2003 application, aka "Windows Kernel SafeSEH Bypass Vulnerability."
CVE-2013-0001	The Windows Forms (aka WinForms) component in Microsoft .NET Framework 1.0 SP3, 1.1 SP1, 2.0 SP2, 3.0 SP2, 4, and 4.5 does not properly initialize memory arrays, which allows remote attackers to obtain sensitive information via (1) a crafted XAML browser application (XBAP) or (2) a crafted .NET Framework application that leverages a pointer to an unmanaged memory location, aka "System Drawing Information Disclosure Vulnerability."
CVE-2014-0001	Buffer overflow in client/mysql.cc in Oracle MySQL and MariaDB before 5.5.35 allows remote database servers to cause a denial of service (crash) and possibly execute arbitrary code via a long server version string.
CVE-2015-0001	The Windows Error Reporting (WER) component in Microsoft Windows 8, Windows 8.1, Windows Server 2012 Gold and R2, and Windows RT Gold and 8.1 allows local users to bypass the Protected Process Light protection mechanism and read the contents of arbitrary process-memory locations by leveraging administrative privileges, aka "Windows Error Reporting Security Feature Bypass Vulnerability."
CVE-2016-0001	REJECT DO NOT USE THIS CANDIDATE NUMBER. ConsultIDs: none. Reason: The CNA or individual who requested this candidate did not associate it with any vulnerability during 2016. Notes: none.
CVE-2017-0001	The Graphics Device Interface (GDI) in Microsoft Windows Vista SP2; Windows Server 2008 SP2 and R2 SP1; Windows 7 SP1; Windows 8.1; Windows Server 2012 Gold and R2; Windows RT 8.1; and Windows 10 Gold, 1511, and 1607 allows local users to gain privileges via a crafted application, aka "Windows GDI Elevation of Privilege Vulnerability." This vulnerability is different from those described in CVE-2017-0005, CVE-2017-0025, and CVE-2017-0047.
CVE-2018-0001	A remote, unauthenticated attacker may be able to execute code by exploiting a use-after-free defect found in older versions of PHP through injection of crafted data via specific PHP URLs within the context of the J-Web process. Affected releases are Juniper Networks Junos OS: 12.1X46 versions prior to 12.1X46-D67; 12.3 versions prior to 12.3R12-S5; 12.3X48 versions prior to 12.3X48-D35; 14.1 versions prior to 14.1R8-S5, 14.1R9; 14.1X53 versions prior to 14.1X53-D44, 14.1X53-D50; 14.2 versions prior to 14.2R7-S7, 14.2R8; 15.1 versions prior to 15.1R3; 15.1X49 versions prior to 15.1X49-D30; 15.1X53 versions prior to 15.1X53-D70.

2018-01-13

【メモ】仮想通貨のハッシュ関数に求められる性質について

自分の頭の中を整理するために調べたり、考えたりしたメモ書きです。備忘としてこちらに残すことにします。

全射性/単射性について

順列の最小完全ハッシュ関数に書いてあるように、全射性も単射性も必須ではない。

全射

def: $f: A \to B$ が全射
$\forall b\in B,\,\exists a\in A\;{\text{ s.t. }}f(a)=b$

射影した先（上記のB）に射影されない元があっても問題ない。
ただし、実装上は終域の大きさは小さくしたいので、全射だとうれしい。

def: $f: A \to B$ が単射
$( \displaystyle{ \forall a_{1},a_{2} \in A ) \; \left[ a_{1} \neq a_{2} \Longrightarrow f(a_{1}) \neq f(a_{2}) \right] \\ \Longleftrightarrow ( \forall a_{1}, a_{2} \in A ) \; \left[ f(a_{1}) = f(a_{2}) \Longrightarrow \ a_{1} = a_{2} \right] }$

単射が満たされないことによって、いわゆる衝突が起こる。つまり、defの上段について、
$( \exists a_{1},a_{2} \in A ) \; \left[ a_{1} \neq a_{2} \Longrightarrow f(a_{1}) = f(a_{2}) \right]$ が反例となる。

→ハッシュ衝突がないハッシュ関数は、完全ハッシュ関数という。さらに終域Bが最小になるような場合を最小完全ハッシュ関数といい、このときは全単射になる。

いいハッシュ関数とは

Wikipediaに挙げられている特性と、仮想通貨で求められる特性とを比較し、まとめると以下表の通り。

特性	内容	仮想通貨では？
低コスト	計算コストが低いこと	PoWでは、ある程度の計算コストが要求される（計算コストが大きいことで、改竄に対する耐性を実現している）
決定性	同じ入力であれば同じ出力	同じく求められる
一様性	一様分布に近いこと	同じく求められる
可変な値域	値域が拡張できること	SHA-256からSHA-512にしたいときなどには求められる
連続性	類似した入力は、類似した出力（線形探索したい場合には有用）	逆に全く違う値であることが求められる

仮想通貨で考えるのに適しているのは、暗号学的ハッシュ関数 でWikipediaから引用すると要求事項は、以下の通り。

同一のハッシュ値であるのに、そっくりだが実は異なるというようなメッセージの作成が不可能であること。

ハッシュ値から、そのようなハッシュ値となるメッセージを得ることが(事実上)不可能であること（原像計算困難性、弱衝突耐性）。

同じハッシュ値となる、異なる2つのメッセージのペアを求めることが(事実上)不可能であること（強衝突耐性）。

一般には以下の特性が必要

原像計算困難性
ハッシュ値からもとのキーを見つけることが困難であること

第2原像計算困難性
h(k) = h(k')となるようなk'が見つけることが困難であること
弱衝突耐性とも。

第2原像計算困難性では、kが与えられている前提での攻撃、つまり、攻撃対象のkと同じハッシュ値を持つk'を見つける攻撃に対して困難性があることを要求している

強衝突耐性
h(k) = h(k')となるようなk, k'が見つけることが困難であること

強衝突耐性では、任意のkとk'に対して、同じハッシュ値を持つ入力を見つける攻撃に対して困難性があることを要求している。誕生日のパラドックスで言及されるように、こちらのほうが計算量は少ない（一般には、終域のサイズを2倍にする必要がある）

計算コストについて

仮想通貨の文脈では、ASIC耐性として、単位金銭あたりのハッシュレートに差がないことも求められる。要は、同じハッシュ計算（主流はSHA-256）するのに、CPU、GPU、ASICで計算するのに掛かる金銭コストが異なるのが不平等だという点。特にASICは、寡占状態という指摘もあるよう。

Cuckoo Cycleでは、memory-boundなアルゴリズムにすることで、この不平等さを解消しようとしている。 ~~paper読んだらまとめたい。~~