înregistrare Logare
Puncte:1
user10030 avatar Crypto

Poate exista o funcție injectivă care mapează un set mare de numere întregi la un set mai mic, fiind „conștient de coliziune”

drapel in
user10030

Luați în considerare două seturi:

„Setul mare” conține toate numerele întregi între $0$ și $2^{160}$ exact o dată.

„Setul mic” conține toate numerele întregi între $0$ și $2^{32}$ exact o dată.

Având în vedere că numărul de membri din „setul mare” este mai mare decât cei din „setul mic”, nu poate exista o funcție injectivă $f(n_b) = n_s$ maparea oricărei intrări fiind membru al „setului mare” $n_b$ la o ieșire care este membru al „setului mic” $n_s$. Daca acea functie $f$ a existat, ar fi răspunsul la întrebări.

Din motive practice, presupunem că poate exista totuși o construcție/algoritm cu funcție practică $f_p$ unde rezultatele tuturor intrărilor în $f_p(n_b)$ sunt membri ai „setului mic” și fiecare $n_b$ indică un distinct $n_s$.

Pentru lipsa de înțelegere a conceptelor criptografice, voi numi această proprietate „conștient de coliziune”. De exemplu. să implementeze această construcție, presupunând o capacitate de stocare de dimensiunea de $2^{256}$ (întreg fără semn de 256 de biți), există o funcție $f_p$ sau un algoritm care pentru oricare $n_b$ fie returnează o „coliziune” („colision-aware”) sau un membru distinct al $n_s$?

174
2 + 12
drapel cn
Maeher
Îmi este foarte neclar ce cauți. Cum diferă ceea ce descrii în al doilea paragraf de o funcție injectivă?
0
Răspunde
drapel cn
Maeher
Ce înseamnă „întoarcerea unei coliziuni”?
0
Răspunde
user10030 avatar
drapel in
user10030
Caut o funcție în care card(domain) > card(codomain), dar fiecare număr pe care îl iau ca intrare în funcție de la hărți de domeniu la un număr distinct în codomeniu. Din înțelegerea mea, acest lucru poate fi posibil numai dacă card(domain) >= card(codomain). Deci, deoarece acest lucru nu este posibil, pot avea o funcție care să permită acest tip de mapare, dar de ex. „erori” dacă o coliziune a fost găsită pentru prima dată.
0
Răspunde
drapel cn
Maeher
Asta e imposibil, da. Dar care este mai exact comportamentul pe care îl dorești? Funcția fie returnează o valoare din domeniu, fie un simbol de eroare?
0
Răspunde
user10030 avatar
drapel in
user10030
Iată ce vreau practic: Din când în când primesc un număr aleatoriu din uint160 (este un cont/adresă Ethereum) și am nevoie de o funcție care mapează în mod distinct fiecare adresă la un anumit slot dintr-o listă cu lungimea de 2^32.Să presupunem că am alocat deja 100 de adrese, acum adresa #101 este lungă și slotul său este același ca de ex. #91, atunci vreau să fiu conștient că există o coliziune pentru sloturile acum #101 nu ar trebui să suprascrie #91. Cu toate acestea, nu pot stoca doar toate adresele stocate anterior. Am doar un slot de capacitate de stocare ca dimensiune, de ex. uin256.
0
Răspunde
drapel cn
Maeher
Fără cerințe suplimentare, funcția este definită ca „Dacă $x\leq2^{32}$, returnează $x$, altfel returnează $\bot$”. pare să vă satisfacă cerințele de la întrebare. Dar sunt sigur că aveți cerințe suplimentare pe care dintr-un motiv oarecare refuzați să le specificați.
1
Răspunde
user10030 avatar
drapel in
user10030
Nu este refuz. Este mai degrabă să nu mă pot exprima corect. O sa incerc sa specific mai multe. Mulțumesc pentru ajutor până acum. Pentru a continua: Dacă am folosit „dacă $x
0
Răspunde
fgrieu avatar
drapel ng
fgrieu
Ce zici de un hash trunchiat? În cazul nostru de utilizare, acesta funcționează până la și inclusiv numărul 101 cu mai puțin de 1 șansă din 850 de mii de contrariu.
1
Răspunde
drapel cn
Maeher
Următoarea încercare evident greșită de a afla ce căutați cu adevărat: Alocați indici secvențial. Mențineți un numărător de 33 de biți n inițializat la zero. De fiecare dată când vedeți o intrare, dacă $n
1
Răspunde
user10030 avatar
drapel in
user10030
@fgrieu Interesant. Ceea ce îmi place la asta este că umple spațiul de codomeniu 2^32 în mod progresiv și distribuit uniform. Problema pe care o văd, totuși, este că, având în vedere funcția hash: vreau să stochez un echilibru Ether în raport cu acesta. De exemplu. Vreau să spun că $n_b$ de ex. 0xabc... â $n_s$ deține 1 eter. Cu toate acestea, pe măsură ce soldurile devin mai mari, la un moment dat - asemănător cu mineritul Bitcoin - poate deveni sănătos din punct de vedere economic să rulezi un algoritm de forță brută pentru, de ex. găsiți o coliziune pentru $n_s$ pentru un cont $n_b$ care deține în prezent un sold mare.
0
Răspunde
user10030 avatar
drapel in
user10030
Bună @Maeher. Având în vedere un contor care crește cu fiecare intrare și are o capacitate cu 1 bit mai mare decât numărul MAX din codomeniu, problema este că pentru orice număr din domeniu, vreau să îi atribui exact un număr în codomeniu chiar și la inserții repetate. Lucrez în informatică, așa că aș numi o astfel de funcție „deterministă”. Având în vedere o anumită intrare, acesta produce întotdeauna aceeași ieșire. Din câte am înțeles este că, dacă am folosi un contor crescător, dacă am inserat în mod repetat aceeași intrare de mai multe ori, am ajunge la rezultate diferite de codomeniu de fiecare dată (creștere cu, de exemplu, +1).
0
Răspunde
drapel cn
Maeher
Ați putea încerca să utilizați un hash trunchiat și să mențineți o structură de date de membru aproximativ setată (de exemplu, un filtru Bloom) a indicilor uzați. Dar este probabil ca acesta să fie prea mare.
2
Răspunde
Puncte:2
Paul Uszak avatar Crypto
drapel cn
Paul Uszak

Ce ziceti:- $$ n_s = \mathcal{H}(n_b) \& (2^{32} - 1) $$ Unde $n_b \în N_b$, etc? $\mathcal{H}$ poate fi o funcție hash la alegerea dvs. Deoarece acesta este un site cripto, sugerez SHA-256. $\&$ înseamnă AND pe biți, dar ar putea fi înlocuit cu deplasări la dreapta sau la stânga ale numărului corespunzător de biți (128 în cazul lui SHA-256). Poate prea lent (?)

Funcțiile hash criptografice sunt surjectiv, ceea ce înseamnă că ieșirile lor se ciocnesc ocazional. Rata de coliziuni va crește foarte mult dacă trunchiați $\mathcal{H}$ la 32 de biți. Cu atât mai mult va fi efectul principiul porumbeii. Deci ai setat $N_b$ umplerea cu numere distribuite uniform, dând $n_b \la n_s$ de la domeniu la codomeniu.

Nu știu despre Ethereum, dar 160 arată suspect de ieșirea lui SHA-1. Dacă da, doar trunchiați contul/adresa la 32 de biți, deoarece este deja distribuit uniform.

0 + 5
drapel ma
Nayuki
„Funcțiile hash criptografice sunt surjective” - nu cred. Surjectiv înseamnă că pentru fiecare valoare hash posibilă, există un mesaj care o generează. Nu puteți dovedi că o funcție hash criptografică nu are „puncte oarbe”.
1
Răspunde
user10030 avatar
drapel in
user10030
Bună @paul-uszak. Am comentat în răspunsul meu inițial de ce cred că trunchierea nu este soluția optimă. Wrt la uint160 și SHA-1: În Ethereum, un cont este derivat dintr-o cheie publică ECDSA, apoi hashing folosind Keccak-256 la o ieșire de 32 de octeți și apoi - surprinzător - trunchiat folosind doar ultimii 20 de octeți. În cele din urmă, este prefixat cu 0x. Vedeți mai multe: https://ethereum.stackexchange.com/a/3619/47031
0
Răspunde
Paul Uszak avatar
drapel cn
Paul Uszak
@user10030 Deci aveți răspunsul dvs. :-) Trunchiați la patru octeți și acolo îl aveți, ca în scriptum-ul meu post.
0
Răspunde
user10030 avatar
drapel in
user10030
Deși apreciez existența soluției tale, cred că nu este ceea ce voi avea nevoie în cele din urmă. În cazul în care trunchez la 4 octeți, încep să ofer utilizatorilor mei un stimulent pentru a-mi plăti pentru $n_b$s care au ca rezultat același $n_s$. Sigur, pentru adresele $n_b$ care dețin doar o sumă mică de valoare monetară, aceasta poate să nu fie o problemă reală sau un atac solid din punct de vedere economic: dar aș dori, în general, să evit acest tip de problemă. Fie nu pot exista coliziuni, fie pot exista coliziuni și sunt imediat conștient de ele, deoarece pot privi înapoi la toate celelalte intrări și ieșiri ale operațiunii de hashing.
0
Răspunde
Paul Uszak avatar
drapel cn
Paul Uszak
@user10030 Absolut vor fi ciocniri din cauza principiului de porumbei. La cel mai bun tarif de $2^{-32}$ per cont. Apoi va crește asimptomatic spre 1 pe măsură ce codomeniul se umple.
0
Răspunde
Puncte:1
avatar Crypto
drapel ph
bmm6o

Dacă înțeleg cerințele, ceea ce ceri nu este o „funcție” conform definiției normale. Se pare că vrei niște $f$ care având în vedere o succesiune de intrări ${x_i}$ va returna fie o valoare deterministă $y_i$ sau un simbol de eroare dacă a revenit deja $y_i$. Dar să presupunem $x_k$ este prima intrare care returnează o eroare. Ce ar trebui să se întâmple dacă suni $f$ cu succesiunea pornind de la $x_k$? Cred că ați dori să nu returneze o eroare, deci valoarea lui $f(x_k)$ nu este bine definit.

Modul de a rezolva asta matematic este schimbarea definiției $f$ a accepta o secvență. Dar practic, ceea ce înseamnă probabil că sistemul tău înregistrează toate intrările cu care a fost apelat. Și vei descoperi că, dacă faci asta, ai putea la fel de bine să te întorci $0, ..., n-1$ pentru primele intrări distincte și erori pentru tot ce urmează.

0 + 1
user10030 avatar
drapel in
user10030
Da, practic a fi „conștient de coliziune” ar însemna probabil să treci o secvență la $f$. De fapt, trecerea într-o secvență nu ar fi o problemă atâta timp cât nu ar duce la o creștere a stocării pentru fiecare nouă operațiune de hashing. Mă întreb dacă există de ex. o modalitate prin care valoarea transmisă anterior ar putea fi factorizată sau comprimată astfel încât să nu ocupe mult spațiu de stocare și în care ar deveni practic să se transmită întotdeauna toate valorile trecute și una nouă pentru a face funcția „conștientă de coliziune”, ca în „returnează un simbol de eroare dacă întâlnește o ieșire mai mult decât prima dată”.
0
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.