Как удаленно проверить целостность данных (на недоверенном узле)?
Представим p2p сервис, где люди доверяют друг-другу хранить данные. (Например, мой фотоальбом хранится еще у 3 человек в сети, а я за это тоже храню чьи-то данные. Если мой диск сгорит - данные можно будет восстановить с их копий).
Восстановление - происходит очень редко. Поэтому есть риск, что удаленный узел будет "врать". Будет принимать данные на хранение и просто "сохранять в /dev/null". Поэтому возникает потребность как-то периодически проверять их. Самый простой метод проверки - периодически скачивать их и сверять, но это очень дорого и работает только если есть полная копия. (Например, сторонний сервис не может это делать автоматически).
Есть ли какой-то более эффективный алгоритм? Например, сходу я вижу такую схему - перед отдачей мы создаем тысячу случайных строк (префиксов), и высчитываем хеш от префикс+данные, храним их локально (это занимает мало места). Затем периодически спрашиваем удаленную сторону тоже посчитать их (даем ей подстроку) и сравниваем. Без наличия полного файла она не может правильно подсчитать хеш от префикс+данные.
Или просто запрашиваем случайный блок из нескольких байт по указанному смещению от начала архива. (А локально храним сколько-то таких блоков для проверки).
Есть ли какие-то готовые подходы для этого? Мне кажется, это должно быть какой-то типовой криптографической задачей, как задача обмена ключами или подсчет хеш-суммы. Может быть даже где-то на практике что-то подобное используется?
В качестве разновидности запроса случайного блока по случайному смещению, можно запрашивать не сам блок, а его хэш. Что-то типа: "Эй, чувак, дай md5 блока длиной 512 по смещению 23121 файла такого-то", и узел отвечает.
Если у тебя самого нет этого куска, можно второй узел попросить сделать то же самое и сравнить. Если сходится, то успокоиться на время, если разошлось, то либо третий узел запрашивать, либо по своим кускам начинать гонять первые два узла, пока один не "спалится".
Средний
Простой
Средний
