Способы и устройство эффективной реализации распределенной базы данных в сети

Изобретение относится к вычислительной технике. Технический результат заключается в повышении скорости конвергенции, при этом уменьшая объем данных, передаваемых между устройствами. Устройство для реализации распределенной базы данных содержит: память и процессор, приспособленный для: определения первой группы вычислительных устройств на основе детерминированной псевдослучайной функции; приема события, привязанного к первому набору событий; идентификации порядка, связанного со вторым набором событий; идентификации порядка, связанного с множеством транзакций; и сохранения в экземпляре распределенной базы данных порядка, связанного с множеством транзакций. 3 н. и 21 з.п. ф-лы, 15 ил.

 

Перекрестная ссылка на родственные заявки

[1001] Эта заявка испрашивает приоритет и преимущество предварительной заявки на патент США № 62/531153, поданной 11 июля 2017 г. и озаглавленной «Methods and Apparatus for Efficiently Implementing a Distributed Database within a Network», которая включена в настоящий документ посредством ссылки во всей своей полноте.

Предпосылки изобретения

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

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

[1004] Такой распределенный консенсус может быть обработан посредством способов и/или процессов, таких как алгоритм Паксос или его варианты. При использовании таких способов и/или процессов один сервер системы базы данных устанавливается в качестве «лидера», и лидер принимает решения относительно порядка событий. События (например, в многопользовательских играх) передаются лидеру, лидер избирает упорядоченную последовательность для событий, и лидер передает эту упорядоченную последовательность на другие серверы системы базы данных.

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

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

[1006] В некоторых вариантах осуществления устройство содержит процессор и память, функционально соединенную с процессором и связанную с экземпляром распределенной базы данных на первом вычислительном устройстве, приспособленном для включения в группу вычислительных устройств, которые реализуют распределенную базу данных посредством сети, функционально соединенной с группой вычислительных устройств. Процессор приспособлен для выбора анонимного пути связи, связанного с (a) вторым вычислительным устройством из группы вычислительных устройств, которые реализуют распределенную базу данных, и (b) набором идентификаторов вычислительных устройств. Анонимный путь связи определен посредством последовательности замаскированных открытых ключей. Каждый замаскированный открытый ключ из последовательности замаскированных открытых ключей связан с псевдонимом вычислительного устройства из набора вычислительных устройств, которые реализуют анонимный путь связи. Процессор приспособлен для генерирования зашифрованного сообщения, зашифрованного с помощью первого замаскированного открытого ключа, включенного в последовательность замаскированных открытых ключей. Первый замаскированный открытый ключ связан со вторым вычислительным устройством. Процессор приспособлен для генерирования зашифрованного пакета данных, содержащего зашифрованное сообщение и идентификатор вычислительного устройства из набора идентификаторов вычислительных устройств. Идентификатор вычислительного устройства связан со вторым вычислительным устройством. Зашифрованный пакет данных зашифрован с помощью второго замаскированного открытого ключа из последовательности замаскированных открытых ключей. Процессор приспособлен для отправки зашифрованного пакета данных на третье вычислительное устройство из набора вычислительных устройств, которые реализуют анонимный путь связи.

Краткое описание графических материалов

[1007] На фиг. 1 представлена структурная схема высокого уровня, на которой проиллюстрирована система распределенной базы данных согласно варианту осуществления.

[1008] На фиг. 2 представлена структурная схема, на которой проиллюстрировано вычислительное устройство системы распределенной базы данных согласно варианту осуществления.

[1009] На фиг. 3–6 проиллюстрированы примеры хешграфа согласно варианту осуществления.

[1010] На фиг. 7 представлена функциональная схема, на которой проиллюстрирован информационный поток между первым вычислительным устройством и вторым вычислительным устройством согласно варианту осуществления.

[1011] На фиг. 8 представлен пример хешграфа согласно варианту осуществления.

[1012] На фиг. 9 представлен пример хешграфа согласно варианту осуществления.

[1013] На фиг. 10A–10B проиллюстрирован примерный способ достижения консенсуса для использования с хешграфом согласно варианту осуществления.

[1014] На фиг. 11A–11B проиллюстрирован примерный способ достижения консенсуса для использования с хешграфом согласно другому варианту осуществления.

[1015] На фиг. 12A–12B проиллюстрирован примерный способ достижения консенсуса для использования с хешграфом согласно другому варианту осуществления.

Подробное описание изобретения

[1016] В некоторых вариантах осуществления устройство содержит процессор и память, функционально соединенную с процессором и связанную с экземпляром распределенной базы данных на первом вычислительном устройстве, приспособленном для включения в группу вычислительных устройств, которые реализуют распределенную базу данных посредством сети, функционально соединенной с группой вычислительных устройств. Процессор приспособлен для выбора анонимного пути связи, связанного с (a) вторым вычислительным устройством из группы вычислительных устройств, которые реализуют распределенную базу данных, и (b) набором идентификаторов вычислительных устройств. Анонимный путь связи определен посредством последовательности замаскированных открытых ключей. Каждый замаскированный открытый ключ из последовательности замаскированных открытых ключей связан с псевдонимом вычислительного устройства из набора вычислительных устройств, которые реализуют анонимный путь связи. Процессор приспособлен для генерирования зашифрованного сообщения, зашифрованного с помощью первого замаскированного открытого ключа, включенного в последовательность замаскированных открытых ключей. Первый замаскированный открытый ключ связан со вторым вычислительным устройством. Процессор приспособлен для генерирования зашифрованного пакета данных, содержащего зашифрованное сообщение и идентификатор вычислительного устройства из набора идентификаторов вычислительных устройств. Идентификатор вычислительного устройства связан со вторым вычислительным устройством. Зашифрованный пакет данных зашифрован с помощью второго замаскированного открытого ключа из последовательности замаскированных открытых ключей. Процессор приспособлен для отправки зашифрованного пакета данных на третье вычислительное устройство из набора вычислительных устройств, которые реализуют анонимный путь связи.

[1017] В некоторых вариантах осуществления первый замаскированный ключ генерируется путем выбора первого случайного значения (R1) из предварительно определенного набора (G) значений, который представляет собой алгебраическую группу, так, чтобы R1 представляло собой генератор для G, и выбора второго случайного значения (R2) из предварительно определенного набора (G) значений. Открытый ключ определяется как пара (B, H) на основе первого случайного значения (R1) и второго случайного значения (R2). Пара (B, H) определяется как (R1, R1^R2). Третье случайное значение (R3) выбирается из предварительно определенного набора (G) значений. Третье случайное значение (R3) выбирается так, чтобы B^R3 представляло собой генератор для G. Первый замаскированный ключ определяется как пара (B’, H’) на основе открытого ключа и третьего случайного значения (R3). Пара (B’, H’) определяется как (B^R3, H^R3). В контексте настоящего документа «^» означает степень и/или возведение в степень (повторяемые применения оператора *). Таким образом, B^R3 означает B в степени R3 и/или применение R3-1 раз оператора * к B.

[1018] В некоторых вариантах осуществления энергонезависимый считываемый процессором носитель содержит код, который при исполнении процессором предписывает процессору выбрать на первом вычислительном устройстве первое случайное значение (R1) из предварительно определенного набора (G) значений, который представляет собой алгебраическую группу, так, чтобы R1 представляло собой генератор для G, и выбрать второе случайное значение (R2) из предварительно определенного набора (G) значений. Код дополнительно содержит код для предписывания процессору определить открытый ключ как пару (B, H) на основе первого случайного значения (R1) и второго случайного значения (R2). Пара (B, H) определяется как (R1, R1^R2). Код дополнительно содержит код для предписывания процессору предоставить открытый ключ (B, H) на второе вычислительное устройство так, что второе вычислительное устройство безопасно предоставляет сообщение (M) на первое вычислительное устройство путем: выбора третьего случайного значения (R3) из предварительно определенного набора (G) значений; шифрования сообщения (M) с использованием открытого ключа (B, H) и третьего случайного значения (R3) для определения зашифрованного шифротекста как (X, Y)=(B^R3, M * H^R3); и отправки зашифрованного шифротекста (X, Y) на первое вычислительное устройство. Код дополнительно содержит код для предписывания процессору принять зашифрованный шифротекст (X, Y) со второго вычислительного устройства и расшифровать зашифрованный шифротекст (X, Y) для идентификации сообщения (M) с использованием второго случайного значения (R2). В некоторых случаях открытый ключ (B, H) представляет собой замаскированный открытый ключ.

[1019] В некоторых вариантах осуществления энергонезависимый считываемый процессором носитель содержит код, который при исполнении процессором предписывает процессору определить анонимный путь связи посредством последовательности замаскированных открытых ключей для набора вычислительных устройств из группы вычислительных устройств, которые реализуют распределенную базу данных. Набор вычислительных устройств определяет анонимный путь связи. Каждый замаскированный открытый ключ из последовательности замаскированных открытых ключей связан с псевдонимом отличного вычислительного устройства из группы вычислительных устройств, которая реализует распределенную базу данных. Код дополнительно содержит код для предписывания процессору сгенерировать набор идентификаторов вычислительных устройств, содержащий (1) незашифрованный идентификатор вычислительного устройства, идентифицирующий вычислительное устройство из группы вычислительных устройств, и (2) последовательность зашифрованных идентификаторов вычислительных устройств. Каждый зашифрованный идентификатор вычислительного устройства из последовательности зашифрованных идентификаторов вычислительных устройств зашифрован с помощью отличного замаскированного открытого ключа из последовательности замаскированных открытых ключей. Код дополнительно содержит код для предписывания процессору предоставить последовательность замаскированных открытых ключей и набор идентификаторов вычислительных устройств на по меньшей мере одно вычислительное устройство из группы вычислительных устройств, так что по меньшей мере одно вычислительное устройство может определять сообщение для процессора для отправки по анонимному пути связи. Код дополнительно содержит код для предписывания процессору принять по анонимному пути связи сообщение, зашифрованное с помощью замаскированного открытого ключа из последовательности замаскированных открытых ключей, и расшифровать сообщение с помощью закрытого ключа, связанного с замаскированным открытым ключом из последовательности замаскированных открытых ключей.

[1020] В некоторых вариантах осуществления устройство содержит память, связанную с экземпляром распределенной базы данных на первом вычислительном устройстве, приспособленном для включения во множество вычислительных устройств, которое реализует распределенную базу данных посредством сети, функционально соединенной с множеством вычислительных устройств и процессором, функционально соединенным с памятью. Процессор приспособлен для определения первой группы вычислительных устройств из множества вычислительных устройств и второй группы вычислительных устройств из множества вычислительных устройств на основе детерминированной псевдослучайной функции. Процессор приспособлен для приема со второго вычислительного устройства из множества вычислительных устройств события, привязанного к первому набору событий, определенному набором вычислительных устройств из множества вычислительных устройств. Набор вычислительных устройств содержит по меньшей мере одно вычислительное устройство из первой группы вычислительных устройств и по меньшей мере одно вычислительное устройство из второй группы вычислительных устройств. Процессор приспособлен для идентификации порядка, связанного со вторым набором событий, в результате того, что протокол консенсуса (1) использует значение для параметра события из первого набора событий, которое было определено вычислительным устройством из первой группы вычислительных устройств, и (2) не использует значение для параметра события из первого набора событий, которое было определено вычислительным устройством из второй группы вычислительных устройств. Процессор приспособлен для идентификации порядка, связанного с набором транзакций, указанным в экземпляре распределенной базы данных, на основе по меньшей мере частично порядка, связанного со вторым набором событий, и сохранения в экземпляре распределенной базы данных порядка, связанного с набором транзакций.

[1021] В некоторых вариантах осуществления устройство содержит экземпляр распределенной базы данных на первом вычислительном устройстве, приспособленном для включения в набор вычислительных устройств, которые реализуют распределенную базу данных посредством сети, функционально соединенной с набором вычислительных устройств. Устройство также содержит процессор, функционально соединенный с памятью, хранящей экземпляр распределенной базы данных. Процессор приспособлен для определения в первый момент времени первого события, привязанного к первому набору событий. Процессор приспособлен для приема во второй момент времени после первого момента времени и со второго вычислительного устройства из набора вычислительных устройств сигнала, представляющего второе событие, (1) определенное вторым вычислительным устройством и (2) привязанное ко второму набору событий. Процессор приспособлен для идентификации порядка, связанного с третьим набором событий, на основе по меньшей мере одного результата протокола. Каждое событие из третьего набора событий представляет собой событие из по меньшей мере одного из первого набора событий или второго набора событий. Процессор приспособлен для сохранения в экземпляре распределенной базы данных порядка, связанного с третьим набором событий.

[1022] В некоторых случаях каждое событие из третьего набора событий связано с набором атрибутов (например, порядковый номер, номер поколения, номер раунда, принятый номер и/или метка времени и т. д.). Результат протокола может содержать значение для каждого атрибута из набора атрибутов для каждого события из третьего набора событий. Значение для первого атрибута из набора атрибутов может включать первое числовое значение, и значение для второго атрибута из набора атрибутов может включать двоичное значение, связанное с первым числовым значением. Двоичное значение для второго атрибута (например, значение приращения раунда) для события из третьего набора событий может быть основано на том, соответствует ли взаимосвязь между тем событием и четвертым набором событий, привязанным к тому событию, критерию (например, количеству событий, строго идентифицированных тем событием). Каждое событие из четвертого набора событий (1) является предком события из третьего набора событий и (2) связано с первым общим атрибутом, как и остальные события из четвертого набора событий (например, общим номером раунда, указанием о том, что представляет собой первое событие раунда R, и т. д.). Первый общий атрибут может являться указанием о первом случае, в котором событие, определенное каждым вычислительным устройством из набора вычислительных устройств, связано с первым конкретным значением (например, указанием о том, что представляет собой первое событие раунда R, и т. д.).

[1023] Значение для третьего атрибута (например, номера принятого раунда) из набора атрибутов может включать второе числовое значение, основанное на взаимосвязи между событием и пятым набором событий, привязанным к событию. Каждое событие из пятого набора событий является потомком события и связано со вторым общим атрибутом (например, является известным), как и остальные события из пятого набора событий. Второй общий атрибут может быть связан с (1) третьим общим атрибутом (например, указанием о том, что представляет собой первое событие раунда R или свидетеля), который является указанием о первом случае, в котором второе событие, определенное каждым вычислительным устройством из набора вычислительных устройств, связано со вторым конкретным значением, отличным от первого конкретного значения, и (2) результатом, основанным на наборе указаний. Каждое указание из набора указаний может быть связано с событием из шестого набора событий. Каждое событие из шестого набора событий может быть связано с четвертым общим атрибутом, который является указанием о первом случае, в котором третье событие, определенное каждым вычислительным устройством из набора вычислительных устройств, связано с третьим конкретным значением, отличным от первого конкретного значения и второго конкретного значения. В некоторых случаях первое конкретное значение является первым целым числом (например, первым номером раунда R), второе конкретное значение является вторым целым числом (например, вторым номером раунда, R+n), превышающим первое целое число, и третье конкретное значение является третьим целым числом (например, третьим номером раунда, R+n+m), превышающим второе целое число.

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

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

[1026] В некоторых вариантах осуществления экземпляр распределенной базы данных на первом вычислительном устройстве может быть приспособлен для включения в набор вычислительных устройств, который реализует распределенную базу данных посредством сети, функционально соединенной с набором вычислительных устройств. Первое вычислительное устройство сохраняет множество транзакций в экземпляре распределенной базы данных. Модуль конвергенции базы данных может быть реализован в памяти или процессоре первого вычислительного устройства. Модуль конвергенции базы данных может быть функционально соединен с экземпляром распределенной базы данных. Модуль конвергенции базы данных может быть приспособлен для определения в первый момент времени первого события, привязанного к первому набору событий. Каждое событие из первого набора событий представляет собой последовательность байтов и связано с (1) набором транзакций из множества наборов транзакций и (b) порядком, связанным с набором транзакций. Каждая транзакция из набора транзакций представляет собой транзакцию из множества транзакций. Модуль конвергенции базы данных может быть приспособлен для приема во второй момент времени после первого момента времени и со второго вычислительного устройства из набора вычислительных устройств второго события, (1) определенного вторым вычислительным устройством и (2) привязанного ко второму набору событий. Модуль конвергенции базы данных может быть приспособлен для определения третьего события, привязанного к первому событию и второму событию. Модуль конвергенции базы данных может быть приспособлен для идентификации порядка, связанного с третьим набором событий, на основе по меньшей мере первого набора событий и второго набора событий. Каждое событие из третьего набора событий представляет собой событие из по меньшей мере одного из первого набора событий или второго набора событий. Модуль конвергенции базы данных может быть приспособлен для идентификации порядка, связанного с множеством транзакций, на основе по меньшей мере (1) порядка, связанного с третьим набором событий, и (2) порядка, связанного с каждым набором транзакций из множества наборов транзакций. Модуль конвергенции базы данных может быть приспособлен для сохранения в экземпляре распределенной базы данных порядка, связанного с множеством транзакций, сохраненных на первом вычислительном устройстве.

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

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

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

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

[1031] На фиг. 1 представлена структурная схема высокого уровня, на которой проиллюстрирована система 100 распределенной базы данных согласно варианту осуществления. На фиг. 1 проиллюстрирована распределенная база 100 данных, реализованная на четырех вычислительных устройствах (вычислительное устройство 110, вычислительное устройство 120, вычислительное устройство 130 и вычислительное устройство 140), но следует понимать, что распределенная база 100 данных может использовать набор из любого количества вычислительных устройств, содержащий вычислительные устройства, не показанные на фиг. 1. Сеть 105 может представлять собой сеть любого типа (например, локальную вычислительную сеть (LAN), глобальную вычислительную сеть (WAN), виртуальную сеть, телекоммуникационную сеть), реализованную в виде проводной сети и/или беспроводной сети и используемую для функционального соединения вычислительных устройств 110, 120, 130, 140. Как более подробно описано в настоящем документе, в некоторых вариантах осуществления, например, вычислительные устройства представляют собой персональные компьютеры, соединенные друг с другом посредством поставщика услуг Интернет (ISP) и Интернета (например, сети 105). В некоторых вариантах осуществления соединение может быть установлено посредством сети 105 между любыми двумя вычислительными устройствами 110, 120, 130, 140. Как показано на фиг. 1, например, соединение может быть установлено между вычислительным устройством 110 и любым из вычислительного устройства 120, вычислительного устройства 130 или вычислительного устройства 140.

[1032] В некоторых вариантах осуществления вычислительные устройства 110, 120, 130, 140 могут осуществлять связь друг с другом (например, отправлять данные на и/или принимать данные с) и с сетью посредством промежуточных сетей и/или альтернативных сетей (не показаны на фиг. 1). Такие промежуточные сети и/или альтернативные сети могут принадлежать к тому же типу и/или другому типу сети в сравнении с сетью 105.

[1033] Каждое вычислительное устройство 110, 120, 130, 140 может представлять собой устройство любого типа, приспособленное для отправки данных по сети 105, чтобы отправлять и/или принимать данные с одного или более других вычислительных устройств. Примеры вычислительных устройств показаны на фиг. 1. Вычислительное устройство 110 содержит память 112, процессор 111 и устройство 113 вывода. Память 112 может представлять собой, например, оперативное запоминающее устройство (RAM), буфер памяти, жесткий диск, базу данных, стираемое программируемое постоянное запоминающее устройство (EPROM), электрически стираемое постоянное запоминающее устройство (EEPROM), постоянное запоминающее устройство (ROM) и/или т. д. В некоторых вариантах осуществления память 112 вычислительного устройства 110 содержит данные, связанные с экземпляром распределенной базы данных (например, экземпляром 114 распределенной базы данных). В некоторых вариантах осуществления память 112 хранит инструкции, предписывающие процессору исполнить модули, процессы и/или функции, связанные с отправкой на другой экземпляр и/или приемом с другого экземпляра распределенной базы данных (например, экземпляра 124 распределенной базы данных на вычислительном устройстве 120) записи события синхронизации, и/или записи предыдущих событий синхронизации с другими вычислительными устройствами, и/или порядка событий синхронизации, и/или порядка транзакций в событиях, параметров, связанных с идентификацией порядка событий синхронизации и/или транзакций, и/или значения для параметра (например, поля базы данных, количественно характеризующего транзакцию, поля базы данных, количественно характеризующего порядок, в котором происходят события, и/или любого другого подходящего поля, для которого значение может быть сохранено в базе данных).

[1034] Экземпляр 114 распределенной базы данных может, например, быть приспособлен для проведений операций с данными, включая сохранение, модификацию и/или удаление данных. В некоторых вариантах осуществления экземпляр 114 распределенной базы данных может представлять собой набор массивов, набор структур данных, реляционную базу данных, объектную базу данных, постреляционную базу данных и/или базу данных или хранилище любого другого подходящего типа. Например, экземпляр 114 распределенной базы данных может хранить данные, относящиеся к любой конкретной функции и/или области. Например, экземпляр 114 распределенной базы данных может хранить финансовые транзакции (например, пользователя вычислительного устройства 110), включая значение и/или вектор значений, относящиеся к истории владения конкретным финансовым инструментом. В целом, вектор может представлять собой любой набор значений для параметра, и параметр может представлять собой любые объект данных и/или поле базы данных, которые могут принимать разные значения. Таким образом, экземпляр 114 распределенной базы данных может иметь ряд параметров и/или полей, каждое из которых связано с вектором значений. Вектор значений используется для определения фактического значения для параметра и/или поля в том экземпляре 114 базы данных. В некоторых случаях экземпляр 114 распределенной базы данных хранит запись события синхронизации, запись предыдущих событий синхронизации с другими вычислительными устройствами, порядок событий синхронизации, порядок транзакций в событиях, параметры и/или значения, связанные с идентификацией порядка событий синхронизации и/или транзакций (например, используемые при вычислении порядка с использованием способа достижения консенсуса, как описано в настоящем документе), значение для параметра (например, поле базы данных, количественно характеризующее транзакцию, поле базы данных, количественно характеризующее порядок, в котором происходят события, и/или любое другое подходящее поле, для которого значение может быть сохранено в базе данных).

[1035] В некоторых случаях экземпляр 114 распределенной базы данных может также хранить переменную состояния базы данных и/или текущее состояние. Текущим состоянием могут быть состояние, баланс, условие и/или т. п., связанные с результатом транзакций. Подобным образом, состояние может включать структуру данных и/или переменные, модифицированные транзакциями. В других случаях текущее состояние можно хранить в отдельной базе данных и/или части памяти 112. В еще других случаях текущее состояние можно хранить в памяти вычислительного устройства, отличного от вычислительного устройства 110.

[1036] В некоторых случаях экземпляр 114 распределенной базы данных может также быть использован для реализации других структур данных, таких как набор пар (ключ, значение). Транзакцией, записанной экземпляром 114 распределенной базы данных, может быть, например, добавление, удаление или модификация пары (ключ, значение) в наборе пар (ключ, значение).

[1037] В некоторых случаях в систему 100 распределенной базы данных или в любой из экземпляров 114, 124, 134, 144 распределенной базы данных может быть отправлен запрос. Например, запрос может состоять из ключа, и результат, возвращаемый системой 100 распределенной базы данных или экземплярами 114, 124, 134, 144 распределенной базы данных, может представлять собой значение, связанное с ключом. В некоторых случаях система 100 распределенной базы данных или любой из экземпляров 114, 124, 134, 144 распределенной базы данных могут быть также модифицированы посредством транзакции. Например, транзакция для модификации базы данных может содержать цифровую подпись, выполненную стороной, авторизирующей транзакцию модификации.

[1038] Система 100 распределенной базы данных может быть использована для многих целей, таких как, например, хранение атрибутов, связанных с различными пользователями в распределенной системе идентификации. Например, такая система может использовать идентификатор пользователя в качестве «ключа», и список атрибутов, связанных с пользователями, в качестве «значения». В некоторых случаях идентификатор может представлять собой криптографический открытый ключ с соответствующим закрытым ключом, известным тому пользователю. Каждый атрибут может, например, быть подписан с помощью цифровой подписи органом, имеющим право на утверждение того атрибута. Каждый атрибут может быть также, например, зашифрован с помощью открытого ключа, связанного с физическим лицом или группой физических лиц, которые обладают правом на считывание атрибута. Некоторые ключи или значения могут также иметь прикрепленный к ним список открытых ключей сторон, которые уполномочены модифицировать или удалять ключи или значения.

[1039] В другом примере экземпляр 114 распределенной базы данных может хранить данные, относящиеся к массовым многопользовательским играм (MMG), такие как текущий статус и принадлежность игровых предметов. В некоторых случаях экземпляр 114 распределенной базы данных может быть реализован в вычислительном устройстве 110, как показано на фиг. 1. В других случаях вычислительное устройство может иметь доступ к экземпляру распределенной базы данных (например, по сети), но он не реализован в вычислительном устройстве (не показано на фиг. 1).

[1040] Процессор 111 вычислительного устройства 110 может представлять собой любое подходящее устройство обработки, приспособленное для запуска и/или исполнения экземпляра 114 распределенной базы данных. Например, процессор 111 может быть приспособлен для обновления экземпляра 114 распределенной базы данных в ответ на прием сигнала с вычислительного устройства 120 и/или предписывания отправить сигнал на вычислительное устройство 120, как более подробно описано в настоящем документе. Более конкретно, как более подробно описано в настоящем документе, процессор 111 может быть приспособлен для исполнения модулей, функций и/или процессов для обновления экземпляра 114 распределенной базы данных в ответ на прием события синхронизации, связанного с транзакцией, с другого вычислительного устройства, записи, связанной с порядком событий синхронизации, и/или т. п. В других вариантах осуществления процессор 111 может быть приспособлен для исполнения модулей, функций и/или процессов для обновления экземпляра 114 распределенной базы данных в ответ на прием значения для параметра, сохраненного в другом экземпляре распределенной базы данных (например, экземпляре 124 распределенной базы данных на вычислительном устройстве 120), и/или предписывания отправить значение для параметра, сохраненного в экземпляре 114 распределенной базы данных на вычислительном устройстве 110, на вычислительное устройство 120. В некоторых вариантах осуществления процессор 111 может представлять собой процессор общего назначения, программируемую пользователем вентильную матрицу (FPGA), интегральную схему специального назначения (ASIC), процессор цифровой обработки сигналов (DSP) и/или т. п.

[1041] Дисплей 113 может представлять собой любой подходящий дисплей, такой как, например, жидкокристаллический дисплей (LCD), дисплей на электронно-лучевой трубке (CRT) или т. п. В других вариантах осуществления любое из вычислительных устройств 110, 120, 130, 140 содержит другое устройство вывода вместо дисплеев 113, 123, 133, 143 или в дополнение к ним. Например, любое из вычислительных устройств 110, 120, 130, 140 может содержать звуковое устройство вывода (например, динамик), тактильное устройство вывода и/или т. п. В еще одних вариантах осуществления любое из вычислительных устройств 110, 120, 130, 140 содержит устройство ввода вместо дисплеев 113, 123, 133, 143 или в дополнение к ним. Например, любое из вычислительных устройств 110, 120, 130, 140 может содержать клавиатуру, мышь и/или т. п.

[1042] Несмотря на то что на фиг. 1 показано, что все находится в одном вычислительном устройстве, в некоторых случаях процессор, приспособленный для исполнения модулей, функций и/или процессов для обновления распределенной базы данных, может находиться в вычислительном устройстве, отдельном от связанной с ним распределенной базы данных. В таком случае, например, процессор может быть функционально соединен с экземпляром распределенной базы данных посредством сети. Например, процессор может исполнять способ достижения консенсуса для идентификации порядка событий и/или транзакций (например, в результате синхронизации с другими экземплярами распределенной базы данных) и может отправлять сигнал, содержащий порядок событий и/или транзакций, на связанный экземпляр распределенной базы данных по сети. Связанный экземпляр распределенной базы данных может затем сохранять порядок событий, порядок транзакций и/или переменную состояния на основе порядка транзакций в связанном экземпляре распределенной базы данных. По существу, функции и хранение, связанные с распределенной базой данных, могут быть распределены. Более того, процессор может запрашивать информацию из связанного с ним экземпляра распределенной базы данных, сохранять переменные состояний и/или текущие состояния базы данных и другие подходящие операции, описанные в настоящем документе, в своем экземпляре распределенной базы данных, даже когда база данных реализована в вычислительном устройстве, отдельном от вычислительного устройства, имеющего процессор, реализующий модули, функции и/или процессы (например, способ достижения консенсуса), связанные с системой распределенной базы данных. В других случаях функции и/или способы, описанные в настоящем документе, могут быть исполнены на любом количестве вычислительных устройств (например, в распределенной вычислительной среде и/или кластере), и результаты и/или значения таких функций и/или способов могут быть сохранены в памяти и/или хранилище на любом подходящем вычислительном устройстве.

[1043] Вычислительное устройство 120 имеет процессор 121, память 122 и дисплей 123, которые могут быть конструктивно и/или функционально подобны процессору 111, памяти 112 и дисплею 113 соответственно. Также экземпляр 124 распределенной базы данных может быть структурно и/или функционально подобен экземпляру 114 распределенной базы данных.

[1044] Вычислительное устройство 130 имеет процессор 131, память 132 и дисплей 133, которые могут быть конструктивно и/или функционально подобны процессору 111, памяти 112 и дисплею 113 соответственно. Также экземпляр 134 распределенной базы данных может быть структурно и/или функционально подобен экземпляру 114 распределенной базы данных.

[1045] Вычислительное устройство 140 имеет процессор 141, память 142 и дисплей 143, которые могут быть конструктивно и/или функционально подобны процессору 111, памяти 112 и дисплею 113 соответственно. Также экземпляр 144 распределенной базы данных может быть структурно и/или функционально подобен экземпляру 114 распределенной базы данных.

[1046] Хотя вычислительные устройства 110, 120, 130, 140 показаны как подобные друг другу, каждое вычислительное устройство системы 100 распределенной базы данных может отличаться от других вычислительных устройств. Каждое вычислительное устройство 110, 120, 130, 140 системы 100 распределенной базы данных может представлять собой любое из, например, вычислительного элемента (например, персонального вычислительного устройства, такого как настольный компьютер, портативный компьютер и т. д.), мобильного телефона, карманного персонального компьютера (PDA) и т. д. Например, вычислительное устройство 110 может представлять собой настольный компьютер, вычислительное устройство 120 может представлять собой смартфон, и вычислительное устройство 130 может представлять собой сервер.

[1047] В некоторых вариантах осуществления одна или более частей вычислительных устройств 110, 120, 130, 140 могут включать аппаратный модуль (например, процессор цифровой обработки сигналов (DSP), программируемую пользователем вентильную матрицу (FPGA)) и/или программный модуль (например, модуль компьютерного кода, хранящегося в памяти и/или исполняемого на процессоре). В некоторых вариантах осуществления одна или более функций, связанных с вычислительными устройствами 110, 120, 130, 140 (например, функции, связанные с процессорами 111, 121, 131, 141), могут быть включены в один или более модулей (см., например, фиг. 2).

[1048] Свойства системы 100 распределенной базы данных, включая свойства вычислительных устройств (например, вычислительных устройств 110, 120, 130, 140), количество вычислительных устройств, и сеть 105 могут быть выбраны любыми способами. В некоторых случаях свойства системы 100 распределенной базы данных могут быть выбраны администратором системы 100 распределенной базы данных. В других случаях свойства системы 100 распределенной базы данных могут быть совместно выбраны пользователями системы 100 распределенной базы данных.

[1049] Поскольку используется система 100 распределенной базы данных, среди вычислительных устройств 110, 120, 130 и 140 не назначен лидер. В частности, ни одно из вычислительных устройств 110, 120, 130 или 140 не идентифицируется и/или не выбирается в качестве лидера для разрешения конфликтов между значениями, хранящимися в экземплярах 111, 12, 131, 141 распределенной базы данных вычислительных устройств 110, 120, 130, 140. Вместо этого, с использованием процессов синхронизации событий, процессов голосования и/или способов, описанных в настоящем документе, вычислительные устройства 110, 120, 130, 140 могут совместно согласовывать значение для параметра.

[1050] Отсутствие лидера в системе распределенной базы данных повышает безопасность системы распределенной базы данных. В частности, при наличии лидера существует единая точка атаки и/или сбоя. Если вредоносное программное обеспечение заражает лидера и/или значение для параметра на экземпляре распределенной базы данных лидера изменяют со злым умыслом, ошибочное и/или неправильное значение распространяется по другим экземплярам распределенной базы данных. Однако в системе без лидера нет единой точки атаки и/или сбоя. В частности, если параметр в экземпляре распределенной базы данных системы без лидера содержит значение, значение изменится после того, как тот экземпляр распределенной базы данных обменяется значениями с другими экземплярами распределенной базы данных в системе, как более подробно описано в настоящем документе. Дополнительно системы распределенной базы данных без лидера, описанные в настоящем документе, повышают скорость конвергенции, при этом уменьшая объем данных, передаваемых между устройствами, как более подробно описано в настоящем документе.

[1051] На фиг. 2 проиллюстрировано вычислительное устройство 200 системы распределенной базы данных (например, системы 100 распределенной базы данных) согласно варианту осуществления. В некоторых вариантах осуществления вычислительное устройство 200 может быть подобным вычислительным устройствам 110, 120, 130, 140, показанным и описанным в отношении фиг. 1. Вычислительное устройство 200 содержит процессор 210 и память 220. Процессор 210 и память 220 функционально соединены друг с другом. В некоторых вариантах осуществления процессор 210 и память 220 могут быть подобными процессору 111 и памяти 112 соответственно, подробно описанным в отношении фиг. 1. Как показано на фиг. 2, процессор 210 содержит модуль 211 конвергенции базы данных и модуль 210 связи, и память 220 содержит экземпляр 221 распределенной базы данных. Модуль 212 связи позволяет вычислительному устройству 200 осуществлять связь с другими вычислительными устройствами (например, отправлять данные на них и/или принимать данные с них). В некоторых вариантах осуществления модуль 212 связи (не показан на фиг. 1) позволяет вычислительному устройству 110 осуществлять связь с вычислительными устройствами 120, 130, 140. Модуль 210 связи может содержать и/или обеспечивать, например, контроллер сетевого интерфейса (NIC), беспроводное соединение, проводной порт и/или т. п. По существу, модуль 210 связи может устанавливать и/или поддерживать сеанс связи между вычислительным устройством 200 и другим устройством (например, посредством сети, такой как сеть 105, представленная на фиг. 1, или Интернет (не показано)). Подобным образом модуль 210 связи может позволять вычислительному устройству 200 отправлять данные на другое устройство и/или принимать данные с него.

[1052] В некоторых случаях модуль 211 конвергенции базы данных может обмениваться событиями и/или транзакциями с другими вычислительными устройствами, сохранять события и/или транзакции, которые принимает модуль 211 конвергенции базы данных, и вычислять упорядоченную последовательность событий и/или транзакций на основе частичного порядка, определенного схемой ссылок между событиями. Каждое событие может представлять собой запись, содержащую криптографический хеш двух более ранних событий (привязывающий то событие к двум более ранним событиями и их событиям-предкам и наоборот), данные полезной нагрузки (такие как транзакции, которые должны быть записаны), другую информацию, такую как текущее время, метка времени (например, дата и время по UTC), которую утвердил ее создатель, представляющая время, в которое событие было впервые определено, и/или т. п. Каждые из осуществляющих связь вычислительных устройств называются «участниками» или «участниками хешграфа». В некоторых случаях первое событие, определенное участником, содержит хеш только одного события, определенного другим участником. В таких случаях участник еще не имеет предыдущего собственного хеша (например, хеша события, ранее определенного тем участником). В некоторых случаях первое событие в распределенной базе данных не содержит хеша никакого предыдущего события (поскольку отсутствует предыдущее событие для той распределенной базы данных).

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

[1054] В некоторых случаях набор событий и их взаимосвязей может формировать направленный ациклический граф (DAG). В некоторых случаях каждое событие в DAG ссылается на несколько (например, два) более ранних событий (привязывая то событие к более ранним событиям и их событиям-предкам и наоборот) или не ссылается ни на одно из них, и каждая ссылка осуществляется строго на более ранние события, так что циклов нет. В некоторых вариантах осуществления DAG основан на криптографических хешах, так что структура данных может называться хешграфом (также называется в настоящем документе «DAG на основе хешей»). Хешграф непосредственно кодирует частичный порядок, обозначая, что известно, что событие X происходит до события Y, если Y содержит хеш X, или если Y содержит хеш события, которое содержит хеш X, или для таких путей произвольной длины. Однако, если путь от X к Y или от Y к X отсутствует, то частичный порядок не определяет, какое событие произошло первым. Следовательно, модуль конвергенции базы данных может вычислять общий порядок из частичного порядка. Это может быть выполнено с помощью любой подходящей детерминированной функции, которая используется вычислительными устройствами, так что вычислительные устройства вычисляют один и тот же порядок. В некоторых вариантах осуществления каждый участник может повторно вычислять этот порядок после каждой синхронизации, и в итоге эти порядки могут сходиться таким образом, что возникает консенсус.

[1055] Алгоритм и/или способ консенсуса могут быть использованы для определения порядка событий в хешграфе и/или порядка транзакций, сохраненных в событиях. Порядок транзакций в свою очередь может определять состояние базы данных в результате выполнения тех транзакций в соответствии с порядком. Определенное состояние базы данных может быть сохранено в качестве переменной состояния базы данных. В некоторых вариантах осуществления экземпляр распределенной базы данных (например, экземпляр 114 распределенной базы данных) сохраняет хешграф, и/или транзакции, и/или порядок транзакций, и/или события, и/или порядок событий, и/или состояние, полученное в результате выполнения транзакций.

[1056] В некоторых случаях модуль конвергенции базы данных может использовать следующую функцию для вычисления общего порядка из частичного порядка в хешграфе. Для каждого из других вычислительных устройств (называемых «участниками») модуль конвергенции базы данных может изучать хешграф для установления порядка, в котором события (и/или указания о тех событиях) были приняты тем участником. Модуль конвергенции базы данных может затем выполнять вычисления таким образом, словно тот участник присвоил числовой «ранг» каждому событию, при этом ранг равен 1 для первого события, которое принял участник, 2 для второго события, которое принял участник, и так далее. Модуль конвергенции базы данных может выполнять это для каждого участника в хешграфе. Затем для каждого события модуль конвергенции базы данных может вычислять медиану присвоенных рангов и может сортировать события по их медианам. Сортировка может разрушать равенства детерминированным образом, например, сортируя два равных события по числовому порядку их хешей или некоторым другим способом, в котором модуль конвергенции базы данных каждого участника использует одинаковый способ. Результатом этой сортировки является общий порядок.

[1057] На фиг. 6 проиллюстрирован хешграф 640 одного примера для определения общего порядка. Хешграф 640 иллюстрирует два события (самый нижний круг с полосками и самый нижний круг с точками) и первый момент времени, когда каждый участник принимает указание на те события (остальные круги с полосками и точками). Имя каждого участника в верхней части окрашено согласно тому, какое событие является первым в их медленном порядке. Первоначальных голосов с полосками больше, чем с точками; следовательно, голоса консенсуса для каждого из участников имеют вид с полосками. Другими словами, участники в итоге приходят к согласию, что событие с полосками произошло до события с точками.

[1058] В этом примере участники (вычислительные устройства, обозначенные как Алиса, Боб, Кэрол, Дэйв и Эд) будут работать таким образом, чтобы достичь консенсуса относительно того, произошло ли первым событие 642 или событие 644. Каждый круг с полосками указывает на событие, когда участник впервые принял событие 644 (и/или указание о том событии 644). Подобным образом каждый круг с точками указывает на событие, когда участник впервые принял событие 642 (и/или указание о том событии 642). Как показано в хешграфе 640, каждый из Алисы, Боба и Кэрол принял событие 644 (и/или указание о событии 644) до события 642. Как Дэйв, так и Эд приняли событие 642 (и/или указание о событии 642) до события 644 (и/или указания о событии 644). Таким образом, поскольку большее количество участников приняли событие 644 до события 642, общий порядок может быть определен каждым участником для указания того, что событие 644 произошло до события 642.

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

[1060] В этом варианте осуществления fast(x,y) дает положение y в общем порядке событий по мнению creator(x) по существу сразу после создания и/или определения x. Если Q равно бесконечности, то вышеописанное вычисляет такой же общий порядок, как получается и в ранее описанном варианте осуществления. Если Q является конечным числом и все участники находятся в режиме онлайн, то вышеописанное вычисляет такой же общий порядок, как получается и в ранее описанном варианте осуществления. Если Q является конечным числом и меньшая часть участников находится в режиме онлайн в заданный момент времени, то эта функция позволяет находящимся онлайн участникам достигать консенсуса между собой, который будет сохраняться неизменным по мере постепенного, поочередного перехода в режим онлайн новых участников. Однако, если речь идет о разделе сети, то участники каждого раздела могут прийти к своему собственному консенсусу. Затем, когда раздел заполняется, участники меньшего раздела примут консенсус большего раздела.

[1061] В еще других случаях, как описано в отношении фиг. 8–12B, модуль конвергенции базы данных может использовать еще другую функцию для вычисления общего порядка из частичного порядка в хешграфе. Как показано на фиг. 8–9, каждый участник (Алиса, Боб, Кэрол, Дэйв и Эд) создает и/или определяет события (1401–1413, как показано на фиг. 8; 1501–1506, показанные на фиг. 9). При использовании функции и подфункций, описанных в отношении фиг. 8–12B, общий порядок для событий может быть вычислен посредством сортировки событий по их принятому раунду, с разрушением равенств по их принятой метке времени и разрушением тех равенств по их подписям, как более подробно описано в настоящем документе. В других случаях общий порядок для событий может быть вычислен посредством сортировки событий по их принятому раунду, с разрушением равенств по их принятому поколению (вместо их принятой метки времени) и с разрушением тех равенств по их подписям. В следующих абзацах подробно изложены функции, используемые для вычисления и/или определения принятого раунда и принятого поколения события для определения порядка для событий. Следующие термины используются и иллюстрируются в связи с фиг. 8–12B.

[1062] «Родитель» («Parent»): событие X является родителем события Y, если Y содержит хеш X. Например, на фиг. 8 родители события 1412 включают событие 1406 и событие 1408.

[1063] «Предок» («Ancestor»): предками события X являются X, его родители, родители его родителей и так далее. Например, как показано на фиг. 8, предками события 1412 являются события 1401, 1402, 1403, 1406, 1408 и 1412. Можно сказать, что предки события привязаны к тому событию и наоборот.

[1064] «Потомок» («Descendant»): потомками события X являются X, его дети, дети его детей и так далее. Например, как показано на фиг. 8, потомком события 1401 является каждое событие, показанное на фигуре. В качестве другого примера, потомками события 1403 являются события 1403, 1404, 1406, 1407, 1409, 1410, 1411, 1412 и 1413. Можно сказать, что потомки события привязаны к тому событию и наоборот.

[1065] «N»: общее количество участников в популяции. Например, как показано на фиг. 8, участники представляют собой вычислительные устройства, обозначенные как Алиса, Боб, Кэрол, Дэйв и Эд, и N равняется пяти.

[1066] «M»: наименьшее целое число, которое превышает определенную процентную долю N (например, превышает 2/3 от N). Например, как показано на фиг. 8, если процентная доля определена как 2/3, то M равняется четырем. В других случаях M может быть определено, например, как другая процентная доля N (например, 1/3, 1/2 и т. д.), конкретное предварительно определенное число и/или любым другим подходящим способом.

[1067] «Собственный родитель» («Self-parent»): собственным родителем события X является его событие-родитель Y, созданное и/или определенное тем же участником. Например, как показано на фиг. 8, собственным родителем события 1405 является 1401.

[1068] «Собственный предок» («Self-ancestor»): собственными предками события X являются X, его собственный родитель, собственный родитель его собственного родителя и так далее.

[1069] «Порядковый номер» («Sequence Number», или «SN»): целочисленный атрибут события, определенный как порядковый номер собственного родителя события плюс один. Например, как показано на фиг. 8, собственным родителем события 1405 является 1401. Поскольку порядковый номер события 1401 равен одному, порядковый номер события 1405 равен двум (т. е. один плюс один).

[1070] «Номер поколения» («Generation Number», или «GN»): целочисленный атрибут события, определенный как максимальное значение номеров поколений родителей события плюс один. Например, как показано на фиг. 8, событие 1412 имеет двух родителей, события 1406 и 1408, имеющих номера поколений четыре и два соответственно. Таким образом, номер поколения события 1412 равен пяти (т. е. четыре плюс один).

[1071] «Приращение раунда» («Round Increment», или «RI»): атрибут события, который может равняться либо нулю, либо единице.

[1072] «Номер раунда» («Round Number», или «RN»): целочисленный атрибут события. В некоторых случаях он также относится к раунду, который создан, или созданному раунду. В некоторых случаях номер раунда может быть определен как максимальное значение номеров раундов родителей события плюс приращение раунда события. Например, как показано на фиг. 8, событие 1412 имеет двух родителей, события 1406 и 1408, которые оба имеют номер раунда, равный одному. Событие 1412 также имеет приращение раунда, равное одному. Таким образом, номер раунда события 1412 равняется двум (т. е. один плюс один). В других случаях событие может иметь номер раунда R, если R является минимальным целым числом, так что событие может строго видеть (как описано в настоящем документе) по меньшей мере M событий, определенных и/или созданных разными участниками, которые все имеют номер раунда R-1. Если такое целое число отсутствует, номер раунда для события может быть значением по умолчанию (например, 0, 1 и т. д.). В таких случаях номер раунда для события может быть вычислен без использования приращения раунда. Например, как показано на фиг. 8, если M определено как наименьшее целое число, превышающее N в 1/2 раза, то M равняется трем. Тогда событие 1412 строго видит M событий 1401, 1402 и 1408, каждое из которых было определено отличным участником и имеет номер раунда, равный 1. Событие 1412 не может строго видеть по меньшей мере M событий с номером раунда, равным 2, которые были определены отличными участниками. Следовательно, номер раунда для события 1412 равняется 2. В некоторых случаях первое событие в распределенной базе данных имеет номер раунда, равный 1. В других случаях первое событие в распределенной базе данных может иметь номер раунда, равный 0, или любой другой подходящий номер.

[1073] «Ответвление» («Forking»): событие X вместе с событием Y являются ответвлением, если они определены и/или созданы одним участником, и ни одно из них не является собственным предком другого. Например, как показано на фиг. 9, участник Дэйв создает ответвление, создавая и/или определяя события 1503 и 1504, оба из которых имеют одного собственного родителя (т. е. событие 1501), так что событие 1503 не является собственным предком события 1504, и событие 1504 не является собственным предком события 1503.

[1074] «Идентификация» («Identification») ответвления: ответвление может быть «идентифицировано» третьим событием, созданным и/или определенным после двух событий, которые вместе являются ответвлениями, если оба те два события являются предками третьего события. Например, как показано на фиг. 9, участник Дэйв создает ответвление, создавая события 1503 и 1504, ни одно из которых не является собственным предком другого. Это ответвление может быть идентифицировано более поздним событием 1506, поскольку оба события 1503 и 1504 являются предками события 1506. В некоторых случаях идентификация ответвления может указывать на то, что конкретный участник (например, Дэйв) мошенничает.

[1075] «Идентификация» («Identification») события: событие X «идентифицирует» или «видит» событие-предка Y, если X не имеет события-предка Z, которое является ответвлением вместе с Y. Например, как показано на фиг. 8, событие 1412 идентифицирует (то есть «видит») событие 1403, поскольку событие 1403 является предком события 1412, и событие 1412 не имеет событий-предков, которые являются ответвлениями вместе с событием 1403. В некоторых случаях событие X может идентифицировать событие Y, если X не идентифицирует ответвление до события Y. В таких случаях, даже если событие X идентифицирует ответвление, создаваемое участником, определяющим событие Y, после события Y, событие X может видеть событие Y. Событие X не идентифицирует события того участника после ответвления. Более того, если участник определяет два разных события, которые оба являются первыми событиями того участника в истории, событие X может идентифицировать ответвление и не идентифицировать никакое событие того участника.

[1076] «Строгая идентификация» («Strong identification», также называемая в настоящем документе «strongly seeing» или «строгое видение») события: событие X «строго идентифицирует» (или «строго видит») событие-предка Y, созданное и/или определенное тем же участником, что и X, если X идентифицирует Y. Событие X «строго идентифицирует» событие-предка Y, которое не было создано и/или определено тем же участником, что и X, если существует набор S событий, которые (1) включают как X, так и Y, и (2) являются предками события X, и (3) являются потомками события-предка Y, и (4) идентифицируются X, и (5) каждое из которых может идентифицировать Y, и которые (6) созданы и/или определены по меньшей мере M разными участниками. Например, как показано на фиг. 8, если M определено как наименьшее целое число, которое превышает 2/3 от N (т. е. M=1+floor(2N/3), что будет равно четырем в этом примере), то событие 1412 строго идентифицирует событие-предка 1401, поскольку набор событий 1401, 1402, 1406 и 1412 представляет собой набор из по меньшей мере четырех событий, которые являются предками события 1412 и потомками события 1401, и они созданы и/или определены четырьмя участниками Дэйвом, Кэрол, Бобом и Эдом соответственно, и событие 1412 идентифицирует каждое из событий 1401, 1402, 1406 и 1412, и каждое из событий 1401, 1402, 1406 и 1412 идентифицирует событие 1401. Подобным образом, событие X (например, событие 1412) может «строго видеть» событие Y (например, событие 1401), если X может видеть по меньшей мере M событий (например, события 1401, 1402, 1406 и 1412), созданных или определенных разными участниками, каждый из которых может видеть Y.

[1077] «Первое событие раунда R» (также называемое в настоящем документе «свидетелем», или «witness»): событие представляет собой «первое событие раунда R» (или «свидетеля»), если событие (1) имеет номер раунда R и (2) имеет собственного родителя, имеющего номер раунда, который меньше R, или не имеет собственного родителя. Например, как показано на фиг. 8, событие 1412 представляет собой «первое событие раунда 2», поскольку оно имеет номер раунда, равный двум, и его собственным родителем является событие 1408, которое имеет номер раунда, равный одному (т. е. меньше двух).

[1078] В некоторых случаях приращение раунда для события X определяют как 1, если и только если X «строго идентифицирует» по меньшей мере M «первых событий раунда R», где R является максимальным номером раунда его родителей. Например, как показано на фиг. 8, если M определено как наименьшее целое число, превышающее N в 1/2 раза, то M равняется трем. Тогда событие 1412 строго идентифицирует M событий 1401, 1402 и 1408, которые все являются первыми событиями раунда 1. Оба родителя события 1412 принадлежат к раунду 1, и 1412 строго идентифицирует по меньшей мере M первых событий раунда 1, следовательно, приращение раунда для 1412 равно одному. Каждое из событий на схеме с отметкой «RI=0» не может строго идентифицировать по меньшей мере M первых событий раунда 1, следовательно, их приращения раунда равны 0.

[1079] В некоторых случаях следующий способ может быть использован для определения того, может ли событие X строго идентифицировать событие-предка Y. Для каждого первого события-предка Y раунда R поддерживается массив A1 целых чисел, по одному на участника, который задает наименьший порядковый номер события X, где тот участник создал и/или определил событие X, и X может идентифицировать Y. Для каждого события Z поддерживается массив A2 целых чисел, по одному на участника, который задает наибольший порядковый номер события W, созданного и/или определенного тем участником, так что Z может идентифицировать W. Для определения того, может ли Z строго идентифицировать событие-предка Y, подсчитывается количество таких положений E элемента, что A1[E] <= A2[E]. Событие Z может строго идентифицировать Y, если и только если эта подсчитанная величина превышает M. Например, как показано на фиг. 8, участники Алиса, Боб, Кэрол, Дэйв и Эд каждый могут идентифицировать событие 1401, при этом самым ранним событием, которое может это сделать, является их событие {1404, 1403, 1402, 1401, 1408} соответственно. Эти события имеют порядковые номера A1={1,1,1,1,1}. Подобным образом, самым поздним событием каждого из них, которое идентифицируется событием 1412, является событие {ОТСУТСТВУЕТ, 1406, 1402, 1401, 1412}, где у Алисы указано «ОТСУТСТВУЕТ», поскольку 1412 не может идентифицировать ни одно из событий Алисы. Эти события имеют порядковые номера A2={0,2,1,1,2} соответственно, при этом все события имеют положительные порядковые номера, так что 0 означает, что у Алисы нет событий, которые идентифицируются событием 1412. При сравнении списка A1 со списком A2 получают результаты {1<=0, 1<=2, 1<=1, 1<=1, 1<=2}, что эквивалентно {ложь, истина, истина, истина, истина}, где имеется четыре значения, которые являются истинными. Следовательно, существует набор S из четырех событий, которые являются предками события 1412 и потомками события 1401. Четыре соответствует по меньшей мере M, следовательно, 1412 строго идентифицирует 1401.

[1080] Еще один вариант реализации способа определения с помощью A1 и A2 того, может ли событие X строго идентифицировать событие-предка Y, является следующим. Если целочисленные элементы в обоих массивах меньше 128, то можно сохранить каждый элемент в одном байте и упаковать 8 таких элементов в одно 64-битное слово, и допустить, что A1 и A2 являются массивами таких слов. Самый старший бит каждого байта в A1 может быть установлен в 0, и самый старший бит каждого байта в A2 может быть установлен в 1. Два соответствующих слова вычитают, затем выполняют побитовую операцию И с использованием маски для обнуления всего, кроме самых старших битов, затем выполняют сдвиг вправо на 7 битовых позиций для получения значения, которое выражается на языке программирования C как: ((A2[i] - A1[i]) & 0x8080808080808080) >> 7). Это может быть добавлено в регистровый стек S, который был инициализирован в нуль. После выполнения этого действия множество раз преобразуют регистр в счетчик посредством сдвига и добавления байтов для получения ((S & 0xff) + ((S >> 8) & 0xff) + ((S >> 16) & 0xff) + ((S >> 24) & 0xff) + ((S >> 32) & 0xff) + ((S >> 40) & 0xff) + ((S >> 48) & 0xff) + ((S >> 56) & 0xff)). В некоторых случаях эти вычисления могут быть выполнены на таких языках программирования, как C, Java и/или т. п. В других случаях вычисления могут быть выполнены с использованием специфических для процессора инструкций, таких как инструкции Advanced Vector Extensions (AVX), предоставленные Intel и AMD, или эквивалента в графическом процессоре (GPU) или графическом процессоре общего назначения (GPGPU). На некоторых архитектурах вычисления могут быть выполнены быстрее с использованием слов, которые длиннее 64 битов, например, длиной 128, 256, 512 или более битов.

[1081] «Известное» («Famous») событие: событие X раунда R является «известным», если (1) событие X является «первым событием раунда R» (или «свидетелем»), и (2) решение «ДА» достигается путем выполнения протокола византийского соглашения, описанного ниже. В некоторых вариантах осуществления протокол византийского соглашения может быть выполнен экземпляром распределенной базы данных (например, экземпляром 114 распределенной базы данных) и/или модулем конвергенции базы данных (например, модулем 211 конвергенции базы данных). Например, как показано на фиг. 8, показаны пять первых событий раунда 1: 1401, 1402, 1403, 1404 и 1408. Если M определено как наименьшее целое число, превышающее N в 1/2 раза, что равняется трем, то 1412 представляет собой первое событие раунда 2. Если протокол продолжается дальше, то хешграф будет расти вверх, и в итоге другие четыре участника будут также иметь первые события раунда 2 над верхней частью этой фигуры. Каждое первое событие раунда 2 будет иметь «голос» («vote») относительно того, является ли каждое из первых событий раунда 1 «известным». Событие 1412 будет голосовать ДА за то, что 1401, 1402 и 1403 являются известными, поскольку они являются первыми событиями раунда 1, которые оно может идентифицировать. Событие 1412 будет голосовать НЕТ против того, что 1404 является известным, поскольку 1412 не может идентифицировать 1404. Для заданного первого события раунда 1, такого как 1402, решение относительно того, является ли его статус «известным» или нет, будет принято на основе подсчета голосов каждого первого события раунда 2 относительно того, является оно известным или нет. Те голоса будут затем распространяться на первые события раунда 3, затем на первые события раунда 4 и так далее до тех пор, пока в итоге не будет достигнуто согласие относительно того, является ли 1402 известным. Подобный процесс повторяется для других первых событий.

[1082] Протокол византийского соглашения может собирать и использовать голоса и/или решения «первых событий раунда R» для идентификации «известных» событий. Например, «первое событие Y раунда R+1» будет голосовать «ДА», если Y может «идентифицировать» событие X, в ином случае оно проголосует «НЕТ». Голоса затем подсчитываются для каждого раунда G, для G = R+2, R+3, R+4 и т. д. до тех пор, пока не будет принято решение любым участником. Голоса подсчитываются для каждого раунда G до тех пор, пока не принято решение. Некоторые из тех раундов могут представлять собой «мажоритарные» раунды, тогда как некоторые из других раундов могут представлять собой раунды «с подбрасыванием монеты». В некоторых случаях, например, раунд R+2 является мажоритарным раундом, и будущие раунды определяются либо как мажоритарный раунд, либо как раунд с подбрасыванием монеты (например, согласно предварительно определенной схеме). Например, в некоторых случаях произвольно может быть определено, является ли будущий раунд мажоритарным раундом или раундом с подбрасыванием монеты, при условии что не может быть двух последовательных раундов с подбрасыванием монеты. Например, может быть предварительно определено, что будет пять мажоритарных раундов, затем один раунд с подбрасыванием монеты, затем пять мажоритарных раундов, затем один раунд с подбрасыванием монеты, с повторением до тех пор, пока не будет достигнуто согласие.

[1083] В некоторых случаях, если раунд G является мажоритарным раундом, голоса могут быть подсчитаны следующим образом. Если существует событие раунда G, которое строго идентифицирует по меньшей мере M первых событий раунда G-1, голосующих V (где V представляет собой либо «ДА», либо «НЕТ»), то согласованным решением является V, и протокол византийского соглашения завершается. В ином случае каждое первое событие раунда G вычисляет новый голос, представляющий собой решение большинства первых событий раунда G-1, которые каждое первое событие раунда G может строго идентифицировать. В случаях равенства голосов и отсутствия большинства решение может быть обозначено как «ДА».

[1084] Подобным образом, если X является свидетелем раунда R (или первым событием раунда R), то результаты голосования в раундах R+1, R+2 и так далее могут быть вычислены, при этом свидетели в каждом раунде голосуют относительно того, является ли X известным. В раунде R+1 каждый свидетель, который может видеть X, голосует ДА, а другие свидетели голосуют НЕТ. В раунде R+2 каждый свидетель голосует согласно большинству голосов свидетелей раунда R+1, которые он может строго видеть. Подобным образом, в раунде R+3 каждый свидетель голосует согласно большинству голосов свидетеля раунда R+2, которого он может строго видеть. Это может продолжаться несколько раундов. В случае равенства голосов голос может быть установлен в ДА. В других случаях равенство голосов может быть установлено в НЕТ или может быть установлено случайным образом. Если какой-либо раунд имеет по меньшей мере M свидетелей, голосующих НЕТ, то выборы завершаются, и X не является известным. Если какой-либо раунд имеет по меньшей мере M свидетелей, голосующих ДА, то выборы завершаются, и X является известным. Если ни ДА, ни НЕТ не имеет по меньшей мере M голосов, выборы переходят к следующему раунду.

[1085] В качестве примера, на фиг. 8 предполагается первое событие X некоторого раунда, которое находится ниже показанной фигуры. Тогда каждое первое событие раунда 1 будет иметь голос относительно того, является ли X известным. Событие 1412 может строго идентифицировать первые события 1401, 1402 и 1408 раунда 1. Таким образом, его голос будет основан на их голосах. Если это мажоритарный раунд, то 1412 будет проверять, имеют ли по меньшей мере M событий {1401, 1402, 1408} голос ДА. Если имеют, то решением является ДА, и согласие было достигнуто. Если по меньшей мере M из них голосует НЕТ, то решением является НЕТ, и согласие было достигнуто. Если количество голосов не составляет по меньшей мере M в любую из сторон, то 1412 получает голос, который представляет собой большинство голосов событий 1401, 1402 и 1408 (и разрушает равенство голосов посредством голосования ДА, если было равенство голосов). Тот голос затем будет использован в следующем раунде, продолжающемся до тех пор, пока не будет достигнуто согласие.

[1086] В некоторых случаях, если раунд G является раундом с подбрасыванием монеты, голоса могут быть подсчитаны следующим образом. Если событие X может идентифицировать по меньшей мере M первых событий раунда G-1, голосующих V (где V представляет собой либо «ДА», либо «НЕТ»), то событие X изменит свой голос на V. Иначе, если раунд G является раундом с подбрасыванием монеты, то каждое первое событие X раунда G меняет свой голос на результат псевдослучайного определения (подобно подбрасыванию монеты в некоторых случаях), который определяется как самый младший бит подписи события X.

[1087] Подобным образом, в таких случаях, если выборы достигают раунда R+K (раунда с подбрасыванием монеты), где K – определенный коэффициент (например, кратный числу, такому как 3, 6, 7, 8, 16, 32 или любому другому подходящему числу), то выборы не завершаются на том раунде. Если выборы достигают этого раунда, они могут продолжиться по меньшей мере на еще один раунд. В таком раунде, если событие Y является свидетелем раунда R+K, то, если оно может строго видеть по меньшей мере M свидетелей из раунда R+K-1, которые голосуют V, Y проголосует V. Иначе Y проголосует согласно случайному значению (например, согласно биту подписи события Y (например, самому младшему биту, самому старшему биту, случайно выбранному биту), где 1=ДА и 0=НЕТ или наоборот, согласно метке времени события Y, с использованием криптографического протокола «shared coin» и/или любого другого случайного определения). Это случайное определение является непредсказуемым до создания Y, и, таким образом, можно повысить безопасность событий и протокола консенсуса.

[1088] Например, как показано на фиг. 8, если раунд 2 является раундом с подбрасыванием монеты, и происходит голосование относительно того, было ли некоторое событие до раунда 1 известным, то событие 1412 будет сначала проверять, проголосовало ли по меньшей мере M событий {1401, 1402, 1408} ДА, или по меньшей мере M из них проголосовало НЕТ. Если это так, то 1412 проголосует так же. Если отсутствует по меньшей мере M голосов в любую из сторон, то 1412 будет иметь случайный или псевдослучайный голос (например, на основе самого младшего бита цифровой подписи, которую Эд создал для события 1412, когда он подписал его во время его создания и/или определения).

[1089] В некоторых случаях результат псевдослучайного определения может быть результатом криптографического протокола shared coin, который может быть, например, реализован как самый младший бит пороговой подписи номера раунда.

[1090] Как описано выше, в некоторых реализациях способ достижения консенсуса хешграфа может включать принятие решения, например, относительно известности свидетеля X в раунде R. Как описано выше, первоначальные голоса могут быть собраны из раунда R+1, подсчитывая голоса ДА или НЕТ каждого события согласно тому, является ли оно потомком X. Альтернативный подход может включать сбор первоначальных голосов из «R+2» вместо «R+1» (или «R+3», «R+4» и т. д. вместо «R+1»). В том подходе может быть факультативно добавлен дополнительный этап. В частности, в такой реализации, каждый раз когда первое событие X раунда R (или свидетель X раунда R) является предком свидетелей раунда R+1, созданных и/или определенных более чем двумя третями популяции (т. е. более чем 2N/3 участников), X сразу объявляется известным, и выборы сразу завершаются, даже до того как любые голоса для X будут подсчитаны. Второй альтернативный подход может включать запуск выборов для R с первоначальными голосами, собранными из R+1, затем, если количество участников, которые создали и/или определили свидетелей в раунде R, относительно которых приняли решение, что они известные, меньше заданного порога T, повторно запускают выборы во второй раз с первоначальными голосами, собранными из R+2.

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

[1092] «Принятый раунд» («Received round»): событие X имеет «принятый раунд» R, если R является таким минимальным целым числом, что по меньшей мере половина известных первых событий раунда R (или известных свидетелей) с номером раунда R являются потомками X и/или могут видеть X. В других случаях может быть использована любая другая подходящая процентная доля. Например, в другом случае событие X имеет «принятый раунд» R, если R является таким минимальным целым числом, что по меньшей мере предопределенная процентная доля (например, 40 %, 60 %, 80 % и т. д.) известных первых событий раунда R (или известных свидетелей) с номером раунда R являются потомками X и/или могут видеть X.

[1093] В некоторых случаях «принятое поколение» события X может быть вычислено следующим образом. Находят, какой участник создал и/или определил каждое первое событие раунда R, которое может идентифицировать событие X. Затем определяют номер поколения для самого раннего события того участника, которое может идентифицировать X. Затем определяют «принятое поколение» X как медиану того списка.

[1094] В некоторых случаях «принятая метка времени» T события X может быть медианой меток времени в событиях, которые включают первое событие каждого участника, которое идентифицирует и/или видит X. Например, принятая метка времени события 1401 может быть медианой значения меток времени для событий 1402, 1403, 1403 и 1408. В некоторых случаях метка времени для события 1401 может быть включена в вычисление медианы. В других случаях принятая метка времени для X может быть любым другим значением или комбинацией значений меток времени в событиях, которые являются первыми событиями каждого участника для идентификации или видения X. Например, принятая метка времени для X может быть основана на среднем значении меток времени, среднеквадратичном отклонении меток времени, модифицированном среднем значении (например, путем убирания из вычисления самой ранней и самой поздней меток времени) и/или т. п. В еще других случаях может быть использована расширенная медиана.

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

[1096] В других случаях вместо использования подписи каждого события может быть использована подпись того события, подвергнутая операции исключающего ИЛИ с подписями известных событий или известных свидетелей с тем же принятым раундом и/или принятым поколением в том раунде. В других случаях любая другая подходящая комбинация подписей событий может быть использована для разрушения равенств, чтобы определять порядок консенсуса событий. Результат подписей, подвергнутых операции исключающего ИЛИ, известных свидетелей в заданном раунде представляет псевдослучайное число, которое сложно предсказать и/или которым сложно манипулировать потенциальным злоумышленникам и другим субъектам. Таким образом, в некоторых реализациях подписи, подвергнутые операции исключающего ИЛИ, могут быть использованы как источник непредсказуемых случайных чисел (т. е. «случайная отметка»). Случайные числа могут быть использованы в нескольких процессах хешграфа, включая исполнение умных контрактов, как обсуждено ниже.

[1097] В некоторых реализациях способ достижения консенсуса могут приспособить так, что исполняемый скрипт или программу («умный контракт») исполняет каждый участник хешграфа (например, процессор каждого участника или вычислительного устройства). Умный контракт может быть самоисполняемым контрактом, контрактом цепочки блоков или цифровым контрактом, преобразованным в компьютерный код, сохраненный и дублированный в хешграфе и контролируемый участниками хешграфа. Умные контракты могут быть использованы, например, для обмена денег, имущества, акций и других подходящих операций. Участники могут записывать результаты исполненного умного контракта в распределенной базе данных или распределенном реестре. В некоторых других реализациях алгоритм консенсуса может быть приспособлен так, что часть участников (а не каждый участник) запускает умный контракт на основе недетерминированного кода, исходом котором является функция распределения времени компьютера, или результатов осуществления связи с еще одним компьютером (например, помимо участников распределенной базы данных). Соответственно, набор участников, выбранных для того и/или имеющих право на то, чтобы исполнять умный контракт, может быть выбран на основе детерминированной псевдослучайной функции случайной отметки (выданной, например, на основе результата подписей, подвергнутых операции исключающего ИЛИ, известных свидетелей). Каждый из выбранных участников может генерировать транзакцию для записывания выходных данных или результатов, полученных вследствие запуска умного контракта. В некоторых случаях, если более чем две трети выбранных участников получают совпадающие результаты, то такие результаты рассматриваются как официальные выходные данные контракта, и состояние распределенной базы данных или реестра может быть модифицировано для отражения консенсуса на умный контракт соответственно. В некоторых других случаях, когда нет единых выходных данных или результата, совпадающего или согласованного у более чем двух третей выбранных участников, то считается, что умный контракт дает сбой, и состояние распределенной базы данных или реестра не меняется. В других реализациях порог, составляющий две трети выбранных участников, может представлять собой любой другой подходящий порог. Например, в некоторых реализациях порог может быть разным для каждого запуска умного контракта.

[1098] В некоторых случаях умные контракты могут быть недетерминированными из-за того, что они используют чисто случайные числа, полученные с аппаратного устройства, путем доступа к сети или внешнему компьютеру, такому как веб-сервер («oracle»), и/или за заданный лимит времени. В некоторых случаях, когда участник или вычислительное устройство исполняет умный контракт и такой контракт не выдает выходных данных в течение заданного количества миллисекунд, то вычислительное устройство прекращает или останавливает работу умного контракта и отправляет отчет о том, что он не имеет выходных данных. В некоторых случаях вычислительные устройства участников могут запускаться с разными скоростями, делая процесс недетерминированным. Кроме того, в некоторых случаях вычислительные устройства участников могут быть приспособлены для запуска со своей полной скоростью скомпилированного кода, без запуска интерпретатора и/или подсчета количества показателей, которые были исполнены до настоящего времени вычислительным устройством.

[1099] В еще других случаях вместо определения «принятого поколения» как медианы списка «принятое поколение» может быть определено как сам список. Тогда при сортировке по принятому поколению два принятых поколения могут быть сравнены по средним элементам их списков, с разрушением равенств по элементу непосредственно перед серединой, с разрушением тех равенств по элементу непосредственно после середины и с продолжением чередования между элементом перед используемым до этого и элементом после, пока равенство не будет разрушено.

[1100] В некоторых случаях медианная метка времени может быть заменена «расширенной медианой». В таких случаях список меток времени может быть определен для каждого события, вместо одной принятой метки времени. Список меток времени для события X может включать первое событие каждого участника, которое идентифицирует и/или видит X. Например, как показано на фиг. 8, список меток времени для события 1401 может включать метки времени для событий 1402, 1403, 1403 и 1408. В некоторых случаях также может быть включена метка времени для события 1401. При разрушении равенства со списком меток времени (т. е. два события имеют один и тот же принятый раунд) могут быть сравнены средние метки времени списка каждого события (или предопределенные первая или вторая из двух средних меток времени, если длина четная). Если эти метки времени являются одинаковыми, могут быть сравнены метки времени непосредственно после средних меток времени. Если эти метки времени являются одинаковыми, могут быть сравнены метки времени непосредственно перед средними метками времени. Если эти метки времени также являются одинаковыми, сравнивают метки времени после трех уже сравненных меток времени. Это чередование может продолжаться до тех пор, пока равенство не будет разрушено. Подобно вышеизложенному обсуждению, если два списка идентичны, равенство может быть разрушено по подписям двух элементов.

[1101] В еще других случаях «усеченная расширенная медиана» может быть использована вместо «расширенной медианы». В таком случае весь список меток времени не сохраняют для каждого события. Вместо этого лишь несколько значений рядом с центром списка сохраняют и используют для сравнения.

[1102] Принятая медианная метка времени может быть потенциально использована для других целей в дополнение к вычислению общего порядка событий. Например, Боб мог подписать контракт, в котором говорится, что он берет на себя обязательства по соблюдению контракта, если и только если существует событие X, содержащее транзакцию, в которой Алиса подписывает тот же контракт, причем принятая метка времени для X соответствует определенному крайнему сроку или более раннему моменту времени. В том случае Боб не возьмет на себя обязательства по соблюдению контракта, если Алиса подпишет его после крайнего срока, указанного «принятой медианной меткой времени», как описано выше.

[1103] В некоторых случаях состояние распределенной базы данных может быть определено после достижения консенсуса. Например, если S(R) является набором событий, который могут видеть известные свидетели в раунде R, в итоге все события в S(R) будут иметь известные принятый раунд и принятую метку времени. На этом этапе порядок консенсуса для событий в S(R) известен и меняться не будет. Когда этот этап достигнут, участник может вычислить и/или определить представление событий и их порядок. Например, участник может вычислить значение хеша событий в S(R) в их порядке консенсуса. Участник может затем подписать с помощью цифровой подписи значение хеша и включить значение хеша в следующее событие, которое определяет участник. Это может быть использовано для оповещения других участников о том, что тот участник определил, что события в S(R) имеют заданный порядок, который не будет меняться. После того как по меньшей мере M участников (или любое другое подходящее количество или процентная доля участников) подписали значение хеша для S(R) (и, таким образом, согласились с порядком, представленным значением хеша), тот список консенсуса событий вместе со списком подписей участников могут образовать один файл (или другую структуру данных), который может быть использован для доказательства того, что порядок консенсуса был таковым, как заявлено, для событий в S(R). В других случаях, если события содержат транзакции, которые обновляют состояние системы распределенной базы данных (как описано в настоящем документе), то значение хеша может представлять состояние системы распределенной базы данных после применения транзакций событий в S(R) в порядке консенсуса.

[1104] В некоторых реализациях хешграф может быть использован для реализации услуги аннулирования. Услуга аннулирования может записывать или сохранять информацию о том, являются ли определенные объекты все еще подлинными. В некоторых случаях услуга аннулирования может быть использована для сохранения подлинных или неистекших хешей удостоверяющих данных, выданных органом, которые орган может позже аннулировать (например, водительские права, выданные DMV, которые могут быть позже аннулированы DMV; паспорта, выданные государством, которые могут быть позже аннулированы государством; информация о составе участников для клуба; и т. д.). В некоторых случаях услуга аннулирования может использовать тип транзакции для добавления новой записи в распределенную базу данных или реестр, имеющий форму (H, T, L), где H представляет собой криптографический хеш, связанный с объектом или субъектом, T представляет собой обозначение для «типа» объекта или субъекта, L представляет собой список открытых ключей, и запись подписана с помощью нескольких закрытых ключей, связанных с открытыми ключами, включенными в список L, или не подписана ни с помощью одного из них. Дополнительный тип транзакции, который может быть использован услугой аннулирования, может удалять или убирать заданный хеш H. Такая транзакция может быть приспособлена так, чтобы быть подписанной с помощью закрытого ключа, связанного с одним (или множеством) из открытых ключей в списке L, связанном с хешем H, который должен быть удален или убран. Другие типы специальных транзакций, которые могут быть использованы услугой аннулирования, включают транзакции для извлечения записи с учетом ее хеша H и транзакции для извлечения, например, всех записей с определенных момента времени и даты, которые имеют заданное значение T, и другие подходящие транзакции. Несмотря на то что вышеизложенные транзакции были обсуждены в отношении услуги аннулирования, такие транзакции могут быть использованы другими подходящими услугами в хешграфе.

[1105] В некоторых случаях M (как описано выше) может быть основано на весовых значениях, присвоенных каждому участнику, нежели всего лишь на части, процентном отношении и/или значении количества всех участников. В таком случае каждый участник имеет долю, связанную с его заинтересованностью и/или влиянием в системе распределенной базы данных. Такая доля может представлять собой весовое значение. Можно сказать, что каждое событие, определенное тем участником, имеет весовое значение его определяющего участника. Тогда M может быть частью от общей доли всех участников. События, описанные выше как зависимые от M, будут происходить, когда набор участников с суммарным количеством долей по меньшей мере M придет к согласию. Таким образом, на основе своей доли определенные участники могут иметь большее влияние на систему и на то, каким образом получается порядок консенсуса. В некоторых случаях транзакция в событии может менять долю одного или более участников, добавлять новых участников и/или удалять участников. Если такая транзакция имеет принятый раунд R, то после вычисления принятого раунда события после свидетелей раунда R будут повторно вычислять свои номера раундов и другую информацию с использованием модифицированных долей и модифицированного списка участников. Голоса относительно того, являются ли события раунда R известными, будут использовать старые доли и список участников, но голоса относительно раундов после R будут использовать новые доли и список участников. Дополнительные подробности относительно использования весовых значений для определения консенсуса описаны в предварительной заявке на патент США № 62/344682, поданной 2 июня 2016 г. и озаглавленной «Methods And Apparatus For A Distributed Database With Consensus Determined Based On Weighted Stakes», которая включена в настоящий документ посредством ссылки во всей своей полноте.

[1106] В некоторых случаях определенные участники могут быть идентифицированы и/или назначены как «ленивые участники». В таких случаях ленивые участники могут определять и/или создавать события, подобно нормальным участникам или неленивым участникам. Кроме того, события, определенные и/или созданные ленивыми участниками, могут быть включены в хешграф, и порядок консенсуса для таких событий может быть вычислен и/или идентифицирован. Однако приращение раунда для событий, определенных ленивыми участниками, равняется нулю. Соответственно, номер раунда (или раунд, который создан) для события, определенного ленивым участником, равняется максимуму номеров раундов родителей события. Подобным образом, поскольку приращение раунда для событий, определенных ленивыми участниками, равняется нулю, номер раунда (или раунд, который создан) для события, определенного ленивым участником, не может превышать максимум номеров раундов родителей события.

[1107] Более того, в некоторых случаях события, определенные ленивыми участниками, не имеют права голосовать на выборах, и события, определенные ленивыми участниками, не имеют права становиться первыми событиями или свидетелями раунда R и/или не учитываются как промежуточные события для события, определенного нормальным или неленивым участником, чтобы строго видеть другое событие. Соответственно, ограничения, накладываемые на ленивых участников, приводят в результате к сокращению вычислений, выполняемых хешграфом, при этом все еще поддерживается безопасность и целостность порядка консенсуса. Участники могут быть выбраны как ленивые участники на основе любых подходящих критериев. Например, в некоторых случаях участники могут быть назначены как ленивые участники на основе детерминированного псевдослучайного выбора, выполняемого в каждом раунде, предварительно определенного в начале раунда, на основе уровней доверия, на основе объема доли, на основе голоса других участников и/или выбора случайным образом. В некоторых случаях участники, назначенные как ленивые участники, могут быть разными для каждого раунда, тогда как в некоторых других случаях участники, назначенные как ленивые участники, остаются таковыми на протяжении разных раундов. В некоторых других случаях события, а не участники могут быть назначены как «ленивые» события. В таком случае ленивые события могут выбираться в каждом раунде вместо выбора участников.

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

[1109] Вышеизложенные термины, определения и алгоритмы используются для иллюстрации вариантов осуществления и концепций, описанных в отношении фиг. 8–10B. На фиг. 10A и фиг. 10B проиллюстрировано первое примерное применение способа и/или процесса достижения консенсуса, показанное в математической форме. На фиг. 11A и фиг. 11B проиллюстрировано второе примерное применение способа и/или процесса достижения консенсуса, показанное в математической форме, и на фиг. 12A и фиг. 12B проиллюстрировано третье примерное применение способа и/или процесса достижения консенсуса, показанное в математической форме.

[1110] На фиг. 2 модуль 211 конвергенции базы данных и модуль 212 связи показаны на фиг. 2 как реализованные в процессоре 210. В других вариантах осуществления модуль 211 конвергенции базы данных и/или модуль 212 связи могут быть реализованы в памяти 220. В еще других вариантах осуществления модуль 211 конвергенции базы данных и/или модуль 212 связи могут быть основаны на аппаратном обеспечении (например, ASIC, FPGA и т. д.).

[1111] В некоторых случаях распределенная база данных (например, показанная и описанная в отношении фиг. 1) может позволять выполнять обработку «посреднических транзакций». В некоторых случаях такие посреднические транзакции могут быть совершены участником распределенной базы данных от имени лица, которое не является участником распределенной базы данных, участника распределенной базы данных с правами, не являющимися полными (например, имеющего права чтения, но не права записи, не оказывающего влияние на согласованные решения и т. д.), и/или т. п. Например, предположим, что Алиса желает подать транзакцию TR в распределенную базу данных, но она не является полноправным участником распределенной базы данных (например, Алиса не является участником или имеет ограниченные права). Предположим, что Боб является полноправным участником и имеет полные права в распределенной базе данных. В этом случае Алиса может отправлять транзакцию TR Бобу, и Боб может подавать TR в сеть с целью оказания влияния на распределенную базу данных. В некоторых случаях Алиса может подписывать TR с помощью цифровой подписи. В некоторых случаях TR может содержать, например, платеж Бобу (например, комиссию за его услугу подачи TR в распределенную базу данных). В некоторых случаях Алиса может передавать TR Бобу посредством анонимизирующей сети, такой как сеть луковой маршрутизации TOR, чтобы ни Боб, ни другие наблюдатели не могли определить, что TR поступило от Алисы.

[1112] В некоторых случаях распределенная база данных (например, показанная и описанная в отношении фиг. 1) может быть использована для реализации криптовалюты. В таком случае каждый экземпляр 114, 124, 134, 144 распределенной базы данных может определять одну или более структур данных кошелька (также называемых в настоящем документе кошельками) для хранения криптовалюты. В некоторых случаях пользователи, которые не связаны с распределенной базой данных (например, вычислительные устройства, которые не являются участниками распределенной базы данных), могут также создавать и/или определять такие кошельки. Структура данных кошелька может содержать пару ключей (открытый ключ и закрытый ключ). В некоторых случаях пара ключей для кошелька может быть сгенерирована вычислительным устройством, на котором создают этот кошелек. Например, если Алиса определяет кошелек (W, K), при этом W является открытым ключом (который также может служить идентификатором для кошелька), и K является закрытым ключом, она может опубликовать W (например, в событии) в остальных экземплярах распределенной базы данных, сохранив при этом свой идентификатор анонимным, чтобы другие экземпляры распределенной базы данных (или их пользователи) не могли идентифицировать, что кошелек W связан с Алисой. Однако в некоторых случаях переводы криптовалюты являются открытыми. Таким образом, если ее работодатель переводит деньги на W (например, путем использования транзакции в событии), и затем Алиса совершает покупку путем перевода денег с W в магазин (например, с использованием отличной транзакции в отличном событии), то работодатель и магазин могут договориться с целью определения того, что W принадлежит Алисе и что покупка была совершена именно Алисой. Таким образом, во избежание этого для Алисы может быть полезным переводить деньги на новый анонимный кошелек для сохранения анонимности своих транзакций.

[1113] В следующем примере исходят из того, что C монет криптовалюты переводят с кошелька W на кошелек R, если опубликована следующая транзакция (например, в событии), где _K на конце означает, что транзакция подписана с помощью цифровой подписи с помощью закрытого ключа K. Может быть использована следующая форма записи:

TRANSFER(C, W, R)_K

[1114] В некоторых случаях для достижения анонимности в переводе криптовалюты могут быть определены новый тип транзакции и/или функция распределенной базы данных. Например, следующие транзакции будут выполнять перевод C1 монет с кошелька W1 на кошелек R1, а также перевод C2 монет с кошелька W2 на кошелек R2. В некоторых случаях, например, каждый из кошельков W1, R1, W2, R2 может быть связан с участником (или вычислительным устройством) распределенной базы данных или с пользователем, который не связан с распределенной базой данных (или вычислительным устройством, связанным с распределенной базой данных). Четыре кошелька могут быть связаны с одним участником или пользователем или могут быть связаны с разными участниками или пользователями. В некоторых случаях транзакции могут включать произвольный идентификатор N (например, идентификатор преобразования и/или идентификатор процесса), который предназначен для их соединения.

TRANSFER_DOUBLE(N, C1, W1, R1, C2, W2, R2, T)_K1

TRANSFER_DOUBLE(N, C1, W1, R1, C2, W2, R2, T)_K2

[1115] В некоторых случаях эти транзакции не оказывают влияния, пока кошелек W1 не будет содержать по меньшей мере C1 монет и кошелек W2 не будет содержать по меньшей мере C2 монет. В некоторых случаях эти транзакции не оказывают влияния, пока не будут опубликованы и распределены по другим экземплярам распределенной базы данных две идентичные копии (например, в одном или более событиях), одна подписывается K1 (с использованием закрытого ключа, связанного с открытым ключом W1), и другая подписывается K2 (с использованием закрытого ключа, связанного с открытым ключом W2). В некоторых случаях каждая транзакция может также содержать защищенную метку времени, как описано выше. Эта защищенная метка времени может быть защищенной меткой времени события, с которым связана транзакция, или отдельной защищенной меткой времени транзакции. Если обе транзакции опубликованы с метками времени в течение T секунд друг за другом (например, защищенная метка времени транзакций в пределах предопределенного периода времени друг за другом), то произойдут оба перевода валюты. В противном случае не происходит ни один из переводов. В некоторых случаях транзакция может быть создана и/или определена с датой и временем T истечения срока, и перевод не произойдет, пока обе подписанные транзакции не будут иметь метки времени консенсуса, предшествующие T.

[1116] В других случаях T не используют, и перевод валюты происходит только в том случае, если обе транзакции произойдут до того, как любая из сторон внесет транзакцию, отменяющую перевод. Например, Алиса может опубликовать свою подписанную транзакцию (например, свою транзакцию TRANSFER_DOUBLE), затем опубликовать другую подписанную транзакцию, содержащую сообщение об отмене в отношении этой первой транзакции, затем Боб публикует свою подписанную транзакцию. Перевод не произойдет, если транзакция Боба была позже, чем сообщение Алисы об отмене, но перевод произойдет, если транзакция Боба была раньше, чем сообщение Алисы об отмене. Таким способом система может работать без T и без меток времени, используя упорядоченную последовательность консенсуса транзакций. В других случаях могут поддерживаться как T, так и сообщения об отмене.

[1117] Следующий пример иллюстрирует, как транзакция типа «TRANSFER_DOUBLE» и/или функция распределенной базы данных могут быть использованы для того, чтобы анонимно и защищенным образом начать передачу данных (таких как валюта). В следующем примере Алиса имеет кошелек W1, на который ее работодатель перевел деньги. Она желает перевести C монет с W1 на анонимный кошелек W2, который она создает, который позже будет использован для покупок. Но она желает иметь защищенную анонимность, чтобы никто из просматривающих транзакции не узнал, что W1 связан с анонимным кошельком W2. Он должен быть защищенным, даже если ее работодатель сотрудничает с магазином с целью совершения атаки на анонимность. В дополнение к этому, например, Боб желает такой же защищенной анонимности при переводе монет со своего кошелька W3 на анонимный кошелек W4, который он создает.

[1118] Алиса и Боб могут достичь формы анонимности путем исполнения следующего протокола. Он может включать любую форму осуществления связи друг с другом, такую как непосредственная электронная переписка друг с другом, отправка сообщений друг другу через сайт для обмена текстовыми сообщениями или через сайт онлайн-форума или посредством транзакций, опубликованных в открытой распределенной базе данных или реестре (например, в событиях). Следующий пример исходит из того, что протокол исполняют через открытый реестр. Предположим, что Алиса и Боб вначале являются незнакомцами, но оба обладают способностью публиковать транзакции на открытом реестре и могут читать транзакции, которые другие публикуют на открытом реестре. Алиса и Боб могут публиковать следующие транзакции на открытом реестре (например, в одном или более событиях):

Алиса публикует: Anonymize1(N, C, W1)_K1

Боб подсчитывает: B = encrypt(W4, W1)

Боб публикует: Anonymize2(N, W3, B)_K3

Алиса подсчитывает: A = encrypt(W2, W3)

Алиса публикует: Anonymize3(N, A)_K1

Оба подсчитывают: MIN = min(W2, W4)

Оба подсчитывают: MAX = max(W2, W4)

Боб публикует: TRANSFER_DOUBLE(N, C, W1, MIN, C, W3, MAX, T)_K3

Алиса публикует: TRANSFER_DOUBLE(N, C, W1, MIN, C, W3, MAX, T)_K1

[1119] В этом примере Алиса желает перевести C монет с кошелька W1 на W2, и Боб желает перевести C монет с кошелька W3 на W4. Каждый из Алисы и Боба генерирует свои собственные кошельки путем генерирования пары ключей (открытый ключ, закрытый ключ) для каждого кошелька. Здесь открытый ключ для кошелька также используют в качестве названия кошелька (в других случаях для идентификации кошелька может быть использован отдельный идентификатор). Алиса и Боб желают выполнить эти переводы таким способом, чтобы наблюдатели могли идентифицировать, что владелец кошелька W1 также является владельцем либо W2, либо W4, но не могли идентифицировать, какого именно. Подобным образом, Алиса и Боб желают выполнить эти переводы таким способом, чтобы наблюдатели могли идентифицировать, что владелец кошелька W3 также является владельцем либо W2, либо W4, но не могли идентифицировать, какого именно. Кошелек с открытым ключом W1 имеет закрытый ключ K1. Подобным образом, кошельки W2, W3 и W4 имеют закрытые ключи K2, K3 и K4 соответственно. Каждую транзакцию или инструкцию выше подписывают с помощью закрытого ключа, указанного в конце. Например, первоначальные транзакцию или инструкцию подписывают с помощью цифровой подписи с помощью закрытого ключа K1.

[1120] Первую транзакцию (Anonymize1(N, C, W1)_K1) используют для анонсирования того, что Алиса желает перевести C монет с W1 на анонимный кошелек. Эта транзакция содержит номер N идентификатора, который может представлять собой хеш транзакции, случайное число, содержащееся в транзакции, и/или любой другой подходящий идентификатор. Этот N (например, идентификатор преобразования и/или идентификатор процесса) используют в последующих транзакциях для обратного обращения к транзакции, которая начала процесс, во избежание путаницы (и для обеспечения возможности идентифицировать процесс или преобразование), если имеются несколько подобных процессов и/или преобразований, происходящих в одно и то же время. В некоторых случаях N может содержать крайний срок времени ожидания, после которого транзакции, включающие N, игнорируют. Эту транзакцию подписывают с помощью цифровой подписи с помощью K1.

[1121] Функция encrypt(W4, W1) зашифровывает W4 (открытый ключ кошелька, принадлежащего Бобу и определяемого им в качестве его целевого анонимного кошелька) с использованием открытого ключа W1, что дает результат B, который может быть расшифрован только с помощью соответствующего закрытого ключа K1 (удерживаемого Алисой). Это обеспечивает то, что ни один из других экземпляров распределенной базы данных, просматривающих транзакцию, не сможет идентифицировать W4, за исключением владельца W1 (в этом примере Алисы).

[1122] Транзакция Anonymize2(N, W3, B)_K3 указывает на то, что в качестве части процесса или преобразования N, Боб желает выполнить перевод C монет с W3 на анонимный кошелек, идентифицируемый посредством B. Эту транзакцию подписывают с помощью цифровой подписи с использованием закрытого ключа K3. Алиса может затем расшифровать B с использованием закрытого ключа K1 для идентификации целевого анонимного кошелька Боба как W4.

[1123] Алиса может выполнить функцию encrypt(W2, W3). Это зашифровывает W2 (открытый ключ кошелька, принадлежащего Алисе и определяемого ею в качестве ее целевого анонимного кошелька) с помощью открытого ключа W3 (первоначальный кошелек Боба). Алиса может затем опубликовать транзакцию Anonymize3(N, A)_K1. Боб может идентифицировать W2 как целевой анонимный кошелек Алисы путем расшифровывания с помощью закрытого ключа K3.

[1124] Функция min(W2, W4) возвращает тот из двух открытых ключей W3 и W4, который является первым лексикографически (в алфавитном порядке). Функция max(W2, W4) возвращает тот из двух открытых ключей W3 и W4, который является последним лексикографически (в алфавитном порядке). Таким образом, MIN может быть либо W2, либо W4, и MAX может быть либо W2, либо W4. Функции min и max позволяют упорядочивать кошельки W2 и W4, оба из которых могут идентифицировать Алиса и Боб, но которые не показывают, какой кошелек был создан и/или определен Алисой, а какой был создан и/или определен Бобом. В других случаях любая другая детерминированная функция может быть использована для идентификации в отношении Алисы и Боба, каким образом упорядочивать анонимные кошельки W2 и W4, например, в виде сортировки по хешу ключа, ранжирования и/или т. п.

[1125] Транзакции TRANSFER_DOUBLE могут быть опубликованы как Бобом, так и Алисой и подписаны с помощью их соответствующих закрытых ключей K1 и K3. В связи с тем, что как Боб, так и Алиса переводят одинаковое количество монет C на каждый из своих соответствующих анонимных кошельков, не имеет значения, какой исходный кошелек W1 или W3 переводит монеты в какой целевой кошелек W2 или W4. Таким образом, в некоторых случаях Алиса переводит C монет на свой собственный анонимный кошелек, и Боб переводит C монет на свой собственный анонимный кошелек. В других случаях Алиса переводит C монет на анонимный кошелек Боба, и Боб переводит C монет на анонимный кошелек Алисы. Это определяется функциями MIN и MAX. Это также обеспечивает то, что наблюдатели могут идентифицировать как W2, так и W4, но не смогут идентифицировать, какой кошелек был определен владельцем W1, а какой кошелек был определен владельцем W3. После того как транзакции опубликованы, наблюдатель знает, что владельцы кошельков W1 и W3 взаимодействуют для перевода C монет на каждый из кошельков W2 и W4, но наблюдатель не будет знать, какому отправителю принадлежит тот или иной получающий кошелек, и, таким образом, кошельки W2 и W4 будут слегка более анонимными, чем кошельки W1 и W3.

[1126] В некоторых случаях транзакции могут представлять собой «посреднические транзакции», что означает, что узел в сети подает транзакции от имени другой стороны. В вышеприведенном примере Алиса является владельцем кошельков W1 и W2 и желает опубликовать несколько транзакций. Если Кэрол является участником распределенной базы данных, имеющим полные права, то Алиса может отправлять транзакции Кэрол для подачи в сеть от имени Алисы. В некоторых случаях посредническая транзакция может включать разрешение на перевод небольшой комиссии с кошелька W1 Кэрол в качестве платежа за эту услугу. В некоторых случаях Алиса может осуществлять связь с Кэрол посредством сети, которая анонимизирует связь, такой как, например, сеть луковой маршрутизации TOR. В некоторых случаях Алиса может также быть участником, но работать через Кэрол для анонимности. В некоторых случаях Алиса не является участником.

[1127] В некоторых случаях, например, Алиса может затем повторить вышеописанный протокол анонимности с Дэйвом, и Боб может повторить протокол с Эдом. В тот момент другие экземпляры распределенной базы данных смогут идентифицировать, что Алиса является владельцем одного из 4 кошельков, но не узнают, какого именно. После 10 таких прогонов Алиса является владельцем одного кошелька из 210, что составляет 1024. После 20 прогонов набор составляет более миллиона. После 30 он составляет более миллиарда. После 40 он составляет более триллиона. Прогон протокола должен занимать долю секунды. Но даже если прогон каждого протокола занимает целую секунду, любой, кто предпримет попытку анонимизировать свой кошелек, будет в случайном порядке меняться местами с кем-то другим намного быстрее, чем за минуту. Наблюдатели знают, что Алиса является владельцем одного из полученных в результате кошельков, но не знают, какого именно.

[1128] Эта система может быть менее безопасной, если лишь несколько человек пытаются анонимизировать свои кошельки. В качестве дополнительной меры безопасности Алиса может ждать определенный период времени (например, день, час, неделю и т. д.) и затем дальше анонимизировать свой конечный кошелек, когда участие принимают дополнительные пользователи. Таким способом она может в конечном итоге скрываться среди толпы, которая включает других пользователей, которые пыталась анонимизироваться в течение очень длительного периода времени. Чем больше пользователей, пользующихся системой, тем быстрее она может достичь своей цели. Эта система может быть безопасной, если существует большое количество пользователей, анонимизирующих свои кошельки, даже если существует очень мало участников, действующих как посредники для них.

[1129] Эта система потенциально может быть скомпрометирована, если злоумышленник сможет идентифицировать IP-адрес Алисы, когда она осуществляет связь с сетью, реализующей распределенную базу данных (например, сетью Интернет). Если злоумышленник идентифицирует, что Алиса запустила протокол с определенного IP-адреса, и знает, что она является владельцем либо W2, либо W4, а затем немедленно видит, что кто-то запустил протокол на кошельке W2 с того же самого адреса, он может прийти к выводу, что Алиса является владельцем кошелька W2. Решением является анонимизация IP-адресов. Например, для достижения анонимной связи может быть использована анонимная сеть связи (например, сеть Tor). Затем оставшиеся экземпляры распределенной базы данных могут идентифицировать, что W2 запустил протокол и подписал транзакции, но не смогут идентифицировать, использует ли W2 компьютер Алисы или компьютер Боба.

[1130] В некоторых случаях, после того как Алиса перевела свою криптовалюту на действительно анонимизированный кошелек, она может затем потратить криптовалюту на множество транзакций так, чтобы транзакции не отследили до нее. Дополнительно Алиса может разделить свою криптовалюту между многими анонимизированными кошельками, а затем купить множество предметов, каждый с использованием разного кошелька, не показывая, что они были куплены одним и тем же человеком и/или субъектом.

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

[1132] Шифр с открытым ключом предназначен для выполнения следующего, где «участник» представляет собой компьютер, который действует как часть анонимизирующей сети и/или является частью сети хешграфа и готов действовать как посредник для нее:

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

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

участник может брать существующий открытый ключ (замаскированный или нет) и шифротекст, зашифрованный с помощью существующего открытого ключа, и генерировать замаскированную версию такого шифротекста;

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

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

[1133] Примерный шифр для достижения вышеупомянутых условий обсужден ниже. Участники (например, вычислительные устройства и/или процессоры) могут исполнять этапы для выполнения этого шифра. Во-первых, члены и/или участники осведомлены о математической группе и/или наборе G значений, сохраняют, генерируют и/или могут определять их, вместе с достаточным количеством информации для быстрого распознавания генераторов G. Например, члены могут быть осведомлены о предварительно определенном наборе G значений (например, каждый член и/или участник может независимо генерировать и/или получать общий набор G значений). В некоторых случаях предварительно определенный набор G значений может представлять собой любую алгебраическую группу (например, числа, эллиптические кривые и т. д.). Например, в некоторых случаях набор значений может представлять собой набор чисел G={1,2,3,…,2P} с умножением по модулю 2P+1, где как P, так и 2P+1 представляют собой простой элемент. В таких случаях групповой оператор * может быть определен как умножение по модулю 2P+1, и возведение в степень может быть определено как повторяемое умножение по модулю 2P+1. В таком примере элемент D из G представляет собой генератор, если и только если ни D^2, ни D^P не является конгруэнтным 1 по модулю (2P+1). Из 2P элементов в G, именно phi(2P)=P-1 из них являются генераторами, что составляет приблизительно половину.

[1134] Члены и/или участники знают, сохраняют и/или могут определять G и знают достаточное количество информации для распознавания генераторов. Так что для вышеизложенного примера, члены знают P и знают G={1,2,3,…,2P} с умножением и возведением в степень по модулю 2P+1. В некоторых реализациях шифр определяют следующим образом:

генерирование ключа: избирают или выбирают случайные R1, R2 из G (например, случайные значения R1 и R2). Если R1 не представляет собой генератор для G, то повторно избирают новое случайное R1 до тех пор, пока не будет найден генератор. Таким образом, R1 представляет собой генератор для G. Открытый ключ может быть определен как пара (B,H), которая основана на первом случайном значении R1 и втором случайном значении R2, так что (B,H)=(R1, R1^R2), и закрытый ключ представляет собой S=R2;

шифрование сообщения: при наличии (возможно замаскированного) открытого ключа (B,H) и сообщения F в виде открытого текста (возможно с детерминированным преобразованием или заполнением, но не с недетерминированным случайным преобразованием или заполнением) избирают или выбирают случайное R3 (например, случайное значение R3) из G. Сообщение F в виде открытого текста может затем быть зашифровано с использованием открытого ключа (B,H) и случайного значения R3 для определения зашифрованного шифротекста как (X,Y)=(B^R3, F * H^R3). В некоторых случаях зашифрованный шифротекст может быть зашифрован с использованием замаскированного открытого ключа (B’,H’) или открытого ключа (B,H), который не был замаскирован. Маскировка ключа описана ниже;

маскировка ключа: при наличии (возможно замаскированного) открытого ключа (B,H) избирают или выбирают случайное R4 (например, случайное значение R4) из G. Замаскированный открытый ключ может быть определен как пара (B’,H’), которая основана на открытом ключе (B,H) и случайном значении R4, так что (B’,H’)= (B^R4, H^R4). Если B^R4 не представляет собой генератор для G, то повторно избирают новое случайное R4 до тех пор, пока B^R4 не будет представлять собой генератор для G. Таким образом, B^R4 представляет собой генератор для G;

маскировка сообщения: при наличии шифротекста (X,Y) и (возможно замаскированного) открытого ключа (B,H), который был использован для шифрования шифротекста (X,Y), замаскированное зашифрованное сообщение (X’,Y’) может быть сгенерировано. Например, случайное R5 (например, случайное значение R5) может быть избрано и/или выбрано из G. Замаскированные зашифрованные сообщение и/или шифротекст могут затем быть определены как (X’,Y’)=(X*(B^R5), Y*(H^R5)). В некоторых случаях шифротекст может быть замаскирован с использованием замаскированного открытого ключа (B’,H’) или открытого ключа (B,H), который не был замаскирован.

[1135] В некоторых случаях шифр, описанный выше, может быть использован для шифрования и безопасной отправки сообщения (например, напрямую или путем внесения сообщения в распределенную базу данных и/или распределенный реестр) с первого вычислительного устройства (например, первым участником) на второе вычислительное устройство (например, второму участнику). Например, в некоторых случаях процессор второго вычислительного устройства может выбирать первое случайное значение R1 из предварительно определенного набора G значений, который представляет собой алгебраическую группу. Первое случайное значение R1 выбирается как генератор для G. Процессор может выбирать второе случайное значение R2 из предварительно определенного набора G значений. Процессор может затем определять открытый ключ как пару (B, H) на основе первого случайного значения R1 и второго случайного значения R2. Пара (B, H), представляющая собой открытый ключ, может быть определена как (R1, R1^R2).

[1136] В некоторых случаях процессор второго вычислительного устройства может предоставлять открытый ключ на первое вычислительное устройство. Процессор первого вычислительного устройства может выбирать третье случайное значение R3 и шифровать сообщение M с использованием открытого ключа (B, H) и третьего случайного значения R3 для определения зашифрованного шифротекста как (X, Y)=(B^R3, M * H^R3). Процессор первого вычислительного устройства может затем отправлять зашифрованный шифротекст на второе вычислительное устройство. Процессор второго вычислительного устройства может принимать зашифрованный шифротекст и расшифровывать зашифрованный шифротекст для идентификации сообщения M с использованием закрытого ключа, определенного на основе второго случайного значения.

[1137] В других случаях процессор второго вычислительного устройства может маскировать открытый ключ для определения замаскированного открытого ключа для предоставления на первое вычислительное устройство (вместо открытого ключа, который не был замаскирован). Процессор первого вычислительного устройства может затем использовать замаскированный открытый ключ для шифрования сообщения для определения зашифрованного шифротекста. В таких случаях процессор второго вычислительного устройства может маскировать открытый ключ путем выбора четвертого случайного значения R4 из предварительно определенного набора G значений так, чтобы B^R4 представляло собой генератор для G. Процессор может определять замаскированный открытый ключ как пару (B’, H’) на основе открытого ключа (B, H) и четвертого случайного значения R4, так что (B’, H’)=(B^R4, H^R4).

[1138] В некоторых случаях процессор первого вычислительного устройства может маскировать зашифрованный шифротекст (X, Y) до отправки зашифрованного шифротекста на второе вычислительное устройство. Например, процессор первого вычислительного устройства может выбирать пятое случайное значение R5 из предварительно определенного набора G значений. На основе открытого ключа, принятого со второго вычислительного устройства (незамаскированного или замаскированного), и пятого случайного значения R5 процессор первого вычислительного устройства может определять замаскированное зашифрованное сообщение как (X’,Y’)=(X*(B^R5), Y*(H^R5)). Процессор первого вычислительного устройства может затем генерировать зашифрованный пакет данных, содержащий замаскированное зашифрованное сообщение, и отправлять зашифрованный шифротекст как замаскированное зашифрованное сообщение на второе вычислительное устройство.

[1139] Шифр, описанный выше, может быть использован для создания новой системы для осуществления связи среди участников, показывая только псевдонимы, без необходимости раскрывать такую информацию, как IP-адреса. Например, участники {Алиса, Боб, Кэрол, Дэйв, Эд} могут публиковать свой IP-адрес вместе со своим публичным именем. Каждый участник может генерировать пару ключей, открытый ключ которой действует как его псевдоним при осуществлении анонимизированной связи по сети. В некоторых случаях Эд может позволять другим участникам отправлять ему сообщения так, чтобы Эду не приходилось идентифицировать свой IP-адрес или делиться им. Эд может публиковать свой псевдоним (например, свой открытый ключ) вместе с одним или более путями. «Путь» представляет собой последовательность участников, через которых сообщения должны быть маршрутизированы, чтобы дойти до него. Например, Эд может избирать последовательность {Боб, Кэрол, Дэйв, Эд} как путь, что означает, что второе вычислительное устройство может отправлять сообщение Бобу, который будет отправлять его Кэрол, которая будет отправлять его Дэйву, который будет отправлять его Эду. Возвращаемые сообщения могут следовать по тому же пути в обратную сторону. Пути могут быть указаны с использованием псевдонимов вместо другой информации, которая может показывать идентификатор пользователя. По существу, такой путь может представлять собой анонимный путь связи. Например, Эд может создавать и публиковать путь {Боб, Кэрол, Дэйв, Эд} путем выполнения следующих этапов. Эд может сначала замаскировать каждый из четырех открытых ключей для тех четырех участников (например, путем использования шифра, упомянутого выше). Эд может затем брать список имен {Кэрол, Дэйв, Эд} (который представляет собой тот же самый список за исключением его первого элемента, т. е. Боба) и шифровать каждое из тех имен с использованием замаскированного открытого ключа, который Эд создал для {Боба, Кэрол, Дэйва} соответственно. Эд может затем публиковать «путь», который содержит (1) четыре замаскированных ключа (например, последовательность замаскированных открытых ключей) и (2) набор идентификаторов вычислительных устройств участника (например, вычислительного устройства). Такой набор идентификаторов вычислительных устройств содержит три зашифрованных имени (последовательность зашифрованных идентификаторов вычислительных устройств, которые уникально связаны с разными участниками) и публичное имя Боб без каких-либо шифрования или маскировки (незашифрованный идентификатор вычислительного устройства). Такие идентификаторы вычислительных устройств могут представлять собой псевдонимы и связаны с замаскированным открытым ключом. В некоторых реализациях Эд может пропускать этап маскировки ключа для первого имени (Боба в этом примере) и маскировать только остальные ключи.

[1140] Если Алиса (например, первое вычислительное устройство) желает отправить сообщение на псевдоним, который использует Эд (например, второе вычислительное устройство), Алиса может осуществить поиск путей, связанных с псевдонимом Эда, и выбрать один из таких путей. Например, Алиса может избрать или выбрать путь, созданный из {Боба, Кэрол, Дэйва, Эда}. Соответственно, Алиса может определять и/или генерировать зашифрованное сообщение путем шифрования сообщения с помощью замаскированного открытого ключа для Эда, созданного Эдом, в частности, этим путем. Алиса может брать имя (или псевдоним) «Эд» (например, идентификатор вычислительного устройства для второго вычислительного устройства) и шифровать имя (или псевдоним) «Эд» с помощью замаскированного открытого ключа Дэйва. Это зашифрованное имя может быть замаскировано и затем приложено к зашифрованному сообщению для Эда для генерирования и/или определения зашифрованного пакета данных. После этого Алиса может повторять это для обработки сообщения в порядке, обратном порядку, указанному в выбранном пути. Соответственно, Алиса может шифровать пакет (например, зашифрованное имя, приложенное к зашифрованному сообщению) с использованием замаскированного открытого ключа для Дэйва. Затем Алиса может прилагать к пакету замаскированную версию имени Дэйва, зашифрованного с помощью ключа Кэрол. Алиса затем зашифровывает тот весь пакет с использованием ключа Кэрол. Затем прилагает замаскированную версию имени Кэрол, зашифрованного с помощью ключа Боба. Боб находится в начале пути или списка, таким образом, процесс шифрования для выбранного пути останавливается здесь.

[1141] На этом этапе Алиса создала большой пакет. Имя Боба является единственным, которое Эд включил как открытый текст, так что Алиса знает, что путь начинается с Боба. Следовательно, Алиса отправляет весь конечный пакет Бобу. Он затем расшифровывает пакет с помощью своего закрытого ключа, затем расшифровывает имя Кэрол с помощью своего закрытого ключа, затем удаляет ее имя и отправляет Кэрол то, что осталось. Кэрол делает то же самое, отправляя Дэйву меньший пакет. Дэйв делает то же самое и отправляет Эду. Наконец, Эд расшифровывает то, что он принимает, и может прочитать сообщение.

[1142] С использованием вышеописанного шифра, который обеспечивает замаскированные ключи и замаскированные сообщения, например, Эд может публиковать путь, который должен быть пройден другими участниками, сохраняя при этом свою анонимность. В отличие от скрытых служб Tor, с помощью вышеупомянутого протокола анонимизированной IP-связи Эд не должен связываться с Бобом заранее, чтобы договориться об этом пути, и Боб ничего не должен сохранять при проведении подготовки в отношении пути. Вместо этого, Эд публикует свои пути, и, когда кто-либо использует один из них, сообщение доходит до него.

[1143] Подобным образом, с использованием вышеописанного способа другие участники (например, Алиса) могут публиковать анонимный путь связи и принимать зашифрованный пакет данных от других участников по анонимному пути связи. В конечном счете, Алиса может расшифровывать принятое сообщение посредством закрытого ключа, специфического для Алисы, и получает оплату с помощью открытого ключа, используемого Алисой в этом анонимном пути связи. Соответственно, любое количество участников (например, вычислительных устройств) может определять любое количество анонимных путей связи. Дополнительно такие анонимные пути связи могут быть определены для включения любого количества промежуточных участников (например, вычислительных устройств). Это может гарантировать, что IP-адрес конечного получателя сообщения остается нераскрытым.

[1144] В некоторых случаях протокол связи может быть оптимизирован путем добавления чисел цепи в протокол. Например, когда Алиса предоставляет Бобу первоначальный пакет, Боб может ответить с помощью случайного числа, которое он избирает для уникальной идентификации цепи. Когда Боб отправляет меньший пакет Кэрол, то Кэрол отвечает Бобу с помощью случайного числа для цепи. Другие участники тоже так делают. Когда Алиса желает отправить больше сообщений Эду в ближайшем будущем, она может зашифровать каждое сообщение с помощью всех открытых ключей в пути (начиная с ключа Эда) и отправить каждое сообщение Бобу вместе с числом цепи, которое он ей дал. Боб может, например, помнить, что это число цепи связано с Кэрол, так что он будет расшифровывать каждое сообщение с помощью своего собственного закрытого ключа и направлять каждое сообщение Кэрол вместе с числом цепи, которое Кэрол дала ему. Каждый участник может сохранять список чисел цепи вместе с тем, кто непосредственно предшествует им и следует за ними в пути для той цепи. В некоторых случаях эта информация хранится в течение ограниченного периода времени. Если никакие сообщения не отправлялись посредством заданного числа цепи в течение периода времени (например, в течение определенного количества секунд или минут), то та запись может быть стерта. После чего Алиса может воссоздавать новую цепь, когда она в следующий раз захочет связаться с Эдом.

[1145] В некоторых случаях, когда Эд отвечает Алисе, его ответ может быть зашифрован с помощью открытых ключей {Алисы, Боба, Кэрол, Дэйва} в том порядке. Затем Эд может отправлять тот ответ Дэйву с использованием того же числа цепи, которое Дэйв дал Эду в первый раз. Дэйв расшифровывает ответ, затем отправляет ответ обратно Кэрол, и это продолжается, пока не дойдет обратно до Алисы. В таком случае Алиса может включать замаскированный открытый ключ для нее самой в первоначальное сообщение, так что никто не может прочитать сообщение от Эда Алисе.

[1146] В некоторых случаях Бобу, Кэрол и Дэйву могут быть предоставлены компенсация или поощрение за предоставление вышеуказанных услуг Алисе и Эду. Это может быть осуществлено с помощью криптовалюты, причем Алиса платит Бобу сразу, как только она принимает обратно сообщение от Эда. На том этапе Алиса может заплатить Бобу достаточно, чтобы заплатить всем из {Боба, Кэрол, Дэйва}. Боб может затем заплатить Кэрол достаточно для {Кэрол, Дэйва}, и затем Кэрол может заплатить Дэйву. Подобные платежи могут осуществляться при отправке каждого нового сообщения по каналу. В некоторых случаях единая цена может быть установлена глобально, например, на основе голосования за такую цену участников в сообществе или хешграфе. Цена может устанавливаться за каждого участника в пути, причем одна цена за установление цепи, и отдельная цена за каждое сообщение, отправленное по цепи. В других случаях цена может быть вычислена за каждый байт, а не за каждое сообщение.

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

[1148] В некоторых случаях вышеупомянутый протокол связи дает одностороннюю анонимность. Например, Алиса не может выяснить IP-адрес Эда, если только она не вступила в сговор со всеми из {Боба, Кэрол, Дэйва}. В некоторых случаях Эд может избирать или выбирать Боба, Кэрол и Дэйва случайным образом, так что маловероятно, что Алиса угадает элемент пути, избранный Эдом. И наоборот, Эд может выяснить IP-адрес Алисы, например, путем выбора или избирания {Боба, Кэрол, Дэйва} из числа своих собственных объектов взаимодействия, и вместе они могут затем вступить в сговор или поделиться информацией, раскрывая IP Алисы. Однако в некоторых случаях Алиса может маршрутизировать свои сообщения через нескольких участников, которых она сама же и избрала, прежде чем сообщения дойдут до Боба. Эта методика удваивает количество этапов, выполняемых Алисой при создании первоначального пакета, но это гарантирует двустороннюю анонимность. В еще одних случаях односторонняя анонимность может быть применена в противоположном направлении, например, если Алиса знает публичное имя Боба и желает отправить сообщение ему, скрывая при этом свой собственный идентификатор, то она может создавать первоначальный пакет так, чтобы он передавался через нескольких участников по пути к Бобу, а затем цепь заканчивалась на Бобе. Алиса может затем узнать идентификатор Боба (или по меньшей мере IP-адрес Боба), но Боб не узнает, кто такая Алиса.

[1149] В некоторых случаях, если Алиса создает и/или определяет новую цепь, Алиса может создавать и/или определять свое оригинальное сообщение, содержащее новый симметричный ключ для каждого уровня зашифрованного сообщения. Затем, каждый узел вдоль пути цепи может сохранять тот симметричный ключ вместе с двумя числами цепи (например, числами цепи для узлов, которые непосредственно предшествуют тому узлу и следуют за ним в пути для той цепи). Затем Алиса может шифровать будущие сообщения с помощью симметричных ключей вместо использования открытых ключей. В некоторых случаях это может быть быстрее, а также гарантировать, что множество уровней шифрования не приводят к тому, что будущие сообщения становятся слишком большими. Шифрование с помощью симметричного ключа может быть выполнено таким способом, который не приводит к тому, что размер сообщения существенно увеличивается при шифровании. Факультативно при использовании симметричных ключей Алиса может включать случайное заполнение в самое внутреннее сообщение. Это убирает необходимость в рандомизации каждого уровня шифрования, и сообщение не обязательно увеличивается в размере на каждом уровне. Когда Алиса отправляет сообщение через цепь, сообщение расшифровывается на каждом узле вдоль пути, таким образом, убирая один уровень симметричного шифрования. Когда конечный получатель осуществляет ответ, ответ может быть зашифрован на каждом уровне с помощью надлежащего симметричного ключа, так что Алиса принимает ответ, зашифрованный с помощью всех симметричных ключей.

[1150] Таким образом, обсужденный протокол связи обеспечивает по меньшей мере три режима анонимности: a) односторонняя защита отправителя, b) односторонняя защита получателя и c) двусторонняя защита отправителя и получателя. В некоторых реализациях протокол связи может быть использован для реализации анонимайзера криптовалюты, описанного выше. В некоторых других реализациях протокол связи может быть использован для анонимизирования протокола способа достижения консенсуса хешграфа и/или других подходящих процессов, выполняемых внутри хешграфа.

[1151] Далее следует краткое изложение еще одного примера того, как вышеописанный шифр может быть использован для осуществления анонимной связи. Закрытый ключ представляет собой элемент y случайной группы. Соответствующий открытый ключ представляет собой (a, b) = (g,g^y). Зашифрованное сообщение – (c, d) = (g^x, m*g^{xy}), где x случайным образом избран отправителем, и m представляет собой оригинальное сообщение. Зашифрованное сообщение n = (e, f) зашифровано подобным образом с помощью отличного случайного x. Образован один «кортеж», который содержит открытый ключ и два зашифрованных сообщения m_1 и m_2. Кортеж представляет собой (a, b, c, d, e, f) = (g, g^y, g^x_1, m_1*g^{x_1 y}, g^x_1, m_2*g^{x_1 y}), где отправитель избирает случайные x_1 и x_2. Чтобы замаскировать запись, избирают случайные r_1, r_2 и r_3 и определяют замаскированную запись как (a’, b’, c’, d’, e’, f’) = (a^r_1, b^r_1, c*a^r_2, d*a^r_2, e*a^r_3,f*a^r_3).

[1152] Узел (вычислительное устройство) Алиса в сети может публиковать «путь», который может быть использован для маршрутизации сообщений на тот узел, не показывая адрес или идентификатор того узла. Путь представляет собой список из n записей (R_1, R_2, ..., R_n). Каждая запись R_i содержит (a_i,b_i), который представляет собой открытый ключ узла в сети, где последний (a_n,b_n) представляет собой открытый ключ того узла. Так что, например, узел (Дэйв) создает и/или определяет путь для маршрутизации сообщений через следующие узлы: Алиса, затем Боб, затем Кэрол, затем Дэйв. В таком примере (a_1,b_1) будет представлять собой открытый ключ для Алисы, и (a_4,b_4) будет представлять собой открытый ключ для Дэйва (поскольку n=4 в этом примере, поскольку имеются четыре узла в пути). Первое сообщение m_1 в каждой записи представляет собой идентификатор следующего узла в пути. Так что (c_1,d_1) представляет собой шифротекст имени (или идентификатора, или псевдонима) для Боба, который может быть использован узлом для выяснения IP-адреса и открытого ключа Боба. Подобным образом, (c_2,d_2) представляет собой идентификатор Кэрол, и (c_3,d_3) представляет собой идентификатор Дэйва. Что касается последнего (c_n,d_n), который представляет собой (c_4,d_4) в этом примере, сообщение представляет собой просто число 1 (или элемент идентификатора для группового оператора алгебраической группы, если это что-то отличное от числа 1). Второй шифротекст в каждом кортеже (e_i,f_i) представляет собой зашифрованную 1 (или элемент идентификатора) для каждой записи в пути.

[1153] После создания и/или определения Дэйвом этого пути они маскирует путь путем маскировки каждой записи, а затем публикует путь, связанный со строго анонимным именем анонимный Дэйв (AnonymousDave). Ни один человек (или вычислительное устройство в сети) не сможет узнать, что анонимный Дэйв на самом деле является Дэйвом. А также не сможет выяснить IP-адрес анонимного Дэйва. При этом остальные могут использовать путь для отправки Дэйву сообщений. Опубликованный путь также связан с идентификатором первого узла на пути. Так что в этом примере опубликованный путь связан с Алисой, так что другим узлам ясно, что первым узлом на пути будет узел Алисы, и идентификатор Алисы не будет скрыт или анонимизирован.

[1154] Затем Эд отправляет анонимному Дэйву сообщение следующим способом. Извлекает и/или идентифицирует путь, который был опубликован для анонимного Дэйва (или один из путей, если было опубликовано несколько). Маскирует записи в пути. Создает и/или определяет список случайных масок (k_1, ... k_n). Меняет каждый f_i на k_i*f_i. Для каждого k_i вычисляет инверсию относительно умножения k'_i, так что k_i * k'_i представляет собой 1 (или представляет собой элемент идентификатора группы, если это не 1). Меняет каждый d_i на d_i*(k'_1 * k'_2 * ... * k'_i). Эд зашифровывает свое сообщение с помощью открытого ключа (a_n,b_n) для определения шифротекста, затем отправляет как шифротекст, так и модифицированный путь на первый узел на пути, то есть Алисе.

[1155] Алиса затем делает следующее. Расшифровывает (e_1,f_1) для получения k_1. Меняет каждый d_i на d_i*k_1. Расшифровывает (c_1,d_1) для нахождения и/или идентификации идентификатора следующего узла на пути, то есть Боба. Убирает первый кортеж с пути, так что теперь запись 2 будет называться запись 1, запись 3 будет называться 2 и так далее. Маскирует зашифрованное сообщение. Отправляет замаскированное зашифрованное сообщение и свой модифицированный путь Бобу. Если зашифрованное сообщение зашифровано с помощью стандартного гибридного подхода (шифрования сообщения с помощью случайного ключа, который сам зашифрован с помощью асимметричного шифра), то сообщение «маскируют» путем повторного шифрования сообщения для того же открытого ключа. В этом случае открытый ключ будет передаваться вместе с сообщением, и открытый ключ будет маскироваться на каждом этапе.

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

[1157] В вышеизложенном примере анонимная связь может быть осуществлена более эффективно путем использования чисел цепи следующим способом. Например, Эд отправляет свой оригинальный модифицированный путь Алисе без включения какого-либо шифротекста в виде сообщения. Алиса генерирует случайное «число цепи» и возвращает его Эду. Когда она передает модифицированный путь Бобу, он генерирует число цепи и возвращает его Алисе. Алиса хранит те два числа как связанную пару в течение короткого периода времени (например, минут или часов). Во время того периода Эд может отправлять сообщения Дэйву путем их шифрования и их отправки Алисе вместе с числом цепи (и без отправки модифицированного пути). Сообщение затем следует по пути, причем его снова маскируют на каждом этапе, пока оно не дойдет до Дэйва. Первое сообщение должно включать открытый ключ для Эда. Дэйв может затем ответить с помощью сообщения, зашифрованного с помощью того ключа, вместе с числом цепи, которое он принял от Кэрол. Сообщение затем передается обратно по цепи, причем его маскируют на каждом этапе, пока Эд не примет сообщение.

[1158] В некоторых юрисдикциях правительство может желать обеспечить через законодательство возможность мониторинга потоков валюты для предотвращения таких преступлений, как отмывание денег или уклонение от уплаты налогов, при этом позволяя гражданам быть анонимными от слежки (например, со стороны их соседей, преступников, правительств иностранных государств и т. д.). В некоторых случаях вышеописанные способ и система анонимности могут поддерживать такое законодательство. В таких случаях правительство может создать или одобрить определенный центр сертификации (CA) или несколько CA с целью создания и/или определения зашифрованных сертификатов, которые подтверждают, что кошелек связан с определенным человеком. Шифрование может быть таким, что только правительство может расшифровать его (возможно только по постановлению суда). Если Алиса создает и/или определяет кошелек, она может факультативно иметь такой сертификат, прикрепленный к кошельку, что означает, что ее соседи не могут видеть, что кошелек принадлежит Алисе, но правительство может расшифровать сертификат и идентифицировать Алису как владельца кошелька. Правительство может настоять на том, чтобы работодатели на территории своей страны могли только вносить деньги в кошельки, которые имеют такой сертификат, и чтобы магазины в этой стране принимали платежи с кошельков с таким сертификатом. Затем Алиса может выполнять вышеуказанный протокол многократно с целью создания и/или определения цепочки кошельков и получать надлежащий сертификат для первого и последнего кошельков в цепочке.

[1159] Хоть выше и описано, что структура данных каждого кошелька имеет одну пару открытого-закрытого ключей, в других случаях структура данных кошелька может содержать две пары открытого-закрытого ключей: одну для подписания и одну для шифрования. В таком случае вышеописанные способы могут быть изменены для использования подписывающего ключа для подписания и ключа шифрования для шифрования.

[1160] Хоть выше и описано, что используют хешграф и хранят транзакции и осуществляют обмен ими в событиях, в других случаях для реализации вышеописанных способов с целью обеспечения защищенных и анонимных транзакций может использоваться любая другая подходящая технология распределенной базы данных и/или распределенного реестра. Например, в других случаях для реализации таких способов могут быть использованы такие технологии, как блокчейн, PAXOS, RAFT, Биткойн, Эфириум и/или т. п. В некоторых случаях защищенная метка времени может быть добавлена в эти технологии (например, надстроена на них) для реализации вышеописанных способов с целью обеспечения защищенных и анонимных транзакций. В других случаях, как описано выше, не используют никакой метки времени.

[1161] Хоть выше и описано, что осуществляется реализация между двумя разными экземплярами распределенной базы данных, в других случаях способ анонимизации может быть реализован более чем двумя экземплярами распределенной базы данных. Например, в других случаях транзакция «TRANSFER_DOUBLE» может поддерживать дополнительные количества транзакций. Например, транзакция TRANSFER_TRIPLE может быть определена с возможностью поддержки передачи данных между тремя разными структурами данных кошелька.

[1162] Хоть выше и описано, что реализуют криптовалюту, в других случаях могут быть анонимизированы транзакции в любом другом типе распределенной базы данных. Например, могут быть анонимизированы запись об обмене товарами, установление личности физического лица, разрешение на использование конкретного ресурса и/или т. п. В таких случаях это может повысить безопасность транзакции в распределенной базе данных.

[1163] На фиг. 7 проиллюстрирована функциональная схема потока сигналов двух вычислительных устройств, синхронизирующих события, согласно варианту осуществления. В частности, в некоторых вариантах осуществления экземпляры 703 и 803 распределенной базы данных могут обмениваться событиями для достижения конвергенции. Вычислительное устройство 700 может выбирать синхронизацию с вычислительным устройством 800 случайным образом, на основе взаимосвязи с вычислительным устройством 700, на основе близости к вычислительному устройству 700, на основе упорядоченного списка, связанного с вычислительным устройством 700, и/или т. п. В некоторых вариантах осуществления, поскольку вычислительное устройство 800 может быть избрано вычислительным устройством 700 из набора вычислительных устройств, относящихся к системе распределенной базы данных, вычислительное устройство 700 может выбирать вычислительное устройство 800 несколько раз подряд или может некоторое время не выбирать вычислительное устройство 800. В других вариантах осуществления указание о ранее выбранных вычислительных устройствах может быть сохранено на вычислительном устройстве 700. В таких вариантах осуществления вычислительное устройство 700 может находиться в ожидании, пока не будет осуществлено предопределенное количество выборов, перед тем, как получить возможность снова выбирать вычислительное устройство 800. Как поясняется выше, экземпляры 703 и 803 распределенной базы данных могут быть реализованы в памяти вычислительного устройства 700 и памяти вычислительного устройства 800 соответственно.

[1164] В некоторых реализациях вычислительное устройство 700 может иметь множество потоков, работающих одновременно, причем каждый поток синхронизируется с другим участником. Соответственно, вычислительное устройство 700 может синхронизироваться с другими вычислительными устройствами (не показанными на фиг. 7) в дополнение к вычислительному устройству 800. В некоторых случаях вычислительное устройство 700 может устанавливать соединения для каждого потока на начальном этапе или в первый раз, а затем поддерживать каждое соединение в действующем состоянии или открытым путем периодической отправки сообщения с тактовым импульсом (например, отправки тактового импульса дважды в секунду). Таким образом, в некоторых случаях вычислительное устройство 700 может предотвращать задержку синхронизации или отлагательства, иным образом вызванные протоколами безопасности уровня передачи (TLS) (например, протоколом записи и протоколом квитирования), каждый раз, когда вычислительное устройство устанавливает соединение с другим участником или вычислительным устройством для синхронизации.

[1165] В некоторых реализациях вычислительное устройство 700 может управлять установлением потоковых соединений с другими участниками или вычислительными устройствами как пулом соединений и/или соединениями с группой вычислительных устройств (например, соединениями протокола управления передачей / Интернет-протокола). В таком случае вычислительное устройство 700 приспособлено так, чтобы не превосходить лимит (порог верхнего лимита) открытых соединений с другими участниками или вычислительными устройствами. В некоторых случаях лимит соединений может быть приспособлен на основе физических ресурсов вычислительного устройства 700, например, оперативного запоминающего устройства, используемого для каждого соединения, или производительности центрального процессорного устройства. Например, вычислительное устройство 700 может быть приспособлено для одновременного поддержания открытых соединений с постоянным количеством V участников или вычислительных устройств, так что его память и ресурсы обработки не используются с максимальной производительностью и/или приводят к неоптимальной эффективности. Другими словами, вычислительное устройство 700 единовременно должно поддерживать открытые соединения не с каждым участником хешграфа, а вместо этого с V участниками или вычислительными устройствами. Соответственно, в некоторых случаях при выборе того, с кем следует синхронизироваться, вычислительное устройство 700 выбирает из случайных участников или вычислительных устройств (или группы участников или вычислительных устройств), с которым оно имеет открытые соединения, установленные в его пуле соединений.

[1166] В некоторых реализациях вычислительное устройство 700 может быть приспособлено для лимитирования или ограничения размера пула соединений согласно пороговому значению нижнего лимита и пороговому значению верхнего лимита. В таком случае вычислительное устройство 700 может случайным образом выбирать участника или вычислительное устройство для синхронизации из вычислительных устройств, имеющих открытое соединение с вычислительным устройством 700. Когда пул соединений больше, чем пороговое значение верхнего лимита, и/или когда количество вычислительных устройств в группе участников и/или вычислительных устройств достигает порогового значения верхнего лимита, после синхронизации вычислительное устройство может закрывать и/или прекращать такое соединение и убирать соединение из пула соединений и/или группы участников или вычислительных устройств. Аналогичным образом, когда пул соединений вычислительного устройства 700 находится ниже порогового значения нижнего лимита и/или когда количество вычислительных устройств в группе участников и/или вычислительных устройств достигает порогового значения нижнего лимита, вычислительное устройство исполняет один или более потоков для установления новых соединений с другими участниками или вычислительными устройствами и добавляет эти новые соединения в пул соединений и/или группу участников или вычислительных устройств. Если пул соединений меньше порогового значения верхнего лимита, но больше порогового значения нижнего лимита, вычислительное устройство 700 может поддерживать текущий пул соединений и/или группу участников или вычислительных устройств. В некоторых случаях определенная часть вызывающих потоков может быть вынуждена устанавливать новые соединения только с участниками или вычислительными устройствами, которые недавно успешно установили соединения. Остальные вызывающие потоки могут случайным образом вызывать других участников из набора из всех участников, даже тех, с которыми вычислительное устройство 700 не устанавливало недавно соединение.

[1167] В некоторых реализациях один хешграф может быть использован для достижения порядка консенсуса для набора транзакций. В случае очень больших систем может быть реализовано сегментирование или горизонтальное разделение хешграфа. Например, в очень большой многопользовательской онлайн-игре (MMO) каждый географический регион виртуального мира может становиться одним сегментом. В таком случае каждый сегмент может иметь свой собственный хешграф, который управляет упорядочиванием транзакций, которые происходят в том сегменте. Каждое вычислительное устройство участника может затем сохранять несколько сегментов и сохранять хешграф, связанный с каждым из сохраненных сегментов, и участвовать в нем.

[1168] В некоторых случаях синхронизация между сегментами может быть достигнута за счет того, что участники в сегменте достигают консенсуса относительно порядка транзакций, связанных с тем сегментом. Те транзакции могут провоцировать создание сообщения, обновляющего состояние сегмента, которое может быть подписано участниками первого сегмента. Подписанное сообщение может быть отправлено во второй сегмент для обновления участников второго сегмента до состояния первого сегмента. Например, активности в первом сегменте (например, для одного региона) могут провоцировать создание сообщения для второго сегмента, который управляет криптовалютой, отдавая инструкцию второму сегменту на перевод криптовалюты между двумя специфическими кошельками. В таком случае сообщение может быть одобрено с помощью подписей от более чем порогового числа (например, 2/3) участников первого сегмента (например, в адресной книге со списком участников первого сегмента). Кроме того, сообщение может содержать саму адресную книгу и может быть одобрено с помощью подписи от более чем порогового числа (например, 2/3) участников в более ранней версии адресной книги. Более ранняя версия адресной книги может быть одобрена с помощью подписей из более ранней версии и так далее обратно к оригинальной адресной книге для того хешграфа. Соответственно, исходящее сообщение из одного сегмента в другой может представлять консенсус среди участников сегмента, создающих исходящее сообщение.

[1169] На фиг. 3–6 проиллюстрированы примеры хешграфа согласно варианту осуществления. Имеется пять участников, каждый из которых представлен темной вертикальной линией. Каждый круг представляет событие. Две нисходящие линии от события представляют хеши двух предыдущих событий. Каждое событие в этом примере имеет две нисходящие линии (одну темную линию к тому же участнику и одну светлую линию к другому участнику), за исключением первого события каждого участника. Время течет вверх. На фиг. 3–6 вычислительные устройства распределенной базы данных обозначены как Алиса, Боб, Кэрол, Дэйв и Эд. Следует понимать, что такие обозначения относятся к вычислительным устройствам, которые конструктивно и функционально подобны вычислительным устройствам 110, 120, 130 и 140, показанным и описанным в отношении фиг. 1.

[1170] Примерная система 1: если вычислительное устройство 700 называется Алиса, и вычислительное устройство 800 называется Боб, то синхронизация между ними может быть выполнена так, как проиллюстрировано на фиг. 7. Синхронизация между Алисой и Бобом может быть выполнена следующим образом:

[1171] - Алиса отправляет Бобу события, сохраненные в распределенной базе 703 данных.

[1172] - Боб создает и/или определяет новое событие, которое содержит:

[1173] -- хеш последнего события, которое создал и/или определил Боб;

[1174] -- хеш последнего события, которое создала и/или определила Алиса;

[1175] -- цифровую подпись вышеуказанного, поставленную Бобом.

[1176] - Боб отправляет Алисе события, сохраненные в распределенной базе 803 данных.

[1177] - Алиса создает и/или определяет новое событие.

[1178] - Алиса отправляет Бобу то событие.

[1179] – Алиса вычисляет общий порядок для событий как функцию хешграфа.

[1180] – Боб вычисляет общий порядок для событий как функцию хешграфа.

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

[1182] Например, на фиг. 3 проиллюстрирован пример хешграфа 600. Событие 602 создается и/или определяется Бобом в результате синхронизации с Кэрол и после нее. Событие 602 содержит хеш события 604 (предыдущего события, созданного и/или определенного Бобом) и хеш события 606 (предыдущего события, созданного и/или определенного Кэрол). В некоторых вариантах осуществления, например, хеш события 604, включенный в событие 602, содержит указатель на его непосредственные события-предки, события 608 и 610. По существу, Боб может использовать событие 602 для ссылки на события 608 и 610 и перестраивания хешграфа с использованием указателей на предыдущие события. В некоторых случаях можно сказать, что событие 602 привязано к другим событиям в хешграфе 600, поскольку событие 602 может ссылаться на каждое из событий в хешграфе 600 посредством более ранних событий-предков. Например, событие 602 привязано к событию 608 посредством события 604. В качестве другого примера, событие 602 привязано к событию 616 посредством событий 606 и события 612.

[1183] Примерная система 2: система на основе примерной системы 1, при этом событие также содержит данные «полезной нагрузки» транзакций или другую информацию для записи. Такие данные полезной нагрузки могут быть использованы для обновления событий с помощью любых транзакций и/или информации, которые произошли и/или были определены начиная с непосредственного предыдущего события вычислительного устройства. Например, событие 602 может содержать любые транзакции, выполненные Бобом, начиная с момента создания и/или определения события 604. Таким образом, во время синхронизации события 602 с другими вычислительными устройствами Боб может делиться этой информацией. Соответственно, транзакции, выполняемые Бобом, могут быть связаны с событием и предоставлены другим участникам с помощью событий.

[1184] Примерная система 3: система на основе примерной системы 1, при этом событие также содержит текущие время и/или дату, полезные для отладки, диагностики и/или других целей. Время и/или дата могут быть локальными временем и/или датой, фиксирующими, когда вычислительное устройство (например, Боб) создает и/или определяет событие. В таких вариантах осуществления такие локальные время и/или дата не синхронизируются с остальными устройствами. В других вариантах осуществления время и/или дата могут быть синхронизированы на всех устройствах (например, при обмене событиями). В еще других вариантах осуществления для определения времени и/или даты может быть использован глобальный таймер.

[1185] Примерная система 4: система на основе примерной системы 1, в которой Алиса не отправляет Бобу ни события, созданные и/или определенные Бобом, ни события-предки такого события. Событие x является предком события y, если y содержит хеш x или y содержит хеш события, которое является предком x. Подобным образом, в таких вариантах осуществления Боб отправляет Алисе события, еще не сохраненные Алисой, и не отправляет события, уже сохраненные Алисой.

[1186] Например, на фиг. 4 проиллюстрирован примерный хешграфа 620, иллюстрирующий события-предки (круги с точками) и события-потомки (круги с полосками) события 622 (черный круг). Линии устанавливают частичный порядок событий, в котором предки идут до события в виде черного круга, и потомки идут после события в виде черного круга. Частичный порядок не указывает, идут ли события в виде белых кругов до или после события в виде черного круга, так что для определения их последовательности используется общий порядок. В качестве другого примера, на фиг. 5 проиллюстрирован примерный хешграф, иллюстрирующий одно конкретное событие (закрашенный круг) и первый момент времени, в который каждый участник принимает указание о том событии (круги с полосками). Когда Кэрол синхронизируется с Дэйвом для создания и/или определения события 624, Дэйв не отправляет Кэрол события-предки события 622, поскольку Кэрол уже осведомлена о таких событиях и приняла их. Вместо этого Дэйв отправляет Кэрол события, которые Кэрол все еще должна принять и/или сохранить в экземпляре распределенной базы данных Кэрол. В некоторых вариантах осуществления Дэйв может идентифицировать, какие события следует отправлять Кэрол, на основе того, что хешграф Дэйва показывает о том, какие события Кэрол приняла ранее. Событие 622 является предком события 626. Следовательно, на момент события 626 Дэйв уже принял событие 622. На фиг. 4 показано, что Дэйв принял событие 622 от Эда, который принял событие 622 от Боба, который принял событие 622 от Кэрол. Кроме того, на момент события 624 событие 622 является последним событием, принятым Дэйвом, которое было создано и/или определено Кэрол. Следовательно, Дэйв может отправлять Кэрол события, которые Дэйв сохранил, отличающиеся от события 622 и его предков. Дополнительно после приема события 626 от Дэйва Кэрол может перестраивать хешграф на основе указателей в событиях, сохраненных в экземпляре распределенной базы данных Кэрол. В других вариантах осуществления Дэйв может идентифицировать, какие события следует отправлять Кэрол, на основе отправки Кэрол события 622 Дэйву (не показано на фиг. 4) и идентификации с использованием события 622 (и ссылок в нем) Дэйвом, чтобы идентифицировать события, которые Кэрол уже приняла.

[1187] Примерная система 5: система на основе примерной системы 1, в которой оба участника отправляют события друг другу в таком порядке, что событие отправляется только после того, как получатель примет и/или сохранит предков того события. Соответственно, отправитель отправляет события от самых старых к самым новым, так что получатель может проверить два хеша в каждом событии при приеме события посредством сравнения двух хешей с двумя событиями-предками, которые уже были приняты. Отправитель может идентифицировать, какие события следует отправлять получателю, на основе текущего состояния хешграфа отправителя (например, переменной состояния базы данных, определенной отправителем), а какие, как указывает тот хешграф, получатель уже принял. Ссылаясь на фиг. 3, например, когда Боб синхронизируется с Кэрол для определения события 602, Кэрол может идентифицировать, что событие 619 является последним событием, созданным и/или определенным Бобом, которое приняла Кэрол. Следовательно, Кэрол может определить, что Бобу известно о том событии и его предках. Таким образом, Кэрол может отправлять Бобу сначала событие 618 и событие 616 (т. е. самые старые события, которые Боб еще должен принять, которые Кэрол приняла). Кэрол может затем отправлять Бобу событие 612, а затем событие 606. Это позволяет Бобу легко привязать события друг к другу и перестроить хешграф Боба. Использование хешграфа Кэрол для идентификации того, какие события еще должен принять Боб, может повысить эффективность синхронизации и может уменьшить сетевой трафик, поскольку Боб не запрашивает события у Кэрол.

[1188] В других вариантах осуществления самое последнее событие может быть отправлено первым. Если получатель определяет (на основе хеша двух предыдущих событий в самом последнем событии и/или указателей на предыдущие события в самом последнем событии), что он еще не принял одно из двух предыдущих событий, получатель может запросить у отправителя отправку таких событий. Это может происходить до тех пор, пока получатель не примет и/или не сохранит предков самого последнего события. Ссылаясь на фиг. 3, в таких вариантах осуществления, например, когда Боб принимает событие 606 от Кэрол, Боб может идентифицировать хеш события 612 и события 614 в событии 606. Боб может определить, что событие 614 было ранее принято от Алисы при создании и/или определении события 604. Соответственно, Бобу не нужно запрашивать событие 614 у Кэрол. Боб может также определить, что событие 612 еще не было принято. Боб может затем запросить событие 612 у Кэрол. Боб может затем на основе хешей в событии 612 определить, что Боб не принял события 616 или 618, и может соответственно запросить эти события у Кэрол. На основе событий 616 и 618 Боб затем сможет определить, что он принял предков события 606.

[1189] Примерная система 6: система на основе примерной системы 5 с дополнительным ограничением, которое заключается в том, что, когда участник имеет возможность избирать между несколькими событиями для отправки далее, событие избирается таким образом, чтобы минимизировать общее количество отправленных на данный момент байтов, созданных и/или определенных тем участником. Например, если Алисе осталось отправить Бобу только два события, и одно из них имеет размер 100 байтов и было создано и/или определено Кэрол, а другое имеет размер 10 байтов и было создано и/или определено Дэйвом, и на данный момент в ходе этой синхронизации Алиса уже отправила 200 байтов событий Кэрол и 210 Дэйва, то Алисе следует сначала отправить событие Дэйву, а затем отправить событие Кэрол. Поскольку 210 + 10 < 100 + 200. Это может быть использовано для предотвращения атак, при которых один участник выдает либо одно огромное событие, либо поток мелких событий. В случае если трафик превышает ограничение по байтам большинства участников (как обсуждается в отношении примерной системы 7), способ согласно примерной системе 6 может обеспечивать, что игнорироваться будут события злоумышленника, а не события правомочных пользователей. Подобным образом, атаки могут быть ослаблены посредством отправки меньших событий перед большими событиями (для защиты от одного огромного события, забивающего канал связи). Более того, если участник не может отправить каждое из событий за одну синхронизацию (например, из-за ограничения сети, ограничений по байтам участника и т. д.), то тот участник может отправить несколько событий от каждого участника, вместо того, чтобы просто отправить события, определенные и/или созданные злоумышленником, и ни одного (из нескольких) события, созданного и/или определенного другими участниками.

[1190] Примерная система 7: система на основе примерной системы 1 с дополнительным первым этапом, на котором Боб отправляет Алисе число, указывающее максимальное количество байтов, которое он желает принять во время этой синхронизации, и Алиса отвечает сообщением со своим ограничением. Алиса затем прекращает отправку, если следующее событие превысило бы это ограничение. Боб делает то же самое. В таком варианте осуществления это ограничивает количество передаваемых байтов. Это может увеличить время конвергенции, но уменьшит объем сетевого трафика на синхронизацию.

[1191] Альтернативно или дополнительно в некоторых реализациях лимит количества байтов на процесс синхронизации и/или количество событий, которые разрешено синхронизировать на процесс синхронизации, реализуются в распределенной базе данных. Например, Алиса может отправлять Бобу события, о которых Боб еще не знает, затем экземпляр базы данных, связанный с Алисой, может останавливать и/или прекращать отправку пакетов данных и/или событий, когда следующее событие превышает пороговое значение синхронизации на основе либо допустимого количества байтов (т. е. объема синхронизируемых данных), либо допустимого количества разрешенных событий, которые должны быть синхронизированы, и/или достигает его. Передача события в таких случаях может быть осуществлена путем отправки родителя события до отправки события, если синхронизируют оба события.

[1192] В некоторых случаях, когда Алиса синхронизируется с Бобом, и ей необходимо отправить ему два события, например, событие X и событие Y, и у Боба уже есть все родители обоих тех событий, тогда Алиса может избирать, какое отправить первым. В некоторых реализациях Алиса может вычислять общее Bx всех байтов в X плюс байты во всех событиях, созданных создателем события X, которые она уже отправила во время этой синхронизация. Подобным образом, она может вычислять общее By для байтов в Y и событий, созданных создателем события Y, которые были отправлены на данный момент. Она может затем решить отправить X перед Y, если Bx<By, и отправить Y перед X, если By<Bx, и отправить их в любом порядке, если Bx=By.

[1193] В некоторых случаях синхронизация между двумя участниками может быть ограничена максимальным количеством принятых событий на синхронизацию (например, для предотвращения атак типа «отказ в обслуживании»). Если такой лимит достигается прежде, чем все события, относящиеся к той синхронизации, были приняты, то синхронизация заканчивается раньше. В некоторых других случаях каждое событие синхронизации может быть ограничено максимальным количеством принятых байтов (вместо ограничения количеством принятых событий или в дополнение к нему). Соответственно, лимиты, такие как максимальное количество принятых событий и максимальное количество принятых байтов, могут быть использованы для ограничения или регулирования количества событий и/или байтов, принятых и/или полученных участником-получателем (например, Бобом) от другого участника (например, Алисы) во время синхронизации. Вышеупомянутые лимиты могут предотвращать атаки, при которых участник-злоумышленник создает большое событие или подвергает сеть потоку из огромного количества мелких событий. Эти лимиты также гарантируют постепенное ухудшение характеристик в случаях, когда, например, один участник имеет соединение с узкой полосой пропускания для обработки среднего объема трафика данных, но не скачка трафика данных.

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

[1195] В некоторых случаях отсутствие консенсуса может вызывать переполнение памяти участника или вычислительного устройства. Например, набор событий, для которого консенсус еще не был идентифицирован, может расти или увеличиваться после заданного порога, когда, например, по меньшей мере 1/3 популяции находится в режиме офлайн, поскольку консенсус не может быть получен, когда слишком мало участников находятся в режиме онлайн. Таким образом, память участника или вычислительного устройства может переполняться за счет совокупного количества событий, для которых консенсус не может быть достигнут. Для предотвращения переполнения памяти вследствие накопленных событий, для которых не может быть достигнут консенсус, каждый из участника и/или вычислительного устройства может быть приспособлен так, что, как только достигается порог событий, для которых консенсус еще не был достигнут, тот участник или то вычислительное устройство может отказаться определять и/или создавать какие-либо новые события до тех пор, пока тот участник или то вычислительное устройство не достигнет консенсуса относительно некоторых из событий, о которых участник или вычислительное устройство осведомлены. Другими словами, в некоторых случаях отсутствие консенсуса может вызывать переполнение, если консенсус не может быть достигнут (например, когда слишком мало участников находятся в режиме онлайн и могут получить консенсус). Таким образом, для предотвращения переполнения событий, которые не могут быть введены в порядок консенсуса (например, поскольку слишком мало участников находятся в режиме онлайн), участник не определяет никаких дополнительных событий до тех пор, пока он не сможет принимать события от некоторых из участников в режиме офлайн для достижения консенсуса относительно некоторых из более старых событий.

[1196] Примерная система 8: система на основе примерной системы 1, в которой следующие этапы добавлены в начале процесса синхронизации:

[1197] - Алиса идентифицирует S, набор событий, которые она приняла и/или сохранила, пропуская события, которые были созданы и/или определены Бобом или которые являются предками событий, созданных и/или определенных Бобом.

[1198] - Алиса идентифицирует участников, которые создали и/или определили каждое событие в S, и отправляет Бобу список ID-номеров участников. Алиса также отправляет количество событий, которые были созданы и/или определены каждым участником, которые она уже приняла и/или сохранила.

[1199] - Боб отвечает списком того, сколько событий он принял, тех, которые были созданы и/или определены другими участниками.

[1200] - Алиса затем отправляет Бобу только события, которые он еще должен принять. Например, если Алиса указывает Бобу, что она приняла 100 событий, созданных и/или определенных Кэрол, и Боб отвечает, что он принял 95 событий, созданных и/или определенных Кэрол, то Алиса отправит только 5 самых последних событий, созданных и/или определенных Кэрол.

[1201] Примерная система 9: система на основе примерной системы 1 с дополнительным механизмом для идентификации и/или устранения мошенников. Каждое событие содержит два хеша, один от последнего события, созданного и/или определенного тем участником («собственный хеш»), и один от последнего события, созданного и/или определенного другим участником («чужой хеш»). Если участник создает и/или определяет два разных события с одним и тем же собственным хешем, то тот участник является «мошенником». Если Алиса устанавливает, что Дэйв является мошенником, посредством приема двух разных событий, созданных и/или определенных им с использованием одного и того же собственного хеша, то она сохраняет индикатор, указывающий на то, что он является мошенником, и избегает синхронизации с ним в будущем. Если она выясняет, что он является мошенником, но все же синхронизируется с ним снова и создает и/или определяет новое событие, записывающее тот факт, то Алиса тоже становится мошенником, и другие участники, которые узнают, что Алиса впоследствии синхронизировалась с Дэйвом, перестают синхронизироваться с Алисой. В некоторых вариантах осуществления это влияет только на синхронизацию в одну сторону. Например, когда Алиса отправляет список идентификаторов и число событий, которые она приняла, для каждого участника, она не отправляет ID или количество для мошенника, так что Боб не ответит никаким соответствующим числом. Алиса затем отправляет Бобу события мошенника, которые она приняла и для которых она не приняла указание о том, что Боб принял такие события. После завершения той синхронизации Боб также сможет определить, что Дэйв является мошенником (если он еще не идентифицировал Дэйва как мошенника), и Боб также откажется от синхронизации с мошенником.

[1202] Примерная система 10: система на основе примерной системы 9 с тем дополнением, что Алиса начинает процесс синхронизации путем отправки Бобу списка мошенников, которых она идентифицировала и события которых она все еще хранит, и Боб отвечает сообщением с указанием любых мошенников, которых он идентифицировал, в дополнение к мошенникам, идентифицированным Алисой. Затем они продолжают работу в обычном режиме, но без подсчета мошенников при синхронизации друг с другом.

[1203] Примерная система 11: система на основе примерной системы 1 с процессом, который постоянно обновляет текущее состояние (например, зафиксированное переменной состояния базы данных, определенной участником системы) на основе транзакций в любых новых событиях, которые принимаются во время синхронизации. Это также может включать второй процесс, который постоянно перестраивает то состояние (например, порядок событий) каждый раз, когда последовательность событий меняется, посредством возвращения к копии более раннего состояния и повторного вычисления настоящего состояния посредством обработки событий в новом порядке. Таким образом, например, каждое вычислительное устройство может поддерживать две версии состояния (одну, обновляемую по мере того, как принимают новые события и транзакции, и другую, обновляемую только после того, как будет достигнут консенсус). В определенный момент времени (например, по истечении периода времени, после того как заданное количество событий определено и/или принято и т. д.), версия состояния, которую обновляют по мере того, как принимают новые события и транзакции, может быть удалена, и новая копия состояния, которую обновляют только после того, как будет достигнут консенсус, может быть выполнена в качестве новой версии состояния, которую обновляют по мере того, как принимают новые события и транзакции. Это может обеспечить синхронизацию обоих состояний.

[1204] В некоторых вариантах осуществления текущим состоянием является состояние, баланс, условие и/или т. п., связанные с результатом транзакций. Подобным образом, состояние может включать структуру данных и/или переменные, модифицированные транзакциями. Например, если транзакциями являются денежные переводы между банковскими счетами, то текущим состоянием может быть текущий баланс счетов. В качестве другого примера, если транзакции связаны с многопользовательской игрой, текущим состоянием может быть положение, количество жизней, полученные предметы, состояние игры и/или т. п., связанные с игрой.

[1205] Примерная система 12: система на основе примерной системы 11, ускоренная за счет использования arrayList с «быстрым клонированием» для поддержания состояния (например, баланса банковских счетов, состояния игры и т. д.). ArrayList с быстрым клонированием представляет собой структуру данных, которая действует как массив с одной дополнительной особенностью: она поддерживает операцию «клонирования», которая представляет собой создание и/или определение нового объекта, который является копией оригинала. Клон действует так, как если бы это была точная копия, поскольку изменения, которым подвергается клон, не влияют на оригинал. Однако операция клонирования быстрее, чем создание точной копии, поскольку создание клона в действительности не включает копирования и/или обновления всего содержимого одного arrayList в другой. Вместо наличия двух клонов и/или копий оригинального списка могут быть использованы два небольших объекта, каждый с хеш-таблицей и указателем на оригинальный список. Когда производится запись в клон, хеш-таблица запоминает, какой элемент модифицирован, и новое значение. Когда выполняется считывание из позиции, сначала проверяется хеш-таблица, и, если тот элемент был модифицирован, возвращается новое значение из хеш-таблицы. Иначе тот элемент возвращается из оригинального arrayList. Таким образом, два «клона» изначально являются лишь указателями на оригинальный arrayList. Но поскольку каждый из них постоянно модифицируется, они расширяются настолько, что имеют большую хеш-таблицу, в которой хранятся отличия между ними и оригинальным списком. Клоны сами могут быть клонированы, что вызывает расширение структуры данных до дерева объектов, каждый из которых имеет свои собственные хеш-таблицу и указатель на своего родителя. Следовательно, считывание вызывает подъем по дереву до тех пор, пока не будет установлена вершина, которая имеет запрашиваемые данные, или не будет достигнут корень. Если вершина становится слишком большой или сложной, то она может быть заменена на точную копию родителя, изменения в хеш-таблице могут быть переведены в копию, а хеш-таблица удалена. Кроме того, если клон больше не нужен, то во время сборки мусора он может быть убран из дерева, и дерево может быть свернуто.

[1206] Примерная система 13: система на основе примерной системы 11, ускоренная за счет использования хеш-таблицы с «быстрым клонированием» для поддержания состояния (например, баланса банковских счетов, состояния игры и т. д.). Она подобна системе 12, за тем исключением, что корень дерева представляет собой хеш-таблицу, а не arrayList.

[1207] Примерная система 14: система на основе примерной системы 11, ускоренная за счет использования реляционной базы данных с «быстрым клонированием» для поддержания состояния (например, баланса банковских счетов, состояния игры и т. д.). Например, база данных с быстрым клонированием может быть использована для обеспечения двух копий состояния, как обсуждено в отношении примерной системы 11. Она представляет собой объект, который действует как обертка вокруг существующей системы управления реляционной базой данных (RDBMS). Каждый явный «клон» является фактически объектом с ID-номером и указателем на объект, содержащий базу данных. Когда пользовательский код пытается выполнить запрос на языке структурированных запросов (SQL) в базу данных, тот запрос сначала модифицируется, а затем отправляется в реальную базу данных. Реальная база данных идентична базе данных с точки зрения клиентского кода, за исключением того, что каждая таблица имеет одно дополнительное поле для ID клона. Например, предположим, что существует оригинальная база данных с ID клона, равным 1, а затем создают два клона базы данных с ID, равными 2 и 3 (например, используемых для поддержания двух копий состояния). Каждая строка в каждой таблице будет иметь значения 1, 2 или 3 в поле ID клона. Когда запрос поступает от пользовательского кода на клон 2, запрос модифицируется таким образом, что запрос будет считываться только из строк, которые имеют значения 2 или 1 в том поле. Подобным образом, запросы к клону 3 считывают строки с ID, равным 3 или 1. Если команда на языке структурированных запросов (SQL) поступает на клон 2 и указывает удалить строку, и та строка имеет 1, то команда должна просто изменить 1 на 3, что помечает строку как более не используемую совместно клонами 2 и 3, и теперь видимую только для 3. Если существуют несколько рабочих клонов, то несколько копий строки могут быть вставлены, и каждая из них может быть установлена на ID разного клона, так что новые строки являются видимыми для всех клонов, за исключением клона, который только что «удалил» строку. Подобным образом, если строка добавляется в клон 2, то строка добавляется в таблицу с ID, равным 2. Модификация строки эквивалентна удалению с последующей вставкой. Как и раньше, если несколько клонов удаляются во время сборки мусора, то дерево может быть упрощено. Структура того дерева будет сохранена в дополнительной таблице, недоступной клонам, но которая полностью используется на внутреннем уровне.

[1208] Примерная система 15: система на основе примерной системы 11, ускоренная за счет использования файловой системы с «быстрым клонированием» для поддержания состояния. Она представляет собой объект, который действует как обертка вокруг файловой системы. Файловая система построена поверх существующей файловой системы с использованием реляционной базы данных с быстрым клонированием для управления разными версиями файловой системы. Основная файловая система хранит большое количество файлов либо в одном каталоге, либо раздельно согласно имени файла (для поддержания малого размера каталогов). Дерево каталогов может храниться в базе данных и не предоставляться базовой файловой системе. Когда файл или каталог клонируются, «клон» представляет собой лишь объект с ID-номером, и база данных модифицируется таким образом, чтобы отражать, что этот клон теперь существует. Если файловая система с быстрым клонированием клонируется, она представляется пользователю такой, как если бы был создан и/или определен целый новый жесткий диск, инициализированный с использованием копии существующего жесткого диска. Изменения, которым подвергается одна копия, могут не влиять на другие копии. В действительности существует только одна копия каждого файла или каталога, и копирование происходит, когда файл модифицируется посредством одного клона.

[1209] Примерная система 16: система на основе примерной системы 15, в которой отдельный файл создается и/или определяется в базовой операционной системе для каждой N-байтной части файла в файловой системе с быстрым клонированием. N может представлять собой некоторый подходящий размер, такой как, например, 4096 или 1024. Таким образом, если один байт изменяется в большом файле, копируется и модифицируется только один блок большого файла. Это также повышает эффективность при сохранении множества файлов на диске, которые отличаются лишь несколькими байтами.

[1210] Примерная система 17: система на основе примерной системы 11, где каждый участник включает в некоторые или во все события, которые он создает и/или определяет, хеш состояния на некоторый предыдущий момент времени вместе с количеством событий, которые произошли вплоть до того момента, указывая на то, что участник распознает и/или идентифицирует, что теперь достигнут консенсус относительно порядка событий. После того как участник собрал подписанные события, содержащие такой хеш, от большинства пользователей для заданного состояния, участник может затем сохранить это как доказательство состояния консенсуса на тот момент и удалить из памяти события и транзакции до того момента.

[1211] Примерная система 18: система на основе примерной системы 1, где операции, которые вычисляют медиану или большинство, заменяются взвешенной медианой или взвешенным большинством, причем участников взвешивают согласно их «доле». Доля представляет собой число, которое указывает на то, как много значит голос участника. Доля может представлять собой активы в криптовалюте или просто произвольное число, которое присваивается, когда участника впервые приглашают присоединиться, а затем разделяется среди новых участников, которых участник приглашает присоединиться. Старые события могут быть удалены, когда достаточное количество участников согласится с состоянием консенсуса, так что их общая доля является большей частью имеющейся доли. Если общий порядок вычисляется с использованием медианы рангов, вносимых участниками, то результатом является число, при котором половина участников имеет более высокий ранг, а половина имеет более низкий. С другой стороны, если общий порядок вычисляется с использованием взвешенной медианы, то результатом является число, при котором приблизительно половина общей доли связана с рангами ниже той, и половина выше. Взвешенные голосование и медианы могут быть полезны в предотвращении атаки Сивиллы, когда один участник приглашает присоединиться огромное количество «виртуальных» пользователей, каждый из которых является просто псевдонимом под управлением приглашающего участника. Если приглашающий участник вынужден делить свою долю с приглашенными, то виртуальные пользователи будут бесполезны для злоумышленника в попытках контролировать результаты консенсуса. Соответственно, доказательство доли владения может быть полезным в некоторых обстоятельствах.

[1212] Примерная система 19: система на основе примерной системы 1, в которой вместо одной распределенной базы данных имеется множество баз данных в иерархии. Например, может существовать одна база данных, пользователи которой являются ее участниками, а также несколько меньших баз данных или «блоков», каждый из которых имеет поднабор участников. Когда события происходят в блоке, они синхронизируются среди участников того блока, но не среди участников вне того блока. Затем периодически после принятия решения относительно порядка консенсуса в блоке полученное в результате состояние (или события со своим общим порядком консенсуса) может совместно использоваться всем составом участников большой базы данных.

[1213] Примерная система 20: система на основе примерной системы 11 с возможностью наличия события, которое обновляет программное обеспечение для обновления состояния (например, зафиксированного переменной состояния базы данных, определенной участником системы). Например, события X и Y могут содержать транзакции, которые модифицируют состояние согласно программному коду, который считывает транзакции в тех событиях, а затем обновляет состояние надлежащим образом. Тогда событие Z может содержать уведомление о том, что теперь доступна новая версия программного обеспечения. Если общий порядок говорит, что события происходят в порядке X, Z, Y, то состояние может быть обновлено посредством обработки транзакций в X с использованием старого программного обеспечения, а затем транзакций в Y с использованием нового программного обеспечения. Но если порядок консенсуса имел вид X, Y, Z, то как X, так и Y могут быть обновлены с использованием старого программного обеспечения, которое может дать другое конечное состояние. Следовательно, в таких вариантах осуществления уведомление об улучшении кода может появляться в событии, так что сообщество может достигать консенсуса относительно того, когда следует перейти со старой версии на новую версию. Это гарантирует, что участники будут поддерживать синхронизированные состояния. Это также гарантирует, что система может оставаться работающей даже во время улучшений без необходимости перезагрузки или перезапуска процесса.

[1214] В некоторых реализациях способ достижения консенсуса хешграфа может быть реализован платформой (т. е. программой, реализованной программно, исполняемой на процессоре вычислительного устройства и/или системы). В целом, платформа хешграфа собирает, распространяет, упорядочивает транзакции и выполняет другие подходящие задачи, связанные с процессами достижения консенсуса. В дополнение к платформе в некоторых случаях отдельное приложение поддерживает и модифицирует совместно используемое состояние хешграфа путем исполнения транзакций в порядке консенсуса, определенном платформой. Когда новая версия такого приложения выпускается, транзакция новой версии может быть создана путем предоставления, например, числа новой версии, хеша нового кода приложения и доказательства того, что улучшение является подлинным (например, цифровой подписи относительно кода приложения, подписанного компанией, которая создала то приложение). В некоторых реализациях транзакция новой версии может быть приспособлена так, что новая версия не исполняется до тех пор, пока порядок консенсуса не идентифицируется для транзакции новой версии. Таким образом, транзакции, идентифицированные как более ранние в порядке консенсуса, обрабатываются старой версией приложения, и транзакции, идентифицированные как более поздние в порядке консенсуса, обрабатываются новой версией приложения. Соответственно, транзакции новой версии гарантируют, что участники осуществляют улучшение до новой версии приложения в одном и том же экземпляре и сохраняют свое состояние согласованным.

[1215] В некоторых реализациях улучшения для платформы могут быть выполнены способом, аналогичным улучшениям для приложения. Например, транзакция новой версии платформы может быть исполнена в момент, когда достигается консенсус относительно такой транзакции новой версии. Альтернативно, когда платформа выясняет, что новая версия платформы доступна, она может отобразить запрос каждому участнику хешграфа, запрашивающий указать, желает ли тот участник осуществить улучшение. В таком случае платформа может быть улучшена на основе ответа участника (участников).

[1216] В некоторых реализациях улучшения приложения и/или платформы могут быть подвергнуты пользовательскому голосованию. Например, вычислительные устройства участников могут отображать всплывающее окно связанному пользователю, предлагающее авторизовать улучшение путем выбора или отправки голоса да или нет, записываемого как транзакция (например, в событии). Соответственно, автоматические обновления платформ и/или приложений могут быть исполнены при авторизации со стороны пороговой величины от популяции (например, более чем 2/3 популяции).

[1217] Примерная система 21: система на основе примерной системы 1, где участники или вычислительные устройства хешграфа приспособлены так, чтобы убирать ненужные события из экземпляров распределенной базы данных путем определения подписанного состояния распределенной базы данных. В некоторых реализациях участники или вычислительные устройства могут исполнять дополнительные процессы для предотвращения переполнения памяти и/или для сохранения ресурсов памяти. Например, участники или вычислительные устройства могут периодически удалять старые события на основе набора правил или критериев. Правило может, например, указывать, что необходимо игнорировать или удалять транзакции в событии, если значение, равное разности раунда, который принят, и номера раунда (или раунда, который создан), события превышает заданный порог. В некоторых случаях события содержат хеши своих родителей и раунд, созданный для каждого родителя. Следовательно, заданное событие может быть все еще принято во время синхронизации, даже если одного или более родителей не хватает вследствие того, что их проигнорировали или удалили, поскольку они были созданы слишком много раундов тому назад. Соответственно, подписанные состояния могут содержать хеш событий, которые были определены и/или созданы в раундах, предшествующих подписанному состоянию, но совсем незадолго до подписанного состояния, при котором их бы проигнорировали или удалили. Убирание или удаление ненужных событий снижает затраты вычислительных ресурсов, вызванные синхронизацией излишних или неуместных событий внутри набора вычислительных устройств, которые реализуют распределенную базу данных (например, участников хешграфа), и снижает недоиспользование блоков локальной памяти такого набора вычислительных устройств. Дополнительные подробности относительно убирания и/или удаления событий могут быть найдены в предварительной заявке на патент США № 62/436066, поданной 19 декабря 2016 г. и озаглавленной «Method and Apparatus for a Distributed Database that Enables Deletion of Events», которая включена в настоящий документ посредством ссылки во всей своей полноте.

[1218] Предполагается, что системы, описанные выше, создают и/или обеспечивают эффективный механизм конвергенции для распределенного консенсуса с итоговым консенсусом. По этому поводу могут быть доказаны несколько теорем, как показано далее.

[1219] Примерная теорема 1: если событие x предшествует событию y в частичном порядке, то в знании заданного участника о других участниках в заданный момент времени каждый из других участников либо принял указание о x до y, либо еще не принял указание о y.

[1220] Доказательство: если событие x предшествует событию y в частичном порядке, то x является предком y. Когда участник принимает указание о y в первый раз, тот участник либо уже принял указание о x ранее (в случае чего он узнает о x раньше y), либо это будет случай, когда синхронизация предоставляет тому участнику как x, так и y (в случае чего он узнает о x раньше y во время той синхронизации, поскольку события, принимаемые во время одной синхронизации, полагают принимаемыми в порядке, согласующемся с взаимосвязями потомственности, как описано в отношении примерной системы 5). Что и требовалось доказать.

[1221] Примерная теорема 2: для любого заданного хешграфа, если x предшествует y в частичном порядке, то x будет предшествовать y в общем порядке, вычисленном для того хешграфа.

[1222] Доказательство: если x предшествует y в частичном порядке, то согласно теореме 1:

[1223] для всех i, rank(i,x) < rank(i,y),

[1224] где rank(i,x) представляет собой ранг, присвоенный участником i событию x, который равен 1, если x является первым событием, принятым участником i, 2, если вторым, и так далее. Допустим, что med(x) представляет собой медиану rank(i,x) для всех i, и аналогично для med(y).

[1225] Для заданного k изберем i1 и i2 таким образом, что rank(i1,x) является k-м наименьшим рангом x, а rank(i2,y) является k-м наименьшим рангом y. Тогда:

[1226] rank(i1,x) < rank(i2,y).

[1227] Это объясняется тем, что rank(i2,y) превышает или равняется k рангов y, каждый из которых строго превышает соответствующий ранг x. Следовательно, rank(i2,y) строго превышает по меньшей мере k рангов x, а значит строго превышает k-й наименьший ранг x. Этот аргумент справедлив для любого k.

[1228] Допустим, что n представляет собой количество участников (которое является количеством значений i). Тогда n должно быть либо нечетным, либо четным. Если n нечетное, то допустим, что k=(n+1)/2, и k-й наименьший ранг будет являться медианой. Следовательно, med(x) < med(y). Если n четное, то, когда k=n/2, k-й наименьший ранг x будет строго меньше, чем k-й наименьший ранг y, а также (k+1)-й наименьший ранг x будет строго меньше, чем (k+1)-й наименьший ранг y. Следовательно, среднее значение двух рангов x будет меньше, чем среднее значение двух рангов y. Следовательно, med(x) < med(y). Следовательно, в обоих случаях медиана рангов x строго меньше, чем медиана рангов y. Следовательно, если общий порядок определен посредством сортировки действий по медианному рангу, то событие x будет предшествовать событию y в общем порядке. Что и требовалось доказать.

[1229] Примерная теорема 3: если «период передачи» представляет собой количество времени, необходимое для распространения существующих событий посредством синхронизации всем участникам, то:

[1230] после 1 периода передачи: все участники приняли события,

[1231] после 2 периодов передачи: все участники приходят к согласию относительно порядка тех событий,

[1232] после 3 периодов передачи: все участники знают, что согласие было достигнуто,

[1233] после 4 периодов передачи: все участники получают цифровые подписи от всех остальных участников, одобряющие этот порядок консенсуса.

[1234] Доказательство: допустим, что S0 представляет собой набор событий, которые были созданы и/или определены к заданному моменту времени T0. Если каждый участник будет в итоге синхронизироваться с каждым из остальных участников бесконечное число раз, то с вероятностью, равной 1, в итоге будет существовать момент времени T1, к которому события в S0 распространятся каждому участнику, так что каждый участник будет осведомлен обо всех событиях. Это конец первого периода передачи. Допустим, что S1 представляет собой набор событий, которые существуют на момент времени T1 и которые еще не существовали на момент времени T0. Тогда с вероятностью, равной 1, в итоге будет существовать момент времени T2, к которому каждый участник примет каждое из событий в наборе S1, которое является существующим на момент времени T1. Это конец второго периода передачи. Подобным образом, T3 представляет собой момент времени, когда все события в S2, существующие к моменту времени T2, но не до момента времени T1, распространились всем участникам. Следует отметить, что каждый период передачи в итоге заканчивается с вероятностью, равной 1. В среднем каждый период будет продолжаться столько, сколько необходимо для выполнения log2(n) синхронизаций, если имеется n участников.

[1235] К моменту времени T1 каждый участник примет каждое событие в S0.

[1236] К моменту времени T2 заданный участник Алиса примет запись каждого из остальных участников, принимающих каждое событие в S0. Следовательно, Алиса может вычислить ранг для каждого действия в S0 для каждого участника (который представляет собой порядок, в котором тот участник принял то действие), а затем отсортировать события по медиане рангов. Полученный в результате общий порядок не меняется для событий в S0. Это объясняется тем, что полученный в результате порядок является функцией порядка, в котором каждый участник впервые принял указание о каждом из тех событий, который не меняется. Возможно, что порядок, вычисленный Алисой, будет иметь несколько событий из S1, рассеянных среди событий S0. Те события S1 могут все еще меняться, где они попадают в последовательность событий S0. Но относительный порядок событий в S0 не будет меняться.

[1237] К моменту времени T3 Алиса узнает общий порядок на объединении S0 и S1, и относительный порядок событий в том объединении меняться не будет. Кроме того, она может найти в этой последовательности самое раннее событие из S1 и может прийти к выводу, что последовательность событий до S1 не будет меняться, даже посредством вставки новых событий не из S0. Следовательно, к моменту времени T3 Алиса может определить, что консенсус был достигнут для порядка событий в истории до первого события S1. Она может подписать с помощью цифровой подписи хеш состояния (например, зафиксированного переменной состояния базы данных, определенной Алисой), являющийся результатом этих событий, происходящих в этом порядке, и отправить подпись в виде части следующего события, которое она создает и/или определяет.

[1238] К моменту времени T4 Алиса примет подобные подписи от других участников. На том этапе она может просто сохранить тот список подписей вместе с состоянием, свидетельством которого они являются, и она может удалить события, которые она сохранила до первого события S1. Что и требовалось доказать.

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

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

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

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

[1243] Другим примером является система открытого реестра. Кто угодно может заплатить, чтобы сохранить некоторую информацию в системе, уплачивая при этом небольшую сумму криптовалюты (или реальной валюты) за байт в год для хранения информации в системе. Эти денежные средства могут затем быть автоматически распределены участникам, которые хранят те данные, и участникам, которые постоянно синхронизируются, чтобы работать над достижением консенсуса. Участникам может автоматически переводиться небольшая сумма криптовалюты каждый раз, когда они синхронизируются.

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

[1245] Альтернативно вычислительные требования в такой системе могут быть снижены, например, следующим образом. Каждая пара участников может вначале провести переговоры относительно двух совместно используемых секретных ключей (по одному для каждого участника в паре), которые они используют для раздачи двух разных криптографически защищенных генераторов случайных чисел (CSPRNG) (по одному для каждого участника в паре). Если Алиса создала такой ключ с Бобом, то она использует свой CSPRNG для генерирования нового псевдослучайного числа каждый раз, когда она добавляет в базу данных сообщение, предназначенное Бобу, и она прилагает то число к зашифрованному сообщению. Затем Боб может быстро проверить число, приложенное к каждому сообщению в базе данных, чтобы проверить, указывает ли любое из таких чисел на сообщения, предназначенные ему. Так как Боб знает совместно используемый ключ, он поэтому знает последовательность чисел, которые будет генерировать Алиса, и, следовательно, он знает, какие числа следует искать при просмотре сообщений в отношении сообщений, адресованных ему Алисой. При нахождении им сообщений с такими приложенными числами он знает, что они являются сообщениями, отправленными ему Алисой, и он может расшифровать их. Только Боб может расшифровывать такие сообщения, поскольку они были зашифрованы с помощью его открытого ключа, и только Боб имеет соответствующий закрытый ключ.

[1246] В некоторых случаях посторонние сообщения, например, от Кэрол Дэйву, могут иметь разные приложенные числа, и Боб может удалить их, не пытаясь расшифровать сообщения. Более того, Алиса может отправлять Бобу K-ое сообщение с приложенным незашифрованным K-м случайным числом из ее CSPRNG. Алиса и Боб могут продолжать отслеживать то, сколько сообщений Алиса отправила Бобу (например, путем сохранения сообщений в хеш-таблице). Таким образом, в любой заданный момент времени Боб может определить следующее число, которое следует ожидать от каждого из других участников хешграфа. При приеме каждого сообщения Боб может определять посредством хеш-таблицы, соответствует ли приложенное число какому-либо ожидаемому числу. Если нет, то Боб не должен тратить время и ресурсы, пытаясь расшифровать принятое сообщение.

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

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

[1249] Хоть выше и описано, что событие содержит хеш двух предыдущих событий (один собственный хеш и один чужой хеш), в других вариантах осуществления участник может синхронизироваться с двумя другими участниками для создания и/или определения события, содержащего хеши трех предыдущих событий (один собственный хеш и два чужих хеша). В еще других вариантах осуществления в событие может быть включено любое количество хешей событий предыдущих событий от любого количества участников. В некоторых вариантах осуществления разные события могут содержать разные количества хешей предыдущих событий. Например, первое событие может содержать два хеша событий, и второе событие может содержать три хеша событий.

[1250] Хоть события и описаны выше как содержащие хеши (или значения криптографических хешей) предыдущих событий, в других вариантах осуществления событие может быть создано и/или определено таким образом, чтобы содержать указатель, идентификатор и/или любую другую подходящую ссылку на предыдущие события. Например, событие может быть создано и/или определено таким образом, чтобы содержать серийный номер, связанный с предыдущим событием и используемый для его идентификации, таким образом привязывая события друг к другу. В некоторых вариантах осуществления такой серийный номер может включать, например, идентификатор (например, адрес управления доступом к среде (MAC), адрес Интернет-протокола (IP-адрес), присвоенный адрес и/или т. п.), связанный с участником, который создал и/или определил событие, и порядком события, определенным тем участником. Например, если участник имеет идентификатор, равный 10, и событие является 15-ым событием, созданным и/или определенным тем участником, то он может присвоить тому событию идентификатор, равный 1015. В других вариантах осуществления любой другой подходящий формат может быть использован для присвоения идентификаторов событиям.

[1251] В других вариантах осуществления события могут содержать полные криптографические хеши, но только части тех хешей передаются во время синхронизации. Например, если Алиса отправляет Бобу событие, содержащее хеш H, и J является первыми 3 байтами H, и Алиса определяет, что из всех событий и хешей, которые она сохранила, H является единственным хешем, начинающимся с J, то она может отправить J вместо H во время синхронизации. Если Боб затем определяет, что у него есть другой хеш, начинающийся с J, то он может отправить ответное сообщение Алисе с запросом полного H. Таким образом хеши могут быть сжаты во время передачи.

[1252] Несмотря на то, что примерные системы, показанные и описанные выше, описаны со ссылкой на другие системы, в других вариантах осуществления любая комбинация примерных систем и связанных с ними функциональных возможностей может быть реализована для создания и/или определения распределенной базы данных. Например, примерная система 1, примерная система 2 и примерная система 3 могут быть объединены для создания и/или определения распределенной базы данных. В качестве другого примера, в некоторых вариантах осуществления примерная система 10 может быть реализована вместе с примерной системой 1, но без примерной системы 9. В качестве еще одного примера, примерная система 7 может быть объединена и реализована вместе с примерной системой 6. В еще других вариантах осуществления могут быть реализованы любые другие подходящие комбинации примерных систем.

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

[1254] Некоторые варианты осуществления, описанные в настоящем документе, относятся к продукту в виде запоминающего устройства с энергонезависимым машиночитаемым носителем (который также может называться энергонезависимым считываемым процессором носителем), на котором хранятся инструкции или компьютерный код для выполнения различных реализуемых компьютером операций. Машиночитаемый носитель (или считываемый процессором носитель) является энергонезависимым в том смысле, что он по существу не содержит временно распространяющихся сигналов (например, распространяющейся электромагнитной волны, несущей информацию по передающей среде, такой как пространство или кабель). Носители и компьютерный код (который также может называться кодом) могут быть выполнены и созданы для конкретной цели или целей. Примеры энергонезависимых машиночитаемых носителей включают, помимо прочего: магнитные запоминающие устройства, такие как жесткие диски, гибкие диски и магнитная лента; оптические запоминающие устройства, такие как компакт-диск / цифровые видеодиски (CD/DVD), постоянные запоминающие устройства на компакт-дисках (CD-ROM) и голографические устройства; магнитооптические запоминающие устройства, такие как оптические диски; модули обработки сигнала несущей частоты; и аппаратные устройства, которые специально приспособлены для хранения и исполнения программного кода, такие как интегральные схемы специального назначения (ASIC), программируемые логические интегральные схемы (PLD), постоянные запоминающие устройства (ROM) и оперативные запоминающие устройства (RAM). Другие варианты осуществления, описанные в настоящем документе, относятся к компьютерному программному продукту, который может включать, например, инструкции и/или компьютерный код, обсуждаемые в настоящем документе.

[1255] Примеры компьютерного кода включают, помимо прочего, микрокод или микроинструкции, машинные инструкции, такие как созданные компилятором, код, используемый для создания веб-службы, и файлы, содержащие инструкции более высокого уровня, которые исполняются компьютером с использованием интерпретатора. Например, варианты осуществления могут быть реализованы с использованием императивных языков программирования (например, C, Fortran и т. д.), функциональных языков программирования (Haskell, Erlang и т. д.), логических языков программирования (например, Prolog), объектно-ориентированных языков программирования (например, Java, C++ и т. д.) или других подходящих языков программирования и/или инструментов разработки. Дополнительные примеры компьютерного кода включают, помимо прочего, сигналы управления, зашифрованный код и сжатый код.

[1256] Хоть выше и были описаны различные варианты осуществления, следует понимать, что они были представлены исключительно в качестве примера, а не ограничения, и различные изменения могут быть выполнены в отношении формы и деталей. Любая часть устройства и/или способов, описанных в настоящем документе, может быть объединена в любой комбинации, за исключением взаимоисключающих комбинаций. Варианты осуществления, описанные в настоящем документе, могут включать различные комбинации и/или подкомбинации функций, компонентов и/или признаков разных описанных вариантов осуществления.

1. Устройство для реализации распределенной базы данных, содержащее:

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

процессор, функционально соединенный с памятью и приспособленный для:

определения первой группы вычислительных устройств из множества вычислительных устройств и второй группы вычислительных устройств из множества вычислительных устройств на основе детерминированной псевдослучайной функции;

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

идентификации порядка, связанного со вторым набором событий, в результате того, что протокол консенсуса (1) использует значение для параметра события из первого набора событий, которое было определено вычислительным устройством из первой группы вычислительных устройств, и (2) не использует значение для параметра события из первого набора событий, которое было определено вычислительным устройством из второй группы вычислительных устройств;

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

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

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

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

4. Устройство по п. 1, отличающееся тем, что процессор дополнительно приспособлен для:

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

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

после синхронизации с вычислительным устройством из третьей группы вычислительных устройств:

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

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

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

5. Устройство по п. 1, отличающееся тем, что процессор дополнительно приспособлен для:

исполнения процесса синхронизации событий со вторым вычислительным устройством для приема события; и

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

6. Устройство по п. 1, отличающееся тем, что процессор дополнительно приспособлен для:

исполнения процесса синхронизации событий со вторым вычислительным устройством для приема события; и

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

7. Устройство по п. 1, отличающееся тем, что процессор дополнительно приспособлен для:

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

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

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

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

идентифицировать порядок, связанный со вторым набором событий, в результате того, что протокол консенсуса (1) использует параметр первого события из первого набора событий на основе того, что первое событие было определено вычислительным устройством из второй группы вычислительных устройств, и (2) не использует параметр второго события из первого набора событий на основе того, что второе событие было определено вычислительным устройством из первой группы вычислительных устройств; и

сохранить порядок, связанный со вторым набором событий.

9. Энергонезависимый, считываемый процессором носитель по п. 8, отличающийся тем, что дополнительно содержит код для предписывания процессору:

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

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

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

12. Энергонезависимый, считываемый процессором носитель по п. 8, отличающийся тем, что код для предписывания процессору осуществить назначение содержит код для предписывания процессору осуществить назначение для первого раунда протокола консенсуса, причем код дополнительно содержит код для предписывания процессору:

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

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

14. Энергонезависимый, считываемый процессором носитель по п. 8, отличающийся тем, что параметр первого события из первого набора событий определен с применением первого способа и параметр второго события из первого набора событий определен с применением второго способа, отличного от первого способа.

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

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

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

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

17. Способ реализации распределенной базы данных, включающий:

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

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

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

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

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

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

сохранение порядка, связанного со вторым набором событий.

18. Способ по п. 17, отличающийся тем, что дополнительно включает:

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

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

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

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

22. Способ по п. 17, отличающийся тем, что идентификация первой группы вычислительных устройств включает идентификацию первой группы вычислительных устройств для первого раунда протокола консенсуса, причем способ дополнительно включает:

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

23. Способ по п. 17, отличающийся тем, что дополнительно включает:

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

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

24. Способ по п. 17, отличающийся тем, что дополнительно включает:

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

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