ビットコインと計算理論

本日のネットワークセキュリティの授業，テーマは「セキュリティ基礎」でした．RSAの回で話した多項式時間を振り返るとともに，問題と個別問題の違い，チューリング機械の3つのバリエーション（決定性・非決定性・確率的），時間計算量とオーダ表記などの紹介あるいは確認をしてから，P≠NP予想やNP完全問題を解説しました．
昨年のスライドを見直した際，NP完全問題や「手に負えない問題」の後のところで，昨今のセキュリティ事情を踏まえ，何かトピックを入れたいなと思いまして…
購入していた，ビットコインの本を開いてみました．

ビットコインとブロックチェーン:暗号通貨を支える技術

しかし，これ1冊に時間をとりすぎるわけにもいきません．
飛ばし読みをしてほどなく，計算理論，そしてセキュリティと密接に関わる，興味深い記述を目にしました(p.135)

チューリング不完全性
　ビットコイントランザクションのScript言語は多くのオペレータを持っています。しかし、意図的にループやif文などの分岐処理がないように制限されています。これは言語がチューリング完全ではないということであり、つまり、scriptが複雑でなく、処理回数が予測できることを意味します。Script言語は汎用言語ではありません。これらの制約によって、無限ループを作ることやビットコインネットワークを使ったDOS攻撃を起こすようなトランザクションに内在する「論理爆弾(logic bomb)」などを作ることができなくなっています。全てのトランザクションは、ビットコインネットワーク上のすべてのフルノードによって有効性が確認されているので、トランザクションの有効性確認の処理に問題があれば、簡単に脆弱性が作れてしまいます。言語が制限されているために、トランザクションの有効性確認メカニズムが、脆弱性を生むことを防いでいるのです。

ここから重要な箇所を取り入れ，本記事冒頭の画像（スライド）にした次第です．なお，「Script言語」について，プログラミング言語の分類としての「スクリプト言語」とは異なること，またリファレンス実装はあるものの標準化されていない点に留意し，スライドでは「Bitcoin Script」と表記しました．
毎回の授業終了時に，「印象に残った語句を3つ挙げてください」と指示し，用紙を提出してもらっていますが，今回は「ビットコイン」が多く書かれていました．準備した甲斐がありました．