Сложить генератор с самим собой тринадцать раз кажется требует двенадцать сложений. Требует пять. А сложить его с самим собой число с семьюдесятью семью цифрами требует менее четырехсот операций. Именно это сокращение делает Bitcoin возможным — и отсутствие эквивалентного сокращения в обратном пути делает его безопасным.
Метод называется удвоение-и-сложение, и рецепт заключается в чтении числа в двоичной системе. Тринадцать в двоичной системе — это 1101. Начните с левого бита, держа точку G в руке. Для каждого следующего бита удваивайте то, что у вас есть; если бит равен единице, добавьте G после удвоения. Второй бит — единица: удвойте до 2G, сложите до 3G. Третий — ноль: удвойте до 6G, и больше ничего. Четвертый — единица: удвойте до 12G, сложите до 13G. Три удвоения, два сложения, и вы пришли к результату.
Для числа из 256 бит это максимум 256 удвоений и, в среднем, 128 сложений. Менее четырехсот операций там, где грубая сила потребовала бы число, которое не поместится на этой странице. Это та же экономия геометрической прогрессии: несколько удвоений достигают того, чего постоянное сложение не достигло бы.
Однако этот рецепт, записанный именно так, имеет серьезный недостаток — и он не в математике. Бит, равный единице, стоит удвоения и сложения; бит, равный нулю, стоит только удвоения. Время, которое машина затрачивает, таким образом, зависит от битов закрытого ключа. Тот, кто сможет точно измерить это время или потребление энергии устройства во время вычислений, может прочитать ключ, не ломая ничего.
Поэтому ни одна серьезная реализация не использует наивный рецепт. Библиотека, которую использует Bitcoin Core, libsecp256k1, выполняет последовательность операций, которая занимает ровно столько же времени, независимо от ключа, выполняя работу нулевого бита, даже когда он равен нулю. Это называется постоянное время, и это разница между хорошо сделанным аппаратным кошельком и украшением.
Теперь обратный путь. Дана точка kG и известно, что началом было G, каково k? Проблема имеет название — дискретный логарифм — и не имеет общего решения лучше, чем квадратный корень из размера группы. Два метода, которые достигают этого корня, это шаг младенца и шаг гиганта, который обменивает память на время, и рё Полларда, который практически не использует память и хорошо параллелизуется. Оба будут рассмотрены в следующем модуле.
Квадратный корень из 2^256 равен 2^128, что составляет 34, за которым следуют 37 нулей. Стоит сделать расчет с намеренной щедростью. Предположим, что вся вычислительная мощность сети Bitcoin, что-то около секстиллиона операций в секунду, была бы перенаправлена на это, и притворимся, что каждая из этих операций — это операция на кривой — что неверно на несколько порядков величины, потому что операция на кривой стоит в тысячи раз больше, чем хеш. Даже с этим воображаемым преимуществом, сканирование заняло бы около десяти миллиардов лет. Исправляя на реальную разницу в стоимости, это займет порядка 10^14 лет: почти десять тысяч раз возраст вселенной.
Запомните одну фразу для следующего модуля, потому что она предотвращает дорогое недоразумение. Этот расчет применим к ключу, выбранному во всем диапазоне. Вызовы, которые существуют в блокчейне и которые создает этот сайт, не атакуют 2^256 или 2^128: они атакуют намеренно небольшие диапазоны, от семидесяти до восьмидесяти бит, где тот же квадратный корень возвращает число, которое помещается в реальный проект. Математика не становится слабее. Диапазон становится меньше.
Осталась одна часть, чтобы завершить криптографию Bitcoin: как эти точки и эти числа превращаются в подпись и почему проверка работает. В следующем уроке ECDSA, рассчитанный шаг за шагом.