Мифы против Web 3.0 & Web. Кейс №02. Самая главная ошибка Биткоина
The DAO форк vs. ошибка Биткоина 2010
Многие биткоин-макси (попросту говоря - спекулянты на цене BTC) считают, что форк 2016 года в Эфире - это зло, чушь и нарушение децентрализации, но... почему-то забывают, что в самой сети Биткоина в 2010, 2013, 2016, 2018 гг. было не мало фейлов.
Нет, это не делает Биткоин плохим, но это делает его историю сопоставимой с эфировской.
Общее сравнение инцидентов
А теперь давайте подробней и по шагам.
Компьютерный счётчик не бесконечен
Представим механический счётчик условного автомобиля с шестью барабанами:
000000 000001 000002 ... 999998 999999
Что произойдёт, если к 999999 прибавить единицу?
1000000
Потому что седьмого барабана нет. Счётчик просто обнулится:
000000
Это и есть простейшая аллегория переполнения, которая пришла мне в голову. Почему?
Да потому что компьютерное число тоже хранится в ограниченном количестве ячеек - битов: когда результат оказывается больше максимально представимого числа, лишняя старшая часть теряется, а счётчик как бы начинает новый круг.
И что? А то, что в Bitcoin суммы хранились на 2010 год не как дробные BTC. То есть данные не хранились в формате:
92 233 720 368,54277039 BTC
Она хранилась в сатоши (логично же?):
1 BTC = 100 000 000 сатоши
Следовательно, каждый из двух выходов транзакции, которую тут разбираем с вами, был равен:
92 233 720 368,54277039 BTC × 100 000 000 = 9 223 372 036 854 277 039 сатоши
A = 9 223 372 036 854 277 039
В транзакции было два одинаковых выхода:
A + A
То есть реальная сумма выходов:
18 446 744 073 708 554 078 сатоши
184 467 440 737,08554078 BTC
Занимательно, что то самое, я бы сказал, историческое, сообщение об ошибке прямо описывало проблему так: "сумма двух выходов переполнилась и превратилась в отрицательное значение".
Но почему именно такие странные числа? Думаю, что суммы были выбраны не случайно: ведь Bitcoin использовал 64-битное знаковое целое число - int64. У него, этого числа, есть ровно 64 двоичных позиции:
[знак] [остальные 63 бита для числа]
Максимальное положительное значение поэтому для int64:
9 223 372 036 854 775 807
92 233 720 368,54775807 BTC
А каждый мошеннический выход составлял:
9 223 372 036 854 277 039 сатоши
498 768 сатоши
Меньше максимального положительного int64.
Иными словами, злоумышленник положил в каждый выход почти максимально возможное число, которое ещё помещалось в контейнер.
Приведу ещё одну аллегорию, чтобы стало понятней: представим два грузовика. Каждый из них рассчитан максимум на:
9 223 372 036 854 775 807 кг
В каждый загружают почти предельный вес:
9 223 372 036 854 277 039 кг
Каждый грузовик по отдельности ещё способен записать это значение в своей накладной и "запихнуть" в себя. Но потом бухгалтер складывает вес обоих грузовиков, используя калькулятор, который также не умеет считать числа больше определённой границы. И что? И калькулятор ломается не физически - он просто показывает совершенно другое число, не то, что загружено в кузовы.
"Ок. Допустим, но как положительное число превращается в отрицательное-то?" - спросите вы меня. И я отвечу: дело в том, что для знакового 64-битного числа диапазон выглядит примерно так:
−9 223 372 036 854 775 808 ... −1 0 1 ... 9 223 372 036 854 775 807
Можно представить этот диапазон не как прямую, а как... круг:
0
положительные
числа
↑
|
отрицательные ← граница → положительные
|
↓
отрицательные
числаИли ещё проще - как часы: да, те самые, что нынешнее поколение упорно не понимает. Возьмём банальный пример:
11 + 2 = 1
Почему 1-то? Не потому ведь, что в математике 11 + 2 действительно равно 1, а потому что циферблат замкнут и после 12 начинается новый круг.
Так вот та же байда происходит и в 64-битном счётчике:
максимальное положительное число + 1 = минимальное отрицательное число
9 223 372 036 854 775 807 + 1 = −9 223 372 036 854 775 808
Это не обычная математика, но это результат того, что контейнер имеет фиксированный размер.
Давайте сделаем прямой расчёт именно той самой транзакции в том самом блоке (точнее их было 2) - два выхода содержали:
9 223 372 036 854 277 039 + 9 223 372 036 854 277 039 = 18 446 744 073 708 554 078 сатоши
Полный круг 64-битного счётчика содержит:
2⁶⁴ = 18 446 744 073 709 551 616
Посмотрим, насколько реальная сумма меньше полного круга:
18 446 744 073 709 551 616 − 18 446 744 073 708 554 078 = 997 538
То есть сумма оказалась почти у самого конца 64-битного круга - всего за 997 538 единиц до нуля. И когда тогда те же биты интерпретировались как знаковое число, результат выглядел как:
−997 538 сатоши
−0,00997538 BTC
Получается парадоксальная картина:
Фактическая сумма выходов: 184 467 440 737,08554078 BTC
Но переменная внутри программы могла увидеть:
−0,00997538 BTC
Именно поэтому современники описывали атаку как транзакцию с отрицательной общей суммой.
И всё дело было в том, что существовала упрощённая модель (старой) проверки. Представим, что код делает следующее:
int64 total = 0;
for (каждый выход) {
total += значение_выхода;
}
if (total > 21_000_000 BTC) {
отклонить транзакцию;
}Выход 1: 92 млрд BTC Выход 2: 92 млрд BTC Итого: 184 млрд BTC 184 млрд > 21 млн → отклонить
Но из-за переполнения программа получила:
Итого: −0,00997538 BTC
−0,00997538 BTC > 21 000 000 BTC?
Нет.
Следовательно? Конкретная проверка максимального значения НЕ срабатола!
Давайте приведу ещё одну аллегорию. Представим склад, куда разрешено заносить не более 21 миллиона монет (на самом деле - ещё чуть меньше).
Охранник на этом складе (по не ведомой нам причине) смотрит не внутрь ящиков, а только на итоговую цифру в электронной системе учёта. Злоумышленник, зная это, заносит два гигантских ящика:
Ящик 1: 92 млрд монет Ящик 2: 92 млрд монет
Система пытается сложить (а что ей ещё делать, если для этого она и была создана?):
92 млрд + 92 млрд
Но её табло слишком маленькое и после переполнения показывает:
−0,00997538 монеты
Число больше 21 миллиона?
Нет, число вообще отрицательное.
Охранник пропускает груз. Почему? Одному Богу ведомо (и Сатоши).
Проблема здесь не в том, что правило не более 21 миллиона отсутствовало. Проблема в том, что число, которое передали этому правилу, уже было испорчено. Совсем. К тому же - намеренно.
Почему же первый огромный выход сразу не остановил проверку?! И да, это ключевой момент. Правильная реализация должна была бы проверить каждый выход до сложения:
for (каждый выход) {
if (выход < 0)
reject;
if (выход > MAX_MONEY)
reject;
if (total > MAX_MONEY - выход)
reject;
total += выход;
}Но уязвимая логика фактически полагалась на итоговую сумму. Упрощённо это выглядит так:
total = output1 + output2; проверить total;
Первый выход был огромным, но вычисление продолжалось. Когда добавили второй, произошло переполнение. Поэтому до окончательной проверки дошло уже не огромное положительное число, а маленькое отрицательное.
Аналогия в рамках именно бухгалтерских инструкций (вспомним, что блокчейн - это в конечном счёте ближайший родственник гроссбуха и леджера): после внесения всех покупок проверьте итоговую сумму. А вот покупки были такими:
Покупка 1: 92 млрд Покупка 2: 92 млрд
Но никто не говорил ведь, что после каждой покупки надо было убедится, что число допустимо и сложение не переполнит калькулятор учёта? Вот именно - никто, поэтому бухгалтер сначала ломает итоговый счётчик и лишь затем проверяет уже неверный результат.
Ок, допустим. Но почему тогда было два выхода, а не один? Всё просто: один выход на всю сумму выглядел бы так:
184 467 440 737 BTC
Но такое значение само по себе уже не помещалось бы в знаковое 64-битное поле! Поэтому были использованы два выхода, каждый из которых:
помещался в int64 по отдельности;
не помещалась в int64.
Это как пройти через дверь с двумя отдельными коробками:
коробка №1 проходит; коробка №2 проходит;
А ошибка возникает уже внутри, когда система пытается записать их (коробок) общий вес в слишком маленькое поле.
Тогда, что значит знак в двоичном числе, раз мы говорим про положительные и отрицательные числа? Опять же - упрощу: возьмём не 64 бита, а всего 4. Четыре бита могут иметь 16 комбинаций:
0000 0001 0010 ... 1111
Если считать число беззнаковым:
0000 = 0 0001 = 1 ... 1111 = 15
Но если число знаковое, те же биты обычно читаются так:
0000 = 0 0001 = 1 ... 0111 = 7 1000 = −8 1001 = −7 ... 1111 = −1
7 + 1
0111 + 0001 = 1000
Но 1000 в знаковом формате означает не 8, а:
−8
7 + 1 = −8
Именно такой тип перехода и произошёл в Bitcoin, только не с четырьмя битами, а с 64: собственно, сложность тут решила многое.
Миниатюрная версия атаки
Давайте теперь сложим 2+2 и получим... 555 :), как этого хотел Сатоши. Допустим, наш вымышленный коин использует 8-битные знаковые числа. Диапазон таков:
−128…127
100 монет
Злоумышленник делает два выхода:
Выход 1: 120 Выход 2: 120
120 + 120 = 240
Но 8-битное знаковое число не может хранить 240. Полный круг 8-битного счётчика (см. выше):
2⁸ = 256
240 − 256 = −16
Итого: −16 монет
−16 > 100?
Нет.
Хотя реально было создано 240 монет. Bitcoin-инцидент был тем же самым, только числа были намного больше. И всё.
И здесь возникает логичный вопрос: "Почему проверка формата "выходы не должны превышать входы" тоже могла сломаться? Возьмём опять же упрощённую схему - обычную транзакцию, которая должна соблюдать простое условие:
сумма входов ≥ сумма выходов
Входы: 1 BTC Выходы: 0,9 BTC Комиссия: 0,1 BTC
Но после переполнения программа могла видеть:
Вход: около 0,5 BTC Сумма выходов: −0,00997538 BTC
Тогда вычисление комиссии выглядело примерно так:
комиссия = входы − выходы
0,5 − (−0,00997538) = 0,50997538 BTC
Вместо того чтобы заметить выпуск 184 млрд BTC, система могла интерпретировать расчёт так, будто транзакция не только не создала деньги, но и заплатила майнеру примерно 0,51 BTC комиссии.
Это как если бухгалтерская система увидела отрицательную стоимость товаров:
покупатель принёс: 0,5 монеты; товары стоят: −0,01 монеты; магазину осталось: 0,51 монеты.
Из-за неправильного знака экономический смысл расчёта полностью перевернулся.
Что именно следовало исправить? Не с моей точки зрения, а объективно. Во-первых, понять, что нельзя сначала выполнять потенциально опасное сложение, а потом проверять результат. А что тогда делать? Очевидно - нужно проверять, безопасно ли сложение до его выполнения:
if (current_total > MAX_VALUE - next_output) {
reject;
}
current_total += next_output;Почему это работает? Возьмём снова простейший пример:
MAX = 100 current_total = 80 next_output = 30
80 + 30 = 110
80 > 100 − 30? 80 > 70? Да.
Значит, сложение переполнит допустимый предел - транзакция сразу отклоняется. Кроме этого, в подобных случаях необходимо проверять каждый выход отдельно:
выход не отрицательный; выход не больше MAX_MONEY; накопленная сумма не больше MAX_MONEY; сложение не переполняет тип данных.
Версия Bitcoin 0.3.10 была опубликована как исправление переполнения в блоке 74638 и, собственно, пошла по похожей схеме.
Теперь каждый из вас, понимая произошедшее, может самостоятельно вывести самую точную и короткую формулу произошедшего. Для начала определим, чего НЕ произошло:
Программа решила, что 184 млрд BTC разрешены.
А потом подумаем и определим, что же всё таки произошло?
1. Программа получила два огромных выхода. 2. Каждый выход помещался в отдельное 64-битное число. 3. При сложении двух выходов 64-битного пространства не хватило. 4. Итоговые биты стали интерпретироваться как отрицательное число. 5. Проверка лимита получила уже неправильную сумму. 6. Маленькое отрицательное число не оказалось больше 21 млн BTC. 7. Транзакция была ошибочно признана допустимой.
Главная мысль моей статьи - фактически цитата.
Лимит Bitcoin был обойдён не потому, что отсутствовало правило, а потому, что арифметическая ошибка подменила число до того, как это правило это число проверило.