コインを購入
マーケット
契約
現物
収益
Web3 new
Phemex学園
Academy > 暗号資産の洞察 > チューリング完全。ブロックチェーンはチューリング完全性を有するか? >

チューリング完全。ブロックチェーンはチューリング完全性を有するか?

2022-06-22 06:41:31

アラン・チューリングはイギリスの数学者であり、無限のテープから読み書きすることによって計算を行う抽象的なモデルである、チューリングマシンを発明しました。チューリング完全性とは、プログラミング言語などの命令体系が、チューリングマシンの動作をシミュレートする能力を持つことを指します。

turing-complete

チューリングマシンとは?

チューリングマシンは、次のように構成されるものです。

  • 無限に広がるテープは、1つ1つのセルに分割されている。テープは、一般的なコンピュータやその他のデータストレージのメモリのような役割を果たす。テープ上の各セルには、有限のアルファベットから選んだ記号(命令を表す)が入っている。この機械は、どのような計算にも対応できる十分なテープを常に持っており、無限メモリといったものを構成している。
  • 現在検査中のメモリのセルへのポインタとして機能するヘッドは、機械によってセルの上に配置され、中に格納されているシンボルを読み取る。機械は一度に1セルだけヘッドを左右に移動させることができる。
  • マシンの現在の状態(マシンの動作を制御するために使用される有限の数の状態の1つ)を格納するステートレジスタ。この中には、レジスタが初期化される特別な「開始状態」も含まれる。
  • 各ステップ中に機械がチェックする命令の有限テーブル(「遷移関数」ともいう)は、状態と記号の有効な組み合わせに対して機械が何をすべきかを定義している。
Example of a finite table
有限のテーブルの例(出典: Brilliant.org)

チューリングマシンのテープは、(通常は空白の)記号列で初期化され、ヘッドがそのセルの1つ上に配置される。ヘッドが任意の記号を読むと、機械は有限テーブルを参照し、次のような動作・確認を行う。

  • ステートレジスタの現在の状態
  • ヘッドが読み取る記号
  • どのシンボルをセルに書き込むか
  • ヘッドを移動させる方向
  • マシンをどのような状態に変化させるか
A Turing machine
文字列が回文かどうかをチェックするチューリングマシン(出典:Anthony Morphett, http://morphett.info/)

チューリング完全機械とは?

機械の各部分(状態、記号、使用済みテープ)とその操作(記号の書き込みと消去、テープの移動)は有限であり、離散的であり、区別可能なものです。機械に無限の記憶空間を与えているのは、無限のテープ(メモリ)だけです。

チャーチ・チューリング論文では、計算可能な問題はすべてチューリングマシンで解くことができると仮定しています。「チューリング完全」な機械やプログラミング言語は、十分な時間とメモリがあれば、その複雑さにかかわらず、コンピュータが達成可能なあらゆるタスクを実行することができるとされています。プログラミング言語の大半は、チューリング完全とみなされています。

チューリング完全システムのメリット

チューリング完全システムの大きな利点は、その適応性にあります。以前は定義されていなかったタスクを実行するためには、チューリング完全でないシステムに全く新しいコードセットを提供する必要があります。一方、チューリング完全システムは、既存のコードベース上で実行するための対応する命令セットを提供するだけでよいのです。

この方法は、あらかじめステップと解が定義されている問題(ほとんどの算術問題など)には有効ですが、決定不可能な問題に関しては問題を引き起こす可能性があります。チューリング完全でないシステムは単に問題を計算することができませんが、チューリング完全なシステムは計算を試みますので、予期しない、あるいは望ましくない動作になる可能性があるのです。

ビットコインとイーサリアムはチューリング完全か?

チューリング完全性がブロックチェーン技術にどのような影響を与えるかを探る最も簡単な方法は、チューリング完全性を持つイーサリアムETH)と、そうでないビットコインBTCを比較することです。ブロックチェーンのチューリング完全性は、技術的な能力よりも設計の問題であり、プロジェクトの機能と課題を知らしめるものです。

なぜビットコイン・ブロックチェーンは非チューリング完全であるように設計されているのか?

ビットコインのブロックチェーンは、チューリング完全性が不要で有害と考えられる特定のユースケース(デジタル通貨)をターゲットに、意図的に非チューリング完全であるように設計されています。ビットコインのスクリプト言語は、マルチシグネチャウォレットやライトニングネットワークなど、スマートコントラクトの機能を実現するには十分強力ですが、ループやメモリ内の任意の位置への読み書きは実装できません。

非チューリング完全なブロックチェーンは善なのか?

ビットコインのような非チューリング完全ブロックチェーンの主な利点は、プロセスがその長さに比例した実行時間で終了することが保証されていることであり、これはデジタル通貨にとって有用なセキュリティ機能となります。また、ビットコインのスクリプト言語はシンプルなものであるため、有限の可能性を持つ状況下において、開発者は自分のアプリケーションがどのように反応するかを予測することができます。しかし、このようなブロックチェーンは、イーサリアムと同じレベルのアプリケーションをサポートできないため、その汎用性が著しく制限されるという欠点があります。

なぜイーサリアムのブロックチェーンはチューリング完全なのか?

一方、イーサリアムのブロックチェーンは、カスタマイズされた分散型アプリケーションのプラットフォームとして機能するよう、ゼロから設計されています(DApps)。ビットコインはトランザクションを処理するだけなのでチューリング完全性は必要ありませんが、イーサリアムはこれらのトランザクションが基づいている基本ロジックを解釈する必要があります。イーサリアムは、どのような取引の解釈を求められるかを事前に知る術がないため、これのベースとなるブロックチェーンはあらゆるものを理解できるように設計されていなければなりません。言い換えれば、チューリング完全でなければならないのです。

チューリング完全性はイーサリウムどのように役立つのか?

チューリング完全性は、Solidityプログラミング言語によるループや分岐、イーサリアム仮想マシン(EVM)による展開や実行をサポートする高度なスマートコントラクトの実装を支援します。イーサリアムのスマートコントラクトはチューリング完全であるため、理論的には通常のコンピュータプログラムで実行可能なあらゆるタスクを実行することが可能です。これにより、ERC-20標準通じた可換トークンの作成、分散型金融(DeFi)アプリケーション、自動マーケットメーカー(AMM)など、さまざまな可能性が広がっています。

チューリングコンプリートブロックチェーンは悪なのか?

イーサリアムのようなチューリング完全ブロックチェーンの主な欠点は、特定の取引が終了しない可能性があるだけでなく、任意の取引が「終了するかどうか」を判断することも不可能であることです。これは停止問題と呼ばれ、ガスが必要とされる理由です。ガスを使い切ると、無限ループを持つトランザクションは終了してしまいます。この意味で、EVMは技術的には準チューリング的な完全性しかありません。なぜなら、すべての実行プロセスは、スマートコントラクト内のガスの量によって許される有限の計算ステップ数に制限されるからです。

もう一つの問題は、チューリング完全性によって提供されるプログラマビリティと柔軟性が、双方向に作用することです。イーサリアムは多くの点でビットコインよりも強力ですが、そのスマートコントラクトの複雑さゆえに、悪意のある相手に対してより脆弱になっているのも事実です。DAOのハッキングを可能にし、イーサリアムのネットワークを分裂させた再帰呼び出しの試みは、スマートコントラクトのチューリング完全性によってのみ可能となったものです。また、リエントランシー攻撃などの他の脆弱性も、チューリング完全でないブロックチェーンには存在しません。

チューリング完全性か、リッチ・ステートフルネスか?

創業者Vitalik Buterinは、イーサリウムの重要な価値として、チューリング完全性よりも、彼が「リッチ・ステートフルネス」と呼ぶコンセプトについて概説しています。リッチ・ステートフルネスとは、ブロックチェーンレベルで情報を記憶するシステムの能力のことです。このコンセプトの例として、誰かが「信頼できない保険」契約に資金を拠出した場合、その拠出総額、チケット、請求はすべてブロックチェーン上に自動的に保存され、更新されます。この機能は、UTXO(未使用トランザクション出力)を利用し、ステートレスとされるビットコインでは不可能なものです。

Buterin氏によると、「一度イーサリウムの哲学的モデル(スクリプトを「述語」ではなく「何かをする」とみなす)を持つと、チューリング完全性は実際に持つことよりも持たないことの方が難しくなります」。イーサリウムのチューリング完全性はその基盤として機能しますが、ネットワークに柔軟性を与え、Bitcoinブロックチェーンで可能な以上の複雑性を可能にするのは、豊富なステートフルネスなのです。

チューリング完全性のセキュリティリスクとは?

イーサリウムプロジェクトがスマートコントラクト用にチューリング完全言語(Solidity)を設計するという決定は、特に数々の著名なセキュリティ侵害の後、多くの公的精査の対象になっています。Solidityのパワーは開発者と悪意ある行為者の両方の存在を可能にし、安定性よりも最先端の機能性を重視するプロジェクトの延長線上にあると見ることができます。

非チューリング完全実装は、ラムデン(TAU)のような安定性を重視する(あるいはそれほど幅広い機能を必要としない)ブロックチェーンにとって魅力的な選択肢であり続けています。Algorand(ALGO)などのプロジェクトは、チューリング完全なスマートコントラクトは膨大な攻撃表面を追加する一方で、大半のユースケースには不要であると主張し、非チューリング完全性を今後の方向性として受け入れています。

Taylor Rolfe氏が書いた記事では、Solidity上の既知の攻撃ベクトルの大部分は、非回転の完全性によって排除することができたと指摘しています。イーサリウムの設計思想とは逆に、他のプロジェクトでは、スマートコントラクトのようなリスク回避の技術は、潜在的なパフォーマンスを犠牲にしてでもリスクを制限するように設計されるべきであると主張しています。

Approximation of the “dead weight” attack
スマートコントラクトにチューリング完全言語を使用した場合に継承される「デッドウェイト」攻撃面の近似値(出典: Kadenka)

さいごに

チューリング完全性をめぐる議論は、基本的にセキュリティとパフォーマンスの関係性の中で行われるものです。ビットコインのようなプロジェクトがイーサリアムよりもプログラム的に安全である主な理由は、その目的がより限定的であることです。イーサリアムは、特定のサービスというよりもむしろプラットフォームとしての位置づけであるため、そのような対策を講じることは困難なのです。

Solidity のようなチューリング完全なスマートコントラクト言語は、有用なアプリケーションと悪意のあるアプリケーションの両方に、より大きな機会を提供します。しかし、このようなメリットの代償として、多くの開発者やユーザーが避けたいと思うようなリスクが追加されています。

giftRegister to get $180 Welcome Bonus!
Email
Password
招待コード(任意)
  • Facebook
  • Twitter
  • LinkedIn
  • Telegram
  • Discord
  • Youtube
Subscribe Phemex

フェメックスに登録して、今すぐ暗号化の旅を始めましょう!

サインアップで$180をゲット

Bonus

新しいモデレーターを呼んで報酬を獲得しましょう。近々オンチェーンに登場します