Что такое Тьюринг-полнота?

Полнота по Тьюрингу - это термин в информатике, который описывает способность системы вычислить любое возможное вычисление или программу, и может использоваться для описания современных языков программирования (Python, C++ и т.д.). 

Полнота Тьюринга описывает программируемую систему, которая может решить любую вычислительную задачу. Это понятие происходит от машины Тьюринга - теоретической модели вычислений, разработанной английским математиком и криптографом Аланом Тьюрингом. И наоборот, неполная по Тьюрингу система ограничена выполнением определенных задач на основе заранее заданных инструкций.

Обычная аналогия заключается в том, что карманный калькулятор является неполным по Тьюрингу, поскольку он запрограммирован на выполнение ограниченного набора математических вычислений. Однако на домашнем компьютере можно написать программу, которая будет выполнять ту же задачу автономно.

Биткойн и Ethereum представляют собой наиболее известный контраст в отношении полноты по Тьюрингу. Биткойн и его язык программирования Script были разработаны как неполная по Тьюрингу система с ограниченной функциональностью. Программное обеспечение Bitcoin было запрограммировано исключительно для обработки биткоин-транзакций и не может поддерживать сложную, многоступенчатую логику смарт-контрактов.

Однако Ethereum позволяет разработчикам писать код, используя тьюринговски полный язык программирования Solidity, и выполнять его с помощью виртуальной машины Ethereum, которая также является тьюринговски полной. Теоретически, можно написать любую программу для любого случая использования и запустить ее на Ethereum.

Таким образом, полнота по Тьюрингу имеет важные последствия для того, чего можно достичь с помощью технологии блокчейн.

Ethereum - первый полный блокчейн по Тьюрингу

Ethereum был первым полным по Тьюрингу блокчейном, который можно было использовать для программирования смарт-контрактов и децентрализованных приложений (dapps). 

Ethereum был разработан таким образом, чтобы быть полным по Тьюрингу в двух направлениях:

• Смарт-контракты Ethereum написаны с использованием языка программирования Solidity - универсального языка, полного по Тьюрингу, разработанного специально для Ethereum.
• Виртуальная машина Ethereum (EVM), которая выполняет смарт-контракты в соответствии с программой, является полной машиной Тьюринга.

EVM может обрабатывать любую конфигурацию смарт-контрактов, даже если их функция или полезность еще не придуманы. Поэтому запуск Ethereum в качестве первого блокчейна с полной машиной Тьюринга ознаменовал собой важный поворотный момент в расширении возможностей технологии блокчейн. Вместо того чтобы быть ограниченным конечным числом вариантов использования, Ethereum допускает потенциально безграничный диапазон применения.

Практические ограничения полноты по Тьюрингу Ethereum

Ethereum можно назвать полным по Тьюрингу только на самом теоретическом уровне из-за практической механики блокчейна. Каждая транзакция в Ethereum требует затрат на газ, поэтому если смарт-контракт зациклится, что теоретически возможно на машине Тьюринга, то в конце концов газ закончится.

Это ограничение полноты Ethereum по Тьюрингу является намеренным, так как наличие нескольких смарт-контрактов, работающих по бесконечным циклам, нежелательно для публичной блокчейн-сети с ограниченными вычислительными мощностями. По этой причине каждая транзакция в Ethereum требует лимита газа, который определяет максимальное количество вычислительной мощности, которое может быть выделено для транзакции. Если транзакция не завершена по достижении лимита, она отклоняется.

Однако важно отметить, что очень немногие смарт-контракты Ethereum используют рекурсивные циклы и другие возможности, требующие полноты Тьюринга.

Недостатки полноты Тьюринга в блокчейне

Бесконечно программируемая природа полных систем Тьюринга является их самой большой силой, но в то же время она может быть и существенной слабостью, особенно в публичных блокчейнах, где код виден всем. Это означает, что код может быть уязвим для сбоев (например, ошибок в смарт-контрактах) или непреднамеренного использования, которые препятствуют целевому функционированию протокола. Возможность программирования любого вида вычислений допускает огромное количество вариантов развития событий, и предусмотреть все из них невозможно.

Если в централизованной системе возникает непредвиденная проблема, компания, владеющая кодом, может немедленно выпустить исправление. Однако в системе на основе блокчейна это может привести к значительным сбоям, если кому-то удастся найти способ вызвать результат, который не был предусмотрен разработчиком. Из-за децентрализованной природы блокчейна обновление программного обеспечения может занять больше времени, поскольку каждое изменение должно пройти голосование сообщества.

Одним из самых известных примеров этого является The DAO, смарт-контракт, созданный на Ethereum в 2016 году в качестве своего рода децентрализованного фонда венчурных инвестиций. В результате взлома злоумышленнику удалось вывести из смарт-контракта Ethereum более 150 миллионов долларов из средств инвесторов, что привело к неоднозначному решению откатить блокчейн Ethereum, чтобы вернуть средства злоумышленнику. Этот инцидент привел к форку Ethereum Classic.

Несмотря на название, этот инцидент не был взломом в истинном смысле этого слова. Злоумышленник использовал малоизвестную на тот момент уязвимость в способе написания основного кода, чтобы выполнить действие, известное сегодня как атака реентерабельности, обратившись к ненадежному контракту для отъема средств.

После инцидента с The DAO разработчики обновили лучшие практики программирования, чтобы устранить эту уязвимость. Однако в системе, полной по Тьюрингу, где инноваторы постоянно пишут новый код, новые уязвимости могут появляться и дальше.