Способ прореженного дерева Меркла и система обработки наборов данных для их хранения и отслеживания в конкретной сети Российский патент 2025 года по МПК H04L9/00 G06F16/00 

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

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

Одним из решений, представленных на предшествующем уровне техники, является использование деревьев Меркла. Деревья Меркла позволяют криптографически фиксировать и обновлять набор данных. Каждый фрагмент данных в наборе сначала хэшируется, а затем хэширование выполняется снова для всех данных и полностью по всему дереву, пока не будет достигнут корневой узел. На фиг. 1 каждые данные, такие как транзакция (T_A, T_S, Т_X, T_z), хэшируются для получения хэша транзакции (H(T_A), H(T_S), H(T_X), H(T_Z)). Затем последовательные хэши ((H(T_A), H(T_S)) хэшируются вместе для получения другого хэш-значения (H(H(T_A)||H(T_S)) ... и т.д. и т.п., пока не будет достигнут корневой узел (H(H((H(T_A) || H (T_S)) || H (H (T_X) || H (T_Z))))).

Корнем этого дерева является хэш. Он может использоваться для показа того, что называют доказательством Меркла, то есть, подтверждением того, что некоторый контент является частью дерева. Это обычно называется включением доказательства, Proving Inclusion. Например, чтобы доказать, что T_A является частью дерева, могут использоваться одноуровневые элементы T_A, чтобы повторно вычислить все дерево и провести проверку, совпадают ли позиции. Конечно, с помощью H(T_S) и H(H (T_X)||H (T₂)) легко повторно вычислить исходный корневой хэш и доказать, что T_A является частью дерева. Эта позиция может содержать информацию о соответствующей транзакции, чтобы надежно и эффективно сохранить ее и/или восстановить обратно. Использование дерева Меркла экономит полосу пропускания и действия по обработке в микроконтроллерах и т.п., поскольку нет необходимости сохранять и повторно предоставлять все дерево или весь набор данных.

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

Дерево Меркла однако испытывает недостаток в возможности доказательства, что позиция не является частью дерева. Это обычно называют невключением доказательства, Proving Non-Inclusion.

Одним из решений, представленных на предшествующем уровне, является использование прореженных деревьев Меркла, Sparsed Merkle tree. Прореженное дерево Меркла подобно дереву Меркла, но содержащиеся в нем данные индексируются и каждый пункт данных помещается в лист, соответствующий индексу пункта данных. В примере на фиг. 1 каждый пункт данных может иметь, например, значение ординаты, такое как (A, B, C, D) вместо (T_A, T_S, Т_X, T_Z), соответственно, на фиг. 1. Чтобы доказать, что T_C является или не является частью дерева, может быть, например, проведена дополнительная проверка на индексе ординаты для сравнения с T_D.

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

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

- криптографически хэшируют данные для получения хэш-значений данных;

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

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

- и так до тех пор, пока не будет получено корневое хэш-значение.

В соответствии с первым подходом, реализуемый компьютером способ характеризуется этапами, на которых

- делят по меньшей мере одно из хэш-значений на несколько секций рым-ключей с заданной разрядной шириной (разрядностью); и

- определяют рым-ключи листов (листьевые рым-ключи), являющихся архивными листьями прореженного дерева Меркла, и родительские рым-ключи, поддерживающие создание субдерева.

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

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

Согласно другим подходам способа, применяемого индивидуально или комбинированно в любом технически возможном сочетании:

- способ содержит создание субдерева на родительском рым-ключе, если архивированные данные имеют тот же рым-ключ, что и родительский рым-ключ и/или;

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

- по меньшей мере одно субдерево является вектором хэша с заданным индексом и/или;

- индекс является соответствующим рым-ключом и/или;

- разрешенное дерево Меркла содержит векторы хэшей и/или;

- данные являются транзакциями.

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

В более общем плане, изобретение дополнительно связано с системой обработки наборов данных для их хранения и отслеживания в конкретной сети, причем система реализует прореженное дерево Меркла и система содержит:

- средства криптографического хэширования данных для получения хэш-значений данных;

- средства криптографического хэширования последовательных хэш-значений данных, чтобы получить объединенные хэш-значения первой стадии;

- средства криптографического хэширования объединенных хэш-значений первой стадии для получения объединенных хэш-значений второй стадии;

- средства для получения корневого хэш-значения.

В соответствии с первым подходом, система отличается тем, что содержит

- средства деления по меньшей мере одного хэш-значения на несколько разделов (секций) рым-ключей с заданной разрядной шириной; и

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

Преимущества способа, упомянутые выше, также применяются к системе, реализующей способ.

В соответствии с другими подходами системы, применяемыми индивидуально или объединенно в любом технически возможном сочетании:

- система содержит средства создания субдерева на родительском рым-ключе, если архивированные данные имеют тот же самый рым-ключ, что и родительский рым-ключ; и/или;

- система содержит средства деления нескольких хэш-значений, предпочтительно, каждого хэш-значения, на несколько разделов хэш-ключей с заданной разрядной шириной и/или;

- по меньшей мере одно субдерево является вектором хэша заданного индекса и/или;

- индекс является соответствующим рым-ключом и/или;

- прореженное дерево Меркла содержит векторы хэшей.

Изобретение также относится к базе данных, содержащей средства хранения и отслеживания в конкретной сети наборов данных, обрабатываемых посредством способа, соответствующего изобретению, или посредством системы, соответствующей изобретению.

В более общем плане, изобретение также относится к базе данных для хранения и отслеживания наборов данных в конкретной сети, реализуя прореженное дерево Меркла, содержащее

- хэш-значения данных, полученные путем криптографического хэширования данных;

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

- объединенные хэш-значения второй стадии, полученные посредством криптографического хэширования некоторых объединенных хэш-значений первой стадии:

…

- корневое хэш-значение,

отличающееся тем, что

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

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

Преимущества, упомянутые выше, способа и системы также применяются к базе данных, содержащей соответствующие данные.

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

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

Фиг. 1 – прореженное дерево Меркла согласно способу, соответствующем предшествующему уровню техники;

Фиг. 2A - пример раздела иерархических прореженных деревьев Меркла согласно способу, соответствующему варианту осуществления изобретения;

Фиг. 2B - вектор прореженных деревьев Меркла в способе, показанном на фиг. 2A;

Фиг. 2C – система, соответствующая варианту осуществления изобретения;

Фиг. 3A - лист транзакций с хэш-значениями;

Фиг. 3B - пример того, как транзакции, показанные на фиг. 3A, архивируются в иерархических субдеревьях; и

Фиг. 4 – графическая иллюстрация базы данных, соответствующей варианту осуществления изобретения.

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

Более конкретно, изобретение относится к хранению и отслеживанию транзакций в конкретной сети.

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

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

Более конкретно, изобретение направлено на эффективное удаление и добавление транзакций безопасным и распределенным способом. В более общем плане, изобретение относится к системе CRUD (Create, Read, Update, Delete (создать, считать, обновить, удалить)) с DHT (Distribute Hash Table, распределенная хэш-таблица).

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

Изобретение реализуется в системе 1a на компьютерной основе, позволяющей иметь распределенный архив произвольных транзакций (Distribute Archive of Random Transactions, DART). Таким образом систему можно назвать системой DART, а способ - способом DART.

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

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

В предпочтительном варианте осуществления значение h может быть получено по формуле:

,

Уравнение 1

где

H – криптографическая хэш-функция,

N – количество битов хэш-значения h.

Затем

Уравнение 2

где b_i означает i-ый бит хэш-значения h.

В соответствии с первым подходом, способ изобретения содержит этап деления по меньшей мере одного из хэш-значений на множество разделов рым-ключей (L, A) с заданной разрядной шириной. Способ дополнительно содержит этап определения рым-ключей L листов, являющихся архивными листьями прореженного дерева Меркла, и родительских рым-ключей А, поддерживающих создание субдерева (subtree, SMT).

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

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

Уравнение 3

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

В частности, разрядная ширина рыма, равна, например, K. Каждый лист в дереве выражается через рым-индекс, называемый рым-ключом. Максимальное количество ветвей определяется как k и, таким образом:

Уравнение 4

Если разрядная ширина М разделов выбирается как количественный множитель C числа K, рым-ключ может быть выражен следующим образом:

Уравнение 5

Раздел может быть выражен как первые C рым-ключей

Уравнение 6

Из этого может быть сформировано хэш-значение h

Уравнение 7

Фиг. 2A и 2B могут использоваться для иллюстрации варианта осуществления изобретения. Они показывают пример раздела иерархических прореженных деревьев Меркла. Рымы маркируются как R_C для рыма C и R_C+1 для последующего рыма.

Когда транзакция хранится в системе DART, хэш-значение h вычисляется и хэш-значение делится на разделы рым-ключей (L, A).

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

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

В соответствии с вариантом осуществления, способ содержит создание субдерева (SMT) на родительском рым-ключе А, если архивированные данные имеют тот же самый рым-ключ, что и родительский рым-ключ A.

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

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

Более того, хэш может быть вычислен из архивированных данных. В нашей реализации векторный элемент может содержать либо

- хэш, содержащий ветвь субдерева; либо

- архивированные данные.

Предпочтительно иметь минимальное количество узлов для хранения в одном полном разделе.

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

На фиг. 2A показана иерархическая древовидная структура. Белые поля A являются хэш-значениями прореженного дерева Меркла. Заштрихованные поля являются архивными листьями L. Круги являются субдеревьями прореженного дерева Меркла. На фиг. 2B показан вектор SMT.

Пример, показанный на фиг. 3A и 3B, показывает, как лист транзакции архивируется в древовидную структуру.

Поскольку самые современные вычисления основаны на многочисленных 8-битовых элементах (байтах), в этом примере k=8 и C=2.

Предположим, что лист транзакций задан с хэш-значениями, перечисленными на фиг. 3A. На чертеже стрелки указывают ветвь или архив (Archive). Если разделением рыма является ветвь, если нет, то это архив. Архивом является лист (Leave). На чертеже жирный пунктирный символ означает хэш ветви. Если ни одного такого символа нет, то это означает, что в архиве хэш вычисляется из данных, находящихся в архиве.

На фиг. 3B показано, где архивы транзакций размещаются в древовидной структуре.

На фиг. 3B заштрихованные квадраты являются хэш-значениями SMT субветви; другие квадраты являются рым-ключами памяти (Brance). Элемент вектора субдерева может содержать Brance (который указывает на субдерево) или архив, который содержит данные архива. Рымы маркируются как R_0 для первого рыма и R_1 для следующего рыма.

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

Полная база данных может быть показана как круговая структура на фиг. 4. Каждый черный прямоугольник представляет структуру, показанную на фиг. 2A и все в центре данных показывает дерево Меркла для всей базы данных.

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

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

Поскольку численное значение хэшей заказывается вокруг круга.

Например, максимальное значение 256 хэшей равняется 2²⁵⁶-1.

Числовое значение сворачивается от 2²⁵⁶-1 до 0. Это означает, что оно может быть графически представлено на круге.

Раздел должен управляться более, чем Q узлами, чтобы поддерживать избыточность и безопасность данных.

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

Пример DART показан на фиг. 4. Архивы (транзакции) хранятся в иерархической древовидной структуре. Архивы хранятся как листья дерева. CN относится к узлам с их номерами. "sSMT" относится к деревьям Меркла разделов. "cSMT" относится к центральным деревьям Меркла. "sH" относятся к хэшу раздела (Sector Hash), "be" относится к мишени (bullseye).

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

В дальнейшем способ описывается как способ вычисления дерева Меркла эффективным способом.

Приведенная ниже функция определяет хэш-функцию двух пар значений.

для остальных

Уравнение 8

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

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

Уравнение 9

Хэш-функция вектора может быть определена как

для k > 2

прочие

Уравнение 10

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

Примеры некоторых вычислений

Пример 1

Значение нулевого вектора приведет в результате к значению 0, которое также доказывает, что SMT пуст.

Пример 2

Если вектор V (0, k) имеет только одно значение h_i, которое не равно нулю, то тогда значение будет равно h_i.

Уравнение 11

Пример 3

Если только вектор V_{(0, k)} содержит два и только два ненулевых значения h_i и h_j, то вычисление может быть следующим:

Уравнение 12

Пример 4

Уравнение 13

Это дает в результате следующее хэш-значение

Уравнение 14

Как пример, чтобы сравнить обычные вычисления дерева Меркла со способом SMT, используем пример 4*10⁹≈2³² архивов, хранящихся в базе данных. В худшем случае, это составит 4*10⁹ хэш-операций.

С высокой степенью вероятностью архив может храниться в рыме 4 и архив, хранящийся в рыме 4, может составлять приблизительно 4*256≈1000.

Изобретение дополнительно относится к системе 1a для реализации способа, как описано выше. Система 1a является компьютеризированной системой и содержит внутренне присущие ей аппаратные и программные модули, выполненные с возможностью реализации способа, описанного выше. Это может называться системой 1а DART. Система позволяет обрабатывать наборы данных для их хранения и отслеживания в конкретной сети, причем система содержит средства выполнения этапов способа, соответствующего изобретению.

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

В соответствии с первым подходом, система содержит

- средства деления по меньшей мере одного хэш-значения на несколько рым-ключей с заданной разрядной шириной; и

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

Система выполнена с возможностью исполнения соответствующей операции(-ий) посредством микроконтроллера и модулей программного и аппаратного обеспечения.

Преимущества способа, упомянутые выше, также применимы к системе, реализующей способ.

Изобретение относится также к базе 2a данных, содержащей средства хранения и отслеживания в конкретной сети наборов данных, обрабатываемых посредством способа, описанного выше, или посредством системы, описанной выше. Она можно называться базой 2а данных DART. База данных содержит один или более микроконтроллеров, аппаратных и программных модулей, известных специалисту в данной области техники, но, однако, конфигурированных для реализации изобретения.

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

В дополнение к этому, база данных содержит

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

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

Преимущества, упомянутые выше для способа и системы 1a, также применимы к базе данных, содержащей соответствующие данные.

Другой задачей изобретения является сеть, содержащая один или более центральных блоков 3a, в частности, один или более компьютеризированных центральных блоков и соединение(-я) 4a с дополнительными командными блоками 5a, реализующими транзакции, в частности, компьютеризированные командные блоки, причем центральный блок(-и) 3a содержит систему la и базу 2a данных, как описано выше. Это может называться сетью DART. Сеть может быть соединена через Интернет с дополнительными командными блоками.

Изобретение относится к способу обработки наборов данных для их хранения и отслеживания в конкретной сети, реализующий прореженное дерево Меркла. Технический результат заключается в оптимизации хранения данных транзакций. В способе выполняют этапы, на которых: криптографически хэшируют наборы данных для получения хэш-значений наборов данных; когда это применимо, криптографически хэшируют последовательные хэш-значения наборов данных для получения объединенных хэш-значений первой стадии; когда это применимо, криптографически хэшируют объединенные хэш-значения предыдущей стадии для получения объединенных хэш-значений последующей стадии до получения корневого хэш-значения, при этом разделяют по меньшей мере одно из хэш-значений на несколько секций, содержащих ключи уровней иерархии деревьев Меркла (далее – рым-ключи) заданной разрядности; определяют листья прореженного дерева Меркла, соответствующие архивированным данным в распределенной хэш-таблице (далее – листьевые рым-ключи), и узлы ветвления прореженного дерева Меркла, поддерживающие создание субдерева (далее – родительские рым-ключи); и создают субдерево на каждом родительском рым-ключе, при этом по меньшей мере одно субдерево содержит более двух ветвей. 3 н. и 9 з.п. ф-лы, 7 ил.

1. Реализуемый компьютером способ обработки наборов данных для их хранения и отслеживания в конкретной сети, реализующий прореженное дерево Меркла и содержащий этапы, на которых:

- криптографически хэшируют наборы данных для получения хэш-значений наборов данных;

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

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

отличающийся тем, что:

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

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

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

2. Способ по п. 1, в котором субдерево на родительском рым-ключе создают, если архивированные данные имеют тот же самый рым-ключ, что и родительский рым-ключ.

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

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

5. Способ по п. 4, в котором прореженное дерево Меркла содержит векторы хэшей.

6. Способ по любому из пп. 1-5, в котором наборы данных представляют транзакции.

7. Система обработки наборов данных для их хранения и отслеживания в конкретной сети, выполненная с возможностью реализации прореженного дерева Меркла и содержащая:

- средство криптографического хэширования наборов данных для получения хэш-значений наборов данных;

- средство криптографического хэширования последовательных хэш-значений наборов данных для получения объединенных хэш-значений первой стадии;

- средство криптографического хэширования объединенных хэш-значений предыдущей стадии для получения объединенных хэш-значений последующей стадии;

- средство получения корневого хэш-значения,

отличающаяся тем, что содержит:

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

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

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

8. Система по п. 7, в которой средство создания субдерева выполнено с возможностью создания субдерева на родительском рым-ключе, когда архивированные данные имеют тот же самый рым-ключ, что и родительский рым-ключ.

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

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

11. Система по любому из пп. 7-10, в которой прореженное дерево Меркла содержит векторы хэшей.

12. Сеть, содержащая один или несколько центральных блоков и одно или несколько соединений с одним или несколькими дополнительными командными блоками, выполненными с возможностью реализации транзакций, причем центральный блок содержит систему, охарактеризованную в любом из пп. 7-11, и базу данных, содержащую:

- хэш-значения наборов данных, полученные посредством криптографического хэширования наборов данных;

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

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

- корневое хэш-значение; и

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