[devel] Маленькая теоретическая задачка

[Paul Wolneykien <manowar@altlinux.org>]

  Предположим, что вы отдали своему знакомому на хранение файл
достаточно большого размера, а свою копию удалили. Через некоторое время
вы захотели узнать, всё ли в порядке с переданной на хранение копией: не
был ли файл случайно (или намеренно) повреждён или удалён.
  Необходимо выполнить данную проверку таким образом, чтобы объём
данных, которые для этого должен сообщить вам ваш знакомый, был бы
существенно меньше объёма переданного на хранение файла.
  Желательно, чтобы данную проверку можно было производить многократно.

  Только для условия задачи предположим также, что ваш знакомый хочет
вас обмануть: сделать вид что всё ещё бережно хранит файл, в то время
как давно его удалил (чтобы заполнить освободившееся место своими файлами).

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

---

  Ясно, что метод вычисления контрольного значения по заранее известной
функции в данном случае не подходит: обманщик может легко произвести
вычисления заранее и удалить файл, сохранив лишь результат вычислений,
чтобы потом предоставить его по вашему требованию. Значит функция, по
которой вычисляется контрольное значение, должна быть заранее ему не
известна.

  В том случае, если ваш знакомый не будет заранее знать, какую функцию
вы предложите ему вычислить, то ему придётся сохранить файл, по крайней
мере до тех пор, пока расчёты не будут произведены. Но для повторных
проверок нельзя использовать одну и ту же функцию: поняв, что результат
вычислений всегда один и тот же, ваш знакомый, поддавшись желанию
освободиться от ненужного ему файла, может его удалить. Значит функции
не должны повторяться.

  Добиться того, чтобы функции, передаваемые для вычисления контрольных
значений, действительно не повторялись, представляет определённую
трудность. Совершенно не похожие на первый взгляд функции могут
коррелировать известным образом. Если ваш знакомый хотя и потенциальный
обманщик, но хороший математик, то известная или легко обнаруживаемая
зависимость между функциями позволит ему получать новые контрольные
значения, на основании старых, что снова освобождает его от
необходимости хранить файл. Однако полностью избежать корреляции функций
не только сложно, но и невыгодно: в том случае если зависимость между
функциями полностью отсутствует, перед тем как удалить свою копию файла
придётся вычислить и сохранить у себя все возможные контрольные
значения. Такой подход, во первых, потребует дополнительных затрат
памяти, а во вторых, сделает количество возможных проверок конечным.
Значит функции, которые вы будете отправлять вашему знакомому для
проверки, должны коррелировать сложно обнаруживаемым, но известным для
вас способом.


  Весь вопрос в том, что это за функции и каков способ их получения.

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

  Павел.