[Romanian] Dagger - whilei/ethereumproject-wiki GitHub Wiki

name: Dagger category:

Pe parcursul a celor peste cinci ani de experienta cu Bitcoin si alte cryptocurrencies alternative, o proprietate importanta pentru functiile proof of work ce a fost descoperita este aceaa a “ duritatii memoriei” (memory-hardness)- calcularea unui proof of work valid ar trebui sa necesite nu doar un numar mare de calcule, dar si o memorie mare. Momentan, exista trei categorii majore de functii memory-hard folosite in mining : scrypt, Primecoin mining si the birthday problem. Cu toate acestea sunt imperfecte: nici una nu necesita cantitatea de memorie pe care o cere o functie memory-hard ideala, si supefa de atacuri time-memory tradeoff, unde functia poate fi calculata cu mult mai putina memorie decat este necesar, cu costul de a sacrifica din eficienta computationala. Dagger este un algoritm proof of work care intentioneaza sa rezolve aceste probleme, furnizand un proof of work memory-hard bazat pe pe grafice aciclice dirijate (directed acyclic graphs –DAG) conectate moderat, care , desi departe de a fi optime, are proprietati de memory-hardness mult mai puternice decat orice alternativa folosita astazi. Why Be Memory-Hard? Principalul motiv pentru care memory hardness este importanta este acela de a face functia proof of work rezistenta la harware specializat. Cu Bitcoin, al carui algoritm de mining necesita doar un simplu calcul SHA256, companiile care au existat timp de un an, au creat "application-specific integrated circuits" (ASICs) specializate proiectate si configurate in silicon pentru singurul scop de a calcula milioane de hash-uri SHA256 intr-o incercare de a “mina” un block Bitcoin valid. Aceste cipuri (chips) nu au aplicatii legitime in afara minarii Bitcoin si crack-uirii parolelor, si prezenta acestora, care sunt de mii de ori mai eficiente per dolar si kilowatt/ora la calcularea hash-urilor fata de genericile CPU, fac imposibila o concurenta a utilizatorilor obisnuiti care folosesc hardware generic CPU si GPU.
Aceasta dominatie a hardware-ului specializat are cateva efecte daunatoare severe:

Neaga aspectul democratic al distributiei minarii cryptocurrency. Intr-un ecosistem dominat de hardvare generic, faptul ca toata lumea detine un computer garanteaza faptul ca toata lumea va avea sanse egale de a castiga cel putin o parte din oferta de bani initiala. Cu hardware-ul specializat, acest factor nu mai exista;potentialul de minare al fiecarui actor economic este linear (de fapt, usor superlinear) in cantitatea lor de capital pre-existent, poate chiar exacerband inegalitati deja existente in ceea ce priveste capitalul.
Creste risipa de resurse. Intr-o piata eficienta,venitul marginal se apropie de costul marginal. Cum venitul din minare este o functie liniara a banilor cheltuiti pe harware-ul de minare si electricitate, implicit venitul total se apropie de costul total. Prin urmare, intr-un ecosistem dominat de hardware specializat, cantitatea de resurse irosite se apropie de 100% din nivelul de securitate al retelei. Intr-un ecosistem dominat de CPU si GPU, deoarece deja toata lumea detine un computer, nimeni nu trebuie sa achizitioneze hardware specializat pentru primele cateva hash-uri pe secunda care detin putere de minare.Deci, venitul este sublinear in cost- toata lumea primeste o parte din venit “pe gratis”. Astfel, cantitatea de resurse irosita de retea este potential mai mica decat parametrul sau de securitate.
Centralizeaza minarea in mainile catorva actori. (ie. Producatorii ASIC), facand 51% din atacuri posibile si cu potentialul de a deschide reteaua pentru presiuni de reglementare. Hardware-ul specializat este atat de puternic deoarece include mii de circuite create special pentru a calcula functia proof of work, permitand hardware-ului sa realizeze aceasta functie de mii de ori in paralel. l. Memory hardness atenueaza aceasta problema stabilind ca principal factor de limitare nu puterea CPU, ci memoria. Se poate face, deasemenea, o imbunatatire modesta prin orientarea clock speed a CPU, dar masura in care astfel de optimizari pot fi facute este fundamental limitata la o valoare foarte scazuta , din considerente tehnologice. Astfel, imbunatatirea prin paralelizare intampina un obstacol: efectuarea a zece calcule memory-hard in paralel nicesita de zece ori mai multa memorie. Producatorii hardware-ului specializat pot ambala cu siguranta terabytes de memorie in dispozitivele lor, insa efectul este atenuat de doi factori. In primul rand, neprofesionistii pot atinge acelasi efect doar prin achizitionarea unor memory cards, iar in al doile arand, memoria este mult mai scumpa ca productie (daca masuram in echivalentul unui laptop) decat SHA256 chips; RAM-ul folosit in computerele obisnuite este deja optim, in esenta. Obiectii la Memory-Hardness
Toti algoritmii vor fi vulnerabili la ASICs, in cele din urma. Acest punct de vedere a devenit mai popular in special dupa recentul anunt al unei companii care produce ASICs pentru Scrypt, si afirma, in esenta, ca teoretic, orice algoritm poate fi facut mai bine cu hardware specializat, asa ca nu are rost sa se incerce directionarea algoritmilor spre hardware-ul general. Ce scapa din vedere acest argument, totusi, este ca speedup-ul din aplicarea hardware-ului specializat la Scrypt-ul moderat memory-hard, a fost demonstrat ca este mult mai jos decat Bitcoin-ul. Mai mult de atat, exista motive pentru a sugera ca acest trend va continua- dupa cum am descris mai sus, memoria din hardware-ul obisnuit este mult mai aproape de un nivel optim fata de circuitele de calcul.
Botnets vor prelua controlul asupra procesului de minare. Acest punct poate fi abordat din doua directii: empiric si teoretic. Empiric, botnets pana acum nu au fost implicati substantial in montarea a 51% din atacuri in altcoins, in general sunt multumiti cu extragerea venitului ca mineri “legitimi”. Teoretic, prezentarea publica a botnets ca amenintare este in mare sprijinita de performanta lor in network flooding/denial a service attacks- situatie unde fiecare computer dintr-un botnet este utilizat doar pentru numarul de conexiuni pe care le poate face. In contextul minarii totusi , computerele infectate cu botnet tind sa utilizeze sisteme de operare mai vechi si au specificatii mai slabe, insemnand ca vor avea o performanta mult mai scazuta, la fel ca si impactul asupra retelei, decat sugereaza initial marimea lor. Alternative existente Existenta fiecarui nou algoritm, protocol cryptografic primitiv, spre deosebire de tehnologii existente si mai bine testate trebuie sa aiba intotdeauna o justificare puternica; intr-o zona atat de delicata precum cryptocurrency, prudenta este foarte importanta, atat pentru ca sistemul se va ocupa de un capital de milioane de dolari, dar si pentru ca daca se face o singura greseala, nu exista nici o modalitate de upgrade la o versiune mai noua printr-un bugfix. Scopul acestei sectiuni va fi listarea a trei alternative existente si demonstrarea ineficientei lor. Scrypt Scrypt este algoritmul folosit de Litecoin, Dogecoin si de majoritatea noilor cryptocurrencies aparute. Odescriere simplificata a algoritmilor asemanatori Scrypt este urmatoarea:
Fie H[0] = D+N unde D sta la baza datelor iar N este nonce.
Pentru i de la 1 la N fie H[i] = f(H[0] ... H[i-1]) unde f este o functie asemanatoare hash-urilor care ia mai multe intrari,
Pentru i de la 1 la M fie R[i] = random([1 ... M])
SCRYPT(D,N) = f(H[R[0]] ... H[R[M]]. Daca SCRYPT(D,N) este destul de scazut, atunci N este un nonce invalid. Ideea este ca nu exista o modalitate de a calcula practic SCRYPT(D) fara a construi intreaga multime H si de a o pastra in memorie pentru ultimul pas. Totusi, algoritmii Scrypt au o proprietate care limiteaza, in mod inerent, cat de memory-hard pot fi: verificarea necesita calcularea unei runde a intregii functii, astfel ca functia este la fel de memory-hard de verificat pe cat este de calculat. Astfel, in timp ce scrypt poate fi viabil pentru atingerea memory-hardness in jurul a catorva megabytes per theread, este un non-starter pentru memory hardness in zona sutelor de megabytes per thread. De fapt, sute de megabytes per thread sunt discutabil necesari; deja exista companii http://www.cryptocoinsnews.com/2013/11/22/alpha-technologies-offer-scrypt-mining-asics/ care lucreaza pe ASICs pentru scrypt in ziua de astazi. Primecoin Algoritmul Primecoin nu este creat pentru a fi memory-hard, dar are aceasta proprietate intr-o anumita masura. Algoritmul cere minerilor sa gaseasca asa-numitele lanturi Cunningham de numere prime- lanturi de forma [ n+1, 2n+1, 4n+1 ... n*2^k+1 ] pentru un k suficient de mare. Dupa cum s-a dovedit, este foarte dificil sa se faca asta pentru orice lungime semnificativa fara a completa intai o data structure cunoscuta ca sita. Avantajul Primecoin este acela ca verificarea este aproape instanta si memory-cheap; tot ce trbuie sa fac utilizatorul este sa ruleze testul primality Fermat pentru a se asigura ca toate valorile sunt numere prime. Cu toate acestea, algoritmul Primecoin are doua slabiciuni in aceasta privinta:
'''Time-memory tradeoff''' – un ASIC are optiunea de a inlatura mare parte din memoria necesara prin sacrificarea eficientei de calcul; chiar si cu doar 100 KB per thread un miner poate fi destul de eficient.
'''All clear effect''' – dupa cum s-a dovedit, este posibil ca GPU si ASIC sa aiba thread-uri multiple care sa imparta aceeasi memorie. Cum minarea Primecoin necesita ca sita sa fie umpluta doar o singura data, un ASIC poate calcula o sita intai si apoi sa ruleze mii de thread-uri prin ea. Birthday attack Algoritmul birthday attack este ingenios, si functioneaza dupa cum urmeaza:
Fie H[i] = sha256(D + N + i) pentru i de la 0 la 232 - 1 cu data D si nonce N.
Daca abs(H[i] - H[j]) este suficient de scazuta, atunci (N,i,j) este o solutie tripla valida. Ingenuitatea protocolului vine din faptul ca in timp ce calculeaza eficient, birthday attack necesita stocarea hash-urilor intr-o structura astfel incat fiecare hash nou sa poata fi comparat cu cele anterioare lui, verificarea solutiilor necesita doar checking two hashes. Algoritmul este rezistent impotriva efectelor all-clear deoarece memoria trebuie eliberata (flushed) la fiecare 232 runde. Cu toate acestea, sunt cateva shortcut-uri time-memory tradeoff attacks. In primul rand, se poate optimiza prin doar prin stocarea primilor cativa bytes ai fiecarui hash in loc de primul hash. In al doilea rand, se pot stoca doar hash-uri cu primii doi bits fiind 00; acest lucru scoate din discutie 75% din solutiile posibile, reducand time efficiency de 4x,dar crescand space efficiency de 4x. In cele din urma, exista potential pentru optimizare prin examinarea diferitelor optiuni intre stocarea hash-urilor intr-un sir mare, un arbore red-black sau bianr, si alte structuri mai complexe; algoritmul optim poate fi destul de complicat. Dagger intentioneaza sa rezolve toate aceste probleme, are o valuta ce este memory-hard pentru computer, dar este memory-easy de verificat, nu are un efect clar , nu are time-memory tradeoff, chiar si la o ratie de 1:1, and for which a close-to-optimal algorithm is the naive one. Algorithm specification: Esential, algoritmul Dagger functioneaza prin crearea unui grafic aciclic directionat (termenul tehnic pentru un arbore in care fiecare nod poate avea mai multi parinti) cu un total de 223 - 1 de noduri intr-o secventa. Daca minerul gaseste un nod intre indexul 222 si 223 astfel incat hash-ul rezultat sa fie sub 2256 divizat de parametrul de dificultate, rezultatul este un proof of work valid. Fie D data de baza (eg. In cazul Bitcoin-ului, header-ul block), N fie nonce si || operatorul concatenarii sirului (ie. 'foo' || 'bar' == 'foobar') . Intregul cod pentru algoritm se desfasoara dupa cum urmeaza: D(data,xn,0) = sha3(data) D(data,xn,n) = with v = sha3(data + xn + n) L = 2 if n < 2^21 else 11 if n < 2^22 else 3 a[k] = floor(v/n^k) mod n for 0 <= k < 2 a[k] = floor(v/n^k) mod 2^22 for 2 <= k < L sha3(v ++ D(data,xn,a[0]) ++ D(data,xn,a[1]) ++ ... ++ D(data,xn,a[L-1])) Proprietati: Obiectiv: gasirea xn, n astfel incat n > 2^22 si D(data,xn,n) < 2^256 / diff
Cu 228 bytes (256 MB) de memorie, algoritmul optim trebuie sa administreze D de la start la finish.
O potentiala problema este evaluarea lenta; parti din arbore pot fi evaluate doar in masura in care se poate reduce numarul de hash-uri necesare. Cu toate acestea, din cauza unul nod (pseudo-) aleatoriu din 225 este luat de 228 ori, putem estima statistic ca fiecare nod are un 1 / e8 rest ramas nefolosit – doar in jur de 0.03%. Astfel, beneficiul de pe urma evaluarii lente nu este substantiala.
Este posibil ca algoritmul sa functioneze cu mult mai putina memorie folosindu-se evaluarea lenta.Totusi, testele empirice arata ca sunt necesare intre 3000 si 25000 de hash-uri pentru calcularea unui nonce.
Verificarea necesita, de asemenea 3000-25000 hash-uri.
Pentru ca fraza 2^21 to 2^22 necesita 11 parinti, atacurile time-memory-tradeoff sunt slabite destul de sever – incercarea de a stoca 2^21 noduri in loc de 2^23 reduce uzarea memoriei cu un factor de 4, dar incetineste calcularea cu un factor de 20. Astfel, nu exista nici un time-memory tradeoff attcal, sunt necesari aproape 256 MB pentru un nivel de eficienta rezonabil. Concluzie Acest algoritm ofera o functie de minare proof of work cu proprietati ale mamory hardness ce nu sunt ideale, dar cu toate acestea reprezinta o imbunatatire majora fata de orice algoritm anterior. Este nevoie de 512 M pentru evaluare, 112 KB si 4078 hash-uri pentru a verifica,It takes 512 MB to evaluate, 112 KB memory and 4078 hashes to verify, and even the tinest time-memory tradeoff is not worthwhile to implement because of the bottom-level branching adjustment. These parameters allow Dagger to be much more daring in its memory requirements than Primecoin or scrypt, asking for 512 MB of RAM for a single thread. Because the primary determinant of hardness is memory, and not computation, specialized hardware has only a tiny advantage; even an optimal Dagger mining ASIC would have little to offer over a hobbyist purchasing hundreds of gigabytes of memory cards off the shelf and plugging them into a medium-power GPU. And even in such an equilibrium, mining with ordinary CPUs will likely continue to be practical. Acknowledgements • Thanks to Adam Back and Charles Hoskinson, for discussion and critique of earlier drafts of the protocol • See also: Fabien Coelho's paper, in which Fabien Coelho had independently discovered a similar algorithm in 2005.