EdDSA и подписи Шнорра

Зачем это нужно в блокчейне

Solana использует EdDSA (Ed25519). Bitcoin с Taproot (2021) получил подписи Шнорра. Почему новые системы отказываются от ECDSA?

Проблемы ECDSA, которые мы видели в предыдущем уроке (опасный случайный nonce, сложная формула, невозможность агрегации подписей), решаются в EdDSA и Schnorr. Эти схемы проще, безопаснее и мощнее.

Три крупнейших блокчейна — три разных алгоритма подписи:

• Bitcoin (legacy): ECDSA на secp256k1
• Bitcoin (Taproot): Schnorr на secp256k1 (BIP 340)
• Solana: EdDSA на Ed25519

Подпись Шнорра: элегантная простота

Клаус-Петер Шнорр предложил свою схему подписи в 1989 году. Она проще ECDSA и обладает уникальными свойствами.

Алгоритм подписи Schnorr

Дано: приватный ключ d, публичный ключ P = d*G, сообщение m

1. Выбираем случайный nonce k из [1, n-1]
2. Вычисляем R = k * G
3. Вычисляем хеш-вызов e = H(R || P || m) (хеш конкатенации R, P и сообщения)
4. Вычисляем s = k + e * d mod n

Подпись: (R, s) — точка и число (или (r, s) где r = R.x)

Верификация Schnorr

Дано: подпись (R, s), публичный ключ P, сообщение m

1. Вычисляем e = H(R || P || m)
2. Проверяем: s * G == R + e * P ?

Почему это работает:

s * G = (k + e*d) * G = k*G + e*d*G = R + e*P

Обратите внимание, как просто! Одна формула для подписи (s = k + e*d), одна проверка для верификации (sG == R + eP). Сравните с ECDSA, где нужны обратные элементы и две промежуточных точки.

Линейность Шнорра: ключевое преимущество

Самое важное свойство Schnorr — линейность. Подписи можно складывать!

Агрегация ключей (Key Aggregation)

Допустим Алиса (d1, P1) и Боб (d2, P2) хотят создать совместную подпись:

Агрегированный ключ: P_agg = P1 + P2

Подписи:
  s1 = k1 + e * d1
  s2 = k2 + e * d2

Агрегированная подпись:
  s_agg = s1 + s2 = (k1 + k2) + e * (d1 + d2)

Верификация:
  s_agg * G == R_agg + e * P_agg
  где R_agg = R1 + R2 = (k1 + k2) * G

Это работает потому, что формула Schnorr линейна: s = k + e*d. Складывая два таких выражения, получаем валидную подпись для суммы ключей.

В ECDSA это невозможно из-за k^(-1) в формуле — обратный элемент ломает линейность.

Почему это важно для Bitcoin

В Bitcoin Taproot (BIP 340) агрегация Schnorr позволяет:

1. Мультиподписи как обычные подписи: 3-of-5 мультисиг выглядит в блокчейне как одна подпись от одного ключа. Это экономит место и улучшает приватность.
2. MuSig2: Протокол агрегации подписей для Bitcoin (2-раундовый).
3. FROST: Пороговые подписи (t-of-n) на основе Schnorr.

EdDSA: Schnorr на кривых Эдвардса

EdDSA (Edwards-curve Digital Signature Algorithm) — это вариант Schnorr с двумя ключевыми улучшениями:

1. Детерминированный nonce

Главная инновация EdDSA — nonce не случайный, а вычисляемый:

k = H(private_key_prefix || message)

Nonce определяется детерминированно из приватного ключа и сообщения. Это полностью исключает:

• Атаку повторного использования nonce
• Зависимость от генератора случайных чисел
• Уязвимости слабых ГСЧ на embedded-устройствах

Сравнение с ECDSA:

2. Кривая Эдвардса

EdDSA работает на twisted Edwards curves (мы разбирали Ed25519 в уроке 10):

• Единая формула сложения — нет особых случаев (P+O, P+(-P))
• Complete addition law — никогда не нужно проверять на деление на ноль
• Быстрее — оптимизированные формулы Эдвардса

Алгоритм EdDSA (Ed25519)

Генерация ключей:

seed = random(32 байта)
H(seed) -> (a, prefix)   -- хеш делится на две половины
a = clamped(first_half)   -- приватный скаляр (с фиксированными битами)
A = a * B                 -- публичный ключ (B -- базовая точка Ed25519)

Подпись:

r = H(prefix || message)  -- детерминированный nonce!
R = r * B                 -- точка nonce
S = r + H(R || A || message) * a mod l  -- l = порядок группы
Подпись: (R, S)

Верификация:

S * B == R + H(R || A || message) * A ?

Сравнение ECDSA vs Schnorr

Эволюция схем подписей

Код на Python: EdDSA с библиотекой ecdsa

from ecdsa import SigningKey, Ed25519

# Генерация ключей Ed25519
sk = SigningKey.generate(curve=Ed25519)
vk = sk.get_verifying_key()

print(f"Приватный ключ: {sk.to_string().hex()}")
print(f"Публичный ключ: {vk.to_string().hex()}")

# Подпись (всегда детерминированная)
message = b"Solana transaction: transfer 10 SOL"
sig1 = sk.sign(message)
sig2 = sk.sign(message)

# Ключевое свойство: детерминированность!
assert sig1 == sig2, "EdDSA подписи должны совпадать"
print(f"Подпись: {sig1.hex()[:32]}...")
print(f"Подписи идентичны: {sig1 == sig2}")

# Верификация
assert vk.verify(sig1, message)
print("Подпись верифицирована!")

Сравнение ECDSA и EdDSA на одном сообщении

from ecdsa import SigningKey, SECP256k1, Ed25519

message = b"Compare signature schemes"

# ECDSA (secp256k1)
sk_ecdsa = SigningKey.generate(curve=SECP256k1)
sig_ecdsa_1 = sk_ecdsa.sign(message)
sig_ecdsa_2 = sk_ecdsa.sign(message)
print(f"ECDSA: подписи одинаковые? {sig_ecdsa_1 == sig_ecdsa_2}")
# False! Каждый раз новый случайный k

# EdDSA (Ed25519)
sk_eddsa = SigningKey.generate(curve=Ed25519)
sig_eddsa_1 = sk_eddsa.sign(message)
sig_eddsa_2 = sk_eddsa.sign(message)
print(f"EdDSA: подписи одинаковые? {sig_eddsa_1 == sig_eddsa_2}")
# True! Детерминированный nonce

Bitcoin Taproot (BIP 340)

В ноябре 2021 года Bitcoin активировал Taproot — крупнейшее обновление протокола. Ключевая технология: Schnorr подписи (BIP 340).

Что дает Schnorr Bitcoin

1. Экономия места: Schnorr подпись на 11% меньше ECDSA (64 vs 72 байта в DER)
2. Batch verification: Множество подписей можно проверить за раз быстрее, чем по одной
3. MuSig2: Мультиподписи неотличимы от обычных подписей
4. MAST (Merkelized Abstract Syntax Trees): Скрытие неиспользованных условий расходования

BIP 340: особенности реализации

Кривая: secp256k1 (та же, что для ECDSA)
Подпись: 64 байта (r || s), r = 32 байта, s = 32 байта
Хеш: tagged hash -- H_tag(x) = SHA256(SHA256(tag) || SHA256(tag) || x)
Публичный ключ: только x-координата (32 байта вместо 33)

BIP 340 использует x-only public keys — публичный ключ занимает 32 байта вместо 33 (как в сжатом формате secp256k1). Это возможно благодаря выбору “четной” y-координаты по соглашению.

Key Path vs Script Path

В Taproot каждый выход имеет два пути расходования:

• Key Path: простая подпись Schnorr (выглядит как обычный перевод)
• Script Path: сложные условия через MAST (мультисиг, timelocks, etc.)

Благодаря агрегации Schnorr, даже сложный мультисиг через key path выглядит как обычная подпись одного ключа. Это улучшает приватность всех пользователей.

Schnorr vs EdDSA vs ECDSA: какой блокчейн что использует

Тренд: новые блокчейны предпочитают EdDSA (Ed25519) за скорость и безопасность. Bitcoin добавил Schnorr для агрегации подписей. ECDSA остается из-за совместимости.

Практика

Откройте Jupyter notebook 08-eddsa-schnorr.ipynb для практики:

• Реализация EdDSA подписи и верификации
• Демонстрация детерминированного nonce
• Schnorr подпись вручную
• Концепция агрегации подписей
• Сравнение ECDSA, EdDSA и Schnorr

Итоги

Главные выводы:

1. Schnorr проще ECDSA: одна формула подписи, одна проверка верификации
2. Линейность Schnorr позволяет агрегировать подписи — критично для Bitcoin Taproot
3. EdDSA = Schnorr + детерминированный nonce + Edwards curves — самый безопасный вариант
4. ECDSA остается в Bitcoin и Ethereum из-за обратной совместимости

Следующий урок: Деревья Меркла — структура данных для эффективной верификации данных в блокчейне.