Topic: Вопрос по хешированию таблицы базы данны&#109 (Read 1817 times)

Подойдет любое аддитивное хеширование, например XOR{по всем строкам} от SHA256(данных строки)

Соответственно, при добавлении или удалении строк нужно пересчитывать только измененные данные.
Плюсом будет, что добавление, а затем удаление той же строки через любое время возвращает хеш к исходному (если не менялись другие строки). Еще один плюс, что SHA256 (или другой внутренний хеш) можно считать в параллель, а уже потом только XOR'ить.

А так, верно написали, за минуту 100Гб даже с диска не загрузить.

Согласен с вами (:

Да, структурирование данных в дерево Меркля затрачивает много ресурсов, но поскольку в биткойне был заложен алгоритм PoW - то там это было как бы к месту. Есть и другие, боле быстрые способы контроля целостности данных. Но в дереве Меркля важно то, что контролируется не только сами данные, но и  структура самого дерева, которая может быть полезной при восстановлении данных. Например, берется контрольная сумма от объёмного каталога файлов. Нам нужно проверить его целостность. Если мы видим, что контрольная сумма не совпадает - то можно спуститься по дереву на один уровень ниже и проверить два хэша - в случае повреждения одного файла в нашем каталоге один из хэшей нижележащего уровня будет совпадать, а другой нет. Далее мы опять спускаемся на один уровень, но только там, где хэш не совпадает. Таким образом мы очень быстро доберёмся до повреждённого файла.  Поскольку там получается степенная функция, то проход по дереву Меркля для поиска повреждённых данных занимает всегда очень мало времени. Буквально за несколько проверок хешей мы можем найти повреждённый файл, даже если этих файлов триллионы. Таким образом, алгоритм Меркля "долго" хеширует, но быстро находит повреждённые данные. И конечно, таким образом можно искать не только повреждённые, но и просто изменённые файлы.

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

Бла-бла-бла.
Поймите. Дерево Меркла - это технология, которую Сатоши использовал для биткойна.
Можно ей рассматривать и отдельно. Забудьте про биткойн и SPV
Вернитесь к первому посту топика
Может быть вам это и нужно?

Если судить из этой статьи https://habrahabr.ru/post/320176/, то это дерево нужно

Это не смысл. Точнее - смысл не в этом.
Смысл в том, что если у нас был посчитан блок с 1000 транзакциями,
а потом нам захотелось к блоку добавить 1001-ую, то
1) не надо всё заново пересчитывать, а пересчитывается сравнительно немного (ну это и так понятно)
2) что-то там связанное с поиском транзакций (вот это мне самому непонятно, но я не старался понять)

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

Мне тоже кажется это не совсем рационально, слишком много операций, уверен, что можно как-то сразу сложить хеши всех транзакций и найти конечный хеш.

В блокчейне используется меркль-хэш
Я не особо понял в чем его прелесть, но как раз и решается проблема хэширования большого количества
записей (транзакций в блоке) без необходимости пересчета хэша всего блока (мегабайта)
Подробнее расписать не могу, сам не особо въехал.

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

От языка сильно зависит... В Python 3.6 появился весьма быстрый алгоритм BLAKE2

Если этот способ делает тоже самое, что я хотел, то можно и так. Смысл именно в модифицированном блокчейне.

Поясните, чем плох такой блокчейн?

наверное можно, но зачем!? это мне напомнило статью с вредными советами "как достичь хайлоада на ровном месте"

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

В этой теме https://bitcointalksearch.org/topic/m-1949631 я предлагаю новую криптовалюту с новым алгоритмом консонсуса POA и измененным блокчейном. Именно здесь я и спрашивал, а возможно ли такое. Теоретическая возможность есть, если не получиться, то не проблема вернуться к старому надежному блокчейну обычного типа.

В лоб всю таблицу захешировать будет долго. Можно оптимизировать.
Если таблица растет только снизу по порядковому номеру, то можно разбить на пачки по 1000 записей (1млн. пачек). Вычислить хеши каждой пачки и запомнить в отдельной таблице. И от них посчитать хеш всей таблицы

Новых блок изменит значения примерно 10 тысяч адресов. Надо будет пересчитать только хеши тех пачек, куда эти адреса попали.  Для этого потребуется загрузить максимум 10000 пачек*1000строк*100байт - 1ГБ данных. Что выглядит уже более реально.  (вместо 100гб)

Это первое, что пришло в голову. Думаю, что далеко не самый оптимальный.
Может стоить почитать литературу, наверняка, такие алгоритмы уже разработаны.

Большое спасибо за ответ.

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

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


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

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

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


Я вот тут в Гугле порылся и откапал неплохую темку "Как посчитать контрольную сумму?" https://php.ru/forum/threads/kak-poschitat-kontrolnuju-summu.8039/ Вроде все реально, поэтому кому интересно почитайте.