xenon
@xenon
Too drunk to fsck

Как удаленно проверить целостность данных (на недоверенном узле)?

Представим p2p сервис, где люди доверяют друг-другу хранить данные. (Например, мой фотоальбом хранится еще у 3 человек в сети, а я за это тоже храню чьи-то данные. Если мой диск сгорит - данные можно будет восстановить с их копий).

Восстановление - происходит очень редко. Поэтому есть риск, что удаленный узел будет "врать". Будет принимать данные на хранение и просто "сохранять в /dev/null". Поэтому возникает потребность как-то периодически проверять их. Самый простой метод проверки - периодически скачивать их и сверять, но это очень дорого и работает только если есть полная копия. (Например, сторонний сервис не может это делать автоматически).

Есть ли какой-то более эффективный алгоритм? Например, сходу я вижу такую схему - перед отдачей мы создаем тысячу случайных строк (префиксов), и высчитываем хеш от префикс+данные, храним их локально (это занимает мало места). Затем периодически спрашиваем удаленную сторону тоже посчитать их (даем ей подстроку) и сравниваем. Без наличия полного файла она не может правильно подсчитать хеш от префикс+данные.

Или просто запрашиваем случайный блок из нескольких байт по указанному смещению от начала архива. (А локально храним сколько-то таких блоков для проверки).

Есть ли какие-то готовые подходы для этого? Мне кажется, это должно быть какой-то типовой криптографической задачей, как задача обмена ключами или подсчет хеш-суммы. Может быть даже где-то на практике что-то подобное используется?
  • Вопрос задан
  • 276 просмотров
Пригласить эксперта
Ответы на вопрос 2
uvelichitel
@uvelichitel
habrahabr.ru/users/uvelichitel
Блокчейн использует дерево Меркла - популярная статья
Ответ написан
robux
@robux
В качестве разновидности запроса случайного блока по случайному смещению, можно запрашивать не сам блок, а его хэш. Что-то типа: "Эй, чувак, дай md5 блока длиной 512 по смещению 23121 файла такого-то", и узел отвечает.

Если у тебя самого нет этого куска, можно второй узел попросить сделать то же самое и сравнить. Если сходится, то успокоиться на время, если разошлось, то либо третий узел запрашивать, либо по своим кускам начинать гонять первые два узла, пока один не "спалится".
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы