Подпись в биткоине состоит из двух чисел, r и s. Процедура их создания умещается в пять строк, проверка — в три, а объяснение, почему это работает, — в одно алгебраическое преобразование. Этот урок охватывает все три аспекта.
Начнем с того, что входит в процесс. Подписываемое сообщение — это транзакция, сокращенная с помощью SHA-256 и читаемая как число, называемое z. Закрытый ключ — это число d, а открытый ключ — это точка Q, которая равна d, умноженному на G. И есть третий компонент, случайно выбранный в момент подписания, — это nonce k.
Процесс подписания состоит из четырех шагов. Выберите k в диапазоне от одного до n минус один. Вычислите точку k, умноженную на G, и возьмите ее координату x, уменьшенную по модулю n: это и есть r. Вычислите s как обратное k, умноженное на сумму z и r, умноженного на d, все это по модулю n. Подпись — это пара r, s. Если r или s равны нулю, выбирается другое k — что на практике почти никогда не происходит.
Обратите внимание, что закрытый ключ d появляется только один раз, на третьей строке, смешанный с z и защищенный умножением на обратное k. Ничто в r или s не позволяет его изолировать — при условии, что k каждый раз разное, и следующий урок полностью посвящен тому, что происходит, когда это не так.
Проверка состоит из трех шагов, и у проверяющего есть только транзакция, открытый ключ Q и пара r, s. Вычислите обратное s по модулю n. Умножьте z на него и назовите результат u1; умножьте r на него и назовите результат u2. Сложите точки u1, умноженные на G, и u2, умноженные на Q. Подпись действительна, если координата x полученной точки, уменьшенная по модулю n, равна r.
Теперь замена, которая все объясняет. Точка, вычисленная при проверке, — это u1, умноженное на G, плюс u2, умноженное на Q. Заменив Q на d, умноженное на G, это становится обратным s, умноженным на сумму z и r, умноженного на d, все это умноженное на G. Но s было определено именно как обратное k, умноженное на ту же самую сумму — таким образом, обратное s, умноженное на сумму, просто равно k. Точка, которую производит проверка, — это k, умноженное на G: именно та точка, которую подписывающий вычислил на втором шаге, и чья координата x стала r, с которым происходит сравнение.
Вот почему проверка работает, не раскрывая ничего. Проверяющий не узнает d, не узнает k и никогда не узнает, какой был выбор. Он просто восстанавливает ту же точку другим путем и подтверждает, что оба пути сходятся.
Три практических детали завершают тему.
Первая заключается в том, что r хранит только координату x точки, а высота отбрасывается. Поскольку каждому x соответствует две точки, одна выше и другая ниже оси, подпись сама по себе не указывает, какая из них была использована. Поэтому восстановление открытого ключа из подписи требует дополнительного бита для восстановления, и поэтому обычная транзакция содержит открытый ключ вместо его вывода.
Второе — это неприятное следствие симметрии. Для каждой допустимой подписи со значением s также допустимо значение n минус s — это две разные пары, доказывающие одно и то же. Это позволяло изменять идентификатор транзакции, не делая ее недействительной, что было недостатком, упомянутым в войне блоков. С 2016 года сеть требует меньшего из двух значений, и другой путь закрыт.
Третье — это упаковка. Оба числа передаются в формате, унаследованном от стандартов сертификатов, DER, который занимает от семидесяти до семидесяти двух байт из-за маркеров длины и типа. Подпись Шнорра, которую принес Taproot, имеет фиксированный размер в шестьдесят четыре байта и не содержит украшений — часть экономии от этого обновления заключается здесь.
Математика этого урока надежна и ни разу не была взломана. То, что уже было взломано, с реальными убытками и в более чем одном известном случае, — это выбор случайного числа на третьей строке. В следующем уроке — повторяющийся nonce и школьная алгебра, которая раскрывает закрытый ключ.