Schnorr подписи

Подписите Schnorr са схема за подписи, която работи върху същата елиптична крива, както ECDSA. Биткойн е приел подписите Schnorr с ъпгрейда Taproot, който е бил активиран на блок 709,632 през ноември 2021 г. Формулите им са по-прости, подписът Schnorr е винаги 64 байта, а няколко подписа могат да се обединят. Изходите Taproot ги използват при харчене по ключовия път. Пълната схема е дефинирана в BIP 340.

Защо подписите Schnorr са по-прости от ECDSA?

Подписът ECDSA изисква модулна обратна стойност на k. Подписът Schnorr се нуждае само от събиране и умножение:

ECDSA:    s = k⁻¹ (z + r·d)  mod n
Schnorr:  s = k + e·d        mod n

Тази линейна форма има три практически последици. Подписването е по-евтино, тъй като не е нужна обратна стойност. Няколко подписа могат да се проверят заедно, като група. И подписите могат да се събират, така че няколко ключа да произведат един подпис. Наивното събиране на ключове е опасно, затова схемата MuSig добавя предпазни мерки.

Груповата проверка работи така. Всяка проверка на подпис се умножава по случаен множител, а резултатите се събират в едно уравнение. Ако всички подписи са валидни, уравнението важи. Ако един е невалиден, уравнението не важи, освен с ничтожна вероятност.

Подписите Schnorr са и по-лесни за доказване на сигурност. BIP 340 цитира доказателство за сигурност в модела на случайния оракул, който приема, че задачата за дискретния логаритъм върху елиптична крива е трудна. За ECDSA няма доказателство със същата сила.

Схемата Schnorr не е нова. Claus Schnorr я е описал през 1989 г., а патентът за нея в САЩ е бил издаден през 1991 г. Патентът е изтекъл през февруари 2010 г., година след старта на биткойн. Сатоши Накамото е използвал ECDSA, който OpenSSL вече предоставяше.

Как се кодират ключовете?

Ключовете Schnorr в биткойн използват само координатата x, 32 байта. За всяко x има две възможни стойности на y: една четна и една нечетна. BIP 340 винаги избира четната, така че знакът на y не е нужен. 33-байтовият компресиран публичен ключ става 32-байтов ключ само с x, като се премахне първият му байт. Два частни ключа, d и n − d, дават един и същ ключ само с x. Те също произвеждат едни и същи подписи, защото подписването сменя знака на ключа, когато е нужно.

Връщането на ключ само с x обратно в точка се нарича lift_x. То решава y² = x³ + 7 за y и избира четния корен:

def lift_x(x: int) -> tuple[int, int]:
    p = 2**256 - 2**32 - 977
    c = (x**3 + 7) % p
    y = pow(c, (p + 1) // 4, p)    # квадратен корен, защото p ≡ 3 (mod 4)
    if y * y % p != c:
        raise ValueError("x is not on the curve")
    if y % 2:
        y = p - y                  # избира четното y
    return x, y

Бързото извличане на корен работи, защото p дава остатък 3 при деление на 4. Ако резултатът не дава квадрат, равен на x³ + 7, няма точка с това x и ключът е невалиден.

Как се подписва със Schnorr?

Подписващият има частен ключ d', съобщението m и 32 байта допълнителни данни a. BIP 340 дефинира тези стъпки:

1. Направете ключа четен. Изчислете публичния ключ P = d'·G. Ако P.y е нечетно, задайте d = n − d'. В противен случай d = d'. Смяната на знака на ключа променя само знака на y, така че P.x остава същият.
2. Смесете допълнителните данни. Изчислете t = d XOR hashBIP0340/aux(a).
3. Направете nonce. Задайте k' = hashBIP0340/nonce(t ‖ P.x ‖ m) mod n и R = k'·G. Ако R.y е нечетно, задайте k = n − k'. В противен случай k = k'.
4. Направете предизвикателството. Задайте e = hashBIP0340/challenge(R.x ‖ P.x ‖ m) mod n.
5. Направете подписа. Задайте r = R.x и s = (k + e·d) mod n. Подписът е 32-байтовото r, следвано от 32-байтовото s.

Предизвикателството зависи от публичния ключ и от съобщението, а не само от nonce-а. Това се нарича префиксиране с ключа (key-prefixing). То спира атака със свързани ключове. Без него подпис за един ключ би могъл да се превърне във валиден подпис за ключ, изместен с известна величина, например неусилен (unhardened) дъщерен ключ по BIP 32 или Taproot tweak. Nonce-ът зависи от частния ключ и от съобщението, а не само от допълнителните байтове. Затова слаб източник на случайни числа сам по себе си не издава ключа. Допълнителните байтове добавят защита срещу атаки през странични канали, а подписването остава сигурно, дори ако са всички нули.

Как се проверява подпис Schnorr?

Проверяващият има 32-байтовия публичен ключ, съобщението m и подписа (r, s). Стъпките са:

1. Изчислете P = lift_x(публичен ключ). Ако това не е възможно, подписът е невалиден.
2. Прочетете r и s. Ако r ≥ p или s ≥ n, подписът е невалиден.
3. Изчислете e = hashBIP0340/challenge(r ‖ P.x ‖ m) mod n. Това е същото e, което е изчислил подписващият.
4. Изчислете R = s·G + (n − e)·P. Членът (n − e)·P е същият като −e·P, така че R = sG − eP.
5. Приемете подписа само ако R не е точката в безкрайността, R.y е четно и R.x = r.

Причината е същата като при ECDSA, но математиката е по-проста. Ако подписващият е построил s = k + e·d, то s·G = kG + e·dG = R + e·P, следователно R = sG − e·P.

Ето tagged hash функцията, която BIP 340 използва във всяка стъпка. Страницата за хеш функцията обяснява конструкцията подробно.

import hashlib

def tagged_hash(tag: str, msg: bytes) -> bytes:
    t = hashlib.sha256(tag.encode()).digest()
    return hashlib.sha256(t + t + msg).digest()

Как изглежда примерът?

Тези стойности са тестовият вектор 1 от BIP 340. Ако изпълните стъпките по-горе върху тях, получавате същия публичен ключ и подпис, а подписът се проверява. Променете един байт от подписа и проверката се проваля.

частен ключ   B7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF
публичен ключ DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659
aux           0000000000000000000000000000000000000000000000000000000000000001
съобщение     243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89
подпис        6896BD60EEAE296DB48A229FF71DFE071BDE413E6D43F917DC8DCF8C78DE33418906D11AC976ABCCB20B091292BFF4EA897EFCB639EA871CFA95F6DE339E4B0A

Публичният ключ е само координатата x. Подписът са 64-те байта r, следвани от s. Към BIP 340 има файл с още тестови вектори и той е правилното място да проверите собствения си код: test-vectors.csv.

Защо подписите Schnorr са устойчиви на промени?

ECDSA подписите могат да се променят по безобиден на вид начин. Замяната на s с n − s дава друг валиден подпис. При Schnorr тази промяна не работи. Проверката в стъпка 5 се проваля, така че валиден подпис не може да се превърне в друг валиден подпис по този прост начин. Така отпада податливостта, която правилото low-s трябваше да кърпи при ECDSA.

Къде се използват подписите Schnorr?

Подписите Schnorr се използват при харчене от P2TR (Taproot) изходи. Харчене по ключовия път има един 64-байтов подпис, който заменя 70 до 72 байта от DER кодирането на ECDSA. Типът sighash може да добави още един байт, така че подписът е 65 байта, когато типът не е по подразбиране. Прочетете страницата за скрипта P2TR и страницата за ъпгрейда Taproot, за да видите цялата картина.

ECDSA все още се използва за по-стари скриптове, така че двете схеми съществуват една до друга. Ключовете, които вече имате, работят за всяка от тях, защото кривата е същата.

Какво да прочетете след това?

Ако още не сте прочели ECDSA, започнете оттам. Той използва същата крива по друг начин, а сравнението прави дизайна на Schnorr по-лесен за проследяване. След това страницата за частния ключ показва как тайно число става публичният ключ, срещу който се проверява всеки подпис тук.