The Math Behind Bitcoin | CAT.DemocraziakmZero.org

The Math Behind Bitcoin

The Math Behind Bitcoin

Eric Rykwalder és un enginyer de programari i un dels fundadors de Chain.com. A continuació, s'ofereix una visió general dels fonaments matemàtics del protocol de Bitcoin.

Una de les raons Bitcoin pot ser confús per a novells és que la tecnologia darrere d'ella redefineix el concepte de propietat.

Posseir alguna cosa en el sentit tradicional, ja sigui una casa o una suma de diners, vol dir o bé que tingui la custòdia personal de la cosa o la concessió de la custòdia a una entitat de confiança, com un banc.

Amb Bitcoin el cas és diferent. Bitcoins mateixos no s'emmagatzemen de forma centralitzada o local i per tant cap entitat és la seva custodi. Hi com registres en un llibre de comptabilitat distribuït s'anomena cadena de bloc, còpies dels quals són compartits per una xarxa de voluntaris d'ordinadors connectats. "Posseir" 1 bitcoin simplement vol dir que té la capacitat de transferir el control del mateix a una altra persona mitjançant la creació d'un registre de la transferència en el bloc de la cadena. El que atorga aquesta capacitat? L'accés a un ECDSAprivate i parell de claus pública. Què significa això i de quina manera segura Bitcoin?

Anem a fer una ullada sota el capó.

ECDSAis abreviatura de Signatura Digital Algorisme de corba el·líptica. És un procés que utilitza un curveand el·líptica un camp finit de dades "senyal" de tal manera que terceres persones poden verificar l'autenticitat de la signatura, mentre que el signant conserva la capacitat exclusiva per crear la signatura. Amb bitcoin, les dades que es va signar és la transacció que transfereix la propietat.

ECDSA té procediments separats per signatura i verificació. Cada procediment és un algorisme composta d'unes poques operacions aritmètiques. L'algoritme de signatura fa ús de la clau privada, i el procés de verificació fa ús de la clau pública. Anem a mostrar un exemple d'això més endavant.

Però primer, un curs ràpid en corbes el·líptiques i camps finits.

Les corbes el·líptiques

Una corba el·líptica es representa algebraicament com una equació de la forma:

Y2 = x3 + ax + b

Per a = 0º i b = 7 (la versió utilitzada per bitcoin), que es veu així:

Les corbes el·líptiques tenen propietats útils. Per exemple, una línia no vertical que intersecta dos punts no tangents de la corba sempre es creuarà amb un tercer punt a la corba. Una propietat addicional és que una línia tangent no vertical a la corba en un punt es creuarà precisament un altre punt de la corba.

Podem utilitzar aquestes propietats per definir dues operacions: suma de punts i la duplicació de punt.

A més Point, P + Q = R, es defineix com la reflexió a través de l'eix X de la tercera punt d'intersecció R'on una línia que inclou PAND Q. És més fàcil d'entendre això usant un diagrama de:

Així mateix, el punt de duplicació, P + P = Ris definida per la recerca de la línia tangent al punt de duplicar-se, P, i tenint reflexió a través de l'eix x del punt d'intersecció R'on la corba per obtenir R. Aquí està un exemple de el que es veuria així:

Juntes, aquestes dues operacions es fan servir per a la multiplicació escalar, R = a P, que es defineix mitjançant l'addició del punt Port sí atimes. Per exemple:

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

El procés de multiplicació escalar és normalment simplifica mitjançant l'ús d'una combinació d'addició punt i operacions de punt de doblegar. Per exemple:

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

Aquí, 7Phas s'ha dividit en dos passos de punts de duplicar i dos passos punt d'addició.

Camps finits

Un camp finit, en el context de ECDSA, pot ser pensat com un rang predefinit de nombres positius dins del qual ha de caure cada càlcul. Qualsevol nombre fora d'aquest rang "en bucle" de manera que caigui dins de la gamma.

La manera més simple de pensar en això és el càlcul de residus, representat per l'operador de mòdul (MOD). Per exemple, 9/7 dóna 1 amb una resta de 2:

9 mod 7 = 2

Aquí el nostre cos finit és mòdul 7, i totes les operacions mod més d'aquest camp donen com a resultat una caiguda dins d'un rang de 0 a 6.

Ajuntant tot

ECDSA utilitza les corbes el·líptiques en el context d'un camp finit, que canvia molt la seva aparença, però no les seves equacions subjacents o propietats especials. La mateixa equació traçada anteriorment, en un camp finit de mòdul 67, es veu així:

És ara un conjunt de punts, en la qual tots els yvalues ​​XAND són nombres enters entre 0 i 66. Recordeu que la "corba" encara conserva la seva simetria horitzontal.

A més Point i duplicació ara són lleugerament diferents visualment. Les línies dibuixades en aquest gràfic s'embolica al voltant de les adreces horitzontal i vertical, igual que en un joc d'asteroides, mantenint el mateix pendent. Per afegir punts (2, 22) i (6, 25) té el següent aspecte:

El tercer punt d'intersecció és (47, 39) i el seu punt de reflexió és (47, 28).

Tornar a ECDSA i bitcoin

Un protocol tal com bitcoin selecciona un conjunt de paràmetres per a la corba el·líptica i la seva representació camp finit que es fixa per a tots els usuaris del protocol. Els paràmetres inclouen la equationused, el primer moduloof al camp, i una base pointthat dins de la corba. El orderof el punt de base, que no es selecciona independentment però és una funció dels altres paràmetres, es pot pensar gràficament com el nombre de vegades que el punt es pot afegir a si mateix fins que el seu pendent és infinita, o una línia vertical. El punt de base es selecciona de manera que l'ordre és un nombre primer gran.

Bitcoin utilitza un nombre molt gran de la seva punt base, mòdul primer i l'ordre. De fet, totes les aplicacions pràctiques de ECDSA utilitzen valors enormes. La seguretat de l'algorisme es basa en aquests valors és gran, i per tant poc pràctic a la força bruta o enginyeria inversa.

En el cas de Bitcoin:

Equació de la corba el·líptica: y 2 = x3 + 7

El primer mòdul = 2256- 232- 29- 28- 27- 26- 24- 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

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

Order = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Qui va triar a aquests números, i per què? Una gran quantitat d'investigació, i una bona quantitat d'intriga, envolta la selecció dels paràmetres adequats. Després de tot, un nombre gran, aparentment a l'atzar podria amagar un mètode de porta del darrere de reconstruir la clau privada. En resum, aquesta realització particular, es coneix amb el nom de secp256k1 i és part d'una família de solucions de corbes el·líptiques sobre camps finits proposats per al seu ús en la criptografia.

Les claus privades i les claus públiques

Amb aquests tràmits fora del camí, ara estem en condicions de comprendre les claus privades i públiques i com es relacionen. Aquí és en poques paraules: En ECDSA, la clau privada és un nombre impredictible elegit entre l'1 i l'ordre. La clau pública es deriva de la clau privada per la multiplicació escalar de la base de punt un nombre de vegades igual al valor de la clau privada. Expressat com una equació:

Clau pública = clau privada * punt base

Això demostra que el màxim nombre possible de claus (i per tant les direccions bitcoin) és igual a l'ordre.

En un camp continu podríem representar gràficament la línia tangent i localitzar la clau pública en el gràfic, però hi ha equationsthat aconseguir el mateix en el context dels cossos finits. A més punt de p + q per ris troballa defineix component a component de la següent manera:

C = (QY - pi) / (qx - px)
ri = c (píxels - RX) - p i

I el punt de duplicació de la presa de força troballa r és el següent:

C = (3px2 + a) / 2py
ri = C (px - rx) - p i

A la pràctica, el càlcul de la clau pública es divideix en un nombre d'operacions de punt de duplicació i d'addició de punt de partida des del punt base.

Anem a executar una part posterior de l'envoltant exemple usant petites quantitats, per obtenir una intuïció sobre com les tecles estan construïts i utilitzats en la signatura i verificació. Els paràmetres que utilitzarem són:

Equació: y 2 = x3 + 7 (és a dir, a = 0 i b = 7)
de clau privada: 2

En primer lloc, trobarem la clau pública. Ja que hem seleccionat la clau privada més simple possible amb el valor = 2, només es requereix un únic punt de duplicar l'operació des del punt base. El càlcul és el següent:

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

Aquí hem de fer una pausa per una mica de prestidigitació de la mà: com fer una divisió en el context d'un camp finit, en el que el resultat ha de ser sempre un nombre enter? Hem de multiplicar per l'invers, que l'espai no ens permet definir aquí (ens referim al fet que hereand aquísi interessats). En el cas que ens ocupa, haurà de confiar en nosaltres de moment que:

44-1 = 32

La dreta mòbil endavant:

C = 12 * 32 mod 67
c = 49

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

Ri = (49 * (2 - 52) - 22) mod 67
ri = 7

La nostra clau pública correspon així al punt (52, 7). Tot aquest treball per a una clau privada de 2!

Aquesta operació - en passar de privat a la clau pública - és computacionalment fàcil en comparació amb tractar de treballar cap enrere per deduir la clau privada de la clau pública, que si bé és teòricament possible és computacionalment impossible a causa de les grans paràmetres utilitzats en la criptografia el·líptica real.

Per tant, en passar de la clau privada de la clau pública és per disseny d'un viatge d'anada.

Igual que amb la clau privada, la clau pública sol representar-se amb una cadena hexadecimal. Però espera, com podem arribar a un punt en un pla, descrit per dos nombres, a un sol nombre? En una clau pública sense comprimir els dos nombres de 256 bits que representen les coordenades i XAND són simplement enganxats entre si en una cadena llarga. També podem aprofitar la simetria de la corba el·líptica per produir una clau pública comprimit, mantenint només el valor de x i prenent nota dels quals la meitat de la corba el punt està encès. A partir d'aquesta informació parcial podem recuperar les dues coordenades.

La signatura de dades amb la clau privada

Ara que tenim un parell de claus pública i privada, anem a signar algunes dades!

Les dades poden ser de qualsevol longitud. El primer pas és usual per discutir les dades per generar un nombre que conté el mateix nombre de bits (256) com l'ordre de la corba. Aquí, en nom de la simplicitat, anem a ometre el pas de hash i només ha de registrar les dades z de cru. Anomenarem gthe punt base, n l'ordre, i dthe clau privada. La recepta de la signatura és la següent:

  1. Trieu algun enter k entre 1 i n - 1.
  2. Calcular el punt (x, y) = k * G, usant multiplicació escalar.
  3. Troba r = x mod n. Si r = 0, tornar al pas 1.
  4. Troba s = (r * d z +) / k mod n. Si s = 0, torni al pas 1.
  5. La signatura és el parell (r, s)

A manera de recordatori, en el pas 4, si els números donen com a resultat una fracció (que a la vida real que gairebé sempre), el numerador s'han de multiplicar per l'invers del denominador. Al pas 1, és important que el nus es repeteix en diferents firmes i que no sigui fàcil d'endevinar per un tercer. És a dir, kshould ser aleatòries o generat mitjançant deterministes que són mantinguts en secret per part de tercers. En cas contrari seria possible extreure la clau privada de l'etapa 4, ja s, z, r, Kand nare tot conegut. Vostè pot llegir sobre un passat explotar d'aquest tipus aquí.

Anem a recollir les nostres dades a ser el número 17, i seguir la recepta. Els nostres variables:

Z = 17 (dades)
d = 2 (clau privada)

  1. Triar un nombre a l'atzar:

K = rand (1, n - 1)
k = 3 (?! És això realment aleatòria bé que ens van donar, però que farà que el nostre exemple més simple)

  1. Calcular el punt. Això es realitza de la mateixa manera que la determinació de la clau pública, però per raons de brevetat anem a ometre l'aritmètica de punt d'addició i duplicació punt.

(X, y) = 3G
i = 63

  1. Troba r:

R = x mod n
r = 62

  1. Troba s:

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

Recordeu que anteriorment hem estat capaços de dividir per 3, ja que el resultat va ser un enter. En els casos de la vida real que utilitzaríem la inversa de k (igual que abans, hem ocultat alguns detalls morbosos de computació en un altre lloc):

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

  1. La nostra signatura és el parell (r, s) = (62, 47).

Igual que amb les claus privades i públiques, aquesta firma sol representar amb una cadena hexadecimal.

Verificació de la signatura amb la clau pública

Ara tenim algunes dades i una signatura perquè les dades. Un tercer que té la nostra clau pública pot rebre els nostres dades i signatura, i verificar que som els remitents. Anem a veure com funciona això.

Amb Qbeing la clau pública i les altres variables definides com abans, els passos per a la verificació d'una signatura són els següents:

  1. Comproveu que r i s són entre 1 i n - 1.
  2. Calcular W = s-1 mod n
  3. Calcula u = z * w n mod
  4. Calcular v = r * w mod n
  5. Calcular el punt (x, y) = gu + VQ
  6. Comproveu que r = x mod n. La signatura no és vàlida si no ho és.

Per què treballen aquests passos? Estem saltant la prova, però es pot llegir els detalls aquí. Seguirem la recepta i veure com funciona. Les nostres variables, un cop més:

Z = 17 (dades)
Q = (52, 7) (clau pública)

  1. Verificar que Sare rand entre 1 i n- 1. Comprovar i verificació.

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

  1. Calcula w:

W = s-1 mod n
w = 37

  1. Calcular u:

U = zw mod n
o = 76

  1. Calcular v:

V = rw mod n
v = 3

  1. Calcular el punt (x, y):

(X, i) = gu + VQ

Anem a trencar la duplicació punt ia més en uGand vQseparately.

UR = 76G
mu g = 2 (2 (G + 2 (G + 2 (2 (2G)))))

Asseure per un moment d'apreciar que en utilitzar el truc agrupació reduïm 75 operacions de suma successives a només sis operacions de punt de duplicació i dues operacions d'addició punt. Aquests trucs serà molt útil quan les xifres són molt grans.

La nostra forma de treball de dins cap a fora:

UR = 2 (2 (G + 2 (G + 2 (2 (2 (2, 22))))))
UR = (62, 4)

I ara per VQ:

VQ = 3T
VQ = (11, 20)

Posar-los junts:

(X, y) = gu + VQ
(x, y) = (62, 63)

Clarament el pas 5 és la major part de la feina. Per a l'etapa final,

  1. Comproveu que r = x mod n

R = x mod n
62 = 62

La nostra signatura és vàlida!

Conclusió

Per a aquells de vosaltres que hagi vist totes les equacions i es va saltar a la part inferior, què hem après sol?

Hem desenvolupat una certa intuïció sobre la relació matemàtica profunda que hi ha entre les claus públiques i privades. Hem vist com fins i tot en els exemples més simples les matemàtiques darrere de les signatures i verificació ràpidament es complica, i podem apreciar l'enorme complexitat que ha de ser involucrat quan els paràmetres que intervenen són nombres de 256 bits. Hem vist com l'aplicació intel·ligent dels procediments matemàtics més simples poden crear les funcions d'un sol sentit de "portes trampa" necessàries per preservar la asimetria de la informació que defineix la propietat d'un bitcoin. I tenim nova confiança en la solidesa del sistema, sempre que fem per protegir acuradament el coneixement de les nostres claus privades.

En altres paraules, és per això que se sol dir que Bitcoin està "recolzat per les matemàtiques".

Si penjat a través dels bits complicats, esperem que li va donar la confiança per donar el següent pas i provar les matemàtiques pel seu compte (una calculadora aritmètica modular fa que les matemàtiques camp finit molt més fàcil). Hem trobat que passar pels passos de signatura i verificació de les dades a mà ofereix una comprensió més profunda de la criptografia que permet de forma única bitcoin de propietat.

En aquest article s'ha tornat a publicar aquí amb permís de l'autor. Publicada originalment en Chain.com. L'autor dóna les gràcies especialment a Steven Phelps per la seva ajuda en aquest article.

Bitcoin ProtocolCryptography

Notícies relacionades


Post Bitcoin

Director General de Blockstream: Bitcoin Creant entorn tòxic per als desenvolupadors

Post Bitcoin

Lactivista pren lenfocament de la vella escola a la promoció de Bitcoin

Post Bitcoin

$ 5,000 en Reach? Bitcoin Falls torna després de colpejar al màxim de 5 setmanes

Post Bitcoin

El preu de Bitcoin cau per sota de 3.500 dòlars, però és un rally de relleu a vista?

Post Bitcoin

La Fundació Bitcoin llança la sèrie Core Development Event

Post Bitcoin

La versió bàsica de Bitcoin 0.9.1 soluciona la vulnerabilitat cardíaca

Post Bitcoin

La febre de lor comença: el dia Bitcoin va acabar el dòlar dels Estats Units

Post Bitcoin

$ 15,000: hi ha límit al rally meteoric de Bitcoin?

Post Bitcoin

Bitcoin en els titulars: més aire calent per a Grècia

Post Bitcoin

El preu de Bitcoin es manté fort entre els informes normatius coreans

Post Bitcoin

Bitcoin Exchange OKCoin llança dipòsits i retirs de USD

Post Bitcoin

Bitcoin Group busca llançar el primer IPO de Bitcoin en el món