Язык Michelson полный по Тьюрингу: что это значит и почему это важно

Язык Michelson полный по Тьюрингу: что это значит и почему это важно

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

Объясняем простыми словами, чем опасны тьюринг-полные языки, почему неполных по Тьюрингу языков почти нет, и как язык Tezos — Michelson — защищен от опасностей.

Детально о полноте по Тьюрингу

Алан Тьюринг — английский математик, основоположник информатики и создатель первого компьютера в современном понимании. В 1936 году он описал понятие алгоритма как машину, которая может вычислить любую функцию через простейшие команды вроде сложения чисел. Эта абстракция получила название «машина Тьюринга».

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

Живой пример этого принципа — язык программирования BrainFuck. В нем всего восемь команд: чтение, запись, сдвиг ячейки влево и вправо, уменьшение и увеличение текущего значения на единицу, открытие и закрытие while-цикла.

Так выглядит «Hello World!» на BrainFuck:

Компьютеры работают с буквами в виде кодировки ASCII: буква H обозначается числом 72, e — 101, l — 108 и так далее. Эта программа сначала записывает в ячейку 0 число 10, а затем запускает цикл из десяти итераций: в ячейку 1 записать 7, в ячейку 2 — 10, и так десять раз. Затем она суммирует в каждую ячейку недостающие числа, и выводит результат — 72 101 108 108 111 — слово «Hello».

Любой современный компьютер работает с таким же набором команд, как и BrainFuck. Когда пользователь в текстовом документе нажимает клавишу «e», компьютер так же двигает каретку, суммирует биты и использует циклы. Но благодаря быстродействию в триллионы операций в секунду пользователи этого не замечают.

Аналогично с компьютером, команда для вывода строки на экран в любом высокоуровневом языке считывает единицы и нули из устройства хранения данных, слагает их в ANSII-код и только тогда выводит «Hello world!». По сути, команды языков программирования запускают огромные циклы из примитивов, которые Тьюринг описал еще в 1936 году.

Почему тьюринг-полные языки — опасные

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

Например, в приставке GameBoy есть 8-битный процессор, который в качестве входящих аргументов принимает числа от 0 до 255. Нажатия кнопок также обозначаются числами, например, нажатие кнопки «вверх» передает в процессор число 16. Игра Pokemon Yellow сохраняет инвентарь и покемонов игрока в виде таких же чисел в отдельном файле.

Если набрать в инвентарь определенное количество предметов, то процессор GameBoy увидит вместо описания вашего Пикачу исполняемый файл, то есть программу. Разработчик Робер МакИнтур использовал эту особенность приставки, чтобы простыми нажатиями кнопок сделать внутри игры программу для проигрывания MIDI-музыки и просмотра PNG-изображений.

Другой разработчик под ником Masterjun похожим образом сломал игру Super Mario World на 16-битной приставке SNES. Он подключил к приставке сразу 8 контроллеров, и с их помощью ввел в Mario исполняемый код простых игр вроде змейки.

Похожим образом игроки ломали стратегию Starcraft: переполняли буфер памяти, а затем с помощью внутриигровых действий вводили бинарный код. Так как Starcrfat работает на полноценных компьютерах, то в нем получилось запустить игру Super Mario Bros. и даже редактор уровней для нее.

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

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

Существуют и неполные по Тьюрингу языки, например HQ9+. В нем всего четыре команды: вывод Hello World, собственного исходного кода, стиха «99 бутылок пива на стене» и бесконечного счетчика. Но на таком языке нельзя написать ничего другого.

Почему Michelson надежен, несмотря на полноту по Тьюрингу

Главная фича Michelson — строгая типизация. Благодаря этому хакер не сможет убедить смарт-контракт принять строку за чистые байты или число с запятой за натуральное число. Именно из-за отсутствия строгой типизации разработчики из примеров выше взламывали игры посредством интерфейса и внедряли в них сторонний исполняемый код.

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

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

Подписывайтесь на социальные сети Tezos Ukraine, чтобы ничего не пропустить:

  1. Telegram-канал
  2. Facebook.
  3. Twitter на русском и украинском языках
  4. Twitter на английском языке
  5. YouTube-канал
  6. Instagram
  7. LinkedIn
  8. hub на ForkLog

следующий

GameFi-проекты: что это такое и кому они приносят пользу на самом деле

Читайте похожие посты

Лимитные ордеры на SpicySwap: нововведение, которое все пропустили

Лимитные ордеры на SpicySwap: нововведение, которое все пропустили

Самый важный кирпичик в DeFi: обзор лендингового протокола Yupana

Самый важный кирпичик в DeFi: обзор лендингового протокола Yupana

Аналитика экономики Tezos: мейнстрим — это хорошо

Аналитика экономики Tezos: мейнстрим — это хорошо

Читайте блог и не пропускайте новостей о TezosЧитать блог

Сообщество