СИСТЕМА ВЕРИФИЦИРУЕМОГО ОТСЕЧЕНИЯ РЕЕСТРОВ Российский патент 2023 года по МПК H04L9/32 

Область техники, к которой относится изобретение

Настоящее изобретение относится к системе отсечения реестров, и, в частности, к системе верифицируемого отсечения реестров.

Уровень техники

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

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

В настоящее время, эфириум имеет скорость обработки в 20 транзакций (Тх)/секунда, а биткоин имеет скорость обработки в 7 Тх/сек. В случае эфириума, ежегодно накапливаются данные в 250 ГБ.

В будущем, эфириум может иметь более высокую скорость обработки транзакций. Например, в механизме реестров для цепочек транзакций на уровне счетов (AWTC) с использованием направленного ациклического графа (DAG), который имеет еще более высокую скорость обработки транзакции, чем цепочка блоков, также можно устанавливать цель в 4 кТх/сек в будущем.

При скорости обработки транзакций в 4 кТх/сек, размер распределенного реестра, производимого ежедневно как 0,5 кбайт/Тх * 4 кТх/сек * 60 сек/мин * 60 мин/час * 24 часа/день, становится равным 172,8 ГБ/день.

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

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

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

Следовательно, может возникать предел при эффективном управлении реестрами только с существующим отсечением.

Сущность изобретения

Техническая задача

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

Техническое решение

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

Здесь, система верифицируемого отсечения реестров может быть выполнена дополнительно включающей в себя модуль верификации целостности узлов, в котором последнее корневое хеш-значение перекошенного дерева Меркла вычисляется посредством последовательного выполнения операции с хеш-значениями посредством использования T_k и предварительно определенного корневого хеш-значения h(T_i) (здесь, k<i<=n) перекошенного дерева Меркла, чтобы верифицировать то, включается или нет предыдущий предварительно определенный блок T_k данных в перекошенное дерево Меркла, и сравнивается то, совпадают или нет вычисленное последнее корневое хеш-значение и заранее известное последнее корневое хеш-значение для того, чтобы проверять целостность блока T_k.

Согласно второму варианту осуществления, система верифицируемого отсечения реестров может быть выполнена включающей в себя модуль создания иерархических (h-)перекошенных деревьев Меркла, в котором согласно схеме связанных списков, корневое хеш-значение R_n-1 предыдущего поддерева включается в блок T_n данных, блок T_n данных, в который включается корневое хеш-значение R_n-1, хешируется, за счет этого получая h(T_n), полученное h(T_n) и корневое хеш-значение R_n-1 предыдущего поддерева и ссылки R_{n-(base^offset)} перехода объединяются и затем хешируются, за счет этого получая h(h(T_n)|R_n-1|R_{n-(base^offset)}, и полученное h(h(T_n)|R_n-1|R_{n-(base^offset)}) последовательно прибавляется к соответствующим узлам двоичной древовидной структуры Меркла, чтобы разворачивать и создавать h-перекошенное дерево Меркла.

Здесь, ссылка R_{n-(base^offset)} перехода может представлять собой корневое хеш-значение для узла в предварительно определенное предыдущее время на h-перекошенном дереве Меркла, основание base может представлять собой кратчайшее расстояние предварительно определенной ссылки перехода, чтобы выделять ссылку перехода с предварительно определенным интервалом, и смещение offset может составлять местоположение n текущего узла % основание.

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

Между тем, модуль создания h-перекошенных деревьев Меркла может быть выполнен с возможностью выделять ссылку перехода каждого узла offset+(base^offset)*k.

В этом случае, k может быть сконфигурирован посредством положительного целого числа.

С другой стороны, система верифицируемого отсечения реестров может быть выполнена дополнительно включающей в себя модуль верификации целостности узлов, в котором последнее корневое хеш-значение h-перекошенного дерева Меркла вычисляется посредством последовательного выполнения операции с хеш-значениями посредством использования T_k и предварительно определенного корневого хеш-значения h(T_i) (здесь, k<i<=n) h-перекошенного дерева Меркла, чтобы верифицировать то, включается или нет предыдущий предварительно определенный блок T_k данных в h-перекошенное дерево Меркла, и сравнивается то, совпадают или нет вычисленное последнее корневое хеш-значение и заранее известное последнее корневое хеш-значение для того, чтобы проверять целостность блока T_k.

Здесь, модуль верификации целостности узлов может быть выполнен с возможностью верифицировать то, существует или нет хеш-значение R_y или блок T_y данных в h-перекошенном дереве Меркла, согласно следующей процедуре, и 1) поиск ссылки перехода или ссылки (узла), которая существует в ближайшее предыдущее время, из числа ссылок (узлов), которые находятся в идентичное время или дальше в будущем, чем R_y, на основе ссылки (узла) в пределах предварительно определенного расстояния в направлении предыдущего времени от последнего корневого хеш-значения R_head, 2) поиск ссылки перехода или ссылки (узла), которая существует в ближайшее предыдущее время, из числа ссылок (узлов), которые находятся в идентичное время или дальше в будущем, чем R_y, на основе ссылки (узла) в пределах предварительно определенного расстояния в направлении предыдущего времени от хеш-значения ссылки перехода или ссылки, которая существует в искомое ближайшее предыдущее время, 3) повторение процесса 2) до достижения R_y, 4) вычисление корневых хешей, направленных в будущем направлении последовательно для набора ссылки перехода или ссылки (узла), искомого многократно в процессах 2) и 3) посредством использования T_y, и 5) сравнение того, равно или нет конечное полученное корневое хеш-значение R_head, и верификацию того, что хеш-значение R_y или блок T_y данных существует в h-перекошенном дереве Меркла, когда конечное полученное корневое хеш-значение равно R_head в качестве результата сравнения.

Здесь, предварительно определенное расстояние может составлять основание.

Преимущества изобретения

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

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

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

Краткое описание чертежей

Фиг. 1 является блок-схемой системы верифицируемого отсечения реестров согласно варианту осуществления настоящего изобретения.

Фиг. 2 является структурной схемой существующего дерева Меркла.

Фиг. 3 и 4 являются концептуальными схемами алгоритма создания перекошенных деревьев Меркла согласно варианту осуществления настоящего изобретения.

Фиг. 5 и 10 являются концептуальными схемами алгоритма создания h-перекошенных деревьев Меркла согласно варианту осуществления настоящего изобретения.

Оптимальный режим осуществления изобретения

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

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

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

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

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

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

Фиг. 1 является блок-схемой системы верифицируемого отсечения реестров согласно варианту осуществления настоящего изобретения, фиг. 2 является структурной схемой существующего дерева Меркла, фиг. 3 и 4 являются концептуальными схемами алгоритма создания перекошенных деревьев Меркла согласно варианту осуществления настоящего изобретения, и фиг. 5 и 10 являются концептуальными схемами алгоритма создания h-перекошенных деревьев Меркла согласно варианту осуществления настоящего изобретения.

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

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

Как проиллюстрировано на фиг. 2, дерево Меркла используется для верификации того, что хеш-значение (например, H₆, H₇, H₈, корень) для любых данных (например, H₁, H₂, H₃, H₄, H₅) включается в дерево Меркла. Иными словами, верификация осуществляется посредством вычисления хеш-значения по маршруту вплоть до корневого узла. Верификация осуществляется, когда конечное вычисляемое значение совпадает с корневым хеш-значением. Например, чтобы проверить H₁, верификация делается, когда результат вычисления и проверки хеш-значения по маршруту посредством использования H₂ и H₈ совпадает с корневым хеш-значением.

Тем не менее, при использовании механизма верификации с использованием дерева Меркла, размер данных хеш-значения (H₆, H₇, H₈, корень) является небольшим, но исходные данные (H₁, H₂, H₃, H₄, H₅) могут иметь относительно очень большой размер данных.

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

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

Когда предполагается, что система распределенных реестров имеет скорость обработки транзакций в 4 кТх/сек в день, только данные в 172,8 ГБ, которые представляют собой данные, собранные за один день, сохраняются, и все оставшиеся предыдущие данные отсекаются, и данные, в отношении которых выполнено отсечение, приспособлены идеально проверять целостность посредством использования сохраняемых данных, т.е. корневого хеш-значения перекошенного дерева Меркла.

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

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

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

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

Модуль 110 создания перекошенных деревьев Меркла может быть выполнен с возможностью вычислять корневое хеш-значение каждого узла посредством h(h(T_n)|R_n-1) и последовательно сохранять корневое хеш-значение в каждом узле, чтобы расширять и формировать перекошенное дерево Меркла.

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

Помимо этого, h(T_n) вычисляется посредством хеширования T_n, вычисленное h(T_n) и корневое хеш-значение R_n-1 предыдущего поддерева прибавляются и затем хешируются снова, чтобы вычислять h(h(T_n)|R_n-1); h(h(T_n)|R_n-1) последовательно сохраняется в перекошенном дереве Меркла.

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

На фиг. 3, хеш-значение R₁ представляет собой хешированное значение посредством прибавления T₁, который представляет собой первый блок данных, и начального корневого хеш-значения R₀. Помимо этого, хеш-значение R₂ представляет собой значение, полученное посредством хеширования T₂, который представляет собой второй блок данных, и самого давнего корневого хеш-значения R₁. Поскольку самое давнее корневое хеш-значение R₁ включается в T₂ посредством механизма связанных списков, T₂ и R₁ хешируются, чтобы вычислять R₂. R₂ прибавляется к блоку T₃ данных посредством такого механизма, чтобы расширять и формировать перекошенное дерево Меркла посредством повторения такого процесса.

Между тем, модуль 130 верификации целостности узлов по фиг. 1 может быть выполнен с возможностью верифицировать целостность для предыдущего конкретного узла на перекошенном дереве Меркла.

На фиг. 4, чтобы верифицировать то, включается или нет T₂ в перекошенное дерево Меркла, R₄, включенный в T₄, получается из T₄, который представляет собой последний блок данных перекошенного дерева Меркла. Помимо этого, для верификации, R₁, включенный в T₂, получается из данного T₂. Помимо этого, h(T₂) вычисляется посредством хеширования T₂, и когда R₁ и h(T₂) прибавляются и хешируются, R₂ может вычисляться.

Здесь, если хеш-значение h(T₃) T₃ является заранее известным, R₃ может вычисляться посредством идентичного механизма, и если h(T₄) также является заранее известным, R₄ может вычисляться посредством использования R₃. Если вычисленное R₄ равно R₄, полученному выше, можно верифицировать то, что соответствующий узел, который представляет собой узел T₂, который должен верифицироваться, включается в перекошенное дерево Меркла.

Иными словами, верификация T₂ обеспечивается в том случае, если только h(T₃) и h(T₄) известны в перекошенном дереве Меркла.

Когда это обобщается и применяется, модуль 130 верификации целостности узлов может верифицировать целостность T_k, если только последнее корневое хеш-значение R_n и хеш-значение h(T_i) (здесь, k<i<=n) блока данных на промежуточном этапе являются заранее известными, чтобы верифицировать блок T_k данных конкретного узла в перекошенном дереве Меркла.

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

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

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

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

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

Каждое значение R_n узла h-перекошенного дерева Меркла, которое дополнительно обладает ссылкой перехода по фиг. 5, может организовываться в качестве h(h(T_n)|R_n-1|R_{n-(base^offset)}).

Здесь, R_{n-(base^offset)} представляет ссылку перехода, которая представляет собой хеш-значение узла в любое предыдущее время.

Основание base в ссылке перехода представляет собой кратчайшее расстояние предварительно определенной ссылки перехода, чтобы выделять ссылку перехода с предварительно определенным интервалом. Если основание равно 3, ссылка перехода выделяется с интервалом в три узла.

Помимо этого, смещение offset представляет собой значение остатка от значения, полученного делением местоположения n текущего узла на основание, т.е. n % base.

Помимо этого, расстояние dist от местоположения n текущего узла до ссылки перехода может вычисляться как значение base^offset.

Фиг. 5 иллюстрирует ссылку перехода, в которой основание равно 3, и смещение равно 1.

Ссылаясь на фиг. 5, расстояние ссылки перехода в качестве base^offset, т.е. 3¹ равно 3.

Что касается узла R₄, можно видеть, что значение R₄ может получаться посредством прибавления и хеширования хеш-значения T₄ и непосредственно предшествующего хеш-значения R₃ и ссылки R₁ перехода.

Фиг. 6 иллюстрирует ссылку перехода, в которой основание равно 3 и смещение равно 2.

На фиг. 6, можно видеть, что расстояние ссылки перехода в качестве 3² становится 9.

Тем не менее, ссылка перехода не должна обязательно выделяться всем узлам, в которых смещение равно 2. Как проиллюстрировано на фиг. 7, ссылка перехода может выделяться только узлу offset+(base^offset)*k в местоположении n узла. В данном документе, k представляет положительное целое число. Ссылка перехода может не выделяться узлу, отличному от вышеуказанного узла.

Как проиллюстрировано на фиг. 7, если основание равно 1 и смещение равно 1, 1+3¹*k, и ссылка перехода выделяется для R₁₉, R₁₃, R₁₀, R₇, R₄, R₁. Помимо этого, если основание равно 3 и смещение равно 2, 2+3²*k, и ссылка перехода выделяется для R₂₀, R₁₁, R₂. Если основание равно 3 и смещение равно 3, то ссылка перехода должна выделяться для R₅₇, R₃₀, R₃.

Фиг. 8 иллюстрирует состояние, в котором выделение ссылки перехода по фиг. 7 завершается. Выделение ссылки перехода многократно выполняется до тех пор, пока каждое смещение не достигает основания.

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

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

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

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

3) Вычисляется корневой хеш, который направлен в будущем направлении последовательно для набора искомых ссылок посредством использования T_y. Если конечный результат вычисления равен R_head, верификация завершается и верифицируется то, что R_head существует в h-перекошенном дереве Меркла.

Фиг. 9 иллюстрирует то, что R₈ обнаруживается для того, чтобы проверять T₈, начиная с R₅₉.

Ссылаясь на фиг. 9, R_head составляет R₅₉, ссылки (узлы) R₅₈ и R₅₇ вплоть до соответствующего расстояния в R₅₉, т.е. расстояния основания 3, ссылаются на значения, и ближайшая предыдущая ссылка R₃₀, которая находится дальше в будущем, чем R₈, находится и опрашивается из числа ссылок перехода с расстоянием смещения в 3 из R₅₇, т.е. 3³.

Здесь, ссылка (узел) R₂₉, вплоть до соответствующего расстояния, т.е. расстояния основания 3, опрашивается снова. Ссылка перехода с расстоянием смещения в 2, т.е. 3², и ссылка R₁₁ перехода ссылки R₂₀ перехода находится и опрашивается из R₂₉ снова. Ссылка R₁₁ перехода становится ближайшей предыдущей ссылкой, которая находится дальше в будущем, чем R₈, из числа ссылок перехода смещения в 2 на основе R₂₉.

Помимо этого, каждая из ссылок R₁₀, R₉ и R₈ в пределах соответствующего расстояния находится из R₁₁ снова, с тем чтобы в итоге достигать R₈.

Помимо этого, корневое хеш-значение последовательно вычисляется в будущем направлении снова посредством использования T₈, которое должно проверяться. Если конечное вычисленное корневое хеш-значение совпадает с R₅₉ на h-перекошенном дереве Меркла, верифицируется то, что T₈ существует в h-перекошенном дереве Меркла.

В этом процессе, в сумме 9 рабочих этапов требуются от R₈ до R₉, R₁₀, R₁₁, R₂₀, R₂₉, R₃₀, R₅₇, R₅₈ и R₅₉. Тем не менее, когда ссылка перехода не используется, все узлы R₈-R₅₉ должны рассчитываться, и, в качестве результата, требуется всего 51 рабочий этап. Можно видеть, что рабочие этапы значительно уменьшаются, и когда размер реестра увеличивается, значительный объем расчетов и значительное время расчетов могут уменьшаться.

Фиг. 10 в качестве примера фактической реализации иллюстрирует h-перекошенное дерево Меркла, в котором основание равно 10. Поскольку ссылка перехода 10offse^t, расстояние ссылки перехода увеличивается до 10, 10² и 10³, и когда расстояние равно 1999, достижение является возможным только посредством 28 этапов.

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

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

Изобретение относится к области обработки данных. Технический результат заключается в обеспечении системы верифицируемого отсечения реестров, в которой структура реестров сконфигурирована как перекошенное дерево Меркла. Согласно схеме связанных списков, корневое хеш-значение R_n-1 предыдущего поддерева включается в блок T_n данных. Блок T_n данных, в который включается корневое хеш-значение R_n-1, хешируется, за счет этого получая h(T_n). Полученное h(T_n) и корневое хеш-значение R_n-1 предыдущего поддерева объединяются и затем хешируются, за счет этого получая h(h(T_n)|R_n-1). Полученное h(h(T_n)|R_n-1) последовательно прибавляется к соответствующим узлам двоичной древовидной структуры Меркла, за счет этого конфигурируя модуль создания перекошенных деревьев Меркла для разворачивания/создания перекошенного дерева Меркла. 4 з.п. ф-лы, 10 ил.

1. Система верифицируемого отсечения реестров, содержащая:

модуль создания иерархических (h-)перекошенных деревьев Меркла, в котором, согласно схеме связанных списков, корневое хеш-значение R_n-1 предыдущего поддерева включается в блок T_n данных, причем блок T_n данных, в который включается корневое хеш-значение R_n-1, хешируется, за счет этого получая h(T_n), при этом полученное h(T_n) и корневое хеш-значение R_n-1 предыдущего поддерева и ссылки R_{n-(base^offset)} перехода объединяются и затем хешируются, за счет этого получая h(h(T_n)|R_n-1|R_{n-(base^offset)}, и полученное h(h(T_n)|R_n-1|R_{n-(base^offset)} последовательно прибавляется к соответствующим узлам двоичной древовидной структуры Меркла, чтобы создавать и разворачивать h-перекошенное дерево Меркла, при этом

ссылка R_{n-(base^offset)} перехода представляет собой корневое хеш-значение для узла в предварительно определенное предыдущее время в h-перекошенном дереве Меркла,

основание base представляет кратчайшее расстояние предварительно определенной ссылки перехода для выделения этой ссылки перехода с предварительно определенным интервалом,

смещение offset представляет остаток от деления местоположения n текущего узла на основание, т.е. n % base, и

расстояние ссылки перехода сконфигурировано получаться посредством значения base^offset.

2. Система верифицируемого отсечения реестров по п.1, в которой модуль создания h-перекошенных деревьев Меркла выполнен с возможностью выделять ссылку перехода каждого узла offset+(base^offset)*k, и k сконфигурировано посредством положительного целого числа.

3. Система верифицируемого отсечения реестров по п.1, дополнительно содержащая модуль верификации целостности узлов, в котором последнее корневое хеш-значение h-перекошенного дерева Меркла вычисляется путем последовательного выполнения операции с хеш-значениями посредством использования T_k и предварительно определенного корневого хеш-значения h(T_i) (здесь, k<i≤n) h-перекошенного дерева Меркла, чтобы верифицировать то, включается или нет предыдущий предварительно определенный блок T_k данных в h-перекошенное дерево Меркла, и сравнивается то, совпадают или нет вычисленное последнее корневое хеш-значение и заранее известное последнее корневое хеш-значение, для проверки целостности блока T_k.

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

1) поиск ссылки перехода или ссылки (узла), которая существует в ближайшее предыдущее время, из числа ссылок (узлов), которые находятся в идентичное время или дальше в будущем, чем R_y, на основе ссылки (узла) в пределах предварительно определенного расстояния в направлении предыдущего времени от последнего корневого хеш-значения R_head,

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

3) повторение процесса 2) до достижения R_y,

4) вычисление корневых хешей, направленных в направлении будущего, последовательно для набора ссылки перехода или ссылки (узла), искомой многократно в процессах 2) и 3) посредством использования T_y, и

5) сравнение того, равно или нет конечное полученное корневое хеш-значение R_head, и верификацию того, что хеш-значение R_y или блок T_y данных существует в h-перекошенном дереве Меркла, когда конечное полученное корневое хеш-значение равно R_head в качестве результата сравнения.

5. Система верифицируемого отсечения реестров по п.4, в которой предварительно определенное расстояние составляет основание.