Войти
В криптографии, памяти трудно функция (MHF) является функцией, которая стоит значительного количества памяти для оценки. Это отличается от функции, связанной с памятью ; последнее требует затрат из-за замедления вычислений из-за задержки памяти. MHF находят свое применение в качестве доказательства работы.
Есть разные способы измерить стойкость к памяти функции. Часто встречающийся показатель - совокупная сложность памяти (CMC). В параллельной модели CMC измеряет жесткость памяти, суммируя все входные данные на каждом этапе.
Еще одна жизнеспособная мера - объединение памяти с физическим временем.
Еще одна мера - это потребление пропускной способности памяти на шине памяти. Эта категория функций также называется «функциями, ограничивающими полосу пропускания».
Есть причина, по которой MHF стоят много памяти вместо, скажем, циклов процессора. Биткойн использовал повторную оценку функции SHA-2 в качестве доказательства работы, но оказалось, что современные процессоры общего назначения, то есть стандартные процессоры, очень неэффективны, когда им приходится постоянно вычислять фиксированную функцию. Майнеры внедрили специализированные интегральные схемы (ASIC) и достигли ускорения в 10 ^ 16. Хотя это нормально для того, для чего нужен Биткойн, нам нужна более «эгалитарная» мера жесткости. Другими словами, мы хотим, чтобы все были одинаково неэффективны при вычислении функции, даже если у них есть ASIC. Потому что, если некоторые люди могут оценить функцию эффективно, а некоторые нет, то, чтобы сделать функцию относительно сложной для тех, кто выбирает короткие пути, мы сделаем функцию слишком сложной для обычного пользователя. Если все неэффективны, тогда каждый может оценить функцию средней сложности.
Со временем было обнаружено, что стоимость памяти остается примерно одинаковой для всех. Следовательно, MHF.
В зависимости от модели оценки MHF можно разделить на два лагеря: зависимые от данных (dMHF) и независимые от данных (iMHF). dMHF - это то, что иногда вы не знаете, какие части информации вам все еще понадобятся для последующих вычислений, а iMHF - это те, в которых нет такой двусмысленности. Примерами dMHF являются scrypt и Argon2d. Примерами iMHF являются Argon2i и catena. Многие из этих MHF разработаны для использования в качестве функций хеширования паролей именно из-за их жесткости памяти.
У dMHF есть очевидная проблема, заключающаяся в том, что они подвержены атакам по сторонним каналам, таким как тайминг кеширования. По этой причине люди склонны к iMHF, особенно для хеширования паролей. Однако математически доказано, что iMHF обладают более слабыми свойствами твердости памяти, чем dMHF.
Для iMHF в параллельной модели случайного оракула (pROM), это известный факт, что совокупная сложность гальки ограничена снизу и ограничена сверху устойчивостью по глубине графа.
