Math Behind Bitcoin | BS.democraziakmzero.org

Math Behind Bitcoin

Math Behind Bitcoin

Eric Rykwalder je softverski inženjer i jedan od Chain.com osnivača. Evo, on daje pregled matematičke osnove protokola Bitcoin.

Jedan od razloga Bitcoin može biti zbunjujuće za početnike je da je tehnologija iza njega redefiniše pojam vlasništva.

Da imate nešto u tradicionalnom smislu, bilo da je to kuća ili sumu novca, znači ili da lično starateljstvo nad stvari ili davanje pritvor pouzdani entitet kao što je banka.

Sa bitcoin slučaj je drugačiji. Bitcoin sami se ne čuvaju ni centralno ili lokalno i tako ni jedan entitet je njihov čuvar. Oni postoje kao evidencija o distribuirani knjizi pod nazivom blok lanac, kopije koje se dijele volonter mreže povezanih računala. Na "svoje" Bitcoin jednostavno znači imati sposobnost da prenese kontrolu nad nekom drugom stvaranjem rekord transfera u bloku lanca. Ono što daje tu sposobnost? Pristup ECDSAprivate i javni ključ par. Što to znači i kako to siguran Bitcoin?

Hajde da pogledamo ispod haube.

ECDSAis kratak za eliptičke Curve Digital Signature Algorithm. To je proces koji koristi eliptične curveand konačnog polja za "znak" podatke na takav način da treće strane mogu potvrditi autentičnost potpisa, dok je potpisnik zadržava isključivo sposobnost stvaranja potpisa. Uz Bitcoin, podaci koji se potpisuje je transakcija koja prenosi vlasništvo.

ECDSA ima odvojene procedure za potpisivanje i verifikacije. Svaki postupak je algoritam koji se sastoji od nekoliko aritmetičkih operacija. Algoritam potpisivanje koristi privatni ključ, a proces verifikacije koristi javnog ključa. Mi ćemo pokazati primjer kasnije.

Ali prvo, ubrzani kurs na eliptičkih krivulja i konačnih polja.

Eliptičkih krivulja

Eliptičkoj kriva je algebarski predstavljeni kao jednadžba oblika:

Y2 = x3 + ax + b

Za = 0and b = 7 (verzija koristi bitcoin), to izgleda ovako:

Eliptičnim krivuljama imaju korisna svojstva. Na primjer, ne-vertikalna linija sijeku dva non-tangenta tačke na krivoj će uvijek seku treće tačke na krivoj. A dalje to što je ne-vertikalna linija tangente na krivu u jednom trenutku će se presijecaju upravo jednu drugu stvar na krivoj.

Možemo koristiti ove osobine za definiranje dvije operacije: tačka toga i tačka dupliranje.

Point toga, P + Q = R, je definiran kao odraz kroz x-osi trećeg graniče brojevi R'on liniju koja uključuje Pand P: Najlakše je shvatiti ovu koristeći dijagram:

Slično tome, tačka udvostručenje, P + P = Ris definisano pronalaženje linija tangenta do tačke da se udvostručio, P, i uzimajući odraz kroz x-osi se ukrštaju tačke R'on krive da se R. Evo primjer šta to bi izgledalo ovako:

Zajedno, ove dvije operacije se koriste za skalarno množenje, R = a P, definiran dodavanjem stvar sama Pto atimes. Na primjer:

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

Proces skalarnog množenja je normalno pojednostavljen kombinacijom toga tačke i operacija tačka udvostručuje. Na primjer:

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

Evo, 7Phas je oborio u dva koraka tačke udvostručenje i dva koraka tačke toga.

Konačna polja

A konačnom polju, u kontekstu ECDSA, može se shvatiti kao predefinisanih niz pozitivnih brojeva u kojoj svaki proračun mora pasti. Bilo koji broj izvan ovog opsega "obavija" kako bi pasti u rasponu.

Najjednostavniji način da se razmišlja o tome izračunava ostataka, koje predstavljaju modula (mod) operatera. Na primjer, 9/7 daje sa 1 ostatak 2:

9 mod 7 = 2

Evo naš konačni polje je modulo 7, a sve mod operacije nad ovom terenu dati rezultat pada u rasponu od 0 do 6.

Stavljajući zajedno

ECDSA koristi eliptičkih krivulja u kontekstu konačnog polja, što uvelike mijenja njihov izgled, ali ne i njihove osnovne jednadžbe ili posebna svojstva. Ista jednačina nacrtane gore, u konačnom polju modulu 67, izgleda ovako:

Sada je skup tačaka, u kojoj su svi xand yvalues ​​su cijeli brojevi između 0 i 66. Imajte na umu da "kriva" i dalje zadržava svoju horizontalna simetrija.

Point toga i udvostručenje su sada malo drugačije vizuelno. Linijama na ovom grafikonu će završiti oko horizontalne i vertikalne pravce, baš kao u igri Asteroids, održavajući istu padinu. Dakle, dodajući poena (2, 22) i (6, 25) izgleda ovako:

Treći preseka Poenta je (47, 39) i njen odraz tačka (47, 28).

Povratak na ECDSA i Bitcoin

Protokol, kao što su Bitcoin bira skup parametara za eliptičke krivulje i njenog konačnog predstavljanja polje koje je fiksna za sve korisnike protokola. Parametri uključuju equationused, premijer moduloof terenu i bazu pointthat pada na krivu. Je orderof baze tačka, koja nije nezavisno izabrana ali je u funkciji drugih parametara, može se smatrati grafički kao broj puta tačke može se dodati da se do njenog nagib je beskonačan, ili vertikalnu liniju. Osnovne tačke je izabran tako da je nalog veliki prost broj.

Bitcoin koristi vrlo veliki broj za svoju bazu trenutku, premijer modulu, i red. U stvari, sve praktične primjene ECDSA koriste ogromne vrijednosti. Sigurnost algoritma se oslanja na te vrijednosti biti velika, a samim tim i nepraktično brute force ili obrnuti inženjering.

U slučaju Bitcoin:

Eliptične krivulje jednadžba: y2 = x3 + 7

Premijer modulu = 2256- 232- 29- 28- 27- 26- 24- 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

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

Bi = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Koji su izabrali ove brojke, i zašto? Veliki dio istraživanja, a dosta intriga, okružuje odabir odgovarajuće parametre. Uostalom, veliki, naizgled slučajni broj bi mogao sakriti backdoor metoda rekonstrukcije privatnog ključa. Ukratko, ovaj realizacija ide po imenu secp256k1 i dio je porodice eliptične rješenja krivulje nad konačnim poljima predloženi za upotrebu u kriptografiji.

Privatne ključeve i javne ključeve

Sa ovim formalnosti se s puta, sada smo u poziciji da razumiju privatne i javne ključeve i kako su povezani. Evo ga ukratko: U ECDSA, privatni ključ je nepredvidivo izabrani broj između 1 i poredak. Javni ključ je izvedena iz privatnog ključa po skalarno množenje baze ukazuju nekoliko puta jednaka vrijednost privatnog ključa. Izraženo kao jednadžba:

Javni ključ = privatnog ključa * osnovne tačke

Ovo pokazuje da je maksimalni mogući broj privatnih ključeva (a time i Bitcoin adresa) jednak je poredak.

U kontinuiranom polje bismo mogli nacrtati tangenta i ukaže na javni ključ na grafikonu, ali postoje neke equationsthat ostvariti istu stvar u kontekstu konačnih polja. Point dodatak p + qto pronađi RIS definiran komponenta-mudar kako slijedi:

C = (qy - py) / (QX - px)
ry = c (px - RX) - py

I tačka udvostručenje pto find r je kako slijedi:

C = (3px2 + a) / 2py
ry = c (px - RX) - py

U praksi, proračun javnog ključa je oborio na veći broj tačke udvostručenje i tačka Osim operacije, počevši od osnovne tačke.

Hajde da pokrenete poleđini primjer koverti koristeći mali broj, da se intuicija o tome kako ključevi se grade i koriste se u potpisivanje i verifikacija. Parametri ćemo koristiti su:

Jednadžba: y2 = x3 + 7 (što će reći, a = 0 i b = 7)
privatnog ključa: 2

Prvo, hajde da javni ključ. S obzirom da smo odabrali najjednostavniji mogući privatni ključ sa vrijednosti = 2, to će zahtijevati samo jedan poen udvostručenje rad iz baze tačke. Obračun izgleda ovako:

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

Ovdje moramo pauzirati malo majstorija-of-ruke: Kako vršimo podjela u kontekstu konačnog polja, gdje je rezultat uvijek mora biti cijeli broj? Moramo pomnožiti inverznu, koji prostor nam ne dozvoljava da se definiše ovdje (mislimo da ovde i hereif zainteresirani). U konkretnom slučaju, morat ćete nam vjerovati na trenutak da:

44-1 = 32

Moving desno uz:

C = 12 * 32 mod 67
c = 49

Rx = (492- 2 * 2) mod 67
rx = 52

Ry = (49 * (2 - 52) - 22) mod 67
ry = 7

Tako naš javni ključ odgovara točki (52, 7). Sve to rade za privatni ključ od 2!

Ova operacija - idući od privatnog do javnog ključa - je računski lako u odnosu na pokušavajući da unazad zaključiti privatnog ključa iz javnog ključa, koji dok je teoretski moguće je računski neizvodljivo zbog velikog parametre koji se koriste u stvarnom eliptičnih kriptografiji.

Dakle, ide iz privatnog ključ javnog ključa je po dizajnu u jednom pravcu putovanje.

Kao i kod privatnog ključa, javnog ključa obično predstavlja heksadecimalni niz. Ali čekajte, kako ćemo dobiti od točke na avion, opisao dva broja, na jedan broj? U nekomprimovani javni ključ dva 256-bitna broja predstavljaju xand y koordinate se samo zaglavila u jednom dugom nizu. Mi također može iskoristiti simetrije eliptične krivulje proizvesti komprimirani javni ključ, zadržavajući samo x vrijednosti i uz napomenu čega je polovina krive poenta je na. Iz ove parcijalne informacije možemo oporaviti i koordinate.

Potpisivanje podataka sa privatnim ključem

Sada kada imamo privatni i javni ključ para, hajde da potpiše neke podatke!

Podaci mogu biti bilo koje dužine. Uobičajena Prvi korak je da hash podatke za stvoriti niz koji sadrži isti broj bita (256) kao poredak krive. Evo, radi jednostavnosti, mi ćemo preskočiti korak heširanja i samo potpisati sirove podatke z. Mi ćemo nazvati gthe polazna tačka, nIzmene reda i dthe privatni ključ. Recept za potpisivanje je kako slijedi:

  1. Odabrati neki cijeli broj k između 1 i n - 1.
  2. Izračunajte točki (x, y) = k * G, koristeći skalarno množenje.
  3. Nađi r = x mod n. Ako je r = 0, vratite se na korak 1.
  4. Nađi e = (z + r * d) / k mod n. Ako e = 0, vratite se na korak 1.
  5. Potpis je par (r, s)

Kao podsjetnik, u koraku 4, ako su brojevi rezultirati frakcija (koja je u stvarnom životu oni gotovo uvijek će), brojilac treba pomnožen inverznu nazivnika. U koraku 1, važno je da se čvor može ponoviti u različitim potpisa i da ne bi bilo lako pogoditi od strane treće osobe. To je, kshould biti ili slučajni ili stvorenim deterministički sredstva koja se drže u tajnosti od trećih strana. U suprotnom bi bilo moguće izvući privatni ključ iz koraka 4, jer e, z, r, kand Nare sve poznate. Možete pročitati o prošlosti iskoristi ovog tipa ovdje.

Uzmimo naše podatke da je broj 17, i slijedite recept. Naša varijable:

Z = 17 (podataka)
d = 2 (privatni ključ)

  1. Pick slučajni broj:

K = rand (1, n - 1)
k = 3 (?! je ovo stvarno slučajan OK imaš nas, ali to će učiniti naš primjer jednostavnije)

  1. Izračunajte stvar. To se radi na isti način kao i utvrđivanju javnog ključa, ali zbog jasnoće hajde da izostavite aritmetika za dodatak point i point dupliranje.

(x, y) = 3G
y = 63

  1. Nađi r:

R = x mod n
r = 62

  1. Nađi s:

S = (z + d r *) / k mod n
s = 47

Imajte na umu da smo iznad mogli podijeliti sa 3 jer je rezultat bio cijeli broj. U stvarnom životu slučajevima bi koristili inverzna k (kao i do sada, mi smo skrivene neke krvave detalje računanjem to drugdje):

S = (z + d r *) / k mod n
s = 47

  1. Naša potpis je par (r, s) = (62, 47).

Kao i kod privatne i javne ključeve, ovaj potpis je obično predstavlja heksadecimalni niz.

Provjeru potpisa sa javnim ključem

Sada imamo neke podatke i potpis za te podatke. A treća strana koja ima naš javni ključ može primati naše podatke i potpis, i provjerite da smo pošiljalaca. Da vidimo kako to radi.

Sa Qbeing javni ključ i druge varijable definirane kao i ranije, koraci za provjeru potpisa su kako slijedi:

  1. Provjerite da r i s su između 1 i n - 1.
  2. Izračunajte w = s-1 mod n
  3. Izračunati u = z * w mod n
  4. Izračunajte v = r * w mod n
  5. Izračunajte točki (x, y) = uG + VQ
  6. Proverite da li je r = x mod n. Potpis je nevažeći ako nije.

Zašto ove korake radi? Mi preskakanje dokaz, ali možete pročitati detalje. Hajde da slijedite recept i vidjeti kako se to radi. Naša varijable, još jednom:

Z = 17 (podataka)
Q = (52, 7) (javni ključ)

  1. Provjerite da li rand Sare između 1 i n 1. Provjerite i provjeriti.

R: 1 <= 62 <79
s: 1 <= 47 <79

  1. Izračunajte w:

W = s-1 mod n
w = 37

  1. Izračunajte U:

U = ZW mod n
U = 76

  1. Izračunajte v:

V = rw mod n
v = 3

  1. Izračunajte točki (x, y):

(X, y) = uG + VQ

Hajde da razbijaju udvostručenje tačke i dodatak u uGand vQseparately.

UG = 76G
uG = 2 (2 (P + 2 (P + 2 (2 (2G)))))

Sedite na trenutak da shvate da pomoću trik grupisanje smo smanjili 75 uzastopnih Osim poslova na samo šest operacija tačke udvostručenje i dvije operacije tačke toga. Ovi trikovi će doći u ruci kada brojeve dobiti zaista veliki.

Rade naš način iznutra:

UG = 2 (2 (P + 2 (P + 2 (2 (2 (2, 22))))))
uG = (62, 4)

A sada VQ:

VQ = 3Q
VQ = (11, 20)

Stavljajući ih zajedno:

(x, y) = uG + VQ
(x, y) = (62, 63)

Jasno korak 5 je najveći dio posla. Za završni korak,

  1. Proverite da li je r = x mod n

R = x mod n
62 = 62

Naša potpis je važeća!

Zaključak

Za one od vas koji su vidjeli sve jednadžbe i preskočili na dno, što smo upravo naučili?

Razvili smo neke intuicije o dubokim matematički odnos koji postoji između javnog i privatnog ključa. Vidjeli smo kako je čak iu najjednostavnijim primjerima matematiku iza potpisa i provjeru brzo zakomplikuje, i možemo cijenimo ogroman složenosti koji moraju biti uključeni kada su parametri koji su uključeni 256-bitne brojeve. Vidjeli smo kako je pametan primjena od najjednostavnijih matematičkih procedure mogu stvoriti u jednom pravcu "zamka vrata" funkcije neophodne za očuvanje asimetrija informacija koja definira vlasništvo nad Bitcoin. I imamo novo samopouzdanje u robusnost sistema, pod uvjetom da pažljivo čuvaju znanje naših privatnih ključeva.

Drugim riječima, to je razlog zašto se često rekao da je Bitcoin je "podržavaju matematike".

Ako je visio kroz komplikovan bita, nadamo se da ti je dao povjerenje da se sljedeći korak i isprobajte matematike na svoju ruku (a modularne aritmetike kalkulator čini konačnom polju matematike mnogo lakše). Otkrili smo da ide kroz korake potpisivanja i verifikaciju podataka ručno daje dublje razumijevanje kriptografije koji omogućava jedinstven oblik Bitcoin je vlasništva.

Ovaj članak je ovdje ponovo objavljen uz dozvolu autora. Originalno objavljeno na Chain.com. Autor daje posebnu zahvalnost Steven Phelps za pomoć sa ovaj članak.

Bitcoin ProtocolCryptography

Povezane vijesti


Post Bitcoin

Defcon hakeri pucaju fizički bitko Casascius novčića

Post Bitcoin

Bitkoin u naslovima: Politički spin i kidnapovani podaci

Post Bitcoin

KPMG: Bitcoin predstavlja pretnju i mogućnost za banke na malo

Post Bitcoin

Bitcoin Ponzi Schemer nagoveštava poslove sa CEO Gox

Post Bitcoin

Bitcoin 2018 će povući 1.000, a Winklevii, u San Jose ovog vikenda

Post Bitcoin

Priprema za povlačenje? Bitcoin cijena koči ispod 6.000 dolara

Post Bitcoin

Severnoamerička bitkoinska konferencija koja će udariti Miami 25. januara

Post Bitcoin

Korisnički fondovi LocalBitcoins ukrašeni nakon Hack klijenta

Post Bitcoin

Bitcoin Developers Pen otvorio pismo o skalabilnosti mreže

Post Bitcoin

Da razumem Bitcoin, studirao sam Karla Marxa

Post Bitcoin

Kontroverzni italijanski novinski il Giornale sada prihvata Bitcoin

Post Bitcoin

Spisak svedoka otkriven za Njujork-ovu virtuelnu valutu