Topic: Вопрос по хешированию таблицы базы данны&#109 (Read 1818 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/ Вроде все реально, поэтому кому интересно почитайте.

Если в одной записи будет порядка 100 байт * миллиард записей ~ 100Гб данных.
Прокачать с диска на обычном компьютере за минуту  - нереально.

Да, Вы именно правильно поняли. Я рад, что такие вещи уже есть. Однако для полных нод Биткоина такой блокчейн именно не подойдет, по причине того, что биткоин реализован на алгоритме консенсуса POW. В котором предусмотрено постоянное появление форков и побеждает именно самая длинная цепочка. Если же криптовалюта будет реализована на другом алгоритме консенсуса, например, на POA https://bitcointalksearch.org/topic/poa-proof-of-auction-1934810 где предусмотрен однозначный результат и форки исключены, то это именно то что нужно, т.к. нет смысла хранить историю всех транзакций.

Спасибо, что помогли разобраться с вопросом.

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

Т.е. я так понимаю, что уже сейчас это реально.

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

Это ж какая экономия по памяти для блокчейна будет.

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

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

Если немного изменить алгоритм, можно использовать параллельные вычисления, это даст возможность увеличить производительность во много раз, при наличии вычислительных мощностей (много процессоров или ASIC).

Хорошо тогда я задам вопрос по конкретнее. Хеш всей данной таблицы нужен чтобы завиксировать или появления/удаления новых строк или изменения балансов.

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

Нужно считать. Вполне вероятно, что можно. Хэши (хэш-функции) бывают разные, требуют разное время для вычисления. поэтому нужно говорить конкретнее, какая будет использоваться хэш-функция. Также конечно всё зависит от вычислительной мощности машины, процессора. Эту задачу можно выполнять в многопоточном режиме, поэтому скорость можно увеличить в разы при многопроцессорном вычислении. Также имеет значения скорость выборки из базы - какая база, какой сервер базы данных, с какой скорость происходит выборка 1 миллиарда записей? Во многих базах есть встроенный функционал подобных вычислений. Поэтому нужно конкретно всё это проанализировать и посчитать.  Теоритически посчитать хэш миллиарда подобных записей за минуту вполне возможно.

Господа перерыл весь интернет, но так и не смог найти ответ на свой вопрос. Поэтому, если есть возможность, то прошу вашего ответа.

Итак у нас есть только одна таблица базы данных вида:

id/            adress           /summ/name        /
1/77rteyueruerurturrurtuy/70     /NULL        /
2/75rteyuerue55rturrurtuf/100    /Detskii Mir/

и таких строк около миллиарда.

Можно ли в течении 1 минуты получить хеш всей этой таблицы?