Funkcja wymagająca pamięci

W kryptografii funkcja twarda w pamięci (MHF) to funkcja, której oszacowanie kosztuje znaczną ilość pamięci . Różni się od funkcji związanej z pamięcią , która wiąże się z kosztami, spowalniając obliczenia z powodu opóźnienia pamięci. MHF można wykorzystać jako dowód pracy .

Twarda miara pamięci

Istnieją różne sposoby mierzenia twardości pamięci funkcji, a powszechnie spotykaną miarą jest skumulowana złożoność pamięci (CMC). W modelu równoległym CMC jest sumą pamięci wymaganej do obliczenia funkcji w każdym kroku czasowym obliczeń.

Inne realne środki to integracja pamięci z czasem fizycznym i pomiar zużycia przepustowości pamięci na szynie pamięci. Funkcje wymagające dużej przepustowości pamięci są czasami określane jako „funkcje wymagające dużej przepustowości”.

Motywacja

MHF zostały zaprojektowane tak, aby zużywały dużo pamięci zamiast innego zasobu, takiego jak cykle procesora. Dowód pracy Bitcoin wykorzystywał wielokrotną ocenę funkcji SHA -2 , ale nowoczesne procesory ogólnego przeznaczenia, takie jak gotowe procesory , są nieefektywne przy wielokrotnym obliczaniu stałej funkcji. Specjalistyczny sprzęt, taki jak układy scalone specyficzne dla aplikacji (ASIC) zaprojektowane do wydobywania bitcoinów mogą obliczać te skróty nawet 100 000 razy szybciej. Doprowadziło to do obaw o centralizację wydobycia Bitcoina i innych kryptowalut. Ze względu na tę nierówność między górnikami korzystającymi z ASIC i górnikami korzystającymi z procesorów lub gotowego sprzętu, projektanci późniejszych systemów proof-of-work chcieli zaprojektować funkcje skrótu, dla których ASIC miał trudności z oceną funkcji skrótu znacznie szybciej niż PROCESOR.

Z biegiem czasu wykazano, że koszty pamięci pozostają względnie stałe między procesorami a bardziej wyspecjalizowanym sprzętem, dlatego MHF znalazły zastosowanie w wydobywaniu kryptowalut. Są również przydatne w haszowaniu haseł, ponieważ znacznie zwiększają koszt wypróbowania wielu możliwych haseł w bazie danych, która wyciekła z zaszyfrowanych haseł.

Warianty

MHF można podzielić na dwie różne grupy na podstawie ich wzorców oceny: zależne od danych funkcje twarde pamięci (dMHF) i niezależne od danych funkcje twarde pamięci (iMHF). dMHF to MHF, w przypadku których nie jest jasne, które dane są potrzebne do późniejszych etapów oceny funkcji, dopóki funkcja nie zostanie oceniona, podczas gdy iMHF to funkcje, w których nie ma takiej niejednoznaczności. Przykładami dMHF są scrypt i Argon2d . Przykładami iMHF są Argon2i i catena . Wiele z tych MHF zostało opracowanych do użytku jako funkcje haszujące hasła właśnie ze względu na ich twardość pamięci.

Godnym uwagi problemem dMHF jest to, że są one podatne na ataki typu side-channel, takie jak taktowanie pamięci podręcznej. Z tego powodu ludzie skłaniają się ku iMHF, zwłaszcza do haszowania haseł. Jednak matematycznie udowodniono, że iMHF mają słabsze właściwości twardości pamięci niż dMHF.