ALT Linux Team development discussions
 help / color / mirror / Atom feed
* [devel] Маленькая теоретическая задачка
@ 2010-09-10 20:43 Paul Wolneykien
  2010-09-10 21:04 ` Alexey I. Froloff
  2010-09-11  4:56 ` Alexey Shabalin
  0 siblings, 2 replies; 11+ messages in thread
From: Paul Wolneykien @ 2010-09-10 20:43 UTC (permalink / raw)
  To: devel


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

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

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

---

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

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

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


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

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

  Павел.


^ permalink raw reply	[flat|nested] 11+ messages in thread

end of thread, other threads:[~2010-09-17  4:37 UTC | newest]

Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2010-09-10 20:43 [devel] Маленькая теоретическая задачка Paul Wolneykien
2010-09-10 21:04 ` Alexey I. Froloff
2010-09-11  7:17   ` Andrey Rahmatullin
2010-09-16 19:37     ` Paul Wolneykien
2010-09-16 19:45       ` Paul Wolneykien
2010-09-16 19:55       ` Alexey I. Froloff
2010-09-16 19:56         ` Alexey I. Froloff
2010-09-16 20:25         ` Paul Wolneykien
2010-09-16 21:52           ` Alexey I. Froloff
2010-09-17  4:37       ` Andrey Rahmatullin
2010-09-11  4:56 ` Alexey Shabalin

ALT Linux Team development discussions

This inbox may be cloned and mirrored by anyone:

	git clone --mirror http://lore.altlinux.org/devel/0 devel/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 devel devel/ http://lore.altlinux.org/devel \
		devel@altlinux.org devel@altlinux.ru devel@lists.altlinux.org devel@lists.altlinux.ru devel@linux.iplabs.ru mandrake-russian@linuxteam.iplabs.ru sisyphus@linuxteam.iplabs.ru
	public-inbox-index devel

Example config snippet for mirrors.
Newsgroup available over NNTP:
	nntp://lore.altlinux.org/org.altlinux.lists.devel


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git