Борьба с коллизиями хэша.

[username1565]

Результат применения хэш-функции от всех комбинаций данных, длины большей, нежели хэш - имеет как минимум одну коллизию (на практике - больше).
Хэш-функция, без коллизий - это утопия, иначе, она позволяла бы сжать данные, бо́льшие по длине, нежели значение хэша.

Корни этой проблемы, заключаются в наличии несжимаемых данных.
В статье https://ru.wikipedia.org/wiki/Сжатие_без_потерь#Сжатие_и_комбинаторика
пишется следующее:

Если перефразировать всё это, другими словами, то,
пытаясь сжать (прохешировать),
все однобайтные комбинации в 4 бита,
получишь как минимум 2^4 коллизий,
описание которых займёт 4 бита.

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

Поэтому, однозначно идентифицировать посты по хэшу
(а в наноборде используется половина sha256 хэша) -
это недальновидно, по причине не исключенной возможности наличия коллизий.

Для решения этой проблемы,
предлагаю идентифицировать посты по паре значений: {Хэш, номер коллизии}.
Если коллизия не найдена, хэш однозначно идентифицирует нанопост (и/или файл-аттач).
Если найдена хотя-бы одна коллизия,
по хэшу возвращается два и более нанопоста (и/или файла-аттача), с номером коллизии.
Тогда, зная номер коллизии,
для однозначной идентификации нанопоста (и/или файла-аттача),
может использоваться пара: {Хэш, номер коллизии}
При этом, номер коллизии - может клеится к хэшу,
формируя единый идентификатор.

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

[username1565]

Оставлю здесь ключевые слова для поиска - "Разрешение коллизий", "Разрешение коллизий в хеш-функциях", "Разрешение коллизий в хеш-таблицах".

[username1565]

В наноборде, в качестве идентификатора нанопоста, используется первая половина sha256-хэша от нанопоста.
Неполный хэш используется видимо для того, чтобы размер ключей не был слишком велик,
по сравнению с короткими нанопостами, вида "Привет", "Как дела?".
Число коллизий хэш-функции, при таком раскладе - растет, разумеется.
Однако, если сменить адресацию нанопостов, она уже не будет обратно-совместимой.

Ранее, я предложил использовать пару {Хэш, номер коллизии},
где номер коллизии - пустое значение, либо номер по порядку (если коллизия была найдена в базе).
При парсинге наноостов из контейнеров в локальной читалке,
очерёдность извлечения нанопостов может быть различной,
поэтому, "номер коллизии", может быть различен в разных базах,
а значит и различные нанопосты, могут выдаваться, из разных баз,
по паре

{ Хэш, номер коллизии}

, которая призвана была бы однозначно идентифицировать нанопосты на всей наноборде.
В качестве решения данной проблемы (неоднозначное идентифицирование разных постов на разных читалках),
подумалось, что вместо "номера коллизии" в паре значений, можно было бы использовать,
второй фрагмент sha256-хэша от нанопоста, склеенный с другим хэшем, скажем md5 хэшем от нанопоста.
Но это не точно. Ведь коллизии всё-равно могут появляться даже при таком раскладе.
Однако, предложенная конструкция

{ хэш(половина хэша), другая половина+md5(нанопоста) }

она была бы обратно-совметимой с предыдущей, одлфажной адресацией нанопостов наноборды,
так как, в случае, если коллизии не обнаружены,
то достаточно идентифицировать нанопосты однозначно - по старой первой половине sha256-хэша.

[username1565]

Тут ещё вот что.

post_hash = sha256(replyTo+message).substring(0, 32)

Это старая схема.
replyTo-хэш может также неоднозначно указывать на пост, если у этого хэша имеются коллизии.
Как тут лучше сделать так, чтобы сохранить обратную совместимость?

Если клеить к replyTo, ещё и вторую часть sha256-хэша, а также md5-хэш,
то обрезаться будут только первые 16 байт с начала,
и если коллизии нет, то в посте будут какие-то кракозябры, в начале поста.
Хотя, впрочем, в нанопостах версии 3.1, в начале постов, следует дата и время, в теге [g][/g],
поэтому всё что идёт до этого тега - можно просто вырезать, походу.

[username1565]

Судя по этой инфе: https://ru.wikipedia.org/wiki/Коллизия_хеш-функции#Разрешение_коллизий_в_хеш-таблицах

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

Было решено, что лучше бороться с коллизиями хэшей - исключением их.

И действительно. Если новый нанопост, хэш которого вычислен, добавляется в базу,
и если существует коллизия (другой пост с таким же хэшем),
достаточно добавить изменить какое-нибудь значение внутри поста, чтобы изменился хэш.
И так, аж пока не получится хэш, котороно нет в хэш-таблице.
Этим значением, может быть значение POW, или значение в теге [g]DateTime[/g] нанопоста.
Достаточно его изменить, и поменяется хэш поста.
Судя по коду вот здесь:

nanoboard/nanodb.exe-source/Captcha/Captcha.cs

Lines 553 to 554 in c15199e

	post = post.ExceptSignature();
	var xpost = ExceptXmg(post);

и здесь:

nanoboard/nanodb.exe-source/Captcha/Captcha.cs

Line 564 in c15199e

hash = ComputeHash(xpost + trash); //Here can be the long chain of different hashes, like sha512hash(sha256hash(SCrypt(Keccak(blake256b(value))))). See WarpWallet: https://keybase.io/warp/

хэш поста считается без xmg-вложений (PNG или ZIP).
C добавлением тега file, новые вложения не удаляются, их следовало бы удалить.

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

Идея черновая, надо имплементировать, разумеется. И на это надо очень, очень, очень, очень - много моих косарей.