ECDSA

ECDSA, Elliptic Curve Digital Signature Algorithm, е схемата за подписи, която биткойн използва от първите си трансакции. Тя приема хеш на съобщението и частен ключ и произвежда две числа, r и s. Всеки, който има публичния ключ, може да провери двойката, без да научи частния ключ. Повечето по-стари скриптове за заключване още очакват подписи ECDSA, затова ще го срещнете в много трансакции.

Какво изисква ECDSA?

За подписване са нужни три входа. За проверка са нужни други три.

Вход	За подписване	За проверка
z	Хешът на данните, които се подписват	Същият хеш, изчислен наново от проверяващия
d	Вашият частен ключ	Не се използва
k	Ново случайно число, nonce	Не се използва
Q	Не е нужен	Публичният ключ, Q = d·G
(r, s)	Създава се от подписващия	Проверява се от проверяващия

В биткойн z е sighash. Това е HASH256 на данните на трансакцията, подготвени за подписване. Какво точно покрива подписът, е описано на страницата за подписа. Частният ключ d е число от 1 до n − 1, а публичният ключ е точката Q = d·G върху елиптичната крива.

Как се подписва съобщение?

Подписващият следва четири стъпки. Цялата аритметика със скаларите е по модул n, редът на кривата.

R = k·G
r = R.x mod n
s = k⁻¹ (z + r·d) mod n
signature = (r, s)

Първо подписващият умножава генераторната точка G по случайния nonce k. Така получава случайна точка R. Запазва се само координатата x на R, като r. После s комбинира хеша на съобщението z с r и частния ключ d, като използва обратната стойност на k. Подписът е двойката (r, s). Ако r или s се окажат нула, подписващият трябва да избере друго k.

Ето пример с точни числа. Фиксираното k прави резултата повторяем, затова примерът е само за учене. При истинско подписване k трябва да е случаен.

message = "ECDSA is the most fun I have ever experienced"
z = 103318048148376957923607078689899464500752411597387986125144636642406244063093
d = 112757557418114203588093402336452206775565751179231977388358956335153294300646
k = 12345
r = 108607064596551879580190606910245687803607295064141551927605737287325610911759
s = 73791001770378044883749956175832052998232581925633570497458784569540878807131

Тук z е SHA-256 хешът на текста на съобщението. Публичният ключ Q = d·G има координата x = 33886286099813419182054595252042348742146950914608322024530631065951421850289.

Формулата за подписване в Python е един ред, след като имате обратната стойност:

s = pow(k, -1, n) * (z + r * d) % n

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

Проверяващият се нуждае от z, подписа (r, s) и публичния ключ Q. Той изчислява:

w  = s⁻¹ mod n
u1 = z·w mod n
u2 = r·w mod n
X  = u1·G + u2·Q
valid if X.x mod n = r

Защо това работи? Уравнението на подписващия дава k = s⁻¹(z + r·d). Разгънете страната на проверката и ще получите u1·G + u2·Q = s⁻¹·z·G + s⁻¹·r·d·G. Това е равно на s⁻¹(z + r·d)·G, което е k·G. Проверяващият стига до същата точка R, от която е тръгнал подписващият. Само някой, който знае d, може да построи валидно s за това R.

За горния пример проверяващият получава X.x равно на r, така че подписът е валиден.

Какво е low-s?

ECDSA има недостатък, наречен податливост (malleability). Ако (r, s) е валиден, то (r, n − s) е валиден за същото съобщение и ключ. Трето лице може да смени едната форма с другата и да промени TXID на трансакцията, без да промени какво прави тя. Правилото в BIP 146 изисква формата low-s, при която s ≤ n/2. Портфейлите публикуват тази форма.

В примера по-горе s е над n/2, така че портфейлът ще публикува n − s, а не s. И двете форми се проверяват, така че правилото определя само коя от тях се счита за стандартна.

Защо никога да не използвате повторно k?

Ако два подписа от един и същ ключ използват един и същ nonce k, те споделят r, защото r зависи само от R = k·G. Всеки подпис дава едно уравнение, а двете уравнения могат да се решат заедно. Резултатът е k, а от k получавате частния ключ d.

k = (z1 − z2) / (s1 − s2)  mod n
d = (k·s1 − z1) / r        mod n

В Python:

def recover_d(z1, z2, s1, s2, r, n):
    k = (z1 - z2) * pow(s1 - s2, -1, n) % n
    return (k * s1 - z1) * pow(r, -1, n) % n

Това не е теория. През декември 2010 г. групата fail0verflow е показала как може да се възстанови ключът за подписване на PlayStation 3. Sony е използвала един и същ nonce за подписите си. Много портфейли вече извличат k детерминистично от частния ключ и съобщението, както описва RFC 6979. Това намалява риска, но поуката остава в сила: повторен nonce издава ключа.

Къде се появява ECDSA в биткойн?

ECDSA подписва входовете на по-старите P2PKH трансакции и на SegWit трансакциите P2WPKH. Подписът е кодиран във формат DER и обикновено е дълъг 70 до 72 байта. След него идва един байт за типа sighash, така че подписът в трансакцията обикновено е 71 до 73 байта. Прочетете страниците за скриптовете, за да видите къде стои подписът при всеки тип заключване.

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

Какъв е стандартът за ECDSA?

Основната дефиниция е в стандарта FIPS 186-4 на NIST. Параметрите на кривата идват от SEC 2. Прочетете първо страницата за елиптичната крива, ако математиката на точките ви е нова. Страницата за подписа показва какво покрива подписът при харчене, а страницата за Schnorr е следващата стъпка.