Funzione memory-hard - Memory-hard function
In crittografia , una funzione memory-hard (MHF) è una funzione che costa una quantità significativa di memoria per essere valutata. È diverso da una funzione legata alla memoria ; quest'ultimo comporta dei costi rallentando il calcolo attraverso la latenza della memoria. Gli MHF trovano il loro uso come una forma di prova del lavoro .
Misura difficile della memoria
Esistono diversi modi per misurare la durezza della memoria di una funzione. Una misura comunemente vista è la complessità della memoria cumulativa (CMC). In un modello parallelo, CMC misura la durezza della memoria sommando tutti gli input su ogni passaggio.
Un'altra misura praticabile è l'integrazione della memoria con il tempo fisico.
Un'altra misura è il consumo di larghezza di banda della memoria su un bus di memoria. Questa categoria di funzioni è anche denominata "funzioni di larghezza di banda pesante".
Motivazione
C'è un motivo per cui gli MHF costano molta memoria invece che, ad esempio, i cicli della CPU. Bitcoin ha utilizzato la valutazione ripetuta della funzione SHA-2 come prova del lavoro, ma si è scoperto che i moderni processori generici, cioè le CPU standard , sono molto inefficienti quando hanno il compito di calcolare una funzione fissa più e più volte. I minatori hanno adottato circuiti integrati specifici per l'applicazione (ASIC) e hanno ottenuto una velocità del 10 ^ 16. Anche se questo va bene per ciò per cui Bitcoin è buono, vogliamo una misura di durezza più "egualitaria". In altre parole, vogliamo che tutti siano ugualmente inefficienti nel calcolare la funzione anche se hanno un ASIC. Perché se alcune persone possono valutare la funzione in modo efficiente e altre no, allora per rendere la funzione relativamente difficile per gli acquirenti di scorciatoie, renderemo la funzione troppo difficile per un utente normale. Se tutti sono inefficienti, allora tutti possono valutare una funzione moderatamente difficile.
Nel tempo, è stato riconosciuto che il costo della memoria rimane abbastanza uguale su tutta la linea. Quindi MHF.
Varianti
Sulla base dei loro modelli di valutazione, gli MHF possono essere suddivisi in due campi: dipendente dai dati (dMHF) e indipendente dai dati (iMHF). I dMHF sono quelli che a volte non sai quali informazioni avresti ancora bisogno per i calcoli successivi, e gli iMHF sono quelli che non c'è tale ambiguità. Esempi di dMHF sono scrypt e Argon2d . Esempi di iMHF sono Argon2i e catena . Molti di questi MHF sono stati sviluppati per essere utilizzati come funzioni di hashing delle password proprio a causa della loro durezza di memoria.
I dMHF hanno il problema evidente di essere inclini ad attacchi di canale laterale come il tempo di cache. Le persone tendono agli iMHF per questo motivo, soprattutto per l'hashing delle password. Tuttavia, è matematicamente dimostrato che gli iMHF hanno proprietà di durezza della memoria più deboli rispetto ai dMHF.
Costruzione
grafico robusto in profondità
Per gli iMHF nel modello di oracolo casuale parallelo (pROM), è un fatto noto che la complessità del pebbling cumulativo è delimitata in basso e delimitata in alto dalla robustezza della profondità di un grafico.
