Matematica din spatele Bitcoin

13 octombrie 2014 bitcoin

Articol scris de Wu Mihu

Eric Rykwalder este un inginer de software și unul din fondatorii Chain.com. El oferă o privire de ansamblu asupra fundamentelor matematice ale protocolului Bitcoin.

math-behind-bitcoin-630x376

 

Un motiv pentru care Bitcoin poate fi confuz pentru începători este că tehnologia din spatele aceastei monede redefinește conceptul de proprietate.

Pentru a deține ceva în sensul tradițional, fie că este vorba de o casă sau o sumă de bani, înseamnă să ai custodia personală de lucru sau acordarea de custodie pentru o entitate de încredere, cum ar fi o bancă.

Cu Bitcoin cazul este diferit. Monedele Bitcoin în sine nu sunt stocate la nivel central sau local, și așa nu este în custodia unei entități. Ele există ca înregistrări pe un registru distribuit numit lanțul de bloc, copii care sunt împărtășite de către o rețea de voluntari de calculatoare conectate. Pentru a „deține” o monedă Bitcoin pur și simplu reprezintă faptul că ai capacitatea de a transfera controlul acesteia altcuiva prin crearea unui record de transfer în lanțul de bloc. Ce oferă această capacitate? Accesul public și privat la perechea de chei ECDSA. Ce înseamnă asta și cum rezultă că Bitcoin este p monedă sigură?

Să aruncăm o privire în spatele acestei tehnologii.

ECDSA este prescurtarea pentru Elliptic Curve Digital Signature Algorithm. Este un proces care folosește o curbă eliptică și un domeniu finit pentru a „semna” date în așa fel încât terții pot verifica autenticitatea semnăturii în timp ce semnatarul își păstrează capacitatea exclusivă de a crea semnătura. Cu Bitcoin, datele care sunt semnat reprezintă tranzacția care transferă dreptul de proprietate.

ECDSA are proceduri separate pentru semnare și verificare. Fiecare procedură este un algoritm compus din câteva operații aritmetice. Algoritmul de semnare face uz de cheia privată, iar procesul de verificare face uz de cheia publică. Vom arăta un exemplu de acest mecanism mai târziu.

Dar, mai întâi, un curs intensiv pe curbe eliptice și corpuri finite.

Curbe eliptice

O curbă eliptică este reprezentată algebric ca o ecuație de forma:

y2 = x3 + ax + b

Pentru a = 0 si b = 7 (versiunea utilizată de către Bitcoin), arată cam așa:

1

Curbele eliptice au proprietăți utile. De exemplu, o linie non-verticală intersectată la două puncte non-tangente la curbă va intersecta întotdeauna un al treilea punct de pe curbă. O proprietate este aceea că o tangentă linie non-verticală a curbei la un moment dat va intersecta exact un alt punct de pe curbă.

Putem folosi aceste proprietăți pentru a defini două operațiuni: punct de adunare și punct de dublare.

Punct plus, P + Q = R, este definit ca reflectarea prin axa x a punctului de intersecție al treilea R pe o linie care include P și Q. Este cel mai ușor de înțeles acest lucru, folosind o diagramă:

2

 

În mod similar, punctul de dublare, P + P = R este definit prin găsirea liniei tangentă de la punctul dublat, P, și luând reflecție prin axa x a punctului de intersecție R pe curba pentru a obține R. Iată un exemplu cum ar arăta:

3

Împreună, aceste două operații sunt utilizate pentru multiplicarea scalară, R = un P, definit prin adăugarea punctului P la sine de câteva ori. De exemplu:

R = 7P
R = P + (P + (P + (P + (P + (P + P)))))

Procesul de multiplicare scalară este în mod normal simplificat prin utilizarea unei combinații de adăugare de punct și operațiuni cu virgulă dublate. De exemplu:

R = 7P
R = P + 6P
R = P + 2 (3P)
R = P + 2 (P + 2P)

Aici, 7P a fost defalcat în două etape de dublare de puncte și două etape de punct de adiție.

Corpuri finite

Un domeniu finit, în contextul ECDSA, poate fi considerat ca o serie predefinită de numere pozitive în care fiecare calcul trebuie să cadă. Orice număr în afara acestui interval „înconjoară”, astfel încât să se încadreze în interval.

Cel mai simplu mod de a te gândi la acest lucru este calcularea resturilor, așa cum este reprezentat de modul operatorul (mod). De exemplu, 9/7 dă 1 cu un rest de 2:

9 mod 7 = 2

Aici domeniul nostru finit este modul 7, și toate operațiile de mod peste acest domeniu obțin un rezultat care se încadrează într-un interval de la 0 la 6.

Punerea împreună

ECDSA utilizează curbe eliptice în contextul unui câmp finit, care schimbă foarte mult aspectul lor, dar nu ecuațiile lor subiacente sau proprietăți speciale. Aceeași ecuație reprezentată grafic de mai sus, într-un domeniu finit de modul 67, arată astfel:

4

Acum este un set de puncte, în care toate valorile x și y sunt numere întregi cuprinse între 0 și 66, Rețineți că „curba” păstrează încă o simetrie orizontală.

Punctul plus și dublarea sunt acum ușor diferite de cum se vede. Liniile trase pe acest grafic se vor încheia în jurul direcțiilor orizontale și verticale, la fel ca într-un joc de asteroizi, menținând aceași pantă. Deci, adăugând punctele (2, 22) și (6, 25), arată astfel:

5

Al treilea punct de intersecție este (47, 39) și punctul său de reflexie este (47, 28).

Înapoi la ECDSA și Bitcoin

Un protocol, precum Bitcoin, selectează un set de parametri de curbe eliptice și a reprezentării sale pe domeniul finit, care este fixat pentru toți utilizatorii de protocol. Parametrii conțin ecuația folosită, prim modul de teren, și un punct de bază care cade pe curbă. Ordinea de punctul de bază, care nu este în mod independent, dar este o funcție de alți parametri, poate fi gândită ca grafic de câte ori punctele pot fi adăugate la sine până panta sa este infinită sau o linie verticală. Punctul de bază este selectat astfel încât ordinea este un număr mare prim.

Bitcoin folosește un număr foarte mare în punctul său de bază, prim modul și ordine. De fapt, toate aplicațiile practice ale ECDSA utilizează valori enorme.Securitatea algoritmului se bazează pe aceste valori fiind mari, și, prin urmare, este imposibilă forța brută sau ingineria inversă.

În cazul Bitcoin:

Ecuație curbe eliptice: y2 = x3 + 7

Prim modul = 2256 – 232 – 29 – 28 – 27 – 26 – 24 – 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

Punct de bază = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Ordine = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Cine a ales aceste numere, și de ce? O mare parte din cercetare și o valoare justă de intrigi înconjoară selectarea parametrilor corespunzătoare. La urma urmei, un număr mare, aparent aleator ar putea ascunde o metodă backdoor de a reconstrui cheia privată. Pe scurt, această realizare specială sub numele de secp256k1, face parte dintr-o familie de soluții de curbe eliptice peste corpuri finite propuse pentru a fi utilizate în criptografie.

Cheile private și chei publice

Cu aceste formalități suntem acum în măsură să înțelegem cheile publice și private și modul în care acestea sunt legate. În ECDSA, cheia privată este un număr imprevizibil ales între 1 și ordinea. Cheia publică este derivată din cheia privată de multiplicare scalară a punctului de bază cu un număr de ori egal cu valoarea cheii private. Exprimat ca o ecuație:

cheie publică = cheie privată * punct de bază

Acest lucru arată că numărul maxim posibil de chei private (și, astfel, adrese Bitcoin) este egal cu ordinul.

Într-un domeniu continuu am putea trasa linia tangentă și identifica cheia publică pe grafic, dar există unele ecuații care realizează același lucru, în contextul de corpuri finite. Punctul plus de p + q pentru a găsi r este definit înțelept pe componente, după cum urmează:

c = (QY – PY) / (qx – px)
rx = C2 – px – QX
Ry = c (PX – RX) – py

Și punct dublare p pentru a găsi r este următorul:

c = (3px2 + a) / 2PY
rx = c2 – 2px
Ry = c (PX – RX) – py

În practică, calcului cheii publice este defalcat într-un număr de operațiuni cu punct de dublare și punct de adiție pornind de la punctul de bază.

Uitându-ne în urmă la numerele mici, pentru a obține o intuiție cu privire la modul în care sunt construite și utilizate în semnarea și verificarea cheilor. Parametrii pe care îi vom folosi sunt:

Ecuația: y2 = x3 + 7 (cum s-ar spune, a = 0 si b = 7)
Prim Modul: 67
Punctul de bază: (2, 22)
Comanda: 79
Cheie privată: 2

În primul rând, haideți să găsim cheia publică. Din moment ce ne-am ales cel mai simplu posibil cheia privată cu valoare = 2, va fi nevoie de doar un singur punct de dublare de funcționare din punctul de bază. Calculul arată astfel:

c = (3 * 22 + 0) / (2 * 22) mod 67
c = (3 * 4) / (44) mod 67
c = 12/44 mod 67

Aici trebuie să ne oprim pentru un pic de prestidigitație de mână: cum vom efectua divizia în cadrul unui câmp finit, în cazul în care rezultatul trebuie să fie întotdeauna un număr întreg? Trebuie să se înmulțeacă cu inversul. În cazul de față, va trebui să ai încredere în noi pentru momentul în care:

44-1 = 32

Mutarea dreaptă de-a lungul:

c = 12 * 32 mod 67
c = 384 mod 67
c = 49

rx = (492-2 * 2) mod 67
rx = (2401-4) mod 67
rx = 2,397 mod 67
rx = 52

riu = (49 * (2-52) – 22) mod 67
riu = (49 * (-50) – 22) mod 67
riu = (-2450 – 22) mod 67
riu = -2472 mod 67
ry = 7

math-behind-bitcoin-630x376

Semnătura noastră este perechea (r, s) = (62, 47).

Ca și în cazul cheilor private și publice, această semnătură este în mod normal reprezentată de un șir hexazecimal.

Verificarea semnăturii cu cheia publică

Avem acum câteva date și o semnătură pentru date. O a treia parte care are cheia noastră publică poate primi date și semnătura noastră ca să verifice că suntem expeditorii. Să vedem cum funcționează acest lucru.

Cu Q fiind cheia publică și celelalte variabile definite ca mai înainte, etapele de verificare a semnăturii sunt următoarele:

Asigurați-vă că r și s sunt între 1 și n – 1.
Calculați w = s-1 mod n
Calculați u = z * w n mod
Calculați v = r * w mod n
Calculați punctul (x, y) = S + VQ
Verificați că r = x mod n. Semnătura nu este valabilă în cazul în care acesta nu este.
Variabile noastre, încă o dată:
z = 17 (date)
(r, s) = (62, 47) (semnătură)
n = 79 (pentru)
G = (2, 22), (punct de bază)
Q = (52, 7) (cheia publică)

Asigurați-vă că r și s sunt între 1 – 1
r: 1 <= 62 <79
s: 1 <= 47 <79

Calculați w:
w = s-1 mod n
w = 47-1 mod 79
w = 37

Calculați u:
u = ZW mod n
u = 17 * 37 mod 79
u = 629 mod 79
u = 76

Calculați v:
v = RW n mod
v = 62 * 37 mod 79
v = 2,294 mod 79
v = 3

Calculați punctul (x, y):
(x, y) = ug + VQ

Descompunem dublarea punctului și adăugarea în UG și VQ separat.

S = 76g
S = 2 (38G)
S = 2 (2 (19G))
S = 2 (2 (G + 18G))
S = 2 (2 (P + 2 (9G)))
S = 2 (2 (P + 2 (G + 8G)))
S = 2 (2 (P + 2 (P + 2 (4G))))
S = 2 (2 (P + 2 (P + 2 (2 (2G)))))

Prin utilizarea trucului de grupare vom reduce 75 de operații de adunare succesive la doar șase operațiuni de la punctul de dublare și două operațiuni de punct plus.
Lucrând de la interior spre exterior:

S = 2 (2 (P + 2 (P + 2 (2 (2 (2, 22))))))
S = 2 (2 (P + 2 (P + 2 (2 (52, 7)))))
S = 2 (2 (P + 2 (P + 2 (25, 17))))
S = 2 (2 (P + 2 ((2, 22) + (21, 42))))
S = 2 (2 (P + 2 (13, 44)))
pG = 2 (2 ((2, 22) + (66, 26)))
S = 2 (2 (38, 26))
pG = 2 (27, 40)
pG = (62, 4)

Și acum pentru VQ:

VQ = T3
VQ = Q + T2
VQ = Q + 2 (52, 7)
VQ = (52, 7) + (25, 17)
VQ = (11, 20)

Punându-le împreună:

(x, y) = ug + VQ
(x, y) = (62, 4) + (11, 20)
(x, y) = (62, 63)

Pentru etapa finală.

Verificați că r = x mod n
r = x mod n
62 = 62 mod 79
62 = 62

Semnătura este validă!

Concluzie

Pentru cei dintre voi care au văzut toate ecuațiile și au sărit la partea de jos, ce am învățat?

Am dezvoltat intuiție în relația matematică profundă care există între cheile publice și private. Am văzut cum, chiar și în cele mai simple exemple de matematică din spatele semnăturii și verificării rapide se complică și putem aprecia complexitatea enormă pe care trebuie să o implicăm atunci când parametrii implicați sunt numere de 256 de biți. Am văzut modul în care aplicarea inteligentă a celor mai simple proceduri matematice pot crea într-o direcție funcțiile „trapă” necesare pentru a păstra asimetria informațiilor care defineșc dreptul de proprietate asupra Bitcoin. Avem încrederea dobândită în soliditatea sistemului, cu condiția ca să protejăm cu atenție cunoștințele de chei private.

Cu alte cuvinte, acesta este motivul pentru care se spune de obicei că Bitcoin este „susținută de matematică„.

Sursa: coindesk

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *

Articole recente

Trade – Activarea Contului

Aparitii TV