2018-01-28

CoinCheckとNemの騒動から暗号通貨について思うこと

何から語ろうか。まずCoinCheckにしよう。CoinCheckという暗号通貨の取引所が、NEMを大量に盗まれたという事件だ。私の法と技術の理解では、盗むというのは物理的な物が伴うので映画泥棒という言葉が法的に正しくないのと同様に違うのではないかと思うんだが、まあそこは置いておこう。ここでは単に悪意としておく。

これについて、自分のNEMが悪意されたのでCoinCheckに金を返せと叫んでいる人間のほとんどは、そもそも筋が悪い。もし、Bitcoinが花開いた暗号通貨が技術的に正しく運用されていたならば、そんなことは起こりようがなかったのだ。つまり、しっかり自分の手元の信頼できる環境でフルノードを実行し、物理的なコンピューターの前には武装した警備員を配備するべきだったのだ。自分でフルノードの実行もせずに、秘密鍵すらCoinCheckに知らせ、やれ盗まれたのなくなったのというのは、紙に印刷してある資料を電子媒体で送れといったら、紙をスキャンした画像をPDFやEXCELに貼り付けて送ってくるバカにも等しい愚かな行為だ。非科学的なアメリカ人は神によって通貨の価値を信じているが、我々科学の信奉者は計算力に裏打ちされた通貨を信じる。計算力の強いやつは正しい。それが暗号通貨の基本的な理念ではなかったのか。

世間では秘密分散共有によるマルチシグネチャーがどうのとか、ホットウォレットがどうのと言っているが、正直本質ではない。秘密鍵を分散させようと、エアギャップさせようと、守りが弱ければ、銃で武装した数人によって脅迫、拷問された末に情報を吐き出すのがオチだ。

さて、今回の事件の記者会見において、NEMのロールバックという面白い概念が提唱された。ロールバック、取引をなかったことにするという救済措置、これについて考えてみよう。

そもそもBitcoinから始まった、あまり正確ではないが俗にブロックチェーンと呼ばれる暗号通貨は、取引の上に取引を重ねる仕組みになっている。

例えば、アリス, ボブ, チャーリーによる取引が、アリス→ボブ→チャーリーの順番で行われた場合、取引チャーリーの取引はボブの取引が成立した上に成り立っており、ボブの取引はアリスの取引が成立した上に成り立っている。

すると、アリスの取引をロールバックするには、ボブとチャーリーの取引もロールバックしなければならないことになる。

もう少し読者が実感できる例で考えてみよう。今週、読者は給料日だったのでまとまったカネを持っている。いまからオーガニック・スシを食べようと出かけたところだ。スシ・レストランに向かう途中の自販機で、財布の中に残っていた小銭で代用ジュースを一本買った。そこに急に、日本自治区政府からのエージェントがやってきて、君に告げる。「君、実は先週、JPYの大量盗難が発生した。ついては被害者救済のために、先週に遡ってJPYの取引をすべてロールバックしたい。全員の同意が必要だ。君が今買った代用ジュースの代金は戻ってくるが、君の給与振込はなかったことになる。被害者救済のため、模範的な一般市民である君はロールバックに同意してくれるだろうね? いや、カネはなくなるわけじゃない。一週間前の状態に戻るだけなんだ。あとで必要な取引は各人で復旧してもらいたい」

読者は同意するだろうか。

しかし、全員が同意するのであれば、アリスの取引だけをなかったことにして、ボブとチャーリーの取引は存在したことにできないだろうか。もちろんできる。それはハードフォーク(通貨の分裂)と呼ばれている。

しかし、我々は計算力によって通貨を信用していたのだ。アリスの取引を無効にすると、その取引に連なるボブとチャーリーの取引は計算では信用できなくなる。しかし、皆がアリスの取引を無効にすることに同意するならば、計算力を持つ皆が信用しているので正しい。自分だけアリスの取引は発生したと主張することは可能だが、過半数がその主張を拒否するのであれば、もはやその価値はなくなる。すると、世の中にはアリスの取引が存在した通貨と、存在しなかった通貨が生まれることになる。どちらを信じるのも自由だ。両方信じてもよい。こうして通貨は分裂する。

わかりやすい例で考えてみよう。日本自治区政府のエージェントは君にこう告げる。「いまから先週発生したJPYの大量盗難の取引を取り消す作業をする。君の財布の中身、銀行口座の金額、その他あらゆるカネとその記録を出し給え。我々がJPYの盗難だけがなかったように書き換えて君に返す。今のカネの状態はすべて破棄される。我々の書き換えは信頼できる。模範的市民の同志、同意してくれたまえ」

読者は同意するだろうか。

今回、このどちらの方法もNEM財団は取らなかった。仮に取ったとしても、マイナー達の同意を取り付けることはできないだろう。

かわりにNEM財団がやったのは、悪意を持った転送先のアドレスに、盗難を意味するモザイクを付与することだ。これはNEMの機能で、詳しくは調べていないが、ここで重要なのことは、アドレスにタグ付けができるということだ。NEM財団が今回悪意を持って取引されたNEMを含むアドレスにすべて盗難タグ付けをしていくことで、そのアドレスとの取引を利用者に拒否するよう促す。これにより、悪意ある者の持っているNEMは私情でかちを失うという目論見だ。なるほど、窃盗アドレスだと知った時点ですでに善意の第三者ではなくなるから、法的にも効果的だ。

しかし、果たしてそううまくいくだろうか。今回の犯人が次にやるべきことは、NEMを小額づつ、適当なアドレスに片っ端から送りつけることだ。大多数のアドレスが窃盗タグで汚染されてしまうと、もはや窃盗タグは意味を為さなくなる。第一、そのタグ付けは計算力に裏打ちされているのだろうか。権威がつけたタグを盲信しているだけではないのだろうか。そして、権威は果たして信用できるのだろうか。するとNEM自体の価値も、果たして信用できるのだろうか。

ただし、この考え方は面白い。我々は権威と計算力のハイブリッドの信用通貨を作り出してもいいのではないだろうか。

通貨の歴史を考える。貴金属のようなもともと価値のあるものが取引されていたのが、貴金属を直接取引するのは非効率的なので、貴金属と交換できる引換券で取引するようになった。しかし、実際に存在する貴金属以上の借金が市場に出回り、この仕組みは崩壊した。今の国家に裏打ちされた通貨は、貴金属と直接交換を保証されていない。

世の中には、存在自体が価値を持つ権威が存在する。国家もそうだが、宗教開祖とかアイドルとか秒速で億ぐらい稼ぐ人とかだ。そういう信者を何十万、何百万と持つ権威が、Bitcoinのような既存の暗号通貨をhard forkして独自の暗号通貨を始めるのはどうだろうか。何十万、何百万の妄信的な信者が価値を認めるのであれば、その暗号通貨には実際に価値が出るだろう。するとマイナーも一枚岩ではなくなるので、誰も過半数の計算力を持つことができずに、マイナーは単なるトランザクション処理係に成り下がる。何か問題が起きれば、権威がイスラム教で言うところのファトワー(見解)を出して訂正するのだ。

と考えてみると、VALUは案外いい線をいっていたのではないかとも思えてしまう。もちろん私は信用しないが。

こうして考えてみると、計算力と権威のハイブリット信用通貨は、国家から通貨発行権を奪還する試みであるとも言える。面白い世の中になってきたが、私としてはもっと現実的な価値を提供してほしい。例えばチューリング完全な計算を提供するとか、実際ストレージとして使えるとか、契約への同意が行われたことの記録ができるとかのブロックチェーンネットワークがほしい。

2018-01-20

物理的に近くの相手とファイル共有する方法

以下のようなTweetを読んだ。

インターネットが普及してからもうかれこれ20年以上もたつが、未だにこの問題が解決できていないのは嘆かわしいことだ。なのでこの問題を解決してみよう。

ただし、今回の問題は、大量に人が集まるため無線通信が難しい状況で、物理的に近い場所にいる相手とのファイル共有だ。

ファイルの転送自体は、前後にインターネット回線を確保してから行ってもいい場合は、どこかに暗号化したファイルを公開しておき、現場では復号鍵を配布すればいいだろう。

しかし、その場で直ちにファイルを転送したい場合はどうするのか。この場合、物理媒体による受け渡しは客が大勢来た場合にスケールせずに非現実的だ。

お互いBluetoothによる通信ができる状況であれば、Bluetoothによるファイル転送が使える。スマフォ端末やタブレット端末ならば、Bluetoothはほぼ確実にあるだろう。問題は、相手がBluetoothによるファイル転送に慣れていない場合、Bluetoothによるファイル転送の方法を説明する必要がある。これには相手の技術レベルにもよるが時間がかかるだろう。これもスケールしない。

もし転送したいファイルが2953バイト以下であれば、QRコードが使える。QRコードはディスプレイに映してもよいし、紙に印刷してもよい。圧倒的にスケールする。ただし、相手の端末にはカメラとQRコードリーダーが必要だ。ほとんどのスマフォとタブレット端末ならQRコードには対応しているだろう。しかし、PDFファイルはまず間違いなく2953バイトではすまないだろう。

やはり一番信頼できるのは有線LANだ。複数の客をさばくためにスイッチングハブを用意する。スマフォやタブレット端末にはEthernetポートがついていないことが多いが、USBポートが一つぐらいはあるだろうから、USBによるEthernetアダプターと各種USB変換ケーブルを用意しておけばよい。相手にIPアドレスを設定させる手間を省くためにDHCPサーバーも用意するとよい。家庭用のどんな格安ルーターでもDHCPサーバー機能はついているので難しくはない。

肝心のファイルを転送する方法であるが、FTP, SMB, HTTPなどが使える。SMBならば家庭用ルーターの機能として提供されていることも多い。しかし、相手への説明のコストを考えると、おそらくHTTPを使うのが一番楽だろう。ただし、URLが"http://192.168.0.100/file.pdf"などではやや相手にとってわかりにくいかもしれない。これを解決するには方法が2つある。ひとつはmDNSを使う方法で、IPアドレスのかわりに、hostname.localと書くことができる。ただし、これは相手の端末がmDNSに対応していなければならない。普通は対応しているはずだ。もう一つは、大抵のルーターについている静的DNSレコードなどと呼ばれている機能を使い、特定のIPアドレスに対してそのルーターのLAN側だけで通用するドメイン名をつけてしまうことだ。これなら相手の端末が万一mDNSに対応していない場合でも使える。

HTTPサーバーを用意する方法としては、転送したいファイルを置いたディレクトリで"python3 -m http.server"を実行するのが最も簡単だろうと思われる。

ただしこの方法は準備する機材がやや多い。ルーター、スイッチングハブ、LANケーブル、USB-Ethernetアダプター、各種USB変換ケーブル、HTTPサーバーを実行するコンピューター、知識を持った人間が必要だ。最後の知識を持った人間が一番用意しにくい。本来ならば、この2018年には全員がコンピューターリテラシーを持ち、この程度のことはできてしかるべきなのだが、スマフォが人をバカにしてしまった。

しかし、手のひらに乗るコンピューターでリアルタイム3DCGが描画でき、メモリ容量の単位がGBで数えられ、GB単位のストレージが数百円もせずに買えるこの2018年だというのに、なぜ身近の人間と物理的にファイルを転送するのにこんなに苦労しなければならないのだろう。

2018-01-19

3月に出版される「江添亮の詳説C++17」が予約できるようになった

3月に発売されるC++17の新機能をすべて解説した参考書、「江添亮の詳説C++17」が予約できるようになった。例えばアマゾンでは以下から予約できる。

江添亮の詳説C++17 | 江添 亮 |本 | 通販 | Amazon

「江添亮の詳説C++17」は、私の名前を冠するエゴの強い書名になっている。これは、次にC++によるプログラミング入門書を出したいために、名前をブランド化する試みだ。これがうまくいくかどうかはわからないが、

江添亮の詳説C++17は、GPLv3でライセンスされる。本のソースコードはGitHubで公開されている。まだもう少しは修正が聞くので、PRを投げてコントリビュートするなら今がチャンスだ。

https://github.com/EzoeRyou/cpp17book

GPLv3なので、本の組版に使ったtexのソースコードも公開されている。わたしはtexに詳しくはないが、できればビルドするためのドキュメントやMakefileなどを整備していきたい。

ちなみに、前回のC++11/14の参考書は、CC-BY-SAでライセンスされている。

https://github.com/EzoeRyou/cpp-book

すでに書いたように、次はC++によるプログラミングの入門書を書く。そのために色々と準備をしている。まず初心者の気持ちを再び味わうために、Haskellに入門した。Haskellは私の知っているプログラミング言語とはだいぶ違う言語であり、最初の数日はとても苦労した。なにより、環境構築が難しいということがわかった。次に書く入門書は、まず環境構築を丁寧に説明しなければならない。環境構築は慣れたものであれば何も意識しないが、何も知らない者にとっては意外と難しいものだということを身をもって学んだ。

C++の入門書はすでに多く書かれているが、いずれも古びてしまい、最新のC++からかけ離れてしまっている。

プログラミングの入門書を書く準備は整ったのだが、もう少しだけ寄り道をして、ブール代数を本格的に学ぼうと思っている。いままで表面的に浅くしか学んでいなかったが、この機会に深く学んでおきたい。

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2018-01-17

今流行りの投機実行脆弱性の影響を一切受けないDOOM実装が公開される

https://github.com/xoreaxeaxeax/movfuscator/tree/master/validation/doom

このDOOMは条件分岐を一切使用していない。したがって今流行りの投機実行の脆弱性であるMeltdownやSpectreによる脆弱性は存在しない。

ちなみに、現代の性能のコンピューターで、1フレームの描画に7時間ほどかかるので、このDOOMで遊ぶには若干の忍耐力を要求される。しかし、脆弱性の完全な排除のためには若干のパフォーマンスの低下はやむを得ないところだろう。

このDOOM実装はオリジナルのDOOMのCコードに若干の変更を施して、M/o/Vfuscatorでコンパイルしたものだ。

https://github.com/xoreaxeaxeax/movfuscator

M/o/Vfuscatorとは、IntelのMMUがチューリング完全であることを利用したmov命令のみを使うC言語コンパイラーだ。

2018-01-14

第4回 ドワンゴからの挑戦状予選に参加してみた

第4回 ドワンゴからの挑戦状

第4回、ドワンゴからの挑戦状の予選が開催されたので参加してみた。

A - ニコニコ文字列判定

まずA問題。数字のみが使われた4文字の文字列sが入力として渡される。数字x, yが存在して、sがxyxyのとき"Yes"を、そうでなければ"No"を出力する。

入力は必ず4文字で、数字のみなので、変な文字列が渡される心配をしなくてもよい。

#include <iostream>

int main()
{
    std::string s ;
    std::cin >> s ;

    if ( s[0] == s[2] && s[1] == s[3] )
        std::cout << "Yes" ;
    else
        std::cout << "No" ;
}

A問題は毎回とても簡単な傾向にある。私は最初の提出が、問題文をさっと見ただけでコードを書いてしまったので、"YES", "NO"を出力するようにしてしまい、間違えた。

B - 2525文字列分解

文字'2'と'5'からなる文字列sが入力として与えられる。その文字列を"25"の1回以上の繰り返しからなる2525文字列に分割する。文字を分割するときには、文字の相対的な順序を変えてはならない。分割できる最小数はいくつか。

この問題はとても簡単に解決できる。

文字列sから"25"を取り除く操作を繰り返して、空文字列になるまでの操作回数を数えた結果が答えだ。つまり何回s/25//gできるかを数えればよい。もし、文字列に対してs/25//gを適用しても文字列が変わらなかった場合、その文字列は2525文字列に分解できないので、-1を出力する。

文字列から"25"を取り除いた結果の文字列は、もしまだ2525文字列が存在するのであれば、必ず”25"が出現する。なので文字列が空になるまで繰り返しs/25//gすればよい。

実際のところ、この問題はbashとsedで解くことができる。sedのみで解くことはできるだろうか。どうやらsedは入力文字列を工夫すればチューリング完全であり、sedでチューリングマシンやテトリスを実装したと主張するWebサイトがあるが、詳しく読んでいないので真偽はわからない。

http://www.catonmat.net/blog/proof-that-sed-is-turing-complete/

さてコードに落としていこう。処理は簡単だ。入力の文字列にs/25//gを何回適用できるか数えるだけだ。ただし、空文字列ではないのに適用できなくなった場合、2525文字列に分割できないので-1となる。

このような問題を解くときは、すでに問題を解き終えたと仮定すると書きやすい。

まず、この問題を解く関数solveがすでに存在すると仮定する。この関数solveは文字列をstd::string &型で与えると出力すべき数値をint型で返してくれるとする。引数に渡した文字列は書き換えられるものとする。すると、もうすでに我々は問題を解き終えたわけなので、入力を受け取って関数solveに渡して出力するだけのコードを書けばよいことになる。

#include <iostream>
#include <string>

int main()
{
    std::string s ;
    std::cin >> s ;

    std::cout << solve( s ) ;
}

これで入出力の部分は書いた。あとは関数solveを実装するだけだ。

このような問題を解くときは、すでに問題を解き終えたと仮定すると書きやすい。

まず、文字列に対してs/25//gを行う関数remove_nicoがすでに存在すると仮定する。この関数remove_nicoはstd::string &型の引数を取り、s/25//gする。もしひとつ以上の"25"を置換したのであればtrueを、そうでなければfalseを返す。すると、我々はすでにs/25//gを実装し終えたわけなので、あとはこの関数remove_nicoを何回文字列に適用できるか数えればよいだけだ。ただし、空文字列ではないのにfalseを返した場合は-1だ。

int solve( std::string & s )
{
    int count = 0 ;
    while ( s.size() != 0 )
    {
        bool removed = remove_nico( s ) ;
        if ( removed ) // 適用した
            ++count ;
        else // 適用できなかったので2525文字列ではない
            return -1 ;
    }
    return count ;
}

さて、残りは関数remove_nicoさえ実装すればよい。実装方法としては、単に文字列を先頭から自分自身にコピーしていき、"25"はコピーをスキップすればよい。

bool remove_nico( std::string & s )
{
    auto dest = std::begin(s) ;
    auto src = dest ;
    auto end = std::end(s) ;

    // 文字を自分自身にコピーする
    while ( src != end )
    {
        // 文字列"25"ならばコピーしないことで除去
        if ( *src == '2' && *std::next(src) == '5' )
        {
            std::advance( src, 2 ) ;
        }
        else
        { // コピー
            *dest = *src ;
            ++dest ;
            ++src ;
        }
    }

    // 一度も"25"を除去していなければfalseを返す
    if ( dest == end )
        return false ;

    // 除去した"25"の数だけ文字列のサイズを減らす
    auto shrink = std::distance( dest, end ) ;
    s.resize( s.size() - shrink ) ;

    return true ;
}

しかしこういう処理を自前で書くのは面倒だ。s/25//gをしたいのであれば正規表現ライブラリを使えばいいのではないか。そう思う読者もいるだろう。実際、正規表現ライブラリはC++11で追加されている。問題は、この手の問題に正規表現ライブラリを使うというのは鶏を割くのに牛刀を用いるほど過剰であり、遅いということだ。そもそも正規表現ライブラリは柔軟なパターンマッチができるもので正規表現文字列からパターンマッチのためのデータ構造を構築する。そして、std::regex_replaceによる置換はin-placeでは行われない。今回の置換は削除なので、in-placeに処理できるが、汎用的なライブラリであるstd::regexにそれを望むことはできない。

それでも書くとなると、以下のようになる。

bool remove_nico( std::string & s )
{
    std::regex re("25") ;
    std::string out ;
    // s/25//g
    auto end = std::regex_replace( std::back_inserter(out), std::begin(s), std::end(s), re, "" ) ;
    // 置換しなかった
    if ( s.size() == out.size() )
        return false ;

    s = out ;
    return true ;
}

ちなみに、手書きの"25"削除をatcoderに提出すると実行時間は最大のテストケースで5msぐらいだが、regex_replaceを使う実装を提出すると50msぐらいかかる。実に10倍も遅い。remove_nicoを手動でインライン展開して、reとoutをループの外に出して使いまわす付け焼き刃の最適化も試してみたが、実行時間は変わらなかった。その程度の最適化はコンパイラーがやっているらしい。

とはいえ、10倍遅くても制限時間内だからいいといえばいい。B問題程度はさっさと解くためにこうしてもよいが、それならもっと簡単な言語を使ってもよいということだ。

C問題以降は私には解けないのでもっと強い人の解説を参考にしてもらいたい。

ドワンゴ広告

ドワンゴからの挑戦状本選は2月3日。

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2018-01-08

fair use権利を侵害するYouTubeのContent IDと戦うために著作権侵害するゲーム批評家の話

Game Critic Uses Brilliant Workaround For YouTube's Copyright Bullshit

Jim SterlingはYouTubeに動画を投稿するゲーム批評家である。動画によるゲーム批評を行うためには、ゲームの動画を引用する必要がある。しかし、ゲームの動画をYouTubeで引用すると困った問題に巻き込まれる。Content IDだ。

YouTubeではContent IDという仕組みが設けられている。これは、ある動画が著作権者の事前に登録した動画にマッチする場合、その動画に対して著作権者が著作権を主張し、取り下げたり、あるいは広告を出して収入を著作権者に回したりする仕組みだ。

しかし、批評のための引用は各国の法律で「著作権の例外」にあたり、著作権が及ばないと定められている。例えば日本では著作権法の第32条、アメリカ合衆国ではfair use、イギリスではfair dealingにより、著作権の例外であり著作権が及ばないと法的に定められている。ゲームの批評のために必要な範囲の引用には著作権が及ばない。著作権が及ばない以上、当然屈辱的なContent IDマッチによる取り下げや広告収入の横取りは、本来ならば著作権を不当に主張している人間による著作権侵害である。

しかし、Googleは人間が問題に対処しないことで悪名高い企業であり、不当なContent IDマッチの取り下げ要求にはまともに人間が対応しないためにどうしようもない。

さて、Jim Sterlingは収入をPatreon経由で得ており、YouTubeの広告には依存していない。そのため、YouTubeには広告を表示しない設定にしているのだが、ひとたびContent IDにマッチしてしまうと否応なく広告が有効にされてしまうという問題を抱えている。

そんなJim Sterlingが、最近自衛のために行っている行動は、Content IDの仕組みを逆手にとったものだ。上の動画では、任天堂の最近のゲームには新規性がなく過去の成功体験を引きずって使いまわしているだけだという旨の批評を行っている。しかし、動画にはなぜか、何の脈絡もなくMetal Gear Solid V, Grand Theft Auto V, Beyond: Two Soulsといったゲーム動画が使われている。これはなぜか。

Jim Sterlingは過去の自分の動画の中でContent IDにマッチした、既知のContent IDマッチ動画を意図的に使うことによって、動画に複数の大企業のContent IDマッチした著作権主張者を作り出している。複数の著作権主張者が同じ動画に著作権主張をした結果、どの著作権者の主張も認められず、結果として動画には収益横取り広告がつかなくなる。

しかし、その利用方法は正統な批評のための引用ではなく、結果的の著作権侵害ではある。32条、fair use, fair dealingといった著作権の例外の権利を保証させるために、あえて著作権侵害を起こす必要があるとは皮肉なものだ。しかしJim Sterlingによれば、結果的にこれが効果的な方法なのだという。

著作権は誤った考えであり私の生きているうちに世界的に破棄されるだろう。

2018-01-02

Clangをブラウザー上で実行してC++をWebAssemblyにコンパイルして実行するデモ

Clang In Browser

タイトル通り。WebAssemblyにコンパイルされたClangをブラウザー上で実行してC++をWebAssemblyにコンパイルしてブラウザー上で実行するデモ

この有名なトークが現実的になってしまう。核戦争によって滅んだ人類がブラウザーを共通プラットフォームとしてブラウザー上でOSを動かす話。

The Birth & Death of JavaScript