Minneshård funktion

Inom kryptografi är en minneshård funktion (MHF) en funktion som kostar en betydande mängd minne att utvärdera. Den skiljer sig från en minnesbunden funktion , som medför kostnader genom att sakta ner beräkningen genom minneslatens. MHF:er kan användas som bevis på arbete .

Minnet hårt mått

Det finns olika sätt att mäta minneshårdheten för en funktion, och ett vanligt mått är Cumulative Memory Complexity (CMC). I en parallell modell är CMC summan av minnet som krävs för att beräkna en funktion över varje tidssteg i beräkningen.

Andra genomförbara åtgärder är att integrera minne mot fysisk tid., och att mäta minnesbandbreddsförbrukning på en minnesbuss. Funktioner som kräver hög minnesbandbredd kallas ibland för "bandbreddshårda funktioner".

Motivering

MHF:er designades för att använda mycket minne istället för en annan resurs, såsom CPU-cykler. Bitcoins proof-of-work använde upprepad utvärdering av SHA-2- funktionen, men moderna processorer för allmänna ändamål, som processorer från hyllan, är ineffektiva när de beräknar en fast funktion många gånger om. Specialiserad hårdvara, såsom applikationsspecifika integrerade kretsar (ASIC) designade för Bitcoin-brytning kan beräkna dessa hash upp till 100 000 gånger snabbare. Detta ledde till oro över centraliseringen av gruvdrift för Bitcoin och andra kryptovalutor. På grund av denna ojämlikhet mellan gruvarbetare som använder ASIC och gruvarbetare som använder processorer eller hårdvara från hyllan, ville designers av senare proof-of-work-system designa hashfunktioner för vilka det var svårt att ASIC som kunde utvärdera hashfunktionen betydligt snabbare än en CPU.

Med tiden har det visat sig att minneskostnaderna förblir relativt konstanta mellan CPU:er och mer specialiserad hårdvara, vilket är anledningen till att MHF:er har hittat användning i kryptovalutautvinning. De är också användbara vid hashning av lösenord, eftersom de avsevärt ökar kostnaden för att prova många möjliga lösenord mot en läckt databas med hashade lösenord.

Varianter

MHF:er kan kategoriseras i två olika grupper baserat på deras utvärderingsmönster: databeroende Memory-Hard Functions (dMHF) och dataoberoende Memory-Hard Functions (iMHF). dMHF:er är MHF:er där det inte är klart vilka data som behövs för de senare stegen av utvärdering av funktionen tills funktionen utvärderas, medan iMHF:er är funktioner där det inte finns någon sådan tvetydighet. Exempel på dMHF är scrypt och Argon2d . Exempel på iMHF är Argon2i och catena . Många av dessa MHF:er är utvecklade för att användas som lösenordshasningsfunktioner precis på grund av deras minneshårdhet.

Ett anmärkningsvärt problem med dMHF:er är att de är benägna att attackera sidokanaler som cache-timing. Människor tenderar mot iMHFs av denna anledning, särskilt för lösenordshashing. Det är dock matematiskt bevisat att iMHF har svagare minneshårdhetsegenskaper än dMHF.