Перекрестная ссылка на родственные заявки на патенты
Настоящая заявка на патент испрашивает приоритет предварительной заявки на патент США № 62/420147, поданной 10 ноября 2016 г., под названием «METHODS AND APPARATUS FOR A DISTRIBUTED DATABASE INCLUDING ANONYMOUS ENTRIES», которая включена в настоящий документ посредством ссылки во всей своей полноте.
Предпосылки изобретения
Варианты осуществления, описанные в настоящем документе, относятся в целом к системе базы данных и более конкретно к способам и устройству для реализации системы базы данных на множестве устройств в сети.
Некоторые известные системы распределенных баз данных пытаются достичь консенсуса для значений в системах распределенных баз данных (например, относительно порядка, в котором происходят транзакции). Например, многопользовательская онлайн-игра может иметь множество компьютерных серверов, доступ к которым пользователи могут получать, чтобы играть в игру. Если два пользователя одновременно пытаются поднять конкретный предмет в игре, то важно, чтобы серверы в системе распределенной базы данных в итоге достигли согласия относительно того, какой из двух пользователей подобрал предмет первым.
Такой распределенный консенсус может быть обработан посредством способов и/или процессов, таких как алгоритм Паксос или его варианты. При использовании таких способов и/или процессов один сервер системы базы данных устанавливается в качестве «лидера», и лидер принимает решения относительно порядка событий. События (например, в многопользовательских играх) передаются лидеру, лидер выбирает упорядоченную последовательность для событий, и лидер передает эту упорядоченную последовательность на другие серверы системы базы данных.
Однако при таких известных подходах используется сервер, управляемый некоторой стороной (например, центральным сервером управления), которой доверяют пользователи системы базы данных (например, игроки в игре). Соответственно, существует необходимость в способах и устройстве для системы распределенной базы данных, для которых не будут требоваться лидер или доверенная третья сторона, чтобы управлять системой базы данных.
Другие распределенные базы данных выполнены таким образом, что не имеют лидера, но транзакции в таких распределенных базах данных являются открытыми. Таким образом, другие экземпляры распределенной базы данных могут идентифицировать, какие экземпляры распределенной базы данных начали определенные транзакции.
Соответственно, существует необходимость в системе распределенной базы данных, которая достигает консенсуса без лидера и способна поддерживать анонимность транзакций.
Сущность изобретения
В некоторых вариантах осуществления устройство содержит по меньшей мере часть первого экземпляра распределенной базы данных на первом вычислительном устройстве, приспособленном для включения в группу вычислительных устройств, которые реализуют посредством сети, функционально соединенной с группой вычислительных устройств, распределенную базу данных. Распределенная база данных содержит первую запись, находящуюся в логической связи с первым открытым ключом, связанным с первым вычислительным устройством. Устройство также содержит процессор, функционально соединенный с частью первого экземпляра распределенной базы данных. Процессор приспособлен для приема со второго вычислительного устройства из группы вычислительных устройств первого открытого ключа, связанного со вторым вычислительным устройством, и (1) зашифрованного с помощью первого открытого ключа, связанного с первым вычислительным устройством, и (2) находящегося в логической связи со второй записью распределенной базы данных. Процессор приспособлен для расшифровки первого открытого ключа, связанного со вторым вычислительным устройством, с помощью закрытого ключа, находящегося в паре с первым открытым ключом, связанным с первым вычислительным устройством. Процессор приспособлен для отправки на второе вычислительное устройство второго открытого ключа, связанного с первым вычислительным устройством и зашифрованного с помощью второго открытого ключа, связанного со вторым вычислительным устройством. Как первое вычислительное устройство, так и второе вычислительное устройство приспособлены для подписания с помощью цифровой подписи или авторизации передачи из исходной записи, связанной с первым открытым ключом, связанным с первым вычислительным устройством, и из исходной записи, связанной со вторым открытым ключом, связанным со вторым вычислительным устройством, в целевую запись, связанную со вторым открытым ключом, связанным с первым вычислительным устройством, и в целевую запись, связанную с первым открытым ключом, связанным со вторым вычислительным устройством. Эта передача в таком случае осуществляет передачу значения из двух исходных записей в две целевые записи.
Краткое описание графических материалов
На фиг. 1 представлена структурная схема высокого уровня, на которой проиллюстрирована система распределенной базы данных согласно варианту осуществления.
На фиг. 2 представлена структурная схема, на которой проиллюстрировано вычислительное устройство системы распределенной базы данных согласно варианту осуществления.
На фиг. 3–6 проиллюстрированы примеры хешграфа согласно варианту осуществления.
На фиг. 7 представлена функциональная схема, на которой проиллюстрирован информационный поток между первым вычислительным устройством и вторым вычислительным устройством согласно варианту осуществления.
На фиг. 8 представлен пример хешграфа согласно варианту осуществления.
На фиг. 9 представлен пример хешграфа согласно варианту осуществления.
На фиг. 10 представлен пример графического представления анонимной транзакции в базе данных между двумя вычислительными устройствами согласно варианту осуществления.
На фиг. 11 проиллюстрировано графическое представление анонимных транзакций в базе данных на нескольких уровнях дерева, представляющего анонимные транзакции в базе данных между различными вычислительными устройствами, согласно варианту осуществления.
На фиг. 12 проиллюстрировано графическое представление анонимных транзакций в базе данных, совершенных параллельно между различными вычислительными устройствами, согласно варианту осуществления.
На фиг. 13A–13B проиллюстрирован примерный способ консенсуса для использования с хешграфом согласно варианту осуществления.
На фиг. 14A–14B проиллюстрирован примерный способ консенсуса для использования с хешграфом согласно другому варианту осуществления.
Подробное описание изобретения
В некоторых вариантах осуществления устройство содержит по меньшей мере часть первого экземпляра распределенной базы данных на первом вычислительном устройстве, приспособленном для включения в группу вычислительных устройств, которые реализуют посредством сети, функционально соединенной с группой вычислительных устройств, распределенную базу данных. Распределенная база данных содержит первую запись, находящуюся в логической связи с первым открытым ключом, связанным с первым вычислительным устройством. Устройство также содержит процессор, функционально соединенный с частью первого экземпляра распределенной базы данных. Процессор приспособлен для приема со второго вычислительного устройства из группы вычислительных устройств первого открытого ключа, связанного со вторым вычислительным устройством, и (1) зашифрованного с помощью первого открытого ключа, связанного с первым вычислительным устройством, и (2) находящегося в логической связи со второй записью распределенной базы данных. Процессор приспособлен для расшифровки первого открытого ключа, связанного со вторым вычислительным устройством, с помощью закрытого ключа, находящегося в паре с первым открытым ключом, связанным с первым вычислительным устройством. Процессор приспособлен для отправки на второе вычислительное устройство второго открытого ключа, связанного с первым вычислительным устройством и зашифрованного с помощью второго открытого ключа, связанного со вторым вычислительным устройством. Как первое вычислительное устройство, так и второе вычислительное устройство приспособлены для подписания с помощью цифровой подписи или авторизации передачи из исходной записи, связанной с первым открытым ключом, связанным с первым вычислительным устройством, и из исходной записи, связанной со вторым открытым ключом, связанным со вторым вычислительным устройством, в целевую запись, связанную со вторым открытым ключом, связанным с первым вычислительным устройством, и в целевую запись, связанную с первым открытым ключом, связанным со вторым вычислительным устройством. Эта передача в таком случае осуществляет передачу значения из двух исходных записей в две целевые записи.
В некоторых вариантах осуществления устройство содержит первый экземпляр по меньшей мере части распределенной базы данных на первом вычислительном устройстве, приспособленном для включения в группу вычислительных устройств, которые реализуют посредством сети, функционально соединенной с группой вычислительных устройств, распределенную базу данных. Распределенная база данных содержит первую запись, находящуюся в логической связи с первым открытым ключом, связанным с первым вычислительным устройством. Процессор первого вычислительного устройства функционально соединен с первым экземпляром по меньшей мере части распределенной базы данных. Процессор приспособлен для приема со второго вычислительного устройства из группы вычислительных устройств первого открытого ключа, связанного со вторым вычислительным устройством, зашифрованного с помощью первого открытого ключа, связанного с первым вычислительным устройством, и значения, запрошенного для передачи из второй записи, находящейся в логической связи со вторым открытым ключом, связанным со вторым вычислительным устройством, в целевую запись, которую предполагается создать в распределенной базе данных. Как первое вычислительное устройство, так и второе вычислительное устройство приспособлены для отправки сигнала для внесения в распределенную базу данных команды передачи, приспособленной для передачи значения из первой записи и второй записи в третью запись и четвертую запись, тем самым создавая третью и четвертую записи в распределенной базе данных. Третья запись находится в логической связи со вторым открытым ключом, связанным с первым вычислительным устройством, и четвертая запись находится в логической связи с первым открытым ключом, связанным со вторым вычислительным устройством. Команда передачи подписана с помощью закрытого ключа, находящегося в паре с первым открытым ключом, связанным с первым вычислительным устройством, а также подписана с помощью закрытого ключа, находящегося в паре со вторым открытым ключом, связанным со вторым вычислительным устройством, и приспособлена для исполнения таким образом, чтобы скрыть идентификатор вычислительного устройства, связанного с закрытым ключом, соответствующим второму открытому ключу, связанному с первым вычислительным устройством, среди набора вычислительных устройств, содержащего первое вычислительное устройство и второе вычислительное устройство.
В некоторых вариантах осуществления устройство содержит первый экземпляр по меньшей мере части распределенной базы данных на первом вычислительном устройстве, приспособленном для включения в группу вычислительных устройств, которые реализуют посредством сети, функционально соединенной с группой вычислительных устройств, распределенную базу данных. Распределенная база данных содержит первую запись, находящуюся в логической связи с первым открытым ключом, вторую запись, находящуюся в логической связи со вторым открытым ключом, третью запись, находящуюся в логической связи с третьим открытым ключом, и четвертую запись, находящуюся в логической связи с четвертым открытым ключом. Процессор первого вычислительного устройства функционально соединен с первым экземпляром по меньшей мере части распределенной базы данных. Процессор приспособлен для приема указания операции над базой данных, которая включает запрос на передачу значения, связанного с первой записью, и значения, связанного со второй записью, как в третью запись, так и в четвертую запись. Команда передачи приспособлена для исполнения таким образом, что команда передачи скрывает идентификатор вычислительного устройства, связанного с закрытым ключом, соответствующим третьему открытому ключу, и идентификатор вычислительного устройства, связанного с закрытым ключом, соответствующим четвертому открытому ключу.
В контексте настоящего документа модуль может представлять собой, например, любой узел и/или набор функционально соединенных электрических компонентов, связанных с выполнением конкретной функции, и может содержать, например, память, процессор, электрические каналы связи, оптические соединители, программное обеспечение (исполняемое в аппаратном обеспечении) и/или т.п.
В контексте настоящего описания форма единственного числа включает ссылки, определяемые объекты во множественном числе, если в контексте явно не указано иное. Таким образом, например, предполагается, что термин «модуль» означает один модуль или комбинацию модулей. Например, предполагается, что «сеть» означает одну сеть или комбинацию сетей.
На фиг. 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.
В некоторых вариантах осуществления вычислительные устройства 110, 120, 130, 140 могут осуществлять связь друг с другом (например, отправлять данные на и/или принимать данные с) и с сетью посредством промежуточных сетей и/или альтернативных сетей (не показаны на фиг. 1). Такие промежуточные сети и/или альтернативные сети могут принадлежать к тому же типу и/или другому типу сети в сравнении с сетью 105.
Каждое вычислительное устройство 110, 120, 130, 140 может представлять собой устройство любого типа, приспособленное для отправки данных по сети 105, чтобы отправлять и/или принимать данные с одного или более других вычислительных устройств. Примеры вычислительных устройств показаны на фиг. 1. Вычислительное устройство 110 содержит память 112, процессор 111 и устройство 113 вывода. Память 112 может представлять собой, например, оперативное запоминающее устройство (RAM), буфер памяти, жесткий диск, базу данных, стираемое программируемое постоянное запоминающее устройство (EPROM), электрически стираемое программируемое постоянное запоминающее устройство (EEPROM), постоянное запоминающее устройство (ROM) и/или т. д. В некоторых вариантах осуществления память 112 вычислительного устройства 110 содержит данные, связанные с экземпляром распределенной базы данных (например, экземпляром 114 распределенной базы данных). В некоторых вариантах осуществления память 112 хранит инструкции, приводящие к исполнению процессором модулей, процессов и/или функций, связанных с отправкой на другой экземпляр и/или приемом с другого экземпляра распределенной базы данных (например, экземпляра 124 распределенной базы данных на вычислительном устройстве 120) записи события синхронизации, записи предыдущих событий синхронизации с другими вычислительными устройствами, порядка событий синхронизации, значения для параметра (например, поля базы данных, количественно характеризующего транзакцию, поля базы данных, количественно характеризующего порядок, в котором происходят события, и/или любого другого подходящего поля, для которого значение может быть сохранено в базе данных).
Экземпляр 114 распределенной базы данных может, например, быть приспособлен для проведений операций с данными, включая сохранение, модификацию и/или удаление данных. В некоторых вариантах осуществления экземпляр 114 распределенной базы данных может представлять собой реляционную базу данных, объектную базу данных, постреляционную базу данных и/или базу данных любого другого подходящего типа. Например, экземпляр 114 распределенной базы данных может хранить данные, относящиеся к любой конкретной функции и/или области. Например, экземпляр 114 распределенной базы данных может хранить финансовые транзакции (например, пользователя вычислительного устройства 110), включая значение и/или вектор значений, относящиеся к истории владения конкретным финансовым инструментом. В целом, вектор может представлять собой любой набор значений для параметра, и параметр может представлять собой любые объект данных и/или поле базы данных, которые могут принимать разные значения. Таким образом, экземпляр 114 распределенной базы данных может иметь ряд параметров и/или полей, каждый из которых связан с вектором значений. Вектор значений используется для определения фактического значения для параметра и/или поля в этом экземпляре 114 базы данных.
В некоторых случаях экземпляр 114 распределенной базы данных может также быть использован для реализации других структур данных, таких как набор пар (ключ, значение). Транзакцией, записанной экземпляром 114 распределенной базы данных, может быть, например, добавление, удаление или модификация пары (ключ, значение) в наборе пар (ключ, значение).
В некоторых случаях в систему 100 распределенной базы данных или в любой из экземпляров 114, 124, 134, 144 распределенной базы данных может быть отправлен запрос. Например, запрос может состоять из ключа, и результат, возвращаемый системой 100 распределенной базы данных или экземплярами 114, 124, 134, 144 распределенной базы данных, может представлять собой значение, связанное с ключом. В некоторых случаях система 100 распределенной базы данных или любой из экземпляров 114, 124, 134, 144 распределенной базы данных могут быть также модифицированы посредством транзакции. Например, транзакция для модификации базы данных может содержать цифровую подпись, выполненную стороной, авторизирующей транзакцию модификации.
Система 100 распределенной базы данных может быть использована для многих целей, таких как, например, хранение атрибутов, связанных с различными пользователями в распределенной системе идентификации. Например, такая система может использовать идентификатор пользователя в качестве «ключа», а список атрибутов, связанных с пользователями, в качестве «значения». В некоторых случаях идентификатор может представлять собой криптографический открытый ключ с соответствующим закрытым ключом, известным этому пользователю. Каждый атрибут может, например, быть подписан с помощью цифровой подписи органом, имеющим право на утверждение этого атрибута. Каждый атрибут может быть также, например, зашифрован с помощью открытого ключа, связанного с физическим лицом или группой физических лиц, которые обладают правом на считывание атрибута. Некоторые ключи или значения могут также иметь прикрепленный к ним список открытых ключей сторон, которые уполномочены модифицировать или удалять ключи или значения.
В другом примере экземпляр 114 распределенной базы данных может хранить данные, относящиеся к массовым многопользовательским играм (MMG), такие как текущее состояние и принадлежность игровых предметов. В некоторых случаях экземпляр 114 распределенной базы данных может быть реализован в вычислительном устройстве 110, как показано на фиг. 1. В других случаях вычислительное устройство может иметь доступ к экземпляру распределенной базы данных (например, по сети), но он не реализован в вычислительном устройстве (не показано на фиг. 1).
Процессор 111 вычислительного устройства 110 может представлять собой любое подходящее устройство обработки, приспособленное для запуска и/или исполнения экземпляра 114 распределенной базы данных. Например, процессор 111 может быть приспособлен для обновления экземпляра 114 распределенной базы данных в ответ на прием сигнала с вычислительного устройства 120 и/или вызова отправки сигнала на вычислительное устройство 120, как более подробно описано в настоящем документе. Более конкретно, как более подробно описано в настоящем документе, процессор 111 может быть приспособлен для исполнения модулей, функций и/или процессов для обновления экземпляра 114 распределенной базы данных в ответ на прием события синхронизации, связанного с транзакцией, с другого вычислительного устройства, записи, связанной с порядком событий синхронизации, и/или т.п. В других вариантах осуществления процессор 111 может быть приспособлен для исполнения модулей, функций и/или процессов для обновления экземпляра 114 распределенной базы данных в ответ на прием значения для параметра, сохраненного в другом экземпляре распределенной базы данных (например, экземпляре 124 распределенной базы данных на вычислительном устройстве 120), и/или вызова отправки значения для параметра, сохраненного в экземпляре 114 распределенной базы данных на вычислительном устройстве 110, на вычислительное устройство 120. В некоторых вариантах осуществления процессор 111 может представлять собой процессор общего назначения, программируемую пользователем вентильную матрицу (FPGA), интегральную схему специального назначения (ASIC), процессор цифровой обработки сигналов (DSP) и/или т.п.
Дисплей 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 может содержать клавиатуру, мышь и/или т.п.
Вычислительное устройство 120 имеет процессор 121, память 122 и дисплей 123, которые могут быть конструктивно и/или функционально подобны процессору 111, памяти 112 и дисплею 113 соответственно. Также экземпляр 124 распределенной базы данных может быть структурно и/или функционально подобен экземпляру 114 распределенной базы данных.
Вычислительное устройство 130 имеет процессор 131, память 132 и дисплей 133, которые могут быть конструктивно и/или функционально подобны процессору 111, памяти 112 и дисплею 113 соответственно. Также экземпляр 134 распределенной базы данных может быть структурно и/или функционально подобен экземпляру 114 распределенной базы данных.
Вычислительное устройство 140 имеет процессор 141, память 142 и дисплей 143, которые могут быть конструктивно и/или функционально подобны процессору 111, памяти 112 и дисплею 113 соответственно. Также экземпляр 144 распределенной базы данных может быть структурно и/или функционально подобен экземпляру 114 распределенной базы данных.
Хотя вычислительные устройства 110, 120, 130, 140 показаны как подобные друг другу, каждое вычислительное устройство системы 100 распределенной базы данных может отличаться от других вычислительных устройств. Каждое вычислительное устройство 110, 120, 130, 140 системы 100 распределенной базы данных может представлять собой любое из, например, вычислительного элемента (например, персонального вычислительного устройства, такого как настольный компьютер, портативный компьютер и т. д.), мобильного телефона, карманного персонального компьютера (PDA) и т. д. Например, вычислительное устройство 110 может представлять собой настольный компьютер, вычислительное устройство 120 может представлять собой смартфон, и вычислительное устройство 130 может представлять собой сервер.
В некоторых вариантах осуществления одна или более частей вычислительных устройств 110, 120, 130, 140 могут включать аппаратный модуль (например, процессор цифровой обработки сигналов (DSP), программируемую пользователем вентильную матрицу (FPGA)) и/или программный модуль (например, модуль компьютерного кода, хранящегося в памяти и/или исполняемого процессором). В некоторых вариантах осуществления одна или более функций, связанных с вычислительными устройствами 110, 120, 130, 140 (например, функции, связанные с процессорами 111, 121, 131, 141), могут быть включены в один или более модулей (см., например, фиг. 2).
Свойства системы 100 распределенной базы данных, включая свойства вычислительных устройств (например, вычислительных устройств 110, 120, 130, 140), количество вычислительных устройств, и сеть 105 могут быть выбраны любыми способами. В некоторых случаях свойства системы 100 распределенной базы данных могут быть выбраны администратором системы 100 распределенной базы данных. В других случаях свойства системы 100 распределенной базы данных могут быть совместно выбраны пользователями системы 100 распределенной базы данных.
Поскольку используется система 100 распределенной базы данных, среди вычислительных устройств 110, 120, 130 и 140 не назначен лидер. В частности, ни одно из вычислительных устройств 110, 120, 130 или 140 не идентифицируется и/или не выбирается в качестве лидера для разрешения конфликтов между значениями, хранящимися в экземплярах 111, 12, 131, 141 распределенной базы данных вычислительных устройств 110, 120, 130, 140. Вместо этого, с использованием процессов синхронизации событий, процессов голосования и/или способов, описанных в настоящем документе, вычислительные устройства 110, 120, 130, 140 могут совместно согласовывать значение для параметра.
Отсутствие лидера в системе распределенной базы данных повышает безопасность системы распределенной базы данных. В частности, при наличии лидера существует единая точка атаки и/или сбоя. Если вредоносное программное обеспечение заражает лидера и/или значение для параметра на экземпляре распределенной базы данных лидера изменяют со злым умыслом, ошибочное и/или неправильное значение распространяется по другим экземплярам распределенной базы данных. Однако в системе без лидера нет единой точки атаки и/или сбоя. В частности, если параметр в экземпляре распределенной базы данных системы без лидера содержит значение, значение изменится после того, как этот экземпляр распределенной базы данных обменяется значениями с другими экземплярами распределенной базы данных в системе, как более подробно описано в настоящем документе. Дополнительно системы распределенной базы данных без лидера, описанные в настоящем документе, повышают скорость конвергенции, при этом уменьшая объем данных, передаваемых между устройствами, как более подробно описано в настоящем документе.
На фиг. 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 отправлять данные на и/или принимать данные с другого устройства.
В некоторых случаях модуль 211 конвергенции базы данных может обмениваться событиями и/или транзакциями с другими вычислительными устройствами, сохранять события и/или транзакции, которые принимает модуль 211 конвергенции базы данных, и вычислять упорядоченную последовательность событий и/или транзакций на основе частичного порядка, определенного схемой ссылок между событиями. Каждое событие может представлять собой запись, содержащую криптографический хеш двух более ранних событий (связывающий это событие с двумя более ранними событиями и их событиями-предками и наоборот), данные полезной нагрузки (такие как транзакции, которые должны быть записаны), другую информацию, такую как текущее время, метка времени (например, дата и время по UTC), которую утвердил ее создатель, представляющая время, в которое событие было впервые определено, и/или т.п. В некоторых случаях первое событие, определенное участником, содержит хеш только одного события, определенного другим участником. В таких случаях участник еще не имеет предыдущего собственного хеша (например, хеша события, ранее определенного этим участником). В некоторых случаях первое событие в распределенной базе данных не содержит хеша никакого предыдущего события (поскольку отсутствует предыдущее событие для этой распределенной базы данных).
В некоторых вариантах осуществления такой криптографический хеш двух более ранних событий может представлять собой значение хеша, определенное на основе криптографической хеш-функции с использованием события в качестве входных данных. А именно, в таких вариантах осуществления событие содержит конкретную последовательность или строку байтов (которые представляют собой информацию этого события). Хеш события может представлять собой значение, возвращаемое хеш-функцией, использующей последовательность байтов для этого события в качестве входных данных. В других вариантах осуществления любые другие подходящие данные, связанные с событием (например, идентификатор, серийный номер, байты, представляющие конкретную часть события, и т. д.), могут быть использованы в качестве входных данных для хеш-функции для вычисления хеша этого события. Любая подходящая хеш-функция может быть использована для определения хеша. В некоторых вариантах осуществления каждый участник использует одну и ту же хеш-функцию, так что один и тот же хеш генерируется у каждого участника для заданного события. Событие может быть затем подписано с помощью цифровой подписи участником, определяющим и/или создающим событие.
В некоторых случаях набор событий и их взаимосвязей может формировать направленный ациклический граф (DAG). В некоторых случаях каждое событие в DAG ссылается на два более ранних события (связывая это событие с двумя более ранними событиями и их событиями-предками и наоборот), и каждая ссылка осуществляется строго на более ранние события, так что циклов нет. В некоторых вариантах осуществления DAG основан на криптографических хешах, так что структура данных может называться хешграфом (также называется в настоящем документе «DAG на основе хешей»). Хешграф непосредственно кодирует частичный порядок, обозначая, что известно, что событие X происходит до события Y, если Y содержит хеш X, или если Y содержит хеш события, которое содержит хеш X, или для таких путей произвольной длины. Однако, если путь от X к Y или от Y к X отсутствует, то частичный порядок не определяет, какое событие произошло первым. Следовательно, модуль конвергенции базы данных может вычислять общий порядок из частичного порядка. Это может быть выполнено с помощью любой подходящей детерминированной функции, которая используется вычислительными устройствами, так что вычислительные устройства вычисляют один и тот же порядок. В некоторых вариантах осуществления каждый участник может повторно вычислять этот порядок после каждой синхронизации, и в итоге эти порядки могут сходиться таким образом, что возникает консенсус.
Алгоритм консенсуса может быть использован для определения порядка событий в хешграфе и/или порядка транзакций, сохраненных в событиях. Порядок транзакций в свою очередь может определять состояние базы данных в результате выполнения этих транзакций в соответствии с порядком. Определенное состояние базы данных может быть сохранено в качестве переменной состояния базы данных.
В некоторых случаях модуль конвергенции базы данных может использовать следующую функцию для вычисления общего порядка из частичного порядка в хешграфе. Для каждого из других вычислительных устройств (называемых «участниками») модуль конвергенции базы данных может изучать хешграф для установления порядка, в котором события (и/или указания этих событий) были приняты тем участником. Модуль конвергенции базы данных может затем выполнять вычисления таким образом, словно этот участник присвоил числовой «ранг» каждому событию, при этом ранг равен 1 для первого события, которое принял участник, 2 для второго события, которое принял участник, и так далее. Модуль конвергенции базы данных может выполнять это для каждого участника в хешграфе. Затем для каждого события модуль конвергенции базы данных может вычислять медиану присвоенных рангов и может сортировать события по их медианам. Сортировка может разрушать равенства детерминированным образом, например, сортируя два равных события по числовому порядку их хешей или некоторым другим способом, в котором модуль конвергенции базы данных каждого участника использует одинаковый способ. Результатом этой сортировки является общий порядок.
На фиг. 6 проиллюстрирован хешграф 640 одного примера для определения общего порядка. Хешграф 640 иллюстрирует два события (самый нижний круг с полосками и самый нижний круг с точками) и первый момент времени, когда каждый участник принимает указание на эти события (остальные круги с полосками и точками). Имя каждого участника в верхней части окрашено согласно тому, какое событие является первым в их медленном порядке. Первоначальных голосов с полосками больше, чем с точками; следовательно, голоса консенсуса для каждого из участников имеют вид с полосками. Другими словами, участники в итоге приходят к согласию, что событие с полосками произошло до события с точками.
В этом примере участники (вычислительные устройства, обозначенные как Алиса, Боб, Кэрол, Дэйв и Эд) будут работать таким образом, чтобы достичь консенсуса относительно того, произошло ли первым событие 642 или событие 644. Каждый круг с полосками указывает на событие, когда участник впервые принял событие 644 (и/или указание этого события 644). Подобным образом каждый круг с точками указывает на событие, когда участник впервые принял событие 642 (и/или указание этого события 642). Как показано в хешграфе 640, каждый из Алисы, Боба и Кэрол принял событие 644 (и/или указание о событии 644) до события 642. Как Дэйв, так и Эд приняли событие 642 (и/или указание о событии 642) до события 644 (и/или указания о событии 644). Таким образом, поскольку большее количество участников приняли событие 644 до события 642, общий порядок может быть определен каждым участником для указания того, что событие 644 произошло до события 642.
В других случаях модуль конвергенции базы данных может использовать другую функцию для вычисления общего порядка из частичного порядка в хешграфе. В таких вариантах осуществления, например, модуль конвергенции базы данных может использовать следующие функции для вычисления общего порядка, при этом положительное целое число Q представляет собой параметр, совместно используемый участниками.
В этом варианте осуществления fast(x,y) дает положение y в общем порядке событий по мнению creator(x) по существу сразу после создания и/или определения x. Если Q равно бесконечности, то вышеописанное вычисляет такой же общий порядок, как получается и в ранее описанном варианте осуществления. Если Q является конечным числом и все участники находятся в режиме онлайн, то вышеописанное вычисляет такой же общий порядок, как получается и в ранее описанном варианте осуществления. Если Q является конечным числом и меньшая часть участников находится в режиме онлайн в заданный момент времени, то эта функция позволяет находящимся онлайн участникам достигать консенсуса между собой, который будет сохраняться неизменным по мере постепенного, поочередного перехода в режим онлайн новых участников. Однако, если речь идет о разделе сети, то участники каждого раздела могут прийти к своему собственному консенсусу. Затем, когда раздел заполняется, участники меньшего раздела примут консенсус большего раздела.
В еще других случаях, как описано в отношении фиг. 8, фиг. 9 и фиг. 13A–14B, модуль конвергенции базы данных может использовать еще другую функцию для вычисления общего порядка из частичного порядка в хешграфе. Как показано на фиг. 8–9, каждый участник (Алиса, Боб, Кэрол, Дэйв и Эд) создает и/или определяет события (1401–1413, как показано на фиг. 8; 1501–1506, показанные на фиг. 9). При использовании функции и подфункций, описанных в отношении фиг. 8, фиг. 9 и фиг. 13A–14B, общий порядок для событий может быть вычислен посредством сортировки событий по их принятому раунду, с разрушением равенств по их принятой метке времени и разрушением этих равенств по их подписям, как более подробно описано в настоящем документе. В других случаях общий порядок для событий может быть вычислен посредством сортировки событий по их принятому раунду, с разрушением равенств по их принятому поколению (вместо их принятой метки времени) и с разрушением этих равенств по их подписям. В следующих абзацах заданы функции, используемые для вычисления и/или определения принятого раунда и принятого поколения события для определения порядка для событий. Следующие термины используются и иллюстрируются в связи с фиг. 8, фиг. 9 и фиг. 13A–14B.
«Родитель» («Parent»): событие X является родителем события Y, если Y содержит хеш X. Например, как показано на фиг. 8, родители события 1412 включают событие 1406 и событие 1408.
«Предок» («Ancestor»): предками события X являются X, его родители, родители его родителей и так далее. Например, как показано на фиг. 8, предками события 1412 являются события 1401, 1402, 1403, 1406, 1408 и 1412. Можно сказать, что предки события связаны с этим событием и наоборот.
«Потомок» («Descendant»): потомками события X являются X, его дети, дети его детей и так далее. Например, как показано на фиг. 8, потомком события 1401 является каждое событие, показанное на фигуре. В качестве другого примера, потомками события 1403 являются события 1403, 1404, 1406, 1407, 1409, 1410, 1411, 1412 и 1413. Можно сказать, что потомки события связаны с этим событием и наоборот.
«N»: общее количество участников в популяции. Например, как показано на фиг. 8, участники представляют собой вычислительные устройства, обозначенные как Алиса, Боб, Кэрол, Дэйв и Эд, и N равняется пяти.
«M»: наименьшее целое число, которое превышает определенную процентную долю N (например, превышает 2/3 от N). Например, как показано на фиг. 8, если процентная доля определена как 2/3, то M равняется четырем. В других случаях M может быть определено, например, как другая процентная доля N (например, 1/3, 1/2 и т. д.), конкретное предварительно определенное число и/или любым другим подходящим способом.
«Собственный родитель» («Self-parent»): собственным родителем события X является его событие-родитель Y, созданное и/или определенное тем же участником. Например, как показано на фиг. 8, собственным родителем события 1405 является 1401.
«Собственный предок» («Self-ancestor»): собственными предками события X являются X, его собственный родитель, собственный родитель его собственного родителя и так далее.
«Порядковый номер» («Sequence Number», или «SN»): целочисленный атрибут события, определенный как порядковый номер собственного родителя события плюс один. Например, как показано на фиг. 8, собственным родителем события 1405 является 1401. Поскольку порядковый номер события 1401 равен одному, порядковый номер события 1405 равен двум (т. е. один плюс один).
«Номер поколения» («Generation Number», или «GN»): целочисленный атрибут события, определенный как максимальное значение номеров поколений родителей события плюс один. Например, как показано на фиг. 8, событие 1412 имеет двух родителей, события 1406 и 1408, имеющих номера поколений четыре и два соответственно. Таким образом, номер поколения события 1412 равен пяти (т. е. четыре плюс один).
«Приращение раунда» («Round Increment», или «RI»): атрибут события, который может равняться либо нулю, либо единице.
«Номер раунда» («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, или любой другой подходящий номер.
«Ответвление» («Forking»): событие X вместе с событием Y являются ответвлением, если они определены и/или созданы одним участником, и ни одно из них не является собственным предком другого. Например, как показано на фиг. 9, участник Дэйв создает ответвление, создавая и/или определяя события 1503 и 1504, оба из которых имеют одного собственного родителя (т. е. событие 1501), так что событие 1503 не является собственным предком события 1504, и событие 1504 не является собственным предком события 1503.
«Идентификация» («Identification») ответвления: ответвление может быть «идентифицировано» третьим событием, созданным и/или определенным после двух событий, которые вместе являются ответвлениями, если оба эти два события являются предками третьего события. Например, как показано на фиг. 9, участник Дэйв создает ответвление, создавая события 1503 и 1504, ни одно из которых не является собственным предком другого. Это ответвление может быть идентифицировано более поздним событием 1506, поскольку оба события 1503 и 1504 являются предками события 1506. В некоторых случаях идентификация ответвления может указывать на то, что конкретный участник (например, Дэйв) мошенничает.
«Идентификация» («Identification») события: событие X «идентифицирует» или «видит» событие-предка Y, если X не имеет события-предка Z, которое является ответвлением вместе с Y. Например, как показано на фиг. 8, событие 1412 идентифицирует (то есть «видит») событие 1403, поскольку событие 1403 является предком события 1412, и событие 1412 не имеет событий-предков, которые являются ответвлениями вместе с событием 1403. В некоторых случаях событие X может идентифицировать событие Y, если X не идентифицирует ответвление до события Y. В таких случаях, даже если событие X идентифицирует ответвление, создаваемое участником, определяющим событие Y, после события Y, событие X может видеть событие Y. Событие X не идентифицирует события этого участника после ответвления. Более того, если участник определяет два разных события, которые оба являются первыми событиями этого участника в истории, событие X может идентифицировать ответвление и не идентифицировать никакое событие этого участника.
«Строгая идентификация» («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.
«Первое событие раунда R» (также называемое в настоящем документе «свидетелем», или «witness»): событие представляет собой «первое событие раунда R» (или «свидетеля»), если событие (1) имеет номер раунда R и (2) имеет собственного родителя, имеющего номер раунда, который меньше R, или не имеет собственного родителя. Например, как показано на фиг. 8, событие 1412 представляет собой «первое событие раунда 2», поскольку оно имеет номер раунда, равный двум, и его собственным родителем является событие 1408, которое имеет номер раунда, равный одному (т. е. меньше двух).
В некоторых случаях приращение раунда для события 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.
В некоторых случаях следующий способ может быть использован для определения того, может ли событие 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.
Еще один вариант реализации способа определения с помощью 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 или более битов.
«Известное» («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 известным. Подобный процесс повторяется для других первых событий.
Протокол византийского соглашения может собирать и использовать голоса и/или решения «первых событий раунда R» для идентификации «известных» событий. Например, «первое событие Y раунда R+1» будет голосовать «ДА», если Y может «идентифицировать» событие X, в ином случае оно проголосует «НЕТ». Голоса затем подсчитываются для каждого раунда G, для G = R+2, R+3, R+4 и т. д. до тех пор, пока не будет принято решение любым участником. Голоса подсчитываются для каждого раунда G до тех пор, пока не принято решение. Некоторые из этих раундов могут представлять собой «мажоритарные» раунды, тогда как некоторые из других раундов могут представлять собой раунды «с подбрасыванием монеты». В некоторых случаях, например, раунд R+2 является мажоритарным раундом, и будущие раунды определяются либо как мажоритарный раунд, либо как раунд с подбрасыванием монеты (например, согласно предварительно определенной схеме). Например, в некоторых случаях произвольно может быть определено, является ли будущий раунд мажоритарным раундом или раундом с подбрасыванием монеты, при условии что не может быть двух последовательных раундов с подбрасыванием монеты. Например, может быть предварительно определено, что будет пять мажоритарных раундов, затем один раунд с подбрасыванием монеты, затем пять мажоритарных раундов, затем один раунд с подбрасыванием монеты, с повторением до тех пор, пока не будет достигнуто согласие.
В некоторых случаях, если раунд G является мажоритарным раундом, голоса могут быть подсчитаны следующим образом. Если существует событие раунда G, которое строго идентифицирует по меньшей мере M первых событий раунда G-1, голосующих V (где V представляет собой либо «ДА», либо «НЕТ»), то согласованным решением является V, и протокол византийского соглашения завершается. В ином случае каждое первое событие раунда G вычисляет новый голос, представляющий собой решение большинства первых событий раунда G-1, которые каждое первое событие раунда G может строго идентифицировать. В случаях равенства голосов и отсутствия большинства решение может быть обозначено как «ДА».
Подобным образом, если X является свидетелем раунда R (или первым событием раунда R), то результаты голосования в раундах R+1, R+2 и так далее могут быть вычислены, при этом свидетели в каждом раунде голосуют относительно того, является ли X известным. В раунде R+1 каждый свидетель, который может видеть X, голосует ДА, а другие свидетели голосуют НЕТ. В раунде R+2 каждый свидетель голосует согласно большинству голосов свидетелей раунда R+1, которые он может строго видеть. Подобным образом, в раунде R+3 каждый свидетель голосует согласно большинству голосов свидетеля раунда R+2, которого он может строго видеть. Это может продолжаться несколько раундов. В случае равенства голосов голос может быть установлен в ДА. В других случаях равенство голосов может быть установлено в НЕТ или может быть установлено случайным образом. Если какой-либо раунд имеет по меньшей мере M свидетелей, голосующих НЕТ, то выборы завершаются, и X не является известным. Если какой-либо раунд имеет по меньшей мере M свидетелей, голосующих ДА, то выборы завершаются, и X является известным. Если ни ДА, ни НЕТ не имеет по меньшей мере M голосов, выборы переходят к следующему раунду.
В качестве примера, на фиг. 8 предполагается первое событие X некоторого раунда, которое находится ниже показанной фигуры. Тогда каждое первое событие раунда 1 будет иметь голос относительно того, является ли X известным. Событие 1412 может строго идентифицировать первые события 1401, 1402 и 1408 раунда 1. Таким образом, его голос будет основан на их голосах. Если это мажоритарный раунд, то 1412 будет проверять, имеют ли по меньшей мере M событий {1401, 1402, 1408} голос ДА. Если имеют, то решением является ДА, и согласие было достигнуто. Если по меньшей мере M из них голосует НЕТ, то решением является НЕТ, и согласие было достигнуто. Если количество голосов не составляет по меньшей мере M в любую из сторон, то 1412 получает голос, который представляет собой большинство голосов событий 1401, 1402 и 1408 (и разрушает равенство голосов посредством голосования ДА, если было равенство голосов). Этот голос затем будет использован в следующем раунде, продолжающемся до тех пор, пока не будет достигнуто согласие.
В некоторых случаях, если раунд G является раундом с подбрасыванием монеты, голоса могут быть подсчитаны следующим образом. Если событие X может идентифицировать по меньшей мере M первых событий раунда G-1, голосующих V (где V представляет собой либо «ДА», либо «НЕТ»), то событие X изменит свой голос на V. Иначе, если раунд G является раундом с подбрасыванием монеты, то каждое первое событие X раунда G меняет свой голос на результат псевдослучайного определения (подобно подбрасыванию монеты в некоторых случаях), который определяется как самый младший бит подписи события X.
Подобным образом, в таких случаях, если выборы достигают раунда 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, и таким образом можно повысить безопасность событий и протокола консенсуса.
Например, как показано на фиг. 8, если раунд 2 является раундом с подбрасыванием монеты, и происходит голосование относительно того, было ли некоторое событие до раунда 1 известным, то событие 1412 будет сначала проверять, проголосовало ли по меньшей мере M событий {1401, 1402, 1408} ДА, или по меньшей мере M из них проголосовало НЕТ. Если это так, то 1412 проголосует так же. Если отсутствует по меньшей мере M голосов в любую из сторон, то 1412 будет иметь случайный или псевдослучайный голос (например, на основе самого младшего бита цифровой подписи, которую Эд создал для события 1412, когда он подписал его во время его создания и/или определения).
В некоторых случаях результат псевдослучайного определения может быть результатом криптографического протокола shared coin, который может быть, например, реализован как самый младший бит пороговой подписи номера раунда.
Система может быть основана на любом из способов вычисления результата псевдослучайного определения, описанных выше. В некоторых случаях система выполняет цикл по разным способам в некотором порядке. В других случаях система может выбирать среди разных способов согласно предварительно определенной схеме.
«Принятый раунд» («Received round»): событие X имеет «принятый раунд» R, если R является таким минимальным целым числом, что по меньшей мере половина известных первых событий раунда R (или известных свидетелей) с номером раунда R являются потомками X и/или могут видеть X. В других случаях может быть использована любая другая подходящая процентная доля. Например, в другом случае событие X имеет «принятый раунд» R, если R является таким минимальным целым числом, что по меньшей мере предопределенная процентная доля (например, 40 %, 60 %, 80 % и т. д.) известных первых событий раунда R (или известных свидетелей) с номером раунда R являются потомками X и/или могут видеть X.
В некоторых случаях «принятое поколение» события X может быть вычислено следующим образом. Находят, какой участник создал и/или определил каждое первое событие раунда R, которое может идентифицировать событие X. Затем определяют номер поколения для самого раннего события этого участника, которое может идентифицировать X. Затем определяют «принятое поколение» X как медиану этого списка.
В некоторых случаях «принятая метка времени» T события X может быть медианой меток времени в событиях, которые включают первое событие каждого участника, которое идентифицирует и/или видит X. Например, принятая метка времени события 1401 может быть медианой значения меток времени для событий 1402, 1403, 1403 и 1408. В некоторых случаях метка времени для события 1401 может быть включена в вычисление медианы. В других случаях принятая метка времени для X может быть любым другим значением или комбинацией значений меток времени в событиях, которые являются первыми событиями каждого участника для идентификации или видения X. Например, принятая метка времени для X может быть основана на среднем значении меток времени, среднеквадратичном отклонении меток времени, модифицированном среднем значении (например, путем удаления из вычисления самой ранней и самой поздней меток времени) и/или т.п. В еще других случаях может быть использована расширенная медиана.
В некоторых случаях общий порядок и/или порядок консенсуса для событий вычисляется посредством сортировки событий по их принятому раунду, с разрушением равенств по их принятой метке времени и разрушением этих равенств по их подписям. В других случаях общий порядок для событий может быть вычислен посредством сортировки событий по их принятому раунду, с разрушением равенств по их принятому поколению и разрушением этих равенств по их подписям. В вышеизложенных абзацах определены функции, используемые для вычисления и/или определения принятого раунда, принятой метки времени и/или принятого поколения события.
В других случаях вместо использования подписи каждого события может быть использована подпись этого события, подвергнутая операции исключающего ИЛИ с подписями известных событий или известных свидетелей с тем же принятым раундом и/или принятым поколением в этом раунде. В других случаях любая другая подходящая комбинация подписей событий может быть использована для разрушения равенств, чтобы определять порядок консенсуса событий.
В еще других случаях вместо определения «принятого поколения» как медианы списка «принятое поколение» может быть определено как сам список. Тогда при сортировке по принятому поколению два принятых поколения могут быть сравнены по средним элементам их списков, с разрушением равенств по элементу непосредственно перед серединой, с разрушением этих равенств по элементу непосредственно после середины и с продолжением чередования между элементом перед используемым до этого и элементом после, пока равенство не будет разрушено.
В некоторых случаях медианная метка времени может быть заменена «расширенной медианой». В таких случаях список меток времени может быть определен для каждого события, вместо одной принятой метки времени. Список меток времени для события X может включать первое событие каждого участника, которое идентифицирует и/или видит X. Например, как показано на фиг. 8, список меток времени для события 1401 может включать метки времени для событий 1402, 1403, 1403 и 1408. В некоторых случаях также может быть включена метка времени для события 1401. При разрушении равенства со списком меток времени (т. е. два события имеют один и тот же принятый раунд) могут быть сравнены средние метки времени списка каждого события (или предопределенные первая или вторая из двух средних меток времени, если длина четная). Если эти метки времени являются одинаковыми, могут быть сравнены метки времени непосредственно после средних меток времени. Если эти метки времени являются одинаковыми, могут быть сравнены метки времени непосредственно перед средними метками времени. Если эти метки времени также являются одинаковыми, сравнивают метки времени после трех уже сравненных меток времени. Это чередование может продолжаться до тех пор, пока равенство не будет разрушено. Подобно вышеизложенному обсуждению, если два списка идентичны, равенство может быть разрушено по подписям двух элементов.
В еще других случаях «усеченная расширенная медиана» может быть использована вместо «расширенной медианы». В таком случае весь список меток времени не сохраняют для каждого события. Вместо этого лишь несколько значений рядом с центром списка сохраняют и используют для сравнения.
Принятая медианная метка времени может быть потенциально использована для других целей в дополнение к вычислению общего порядка событий. Например, Боб мог подписать контракт, в котором говорится, что он берет на себя обязательства по соблюдению контракта, если и только если существует событие X, содержащее транзакцию, в которой Алиса подписывает этот же контракт, причем принятая метка времени для X соответствует определенному крайнему сроку или более раннему моменту времени. В этом случае Боб не возьмет на себя обязательства по соблюдению контракта, если Алиса подпишет его после крайнего срока, указанного «принятой медианной меткой времени», как описано выше.
В некоторых случаях состояние распределенной базы данных может быть определено после достижения консенсуса. Например, если S(R) является набором событий, который могут видеть известные свидетели в раунде R, в итоге все события в S(R) будут иметь известные принятый раунд и принятую метку времени. На этом этапе порядок консенсуса для событий в S(R) известен и меняться не будет. Когда этот этап достигнут, участник может вычислить и/или определить представление событий и их порядок. Например, участник может вычислить значение хеша событий в S(R) в их порядке консенсуса. Участник может затем подписать с помощью цифровой подписи значение хеша и включить значение хеша в следующее событие, которое определяет участник. Это может быть использовано для оповещения других участников о том, что этот участник определил, что события в S(R) имеют заданный порядок, который не будет меняться. После того как по меньшей мере M участников (или любое другое подходящее количество или процентная доля участников) подписали значение хеша для S(R) (и, таким образом, согласились с порядком, представленным значением хеша), этот список консенсуса событий вместе со списком подписей участников могут образовать один файл (или другую структуру данных), который может быть использован для доказательства того, что порядок консенсуса был таковым, как заявлено, для событий в S(R). В других случаях, если события содержат транзакции, которые обновляют состояние системы распределенной базы данных (как описано в настоящем документе), то значение хеша может представлять состояние системы распределенной базы данных после применения транзакций событий в S(R) в порядке консенсуса.
В некоторых случаях M (как описано выше) может быть основано на весовых значениях, присвоенных каждому участнику, нежели всего лишь на части, процентном отношении и/или значении количества всех участников. В таком случае каждый участник имеет долю, связанную с его заинтересованностью и/или влиянием в системе распределенной базы данных. Такая доля может представлять собой весовое значение. Можно сказать, что каждое событие, определенное этим участником, может иметь весовое значение его определяющего участника. Тогда M может быть частью от общей доли всех участников. События, описанные выше как зависимые от M, будут происходить, когда набор участников с суммарным количеством долей по меньшей мере M придет к согласию. Таким образом, на основе своей доли определенные участники могут иметь большее влияние на систему и на то, каким образом получается порядок консенсуса. В некоторых случаях транзакция в событии может менять долю одного или более участников, добавлять новых участников и/или удалять участников. Если такая транзакция имеет принятый раунд R, то после вычисления принятого раунда события после свидетелей раунда R будут повторно вычислять свои номера раундов и другую информацию с использованием модифицированных долей и модифицированного списка участников. Голоса относительно того, являются ли события раунда R известными, будут использовать старые доли и список участников, но голоса относительно раундов после R будут использовать новые доли и список участников. Дополнительные подробности относительно использования весовых значений для определения консенсуса описаны в заявке на патент США № 15/387048, поданной 21 декабря 2016 г., под названием «Methods And Apparatus For A Distributed Database With Consensus Determined Based On Weighted Stakes», которая включена в настоящий документ посредством ссылки во всей своей полноте.
На фиг. 2 модуль 211 конвергенции базы данных и модуль 212 связи показаны реализованными в процессоре 210. В других вариантах осуществления модуль 211 конвергенции базы данных и/или модуль 212 связи могут быть реализованы в памяти 220. В еще других вариантах осуществления модуль 211 конвергенции базы данных и/или модуль 212 связи могут быть основаны на аппаратном обеспечении (например, ASIC, FPGA и т. д.).
В некоторых случаях распределенная база данных (например, показанная и описанная в отношении фиг. 1) может позволять выполнять обработку «посреднических транзакций». В некоторых случаях такие посреднические транзакции могут быть совершены участником распределенной базы данных (например, вычислительным устройством, имеющим экземпляр по меньшей мере части распределенной базы данных) от имени лица, которое не является участником распределенной базы данных (например, вычислительного устройства, не имеющего экземпляр распределенной базы данных), участника распределенной базы данных с правами, не являющимися полными (например, имеющего права чтения, но не права записи, не оказывающего влияние на согласованные решения и т. д.), и/или т.п. Например, предположим, что Алиса желает подать транзакцию TR в распределенную базу данных, но она не является полноправным участником распределенной базы данных (например, Алиса не является участником или имеет ограниченные права). Предположим, что Боб является полноправным участником и имеет полные права в распределенной базе данных. В этом случае Алиса может отправлять транзакцию TR Бобу, и Боб может подавать TR в сеть с целью оказания влияния на распределенную базу данных. В некоторых случаях Алиса может подписывать TR с помощью цифровой подписи. В некоторых случаях TR может содержать, например, платеж Бобу (например, комиссию за его услугу подачи TR в распределенную базу данных). В некоторых случаях Алиса может передавать TR Бобу посредством анонимизирующей сети, такой как сеть луковой маршрутизации TOR, чтобы ни Боб, ни другие наблюдатели не могли определить, что TR поступило от Алисы.
В некоторых случаях распределенная база данных (например, показанная и описанная в отношении фиг. 1) может быть использована для реализации криптовалюты. В таком случае каждый экземпляр 114, 124, 134, 144 распределенной базы данных может определять одну или более структур данных кошелька (также называемых в настоящем документе кошельками) для хранения криптовалюты. Структура данных кошелька может содержать пару ключей (открытый ключ и закрытый ключ). В некоторых случаях пара ключей для кошелька может быть сгенерирована вычислительным устройством, на котором создают этот кошелек. Например, если Алиса определяет кошелек (W, K), при этом W является открытым ключом (который также может служить идентификатором для кошелька), и K является закрытым ключом, она может опубликовать W (например, в событии) в остальных экземплярах распределенной базы данных, сохранив при этом свой идентификатор анонимным, чтобы другие экземпляры распределенной базы данных (или их пользователи) не могли идентифицировать, что кошелек W связан с Алисой. Однако в некоторых случаях переводы криптовалюты являются открытыми. Таким образом, если ее работодатель переводит деньги на W (например, с использованием транзакции в событии), и затем Алиса совершает покупку путем перевода денег с W в магазин (например, с использованием отличной транзакции в отличном событии), то работодатель и магазин могут договориться с целью определения того, что W принадлежит Алисе, и что покупка была совершена именно Алисой. Таким образом, во избежание этого для Алисы может быть полезным переводить деньги на новый анонимный кошелек для сохранения анонимности своих транзакций.
В некоторых реализациях операция WALLET_ADD может быть использована для сохранения пары (W, D) в распределенной базе данных, а WALLET_DEL может быть использована для удаления кошелька. В некоторых случаях пользователь может добавлять кошелек в распределенную базу данных путем уплаты комиссии, и такой кошелек может оставаться активным в распределенной базе данных в течение периода времени, покрываемого уплаченной комиссией. Параметр W в паре (W, D) соответствует открытому ключу кошелька, и параметр D является структурой данных, которая может включать список открытых ключей, каждый из которых соответствует закрытому ключу, при этом любой из таких закрытых ключей может быть использован, например, для подписания операции WALLET_DEL. В других случаях любой достаточно большой набор таких закрытых ключей может быть использован для подписания операции WALLET_DEL. Например, в таких случаях количество таких закрытых ключей, подписывающих WALLET_DEL, должно быть выше предопределенного порогового значения.
В других реализациях WALLET_ADD (W, D) может представлять собой операцию или функцию для добавления и/или привязки цифрового сертификата к открытому ключу W. Цифровой сертификат представляет собой электронные учетные данные, которые привязывают пользователя, компьютер или идентификатор услуги к открытому ключу путем предоставления информации о предмете сертификата и приложениях и услугах, которые могут использовать сертификат. Таким образом, в некоторых случаях структура D данных может содержать сертификат открытого ключа (например, сертификат X.509) для W и список открытых ключей, которым разрешено выполнять отвязку сертификата от открытого ключа W. Открытые ключи в таком списке могут содержать как W, так и ключи в цепочке сертификата открытого ключа.
Участник, например, Алиса, может создавать и/или определять новый кошелек посредством операции WALLET_ADD (W, D). Такой кошелек содержит открытый ключ W. По умолчанию вновь созданный кошелек является анонимным, так как в кошельке нет ничего, что привязывает кошелек к участнику Алисе (т. е. вычислительному устройству, представленному как Алиса). Распределенная база данных также позволяет участникам создавать неанонимные кошельки, например, для предотвращения операций по отмыванию денег, предотвращения уклонения от уплаты налогов, соблюдения принципов «знай своего клиента» (KYC) или других подходящих политик и практик. Таким образом, Алиса и другие участники распределенной базы данных могут: (1) использовать доверенный центр сертификации (CA) для подтверждения идентификатора участника (например, идентификатора Алисы) и получения сертификата (например, сертификата X.509), привязывающего участника к кошельку W, и/или (2) использовать доверенный центр депонирования идентификатора (IEA) для подтверждения идентификатора участника (например, Алисы), выполнять слепую подпись файла депонирования идентификатора (IEF), созданного таким участником, и получать сертификат (например, сертификат X.059) для ключа подписи IEA.
В некоторых случаях участники распределенной базы данных могут прикреплять, например, сертификат D, созданный CA или IEF, к кошельку, используя операцию WALLET_ADD (A, D), и в конечном итоге удалять такой сертификат, используя операцию WALLET_DEL (A, D). В таком случае цепочка сертификата может продолжаться до CA или IEA, которые выдали сертификат, и/или может дальше продолжаться до организации, одобряющей CA или IEA, которые предполагается использовать в распределенной базе данных, например, до правительственного органа или другого подходящего учреждения.
В некоторых случаях, когда транзакции, совершенные посредством распределенной базы данных, должны соблюдать принципы или политики KYC, транзакции между кошельками, банковскими счетами и/или частными продавцами товаров и услуг могут быть совершены после верификации сертификата, выданного посредством CA. В таком случае цепочка сертификата может продолжаться до органа (например, правительственного органа), который одобрил CA. Таким образом, такие транзакции могут отслеживаться органом. В некоторых случаях пользователь может привязывать сертификат к кошельку путем уплаты комиссии, и такой кошелек может оставаться активным в распределенной базе данных в течение периода времени, покрываемого уплаченной комиссией.
В некоторых случаях транзакции, совершенные посредством распределенной базы данных, могут соблюдать принципы KYC и законы о конфиденциальности или соответствующие политики. В таких случаях, например, транзакции между частными продавцами товаров и услуг могут совершаться после верификации сертификата, выданного посредством IEA. В таком случае цепочка сертификата может продолжаться до органа, который одобрил IEA. Например, IEF может содержать W и имя и адрес пользователя, зашифрованные с помощью открытого ключа, принадлежащего органу, который одобрил IEA. Таким образом, такой орган может расшифровывать поля, соответствующие W и имени и адресу пользователя, и идентифицировать владельца кошелька. Однако идентификатор пользователя не доступен другим участникам и/или пользователям распределенной базы данных или другим органам.
В некоторых случаях, например, участник может создавать и/или определять некоторое количество случайных кошельков (например, 100 случайных кошельков) и отправлять слепые версии их соответствующих файлов депонирования идентификатора (например, 100 файлов) в IEA, а затем отправлять информацию в IEA, чтобы раскрывать и расшифровывать поднабор этих файлов (например, 99 файлов), выбираемых в случайном порядке IEA. Такой участник может не принимать во внимание 99 кошельков, связанных с 99 файлами, и принимать от IEA слепую подпись для оставшегося файла депонирования идентификатора. Участник может затем раскрывать оставшийся файл депонирования идентификатора и прикреплять его к оставшемуся кошельку. Таким образом, IEA может подтвердить, что такой участник прикрепляет депонированный идентификатор к оставшемуся кошельку. Таким образом, участник может иметь конфиденциальность от IEA, и только орган, одобривший IEA, может иметь доступ к депонированной информации.
В некоторых случаях, когда, например, страна или другое учреждение имеет законодательную базу относительно конфиденциальности, система может быть еще больше усовершенствована таким образом, что вместо того, чтобы иметь один ключ для расшифровки файлов депонирования идентификатора, правительство или другое учреждение могут иметь несколько органов, которые взаимодействуют для расшифровки идентификатора участника (например, каждый орган и/или учреждение имеет часть ключа, которую объединяют с другими частями ключа для расшифровки файла депонирования идентификатора). Соответственно, между несколькими органами может быть заключено соглашение или могут выполняться совместные операции для раскрытия идентификатора участника. Таким образом, распределенная база данных служит инструментом, который может в равной степени обеспечивать сбалансированный компромисс между конфиденциальностью участников или пользователей распределенной базы данных и прозрачностью транзакций, совершенных посредством распределенной базы данных. Более того, разделение одного ключа для расшифровки файлов депонирования идентификатора улучшает безопасность и конфиденциальность вычислительных устройств, реализующих распределенную базу данных.
В нижеприведенном примере исходят из того, что C монет криптовалюты переводят с кошелька W на кошелек R, если опубликована следующая транзакция (например, в событии), где _K на конце означает, что транзакция подписана с помощью цифровой подписи с помощью закрытого ключа K. Может быть использована следующая форма записи:
TRANSFER(C, W, R)_K
В некоторых случаях для достижения анонимности в переводе криптовалюты могут быть определены новый тип транзакции и/или функция распределенной базы данных. Например, следующие транзакции будут выполнять перевод 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
В некоторых случаях эти транзакции не оказывают влияния, пока не будут опубликованы и распределены по другим экземплярам распределенной базы данных две идентичные копии (например, в одном или более событиях), одна подписывается K1 (с использованием закрытого ключа, связанного с открытым ключом W1), и другая подписывается K2 (с использованием закрытого ключа, связанного с открытым ключом W2). В некоторых случаях каждая транзакция может также содержать защищенную метку времени, как описано выше. Эта защищенная метка времени может быть защищенной меткой времени события, с которым связана транзакция, или отдельной защищенной меткой времени транзакции. Если обе транзакции опубликованы с метками времени в течение T секунд друг за другом (например, защищенная метка времени транзакций в пределах предопределенного периода времени друг за другом), то произойдут оба перевода валюты. В противном случае не происходит ни один из переводов.
В других случаях T не используют, и перевод валюты происходит только в том случае, если обе транзакции произойдут до того, как любая из сторон внесет транзакцию, отменяющую перевод. Например, Алиса может опубликовать свою подписанную транзакцию (например, свою транзакцию TRANSFER_DOUBLE), затем опубликовать другую подписанную транзакцию, содержащую сообщение об отмене в отношении этой первой транзакции, затем Боб публикует свою подписанную транзакцию. Перевод не произойдет, если транзакция Боба была позже, чем сообщение Алисы об отмене, но перевод произойдет, если транзакция Боба была раньше, чем сообщение Алисы об отмене. Таким способом система может работать без T и без меток времени, используя упорядоченную последовательность консенсуса транзакций. В других случаях могут поддерживаться как T, так и сообщения об отмене.
Нижеприведенный пример иллюстрирует, как транзакция типа «TRANSFER_DOUBLE» и/или функция распределенной базы данных могут быть использованы для того, чтобы анонимно и защищенным образом начать передачу данных (таких как валюта). В нижеприведенном примере Алиса имеет кошелек W1, на который ее работодатель перевел деньги. Она желает перевести C монет с W1 на анонимный кошелек W2, который она создает, который позже будет использован для покупок. Но она желает иметь защищенную анонимность, чтобы никто из просматривающих транзакции не узнал, что W1 связан с анонимным кошельком W2. Он должен быть защищенным, даже если ее работодатель сотрудничает с магазином с целью совершения атаки на анонимность. В дополнение к этому, например, Боб желает такой же защищенной анонимности при переводе монет со своего кошелька W3 на анонимный кошелек W4, который он создает.
Алиса и Боб могут достичь формы анонимности путем выполнения следующего протокола. Он может включать любую форму осуществления связи друг с другом, такую как непосредственная электронная переписка друг с другом, отправка сообщений друг другу через сайт для обмена текстовыми сообщениями или через сайт онлайн-форума или посредством транзакций, опубликованных в том же самом открытом реестре, на котором размещена криптовалюта (например, в событиях). Нижеприведенный пример исходит из того, что протокол выполняют через открытый реестр. Предположим, что Алиса и Боб вначале являются незнакомцами, но оба обладают способностью публиковать транзакции на открытом реестре и могут читать транзакции, которые другие публикуют на открытом реестре. Алиса и Боб могут публиковать следующие транзакции на открытом реестре (например, в одном или более событиях):
Алиса публикует: 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
В этом примере Алиса желает перевести C монет с кошелька W1 на W2, и Боб желает перевести C монет с кошелька W3 на W4. Каждый из Алисы и Боба генерирует свои собственные кошельки путем генерирования пары ключей (открытый ключ, закрытый ключ) для каждого кошелька. Здесь открытый ключ для кошелька также используют в качестве названия кошелька (в других случаях для идентификации кошелька может быть использован отдельный идентификатор). Алиса и Боб желают выполнить эти переводы таким способом, чтобы наблюдатели могли идентифицировать, что владелец кошелька W1 также является владельцем либо W2, либо W4, но не могли идентифицировать, какого именно. Подобным образом, Алиса и Боб желают выполнить эти переводы таким способом, чтобы наблюдатели могли идентифицировать, что владелец кошелька W3 также является владельцем либо W2, либо W4, но не могли идентифицировать, какого именно. Кошелек с открытым ключом W1 имеет закрытый ключ K1. Подобным образом, кошельки W2, W3 и W4 имеют закрытые ключи K2, K3 и K4 соответственно. Каждую транзакцию или инструкцию выше подписывают с помощью закрытого ключа, указанного в конце. Например, первоначальные транзакцию или инструкцию подписывают с помощью цифровой подписи с помощью закрытого ключа K1.
Первую транзакцию (Anonymize1(N, C, W1)_K1) используют для анонсирования о том, что Алиса желает перевести C монет с W1 на анонимный кошелек. Эта транзакция содержит номер N идентификатора, который может представлять собой хеш транзакции, случайное число, содержащееся в транзакции, и/или любой другой подходящий идентификатор. Этот N (например, идентификатор преобразования и/или идентификатор процесса) может быть использован в последующих транзакциях для обратного обращения к транзакции, которая начала процесс, во избежание путаницы (и для обеспечения возможности идентифицировать процесс или преобразование), если имеются несколько подобных процессов и/или преобразований, происходящих в одно и то же время. В некоторых случаях N может содержать крайний срок времени ожидания (например, T), после которого транзакции, включающие N, игнорируют. Эту транзакцию подписывают с помощью цифровой подписи с помощью K1.
Функция encrypt(W4, W1) зашифровывает W4 (открытый ключ кошелька, принадлежащего Бобу и определяемого им в качестве его целевого анонимного кошелька) с использованием открытого ключа W1, что дает результат B, который может быть расшифрован только с помощью соответствующего закрытого ключа K1 (удерживаемого Алисой). Это обеспечивает то, что ни один из других экземпляров распределенной базы данных, просматривающих транзакцию, не сможет идентифицировать W4, за исключением владельца W1 (в этом примере Алисы).
Транзакция Anonymize2(N, W3, B)_K3 указывает на то, что в качестве части процесса или преобразования N, Боб желает выполнить перевод C монет с W3 на анонимный кошелек, идентифицируемый посредством B. Эту транзакцию подписывают с помощью цифровой подписи с использованием закрытого ключа K3. Алиса может затем расшифровать B с использованием закрытого ключа K1 для идентификации целевого анонимного кошелька Боба как W4.
Алиса может выполнить функцию encrypt(W2, W3). Это зашифровывает W2 (открытый ключ кошелька, принадлежащего Алисе и определяемого ею в качестве ее целевого анонимного кошелька) с помощью открытого ключа W3 (первоначальный кошелек Боба). Алиса может затем опубликовать транзакцию Anonymize3(N, A)_K1. Боб может идентифицировать W2 как целевой анонимный кошелек Алисы путем расшифровки A с помощью закрытого ключа K3.
Функция min(W2, W4) возвращает тот из двух открытых ключей W3 и W4, который является первым лексикографически (в алфавитном порядке). Функция max(W2, W4) возвращает тот из двух открытых ключей W3 и W4, который является последним лексикографически (в алфавитном порядке). Таким образом, MIN может быть либо W2, либо W4, и MAX может быть либо W2, либо W4. Функции min и max позволяют упорядочивать кошельки W2 и W4, оба из которых могут идентифицировать Алиса и Боб, но которые не могут идентифицировать другие. В других случаях любая другая детерминистская функция может быть использована для идентификации в отношении Алисы и Боба, каким образом упорядочивать анонимные кошельки W2 и W4, например, в виде хеш-функции, ранжирования и/или т.п.
Транзакции 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.
В некоторых случаях транзакции могут представлять собой «посреднические транзакции», что означает, что узел в сети подает транзакции от имени другой стороны. В вышеприведенном примере Алиса является владельцем кошельков W1 и W2 и желает опубликовать несколько транзакций. Если Кэрол является участником распределенной базы данных, имеющим полные права, то Алиса может отправлять транзакции Кэрол для подачи в распределенную базу данных от имени Алисы. В некоторых случаях посредническая транзакция может включать разрешение на перевод небольшой комиссии с кошелька W1 Кэрол в качестве платежа за эту услугу. В некоторых случаях Алиса может осуществлять связь с Кэрол посредством сети, которая анонимизирует связь, такой как, например, сеть луковой маршрутизации TOR.
В некоторых случаях Алиса может затем повторить вышеописанный протокол анонимности с Дэйвом, и Боб может повторить протокол с Эдом. В тот момент другие экземпляры распределенной базы данных смогут идентифицировать, что Алиса является владельцем одного из 4 кошельков, но не узнают, какого именно. После 10 таких прогонов Алиса является владельцем одного кошелька из 210, что составляет 1024. После 20 прогонов набор составляет более миллиона. После 30 это составляет более миллиарда. После 40 это составляет более триллиона. Прогон протокола занимает долю секунды. Но даже если прогон каждого протокола занимает целую секунду, любой, кто предпримет попытку анонимизировать свой кошелек, будет в случайном порядке меняться местами с кем-то другим намного быстрее, чем за минута. Наблюдатели знают, что Алиса является владельцем одного из полученных в результате кошельков, но не знают, какого именно.
Эта система является менее безопасной, если лишь несколько человек пытаются анонимизировать свои кошельки. В качестве дополнительной меры безопасности Алиса может ждать определенный период времени (например, день, час, неделю и т. д.) и затем дальше анонимизировать свой конечный кошелек. Таким способом она может в конечном итоге скрываться среди толпы, которая включает другие экземпляры распределенной базы данных, которая пыталась анонимизироваться в течение очень длительного периода времени. Чем больше экземпляров распределенной базы данных, пользующихся системой, тем быстрее она может достичь своей цели.
Эта система потенциально может быть скомпрометирована, если злоумышленник сможет идентифицировать IP-адрес Алисы, когда она осуществляет связь с сетью, реализующей распределенную базу данных (например, сетью Интернет). Если злоумышленник идентифицирует, что Алиса запустила протокол с определенного IP-адреса, и затем немедленно видит, что кто-то запустил протокол на кошельке W2 с того же самого адреса, он может прийти к выводу, что Алиса является владельцем кошелька W2. В некоторых случаях IP-адреса могут быть анонимизированы. Например, для достижения анонимной связи может быть использована анонимная сеть связи (например, сеть Tor). Затем оставшиеся экземпляры распределенной базы данных могут идентифицировать, что W2 запустил протокол и подписал транзакции, но не смогут идентифицировать, использует ли W2 компьютер Алисы или компьютер Боба.
В некоторых юрисдикциях правительство может желать обеспечить через законодательство возможность мониторинга потоков валюты для предотвращения таких преступлений, как отмывание денег или уклонение от уплаты налогов, при этом позволяя гражданам быть анонимными от слежки (например, со стороны их соседей, преступников, правительств иностранных государств и т. д.). В некоторых случаях вышеописанные способ и система анонимности могут поддерживать такое законодательство. В таких случаях правительство может создать или одобрить определенный центр сертификации (CA) или несколько CA с целью создания и/или определения зашифрованных сертификатов, которые подтверждают, что кошелек связан с определенным человеком. Шифрование может быть таким, что только правительство может расшифровать его (возможно только по постановлению суда). Если Алиса создает и/или определяет кошелек, она по желанию может иметь такой сертификат, прикрепленный к кошельку, что означает, что ее соседи не могут видеть, что кошелек принадлежит Алисе, но правительство может расшифровать сертификат и идентифицировать Алису как владельца кошелька. Правительство может настоять на том, чтобы работодатели на территории своей страны могли только вносить деньги в кошельки, которые имеют такой сертификат, и чтобы магазины в этой стране принимали платежи с кошельков с таким сертификатом. Затем Алиса может выполнять вышеуказанный протокол многократно с целью создания и/или определения цепочки кошельков, и получать надлежащий сертификат для первого и последнего кошельков в цепочке.
Хоть выше и описано, что структура данных каждого кошелька имеет одну пару открытого-закрытого ключей, в других случаях структура данных кошелька может содержать две пары открытого-закрытого ключей: одну для подписания и одну для шифрования. В таком случае вышеописанные способы могут быть изменены для использования подписывающего ключа для подписания и ключа шифрования для шифрования.
Хоть выше и описано, что используют хешграф и хранят транзакции и осуществляют обмен ими в событиях, в других случаях для реализации вышеописанных способов с целью обеспечения защищенных и анонимных транзакций может использоваться любая другая подходящая технология распределенной базы данных и/или распределенного реестра. Например, в других случаях для реализации таких способов могут быть использованы такие технологии, как блокчейн, PAXOS, RAFT, Биткойн, Эфириум и/или т.п. В некоторых случаях защищенная метка времени может быть добавлена в эти технологии (например, надстроена на них) для реализации вышеописанных способов с целью обеспечения защищенных и анонимных транзакций. В других случаях, как описано выше, не используют никакой метки времени.
Хоть выше и описано, что осуществляется реализация между двумя различными экземплярами распределенной базы данных, в других случаях способ анонимизации может быть реализован более чем двумя экземплярами распределенной базы данных. Например, в других случаях транзакция «TRANSFER_DOUBLE» может поддерживать дополнительные количества транзакций. Например, транзакция TRANSFER_TRIPLE может быть определена с возможностью поддержки передачи данных между тремя различными структурами данных кошелька.
Хоть выше и описано, что реализуют криптовалюту, в других случаях могут быть анонимизированы транзакции в любом другом типе распределенной базы данных. Например, могут быть анонимизированы запись об обмене товарами, установление личности физического лица, разрешение на использование конкретного ресурса и/или т.п. В таких случаях это может повысить безопасность транзакции в распределенной базе данных.
На фиг. 3–6 проиллюстрированы примеры хешграфа согласно варианту осуществления. Имеется пять участников, каждый из которых представлен темной вертикальной линией. Каждый круг представляет событие. Две нисходящие линии от события представляют хеши двух предыдущих событий. Каждое событие в этом примере имеет две нисходящие линии (одну темную линию к тому же участнику и одну светлую линию к другому участнику), за исключением первого события каждого участника. Время течет вверх. На фиг. 3–6 вычислительные устройства распределенной базы данных обозначены как Алиса, Боб, Кэрол, Дэйв и Эд. Следует понимать, что такие обозначения относятся к вычислительным устройствам, которые конструктивно и функционально подобны вычислительным устройствам 110, 120, 130 и 140, показанным и описанным в отношении фиг. 1.
На фиг. 7 проиллюстрирована функциональная схема потока сигналов двух вычислительных устройств, синхронизирующих события, согласно варианту осуществления. В частности, в некоторых вариантах осуществления экземпляры 703 и 803 распределенной базы данных могут обмениваться событиями для достижения конвергенции. Вычислительное устройство 700 может выбирать синхронизацию с вычислительным устройством 800 случайным образом, на основе взаимосвязи с вычислительным устройством 700, на основе близости к вычислительному устройству 700, на основе упорядоченного списка, связанного с вычислительным устройством 700, и/или т.п. В некоторых вариантах осуществления, поскольку вычислительное устройство 800 может быть выбрано вычислительным устройством 700 из набора вычислительных устройств, относящихся к системе распределенной базы данных, вычислительное устройство 700 может выбирать вычислительное устройство 800 несколько раз подряд или может некоторое время не выбирать вычислительное устройство 800. В других вариантах осуществления указание о ранее выбранных вычислительных устройствах может быть сохранено на вычислительном устройстве 700. В таких вариантах осуществления вычислительное устройство 700 может находиться в ожидании, пока не будет осуществлено предопределенное количество выборов, перед тем, как получить возможность снова выбирать вычислительное устройство 800. Как поясняется выше, экземпляры 703 и 803 распределенной базы данных могут быть реализованы в памяти вычислительного устройства 700 и памяти вычислительного устройства 800 соответственно.
Вышеизложенные термины, определения и алгоритмы используются для иллюстрации вариантов осуществления и концепций, описанных в отношении фиг. 8–12. На фиг. 13A и фиг. 13B проиллюстрировано первое примерное применение способа и/или процесса достижения консенсуса, показанное в математической форме. На фиг. 14A и фиг. 14B проиллюстрировано второе примерное применение способа и/или процесса достижения консенсуса, показанное в математической форме.
Примерная система 1: если вычислительное устройство 700 называется Алиса, и вычислительное устройство 800 называется Боб, то синхронизация между ними может быть выполнена так, как проиллюстрировано на фиг. 7. Синхронизация между Алисой и Бобом может быть выполнена следующим образом:
- Алиса отправляет Бобу события, сохраненные в распределенной базе 703 данных.
- Боб создает и/или определяет новое событие, которое содержит:
-- хеш последнего события, которое создал и/или определил Боб;
-- хеш последнего события, которое создала и/или определила Алиса;
-- цифровую подпись вышеуказанного, поставленную Бобом.
- Боб отправляет Алисе события, сохраненные в распределенной базе 803 данных.
- Алиса создает и/или определяет новое событие.
- Алиса отправляет Бобу это событие.
- Алиса вычисляет общий порядок для событий как функцию хешграфа.
- Боб вычисляет общий порядок для событий как функцию хешграфа.
В любой заданный момент времени участник может сохранить принятые на данный момент события вместе с идентификатором, связанным с вычислительным устройством и/или экземпляром распределенной базы данных, которые создали и/или определили каждое событие. Каждое событие содержит хеши двух более ранних событий, за исключением первоначального события (которое не имеет родительских хешей) и первого события для каждого нового участника (которое имеет один хеш события-родителя, представляющий событие существующего участника, который пригласил их присоединиться). Для представления этого набора событий может быть нарисована схема. На ней могут быть показаны вертикальная линия для каждого участника и точка на этой линии для каждого события, созданного и/или определенного этим участником. Диагональная линия изображена между двумя точками в каждом случае, когда событие (расположенная выше точка) содержит хеш более раннего события (расположенная ниже точка). Можно сказать, что событие связано с другим событием, если это событие может ссылаться на другое событие посредством хеша этого события (либо непосредственно, либо через промежуточные события).
Например, на фиг. 3 проиллюстрирован пример хешграфа 600. Событие 602 создается и/или определяется Бобом в результате синхронизации с Кэрол и после нее. Событие 602 содержит хеш события 604 (предыдущего события, созданного и/или определенного Бобом) и хеш события 606 (предыдущего события, созданного и/или определенного Кэрол). В некоторых вариантах осуществления, например, хеш события 604, включенный в событие 602, содержит указатель на его непосредственные события-предки, события 608 и 610. По существу, Боб может использовать событие 602 для ссылки на события 608 и 610 и перестраивания хешграфа с использованием указателей на предыдущие события. В некоторых случаях можно сказать, что событие 602 связано с другими событиями в хешграфе 600, поскольку событие 602 может ссылаться на каждое из событий в хешграфе 600 посредством более ранних событий-предков. Например, событие 602 связано с событием 608 посредством события 604. В качестве другого примера, событие 602 связано с событием 616 посредством событий 606 и события 612.
Примерная система 2: система на основе примерной системы 1, при этом событие также содержит данные «полезной нагрузки» транзакций или другую информацию для записи. Такие данные полезной нагрузки могут быть использованы для обновления событий с помощью любых транзакций и/или информации, которые произошли и/или были определены начиная с непосредственного предыдущего события вычислительного устройства. Например, событие 602 может включать любые транзакции, выполненные Бобом, начиная с момента создания и/или определения события 604. Таким образом, во время синхронизации события 602 с другими вычислительными устройствами Боб может делиться этой информацией. Соответственно, транзакции, выполняемые Бобом, могут быть связаны с событием и предоставлены другим участникам с помощью событий.
Примерная система 3: система на основе примерной системы 1, при этом событие также включает текущие время и/или дату, полезные для отладки, диагностики и/или других целей. Время и/или дата могут быть локальными временем и/или датой, фиксирующими, когда вычислительное устройство (например, Боб) создает и/или определяет событие. В таких вариантах осуществления такие локальные время и/или дата не синхронизируются с остальными устройствами. В других вариантах осуществления время и/или дата могут быть синхронизированы на всех устройствах (например, при обмене событиями). В еще других вариантах осуществления для определения времени и/или даты может быть использован глобальный таймер.
Примерная система 4: система на основе примерной системы 1, в которой Алиса не отправляет Бобу ни события, созданные и/или определенные Бобом, ни события-предки такого события. Событие x является предком события y, если y содержит хеш x или y содержит хеш события, которое является предком x. Подобным образом, в таких вариантах осуществления Боб отправляет Алисе события, еще не сохраненные Алисой, и не отправляет события, уже сохраненные Алисой.
Например, на фиг. 4 проиллюстрирован примерный хешграф 620, иллюстрирующий события-предки (круги с точками) и события-потомки (круги с полосками) события 622 (черный круг). Линии устанавливают частичный порядок событий, в котором предки идут до события в виде черного круга, и потомки идут после события в виде черного круга. Частичный порядок не указывает, идут ли события в виде белых кругов до или после события в виде черного круга, так что для определения их последовательности используется общий порядок. В качестве другого примера, на фиг. 5 проиллюстрирован примерный хешграф, иллюстрирующий одно конкретное событие (закрашенный круг) и первый момент времени, в который каждый участник принимает указание этого события (круги с полосками). Когда Кэрол синхронизируется с Дэйвом для создания и/или определения события 624, Дэйв не отправляет Кэрол события-предки события 622, поскольку Кэрол уже осведомлена о таких событиях и приняла их. Вместо этого Дэйв отправляет Кэрол события, которые Кэрол все еще должна принять и/или сохранить в экземпляре распределенной базы данных Кэрол. В некоторых вариантах осуществления Дэйв может идентифицировать, какие события следует отправлять Кэрол, на основе того, что хешграф Дэйва показывает о том, какие события Кэрол приняла ранее. Событие 622 является предком события 626. Следовательно, на момент события 626 Дэйв уже принял событие 622. На фиг. 4 показано, что Дэйв принял событие 622 от Эда, который принял событие 622 от Боба, который принял событие 622 от Кэрол. Кроме того, на момент события 624 событие 622 является последним событием, принятым Дэйвом, которое было создано и/или определено Кэрол. Следовательно, Дэйв может отправлять Кэрол события, которые Дэйв сохранил, отличающиеся от события 622 и его предков. Дополнительно после приема события 626 от Дэйва Кэрол может перестраивать хешграф с помощью указателей в событиях, сохраненных в экземпляре распределенной базы данных Кэрол. В других вариантах осуществления Дэйв может идентифицировать, какие события следует отправлять Кэрол, на основе отправки Кэрол события 622 Дэйву (не показано на фиг. 4) и идентификации с использованием события 622 (и ссылок в нем) Дэйвом, чтобы идентифицировать события, которые Кэрол уже приняла.
Примерная система 5: система на основе примерной системы 1, в которой оба участника отправляют события друг другу в таком порядке, что событие отправляется только после того, как получатель примет и/или сохранит предков этого события. Соответственно, отправитель отправляет события от самых старых к самым новым, так что получатель может проверить два хеша в каждом событии при приеме события посредством сравнения двух хешей с двумя событиями-предками, которые уже были приняты. Отправитель может идентифицировать, какие события следует отправлять получателю, на основе текущего состояния хешграфа отправителя (например, переменной состояния базы данных, определенной отправителем), а какие, как указывает этот хешграф, получатель уже принял. Ссылаясь на фиг. 3, например, когда Боб синхронизируется с Кэрол для определения события 602, Кэрол может идентифицировать, что событие 619 является последним событием, созданным и/или определенным Бобом, которое приняла Кэрол. Следовательно, Кэрол может определить, что Бобу известно об этом событии и его предках. Таким образом, Кэрол может отправлять Бобу сначала событие 618 и событие 616 (т. е. самые старые события, которые Боб еще должен принять, которые Кэрол приняла). Кэрол может затем отправлять Бобу событие 612, а затем событие 606. Это позволяет Бобу легко связать события и перестроить хешграф Боба. Использование хешграфа Кэрол для идентификации того, какие события еще должен принять Боб, может повысить эффективность синхронизации и может уменьшить сетевой трафик, поскольку Боб не запрашивает события у Кэрол.
В других вариантах осуществления самое последнее событие может быть отправлено первым. Если получатель определяет (на основе хеша двух предыдущих событий в самом последнем событии и/или указателей на предыдущие события в самом последнем событии), что он еще не принял одно из двух предыдущих событий, получатель может запросить у отправителя отправку таких событий. Это может происходить до тех пор, пока получатель не примет и/или не сохранит предков самого последнего события. Ссылаясь на фиг. 3, в таких вариантах осуществления, например, когда Боб принимает событие 606 от Кэрол, Боб может идентифицировать хеш события 612 и события 614 в событии 606. Боб может определить, что событие 614 было ранее принято от Алисы при создании и/или определении события 604. Соответственно, Бобу не нужно запрашивать событие 614 у Кэрол. Боб может также определить, что событие 612 еще не было принято. Боб может затем запросить событие 612 у Кэрол. Боб может затем на основе хешей в событии 612 определить, что Боб не принял события 616 или 618, и может соответственно запросить эти события у Кэрол. На основе событий 616 и 618 Боб затем сможет определить, что он принял предков события 606.
Примерная система 6: система на основе примерной системы 5 с дополнительным ограничением, которое заключается в том, что, когда участник имеет выбор между несколькими событиями для отправки далее, событие выбирается таким образом, чтобы минимизировать общее количество отправленных на данный момент байтов, созданных и/или определенных этим участником. Например, если Алисе осталось отправить Бобу только два события, и одно из них имеет размер 100 байтов и было создано и/или определено Кэрол, а другое имеет размер 10 байтов и было создано и/или определено Дэйвом, и на данный момент в ходе этой синхронизации Алиса уже отправила 200 байтов событий Кэрол и 210 Дэйва, то Алисе следует сначала отправить событие Дэйву, а затем отправить событие Кэрол. Поскольку 210 + 10 < 100 + 200. Это может быть использовано для предотвращения атак, при которых один участник выдает либо одно огромное событие, либо поток мелких событий. В случае если трафик превышает ограничение по байтам большинства участников (как обсуждается в отношении примерной системы 7), способ согласно примерной системе 6 может обеспечивать, что игнорироваться будут события злоумышленника, а не события правомочных пользователей. Подобным образом, атаки могут быть ослаблены посредством отправки меньших событий перед большими событиями (для защиты от одного огромного события, забивающего канал связи). Более того, если участник не может отправить каждое из событий за одну синхронизацию (например, из-за ограничения сети, ограничений по байтам участника и т. д.), то этот участник может отправить несколько событий от каждого участника, вместо того, чтобы просто отправить события, определенные и/или созданные злоумышленником, и ни одного (из нескольких) события, созданного и/или определенного другими участниками.
Примерная система 7: система на основе примерной системы 1 с дополнительным первым этапом, на котором Боб отправляет Алисе число, указывающее максимальное количество байтов, которое он желает принять во время этой синхронизации, и Алиса отвечает сообщением со своим ограничением. Алиса затем прекращает отправку, если следующее событие превысило бы это ограничение. Боб делает то же самое. В таком варианте осуществления это ограничивает количество передаваемых байтов. Это может увеличить время конвергенции, но уменьшит объем сетевого трафика на синхронизацию.
Примерная система 8: система на основе примерной системы 1, в которой следующие этапы добавлены в начале процесса синхронизации:
- Алиса идентифицирует S, набор событий, которые она приняла и/или сохранила, пропуская события, которые были созданы и/или определены Бобом или которые являются предками событий, созданных и/или определенных Бобом.
- Алиса идентифицирует участников, которые создали и/или определили каждое событие в S, и отправляет Бобу список ID-номеров участников. Алиса также отправляет количество событий, которые были созданы и/или определены каждым участником, которые она уже приняла и/или сохранила.
- Боб отвечает списком того, сколько событий он принял, тех, которые были созданы и/или определены другими участниками.
- Алиса затем отправляет Бобу только события, которые он еще должен принять. Например, если Алиса указывает Бобу, что она приняла 100 событий, созданных и/или определенных Кэрол, и Боб отвечает, что он принял 95 событий, созданных и/или определенных Кэрол, то Алиса отправит только 5 самых последних событий, созданных и/или определенных Кэрол.
Примерная система 9: система на основе примерной системы 1 с дополнительным механизмом для идентификации и/или устранения мошенников. Каждое событие содержит два хеша, один от последнего события, созданного и/или определенного этим участником («собственный хеш»), и один от последнего события, созданного и/или определенного другим участником («чужой хеш»). Если участник создает и/или определяет два разных события с одним и тем же собственным хешем, то этот участник является «мошенником». Если Алиса устанавливает, что Дэйв является мошенником, посредством приема двух разных событий, созданных и/или определенных им с использованием одного и того же собственного хеша, то она сохраняет индикатор, указывающий на то, что он является мошенником, и избегает синхронизации с ним в будущем. Если она устанавливает, что он является мошенником, но все же синхронизируется с ним снова и создает и/или определяет новое событие, записывающее этот факт, то Алиса тоже становится мошенником, и другие участники, которые узнают, что Алиса впоследствии синхронизировалась с Дэйвом, перестают синхронизироваться с Алисой. В некоторых вариантах осуществления это влияет только на синхронизацию в одну сторону. Например, когда Алиса отправляет список идентификаторов и число событий, которые она приняла, для каждого участника, она не отправляет ID или количество для мошенника, так что Боб не ответит никаким соответствующим числом. Алиса затем отправляет Бобу события мошенника, которые она приняла и для которых она не приняла указание о том, что Боб принял такие события. После завершения этой синхронизации Боб также сможет определить, что Дэйв является мошенником (если он еще не идентифицировал Дэйва как мошенника), и Боб также откажется от синхронизации с мошенником.
Примерная система 10: система на основе примерной системы 9 с тем дополнением, что Алиса начинает процесс синхронизации путем отправки Бобу списка мошенников, которых она идентифицировала и события которых она все еще хранит, и Боб отвечает сообщением с указанием любых мошенников, которых он идентифицировал, в дополнение к мошенникам, идентифицированным Алисой. Затем они продолжают работу в обычном режиме, но без подсчета мошенников при синхронизации друг с другом.
Примерная система 11: система на основе примерной системы 1 с процессом, который постоянно обновляет текущее состояние (например, зафиксированное переменной состояния базы данных, определенной участником системы) на основе транзакций в любых новых событиях, которые принимаются во время синхронизации. Это также может включать второй процесс, который постоянно перестраивает это состояние (например, порядок событий) каждый раз, когда последовательность событий меняется, посредством возвращения к копии более раннего состояния и повторного вычисления настоящего состояния посредством обработки событий в новом порядке. В некоторых вариантах осуществления текущим состоянием является состояние, баланс, условие и/или т.п., связанные с результатом транзакций. Подобным образом, состояние может включать структуру данных и/или переменные, модифицированные транзакциями. Например, если транзакциями являются денежные переводы между банковскими счетами, то текущим состоянием может быть текущий баланс счетов. В качестве другого примера, если транзакции связаны с многопользовательской игрой, текущим состоянием может быть положение, количество жизней, полученные предметы, состояние игры и/или т.п., связанные с игрой.
Примерная система 12: система на основе примерной системы 11, ускоренная за счет использования arrayList с «быстрым клонированием» для поддержания состояния (например, баланса банковских счетов, состояния игры и т. д.). ArrayList с быстрым клонированием представляет собой структуру данных, которая действует как массив с одной дополнительной особенностью: она поддерживает операцию «клонирования», которая представляет собой создание и/или определение нового объекта, который является копией оригинала. Клон действует так, как если бы это была точная копия, поскольку изменения, которым подвергается клон, не влияют на оригинал. Однако операция клонирования быстрее, чем создание точной копии, поскольку создание клона в действительности не включает копирования и/или обновления всего содержимого одного arrayList в другой. Вместо наличия двух клонов и/или копий оригинального списка могут быть использованы два небольших объекта, каждый с хеш-таблицей и указателем на оригинальный список. Когда производится запись в клон, хеш-таблица запоминает, какой элемент модифицирован, и новое значение. Когда выполняется считывание из позиции, сначала проверяется хеш-таблица, и, если этот элемент был модифицирован, возвращается новое значение из хеш-таблицы. Иначе этот элемент возвращается из оригинального arrayList. Таким образом, два «клона» изначально являются лишь указателями на оригинальный arrayList. Но поскольку каждый из них постоянно модифицируется, они расширяются настолько, что имеют большую хеш-таблицу, в которой хранятся отличия между ними и оригинальным списком. Клоны сами могут быть клонированы, что вызывает расширение структуры данных до дерева объектов, каждый из которых имеет свои собственные хеш-таблицу и указатель на своего родителя. Следовательно, считывание вызывает подъем по дереву до тех пор, пока не будет установлена вершина, которая имеет запрашиваемые данные, или не будет достигнут корень. Если вершина становится слишком большой или сложной, то она может быть заменена на точную копию родителя, изменения в хеш-таблице могут быть переведены в копию, а хеш-таблица удалена. Кроме того, если клон больше не нужен, то во время сборки мусора он может быть удален из дерева, и дерево может быть свернуто.
Примерная система 13: система на основе примерной системы 11, ускоренная за счет использования хеш-таблицы с «быстрым клонированием» для поддержания состояния (например, баланса банковских счетов, состояния игры и т. д.). Она подобна системе 12, за тем исключением, что корень дерева представляет собой хеш-таблицу, а не arrayList.
Примерная система 14: система на основе примерной системы 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. Модификация строки эквивалентна удалению с последующей вставкой. Как и раньше, если несколько клонов удаляются во время сборки мусора, то дерево может быть упрощено. Структура этого дерева будет сохранена в дополнительной таблице, недоступной клонам, но которая полностью используется на внутреннем уровне.
Примерная система 15: система на основе примерной системы 11, ускоренная за счет использования файловой системы с «быстрым клонированием» для поддержания состояния. Она представляет собой объект, который действует как обертка вокруг файловой системы. Файловая система построена поверх существующей файловой системы с использованием реляционной базы данных с быстрым клонированием для управления разными версиями файловой системы. Основная файловая система хранит большое количество файлов либо в одном каталоге, либо раздельно согласно имени файла (для поддержания малого размера каталогов). Дерево каталогов может храниться в базе данных и не предоставляться базовой файловой системе. Когда файл или каталог клонируются, «клон» представляет собой лишь объект с ID-номером, и база данных модифицируется таким образом, чтобы отображать, что этот клон теперь существует. Если файловая система с быстрым клонированием клонируется, она представляется пользователю такой, как если бы был создан и/или определен целый новый жесткий диск, инициализированный с использованием копии существующего жесткого диска. Изменения, которым подвергается одна копия, могут не влиять на другие копии. В действительности существует только одна копия каждого файла или каталога, и копирование происходит, когда файл модифицируется посредством одного клона.
Примерная система 16: система на основе примерной системы 15, в которой отдельный файл создается и/или определяется в базовой операционной системе для каждой N-байтной части файла в файловой системе с быстрым клонированием. N может представлять собой некоторый подходящий размер, такой как, например, 4096 или 1024. Таким образом, если один байт изменяется в большом файле, копируется и модифицируется только один блок большого файла. Это также повышает эффективность при сохранении множества файлов на диске, которые отличаются лишь несколькими байтами.
Примерная система 17: система на основе примерной системы 11, где каждый участник включает в некоторые или во все событиях, которые он создает и/или определяет, хеш состояния на некоторый предыдущий момент времени вместе с количеством событий, которые произошли вплоть до этого момента, указывая на то, что участник распознает и/или идентифицирует, что теперь достигнут консенсус относительно порядка событий. После того как участник собрал подписанные события, содержащие такой хеш, от большинства пользователей для заданного состояния, участник может затем сохранить это как доказательство состояния консенсуса на тот момент и удалить из памяти события и транзакции до того момента.
Примерная система 18: система на основе примерной системы 1, где операции, которые вычисляют медиану или большинство, заменяются взвешенной медианой или взвешенным большинством, причем участников взвешивают согласно их «доле». Доля представляет собой число, которое указывает на то, как много значит голос участника. Доля может представлять собой активы в криптовалюте или просто произвольное число, которое присваивается, когда участника впервые приглашают присоединиться, а затем разделяется среди новых участников, которых участник приглашает присоединиться. Старые события могут быть удалены, когда достаточное количество участников согласится с состоянием консенсуса, так что их общая доля является большей частью имеющейся доли. Если общий порядок вычисляется с использованием медианы рангов, вносимых участниками, то результатом является число, при котором половина участников имеет более высокий ранг, а половина имеет более низкий. С другой стороны, если общий порядок вычисляется с использованием взвешенной медианы, то результатом является число, при котором приблизительно половина общей доли связана с рангами ниже этой, и половина выше. Взвешенные голосование и медианы могут быть полезны в предотвращении атаки Сивиллы, когда один участник приглашает присоединиться огромное количество «виртуальных» пользователей, каждый из которых является просто псевдонимом под управлением приглашающего участника. Если приглашающий участник вынужден делить свою долю с приглашенными, то виртуальные пользователи будут бесполезны для злоумышленника в попытках контролировать результаты консенсуса. Соответственно, доказательство доли владения может быть полезным в некоторых обстоятельствах.
Примерная система 19: система на основе примерной системы 1, в которой вместо одной распределенной базы данных имеется множество баз данных в иерархии. Например, может существовать одна база данных, пользователи которой являются ее участниками, а также несколько меньших баз данных или «блоков», каждый из которых имеет поднабор участников. Когда события происходят в блоке, они синхронизируются среди участников этого блока, но не среди участников вне этого блока. Затем периодически после принятия решения относительно порядка консенсуса в блоке полученное в результате состояние (или события со своим общим порядком консенсуса) может совместно использоваться всем составом участников большой базы данных.
Примерная система 20: система на основе примерной системы 11 с возможностью наличия события, которое обновляет программное обеспечение для обновления состояния (например, зафиксированного переменной состояния базы данных, определенной участником системы). Например, события X и Y могут содержать транзакции, которые модифицируют состояние согласно программному коду, который считывает транзакции в этих событиях, а затем обновляет состояние надлежащим образом. Тогда событие Z может содержать уведомление о том, что теперь доступна новая версия программного обеспечения. Если общий порядок говорит, что события происходят в порядке X, Z, Y, то состояние может быть обновлено посредством обработки транзакций в X с использованием старого программного обеспечения, а затем транзакций в Y с использованием нового программного обеспечения. Но если порядок консенсуса имел вид X, Y, Z, то как X, так и Y могут быть обновлены с использованием старого программного обеспечения, которое может дать другое конечное состояние. Следовательно, в таких вариантах осуществления уведомление об обновлении кода может появляться в событии, так что сообщество может достигать консенсуса относительно того, когда следует перейти со старой версии на новую версию. Это гарантирует, что участники будут поддерживать синхронизированные состояния. Это также гарантирует, что система может оставаться работающей даже во время обновлений без необходимости перезагрузки или перезапуска процесса.
Примерная система 21: предполагается, что системы, описанные выше, создают и/или обеспечивают эффективный механизм конвергенции для распределенного консенсуса с итоговым консенсусом. По этому поводу могут быть доказаны несколько теорем, как показано далее.
На фиг. 10 проиллюстрированы участник Алиса, имеющий первую запись в базе данных (например, кошелек 1002A) и вторую запись в базе данных (например, кошелек 1002B), и участник Боб, имеющий первую запись в базе данных (например, кошелек 1004A) и вторую запись в базе данных (например, кошелек 1004B). Как обсуждено выше, Алиса и Боб могут посредством вычислительного устройства создавать экземпляр новой записи в базе данных или определять ее путем внесения команды, такой как wallet(W, K), с парой открытого-закрытого ключей в качестве параметров (например, W является открытым ключом, находящимся в логической связи с новой записью, и K является закрытым ключом, находящимся в логической связи с новой записью). Распределенная база данных может отслеживать и/или вести запись значения, соответствующего сумме цифрового актива (например, криптовалюты), хранящегося, например, на первом кошельке 1002A Алисы и на первом кошельке 1004A Боба. В некоторых случаях участники или пользователи распределенной базы данных могут идентифицировать, что кошелек 1002A принадлежит Алисе, и что кошелек 1004A принадлежит Бобу. В таком случае Алиса может создавать экземпляр второго кошелька (например, кошелька 1002B) и/или определять его таким образом, что другие участники или пользователи распределенной базы данных не могут идентифицировать, что кошелек 1002B принадлежит Алисе. Другими словами, Алиса может определять анонимный кошелек 1002B или создавать его экземпляр, чтобы сделать транзакции, совершенные на кошелек 1002B, анонимными для других участников или пользователей распределенной базы данных. Аналогичным образом, Боб может создавать экземпляр анонимного кошелька 1004B и делать транзакции, совершенные на кошелек 1004B, анонимными.
Второй кошелек 1002B Алисы и второй кошелек 1004B Боба являются пустыми после создания экземпляра и еще не являются частью распределенной базы данных. Если Алиса вносит прямой перевод криптовалюты со своего первого кошелька 1002A на свой второй кошелек 1002B, такой прямой перевод будет видимым для других участников или пользователей распределенной базы данных. Аналогичным образом, прямые переводы криптовалюты с первого кошелька 1004A Боба на его второй кошелек 1004B будут видимыми для других участников или пользователей распределенной базы данных.
Преимущественно в некоторых случаях Алиса и Боб могут осуществлять анонимные переводы со своих первых кошельков на свои вторые кошельки, выполняя протокол передачи или последовательность операций, показанных на фиг. 10. Некоторые из операций, показанных на фиг. 10, были обсуждены выше (например, TRANSER_DOUBLE, описанная выше, функционально подобна TRANSFER2, показанной на фиг. 10). В таких случаях Алиса может отправлять запрос 1001 относительно свопинга Бобу. Запрос 1001 относительно свопинга может содержать открытый ключ A1 первого кошелька 1002A Алисы, значение C, указывающее сумму цифрового актива (например, криптовалюты), которое Алиса желает перевести на свой второй кошелек 1002B, идентификатор случайного числа N (например, для идентификации ряда находящихся в связи друг с другом транзакций, связанных с анонимным переводом) и метку T времени завершения. Запрос 1001 относительно свопинга может быть сделан Алисой посредством личного сообщения Бобу и/или путем внесения запроса относительно свопинга в открытый форум, открытый реестр, распределенную базу данных или посредством других подходящих средств связи. В некоторых случаях Алиса может подписывать запрос относительно свопинга с помощью закрытого ключа A1’, соответствующего ее первому кошельку 1002A, таким образом, Боб может подтверждать с использованием открытого ключа A1 Алисы, что, например, Алиса делает запрос относительно свопинга.
В некоторых случаях Боб может отвечать на запрос 1001 относительно свопинга ответом 1003 относительно свопинга. Ответ 1003 относительно свопинга может содержать открытый ключ B1 Боба, случайное число N (принятое при 1001) и открытый ключ B2 второго кошелька 1004B Боба, зашифрованный с помощью открытого ключа A1 первого кошелька Алисы. Соответственно, только Алиса может расшифровывать открытый ключ второго кошелька 1004B Боба, поскольку только Алиса имеет закрытый ключ A1’, который находится в паре с открытым ключом ее первого кошелька (т. е. A1). Аналогичным образом, Боб может подписывать ответ 1003 относительно свопинга с помощью закрытого ключа B1’, который находится в паре с открытым ключом его первого кошелька 1004A (т. е. B1). Боб может вносить или отправлять ответ 1003 относительно свопинга с использованием тех же самых средств связи, использованных Алисой для отправки запроса 1001 относительно свопинга, или на адрес, например, адрес универсального указателя ресурса, указанный Алисой. В некоторых случаях Алиса может также отправлять Бобу открытый ключ A2 второго кошелька 1002B Алисы, зашифрованный с помощью открытого ключа первого кошелька 1002A Боба, так что Боб может идентифицировать в закрытом порядке открытый ключ A2 второго кошелька 1002B Алисы.
Как только Алиса примет ответ 1003 относительно свопинга, она может внести команду 1005 передачи в распределенную базу данных, подписанную с помощью закрытого ключа A1’, соответствующего ее первому кошельку 1002A. Команда 1005 передачи может содержать открытый ключ A1 первого кошелька 1002A Алисы и открытый ключ B1 первого кошелька 1004A Боба, сумму или значение, представляющие C цифрового актива, которые должны быть переведены, случайное число N и метку T времени завершения. Как обсуждено выше, метка T времени указывает порог времени, обусловливающий игнорирование или аннулирование команды 1005 передачи в случае недостижения конвергенции в распределенной базе данных посредством протокола консенсуса до наступления T. Команда 1005 передачи приспособлена для идентификации или определения того, имеют ли первая запись или кошелек 1102A и вторая запись или кошелек 1104A по меньшей мере значение C цифрового актива. Значение C цифрового актива может представлять собой числовое значение, которое после исполнения команды 1005 передачи вычитают из исходных записей (например, кошелька 1002A или 1004A) и объединяют с целевыми записями (например, кошельком 1002B или 1004B). Команда 1005 передачи может также содержать открытый ключ A2 второго кошелька 1002B Алисы и открытый ключ B2 второго кошелька 1004B Боба.
Открытый ключ A2 второго кошелька 1002B Алисы и открытый ключ B2 второго кошелька 1004B Боба может каждый быть представлен в виде строки символов. Каждая строка символов может иметь связанное лексикографическое значение. До внесения команды 1005 передачи Алиса может сортировать открытые ключи A2 и B2 в лексикографическом порядке. Если команда передачи указывает min(A2, B2), Алиса может содержать минимум две строки символов. Таким образом, если Алиса определит, что строка A2 расположена до строки B2 в лексикографическом порядке, Алиса включит A2 в команду 1005 передачи (т. е. в то место, где min(A2,B2) указана на фиг. 10). Подобным образом, до внесения команды 1005 передачи Алиса может сортировать открытые ключи A2 и B2 в лексикографическом порядке для того, чтобы найти максимум двух строк символов. Если команда передачи указывает max(A2,B2), Алиса может содержать максимум две строки символов. Таким образом, если Алиса определит, что строка B2 расположена после строки A2 в лексикографическом порядке, Алиса включит B2 в команду 1005 передачи (т. е. в то место, где max(A2,B2) указана на фиг. 10). Другими словами, функции min и max выполняют лексикографическое сравнение открытых ключей, которые они получили как параметры. Соответственно, несмотря на то, что как A2, так и B2 будут включены в команду 1005 передачи, порядок перечисления A2 и B2 в команде передачи не будет основан на владении или связи кошельков, связанных с A2 и B2.
Соответственно, команда 1005 передачи может давать инструкции распределенной базе данных по переводу таким образом, что сумма C цифрового актива может быть вычтена из каждой из двух исходных записей (например, первого кошелька 1002A Алисы и первого кошелька 1002A Боба), и сумма C цифрового актива может быть начислена на каждую из двух целевых записей (например, второй кошелек 1002B Алисы и второй кошелек 1004B Боба). Определение min и max открытых ключей A2 и B2 гарантирует, что сумму C цифрового актива переводят на каждый из второго кошелька 1002B Алисы и второго кошелька 1004B Боба, при этом скрывая, какой из целевых кошельков 1002B или 1004B связан с каким из исходных кошельков 1002A или 1004A (и/или какой из целевых кошельков 1002B или 1004B связан с Алисой, и какой из целевых кошельков связан с Бобом). Порядок сортировки, выдаваемый функциями min и max, не имеет отношения к тому, кто является владельцем каждого кошелька, и, таким образом, скрывает эту информацию от других участников или пользователей распределенной базы данных. Таким образом, после того как Алиса внесет команду 1005 передачи, другие участники или пользователи распределенной базы данных могут, самое большее, предполагать, что Алиса является владельцем одного из целевых кошельков (т. е. 1002B или 1004B), на которые переводят сумму C цифрового актива, но не будут знать, какой из двух целевых кошельков 1002B или 1004B фактически принадлежит Алисе (или пользователю, связанному с вычислительным устройством, которое представляет Алиса). Другими словами, идентификатор вычислительного устройства (например, Алисы или Боба), связанного с закрытым ключом (например, A2’ или B2’), находящимся в паре с открытым ключом (например, A2 или B2), находящимся в логической связи с целевой записью (например, 1002B или 1004B), скрывают среди набора вычислительных устройств, который содержит Алису и Боба.
Боб может вносить команду 1007 передачи, соответствующую и/или идентичную команде 1005 передачи, внесенной Алисой, но подписанную с помощью закрытого ключа B1’, соответствующего первому кошельку Боба. В частности, Боб может выполнять ту же самую сортировку, что и Алиса, (например, лексикографическую сортировку открытых ключей A2 и B2) для внесения той же самой транзакции, что и Алиса. Альтернативным образом, Алиса может отправлять команду 1005 передачи только Бобу, и затем Боб может внести одну команду 1007 передачи в распределенную базу данных с обеими подписями. После этого распределенная база данных может исполнять внесенную команду передачи, как только будет достигнут консенсус, если обе подписи действительны. Таким образом, в некоторых случаях протокола передачи обе команды 1005 и 1007 передачи могут быть внесены в распределенную базу данных, тогда как в других случаях только команду 1007 передачи вносят в распределенную базу данных вместе с обеими подписями.
Хоть выше и обсуждено, что Алиса и Боб определяют минимальное и максимальное значения открытых ключей A2 и B2 вторых кошельков, в других реализациях может быть использована любая другая детерминистская сортировка для идентификации порядка, в котором будут представлены открытые ключи A2 и B2, связанные с целевыми записями. Соответственно, Алиса и Боб оба могут выполнять следующее:
S ={A1, B1}
D = sortList({A2, B2})
Внести/Отправить (Post/Send): Transfer2(S, D, C, N, T)
В некоторых других случаях Алиса и Боб могут отправлять сообщения третьей стороне (например, Кэрол, не показанной на фиг. 10) таким образом, что Кэрол вносит команду передачи в распределенную базу данных от имени Боба и/или Алисы. В еще некоторых других случаях третья сторона выступает в качестве промежуточного звена для связи, связанной с анонимным переводом между Алисой и Бобом. Таким образом, когда Алиса и/или Боб используют третью сторону в качестве промежуточного звена, их записи (т. е. кошельки) могут быть включены в распределенную базу данных и их связанные открытые ключи могут быть использованы распределенной базой данных даже тогда, когда вычислительные устройства, соответствующие Алисе и Бобу, не реализуют распределенную базу данных (или реализуют только поднабор и/или часть распределенной базы данных). В таком случае другой участник распределенной базы данных (например, Кэрол) может принимать указания операции над базой данных, например, запрос на перевод значения C (указывающего сумму цифрового актива) от Алисы (подобный запросу 1001 относительно свопинга), и Кэрол может передать этот запрос Бобу. Боб может затем ответить Алисе путем отправки Алисе через Кэрол ответа относительно свопинга (подобного ответу 1003 относительно свопинга). Алиса и Боб могут затем предоставить указания операций над базой данных, например, их команды передачи (подобные командам 1005 и 1007 передачи), Кэрол, и Кэрол может внести запрошенные операции над базой данных (например, команды передачи) в распределенную базу данных.
В качестве другого примера в некоторых случаях вычислительное устройство, соответствующее Алисе, не реализует распределенную базу данных, однако ее реализует вычислительное устройство, соответствующее Бобу. В таком случае Алиса может отправить указание операции над базой данных Кэрол, и Кэрол может внести соответствующую команду передачи в распределенную базу данных от имени Алисы. Другими словами, распределенная база данных может содержать записи (т. е. кошельки), принадлежащие вычислительным устройствам, которые не реализуют распределенную базу данных, и выполнять протоколы передачи, используя эти записи, через вычислительное устройство третьей стороны, которое является участником распределенной базы данных и/или реализует ее.
В качестве еще одного примера в некоторых случаях Алиса и/или Боб могут реализовывать и/или хранить часть распределенной базы данных. В частности, если вычислительное устройство (Кэрол) третьей стороны является участником распределенной базы данных и/или реализует и/или хранит всю распределенную базу данных, Алиса и/или Боб могут хранить и/или поддерживать часть из того, что хранит Кэрол. В качестве примера, Алиса может хранить записи, связанные с ее открытыми ключами, но не записи, связанные с другие пользователями распределенной базы данных. Подобным образом, Боб может хранить записи, связанные с его открытыми ключами, но не записи, связанные с другие пользователями распределенной базы данных. В таком случае, тогда как Алиса и Боб хранят часть распределенной базы данных, Кэрол может выступать в качестве посредника Алисы и Боба для доступа к полной распределенной базе данных.
В некоторых реализациях распределенная база данных может хранить целочисленный «размер пула» для каждого кошелька, представляющий количество кошельков в наборе кошельков, в котором скрывают заданный кошелек. Таким образом, если наблюдатель только знает, что кошелек X принадлежит одному из N различных участников, то размер пула N может быть прикреплен к этому кошельку, указывая на то, насколько сильно он анонимизирован. Неанонимизированные кошельки, такие как 1002A и 1004A, могут иметь пул 1, так как владелец известен, и, таким образом, наблюдатели могут сузить идентификатор до набора из всего лишь 1 физического лица. Другие кошельки могут быть более анонимизированными, если протокол выполняли неоднократно для таких кошельков. Например, если наблюдатель может идентифицировать, что кошелек A1 принадлежит одному из PA1 физических лиц, и что B1 принадлежит одному из PB1 физических лиц, то целое число PA1 может быть связано с A1, и целое число PB1 может быть связано с B1.
В некоторых случаях одно или более сообщений 1001, 1003, 1005 и/или 1007 могут содержать PA1 и PB1. Алиса и Боб могут использовать PA1 и PB1, чтобы решить, продолжать ли перевод цифрового актива. Например, если Алиса уже выполнила этот процесс 10 раз, то PA1 может составлять 1024. Если Боб еще не выполнил этот процесс, то PB1 может составлять 1. Алиса, следовательно, может отказаться выполнять протокол с Бобом, так как результатом будет лишь незначительное повышение ее анонимности, от сокрытия в пуле из 1024 кошельков до пула из 1025 кошельков. Алиса вместо этого может предпочесть использовать кошелек с размером пула 1024, чтобы одна итерация могла повысить PA1 с 1024 до 2048. В некоторых случаях кошелек может быть связан с набором кошельков вместо целого числа. Это будет представлять собой такой набор кошельков, что наблюдатель может только знать, что заданный участник является владельцем одного из кошельков в наборе, но не знать, какого именно. Таким образом, в последнем примере PA1 будет представлять собой набор из 1024 кошельков, и PB1 будет представлять собой набор из 1024 кошельков. По завершении протокола PA1 будет расширено таким образом, чтобы являться объединением наборов PA1 и PB1. Алиса может только согласиться использовать кошелек таким образом, чтобы это объединение было намного большим, чем PA1, чтобы она не теряла времени на процесс, который лишь в незначительной степени повысит ее анонимность.
В некоторых случаях сообщение 1001 может содержать параметр, указывающий на минимальное пороговое значение для PB2, которое, например, согласна принять Алиса. Соответственно, Алиса может принять решение о том, чтобы не продолжать осуществление свопинга с Бобом, если, например, PB1 находится ниже порога минимального значения.
В некоторых реализациях одно или более сообщений 1001, 1003, 1005 и/или 1007 могут содержать: (1) значение строки, представляющее замечания пользователя; (2) дату и время подачи сообщения; (3) разрешение на перевод комиссии с кошелька (кошельков) пользователя на кошелек вычислительного устройства, подающего или вносящего сообщение или транзакцию; (4) разрешение на перевод комиссии с кошелька пользователя на вычислительное устройство (вычислительные устройства), которое (которые) способствовало (способствовали) анонимизации адреса Интернет-протокола (IP-адреса) вычислительного устройства (например, вычислительные устройства в сети TOR); и/или любые другие подходящие метаданные.
В других реализациях команды передачи могут быть реализованы с транзакцией по передаче, такой как:
TRANSFER2 (S, W, R, D, N, T)
где:
K= количество отправляющих кошельков
S= список отправляющих кошельков с открытыми ключами {S1, S2, …, SK)
W= количество монет или сумма цифрового актива для снятия с каждого кошелька {W1, W2, …, WK)
M= количество принимающих кошельков
R= список принимающих кошельков с открытыми ключами {R1, R2, …, RM}
D= количество монет или сумма цифрового актива для внесения в каждый кошелек: {D1, D2, …, WM}
N= случайное число
T= метка времени завершения
где суммарное количество монет, подлежащих снятию, или сумма цифрового актива W соответствуют суммарному количеству монет или суммам цифрового актива, подлежащих внесению на каждый кошелек D, и имеются подписи посредством закрытых ключей, связанных с открытыми ключами в S. Одна транзакция TRANSFER2 (S, W, R, D, N, T) может содержать приложение, подписанное посредством таких закрытых ключей. В некоторых случаях может быть несколько идентичных транзакций (с одинаковым N), каждая из которых имеет одну или более подписей, и которые вместе имеют требующиеся подписи. Другие параметры, которые могут быть включены в команду TRANSFER2, могут включать (1) строку для передачи замечаний; (2) дату/время, указывающие время внесения команды передачи; (3) параметр, указывающий на разрешение на перевод комиссии с записи (т. е. кошелька) на запись (т. е. кошелек) вычислительного устройства, используемого в качестве третьей стороны для внесения команды передачи, и другие подходящие метаданные.
В других реализациях команды 1005 и 1007 передачи могут быть изменены таким образом, чтобы содержать меньше параметров, чем количество параметров, показанных на фиг. 10. Например, команда 1005 передачи может быть внесена в распределенную базу данных как TRANSFER2(min(A2,B2), max(A2,B2), N, T)A1’, и команда 1007 передачи может быть внесена как TRANSFER2(N,T)B1’. В таком случае полоса пропускания, используемая излишним количеством параметров, уменьшается благодаря уникальности случайного числа N, которое уникальным образом идентифицирует ряд находящихся в связи друг с другом транзакций, связанных с анонимным переводом.
На фиг. 11 показана структура дерева из четырех уровней, выполненная путем многократного применения протокола передачи, обсужденного со ссылкой на фиг. 10, для анонимизации переводов между кошельками. Как было обсуждено выше, после выполнения четырех сообщений протокола передачи по фиг. 10, монеты в кошельке 1002A и 1004A были переведены на кошельки 1002B и 1004B. Участники или пользователи распределенной базы данных могут делать заключение из истории транзакций, записанных в распределенной базе данных, что, например, перевод был выполнен из первого кошелька 1101 Алисы либо на второй кошелек 1104 Боба, либо на второй кошелек 1105 Алисы. Аналогичным образом, может быть сделано заключение, что перевод был выполнен с первого кошелька 1103 Боба либо на второй кошелек 1104 Боба, либо на второй кошелек 1105 Алисы. Таким образом, на уровне 1 структуры дерева второй кошелек 1105 Алисы скрыт от других участников или пользователей распределенной базы данных среди пула из двух кошельков (т. е. кошелька 1104 и 1105).
На уровне 2 Алиса повторяет протокол передачи, обсужденный со ссылкой на фиг. 10, с Дэйвом. Боб повторяет протокол передачи с Кэрол. Таким образом, на уровне 2 количество монет или сумму цифрового актива переводят со второго кошелька 1105 Алисы на один из кошельков 1107 или 1109, и кошелек Алисы скрывают для других участников или пользователей распределенной базы данных среди четырех кошельков, т. е. кошельков 1107, 1109, 1111 и 1113. Алиса может продолжать повторять протокол передачи, обсужденный со ссылкой на фиг. 10. На каждом уровне кошелек Алисы скрывают в экспоненциально растущем пуле кошельков. Например, на уровне 3 Алиса повторяет протокол передачи с Хэнком, и ее кошелек 1115 скрывают в пуле из восьми кошельков. На уровне 4 Алиса повторяет протокол передачи с Оскаром, и ее кошелек 1117 скрывают в пуле из шестнадцати кошельков. На уровне сорок (не показан на фиг. 11) кошелек Алисы скрывают в пуле из более чем триллиона кошельков.
Протоколы передачи, показанные на фиг. 11, могут аналогичным образом быть выполнены параллельно, как показано на фиг. 12. Например, Алиса может выполнять протокол передачи с Бобом, Дэйвом, Хэнком и Оскаром таким образом, что переводы выполняются в одно и то же время или почти в одно и то же время. Соответственно, Алиса может одновременно выполнять и/или вносить операции протокола передачи, показанные на 1201, 1203, 1205 и 1207. Если на тот момент времени, когда достигнут порядок консенсуса, все кошельки, приспособленные для перевода суммы C цифрового актива, имеют по меньшей мере такую сумму, то все переводы выполняются параллельно. Если по меньшей мере один из кошельков, приспособленных для перевода суммы C цифрового актива, не имеет такой суммы, то одна или более операций протокола передачи, показанных на 1201, 1203, 1205 и 1207, могут храниться в распределенной базе данных в «активном» состоянии. Соответственно, операции протокола передачи, показанные на 1201, 1203, 1205 и 1207, хранящиеся в «активном» состоянии, могут быть выполнены в первой точке в истории консенсуса, в которой кошельки, которые не имели суммы C цифрового актива, имеют по меньшей мере такую сумму.
Как было обсуждено выше, команды перевода, внесенные в распределенную базу данных, могут включать параметр T для указания времени завершения. Если время T достигнуто до того, как операции протокола передачи, показанные на 1201, 1203, 1205 и/или 1207, будут выполнены, то такие операции игнорируют и не выполняют. Если в некоторой точке операции протокола передачи, показанные на 1201, 1203, 1205 и/или 1207, являются «активными» в распределенной базе данных в ожидании того, что кошелек будет иметь достаточную сумму цифрового актива (например, сумму C), чтобы в этом случае быть выполненными, как только достаточную сумму цифрового актива помещают в такой кошелек, одна или более операций протокола передачи, показанных на 1201, 1203, 1205 и/или 1207, запускаются в своем порядке консенсуса. В таком случае порядок консенсуса операций протоколов передачи, показанных на 1201, 1203, 1205 и/или 1207, может быть последним из порядков консенсуса подписанных операций, включенных в операции таких протоколов передачи. Таким образом, операции протоколов передачи могут быть отсрочены или оставаться в «активном» состоянии, пока не будет достигнуто время T. Если достаточную сумму цифрового актива для выполнения операций в «активном» состоянии не помещают в запись до наступления времени T, то операции протоколов передачи, показанные на 1201, 1203, 1205 и/или 1207, игнорируют.
В примере, показанном на фиг. 12, Алиса вносит в распределенную базу данных операции протокола передачи, показанные в 1201, 1203, 1205 и 1207, по существу параллельно и по существу в одно и то же время. Такие операции будут выполнены, как только порядок консенсуса будет достигнут и после того как исходные записи или кошельки будут иметь по меньшей мере сумму C цифрового актива в пределах периода T времени, как указано во внесенных командах передачи. Другими словами, если записи, связанные с открытыми ключами (A1, B1) на 1201, (A2, D2) на 1203, (O4, A4) на 1205 и (A3, H3) на 1207, связаны с по меньшей мере суммой C цифрового актива в любой точке в пределах периода T времени, то операции протокола передачи 1201, 1203, 1205 и 1207 выполняют после того, как открытые ключи связаны с суммой C. Однако, если одна из записей, связанных с открытым ключом, вовлеченным в транзакцию, не содержит по меньшей мере сумму C цифрового актива в точке в пределах периода T времени, то перевод отменяют (после того как истечет период T времени), тогда как любые другие транзакции будут все еще выполнены, при условии, что записи, связанные с открытыми ключами для этой транзакции, связаны с суммой C в точке в пределах периода T времени. Таким образом, выполнение операций протоколов передачи, показанных на 1201, 1203, 1205, 1207, может быть основано на том, имеют ли исходные записи или кошельки сумму C, предназначенную для перевода, и, если не имеют, получат ли исходные записи или кошельки сумму C цифрового актива до истечения времени T. Это позволяет участнику (например, Алисе) вносить в распределенную базу данных несколько последовательных транзакций в одно и то же время, при этом все еще позволяя совершать транзакции последовательно.
Например, если Алиса вносит в распределенную базу данных операции протокола передачи, показанные в 1201, 1203, 1205 и 1207, по существу параллельно и по существу в одно и то же время, но только записи A1 и B1 содержат сумму C в момент внесения, только транзакция 1201 будет совершена. Это выполнит перевод суммы C в записи, связанные с A2 и B2. Если запись, связанная с D2, также получает сумму C в пределах периода T времени, транзакция 1203 будет совершена (так как запись, связанная с A2, приняла сумму C за одну транзакцию 1201). Подобным образом, транзакция 1207 и затем транзакция 1205 могут в таком случае быть выполнены. Таким образом, каждая из транзакций 1201, 1203, 1205 и 1207 может быть внесена в распределенную базу данных в одно и то же время, но все еще может быть совершена в последовательном порядке, исходя из времени, когда сумма C была принята в записях (в пределах периода T времени).
Примерная теорема 1: если событие x предшествует событию y в частичном порядке, то в знании заданного участника о других участниках в заданный момент времени каждый из других участников либо принял указание о x до y, либо еще не принял указание о y.
Доказательство: если событие x предшествует событию y в частичном порядке, то x является предком y. Когда участник принимает указание о y в первый раз, этот участник либо уже принял указание о x ранее (в случае чего он узнает о x раньше y), либо это будет случай, когда синхронизация предоставляет этому участнику как x, так и y (в случае чего он узнает о x раньше y во время этой синхронизации, поскольку события, принимаемые во время одной синхронизации, полагают принимаемыми в порядке, согласующемся с взаимосвязями потомственности, как описано в отношении примерной системы 5). Что и требовалось доказать.
Примерная теорема 2: для любого заданного хешграфа, если x предшествует y в частичном порядке, то x будет предшествовать y в общем порядке, вычисленном для этого хешграфа.
Доказательство: если x предшествует y в частичном порядке, то согласно теореме 1:
для всех i, rank(i,x) < rank(i,y),
где rank(i,x) представляет собой ранг, присвоенный участником i событию x, который равен 1, если x является первым событием, принятым участником i, 2, если вторым, и так далее. Допустим, что med(x) представляет собой медиану rank(i,x) для всех i, и аналогично для med(y).
Для заданного k выберем i1 и i2 таким образом, что rank(i1,x) является k-м наименьшим рангом x, а rank(i2,y) является k-м наименьшим рангом y. Тогда:
rank(i1,x) < rank(i2,y).
Это объясняется тем, что rank(i2,y) превышает или равняется k рангов y, каждый из которых строго превышает соответствующий ранг x. Следовательно, rank(i2,y) строго превышает по меньшей мере k рангов x, а значит строго превышает k-й наименьший ранг x. Этот аргумент справедлив для любого k.
Допустим, что 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 в общем порядке. Что и требовалось доказать.
Примерная теорема 3: если «период передачи» представляет собой количество времени, необходимое для распространения существующих событий посредством синхронизации всем участникам, то:
после 1 периода передачи: все участники приняли события,
после 2 периодов передачи: все участники приходят к согласию относительно порядка этих событий,
после 3 периодов передачи: все участники знают, что согласие было достигнуто,
после 4 периодов передачи: все участники получают цифровые подписи от всех остальных участников, одобряющие этот порядок консенсуса.
Доказательство: допустим, что S0 представляет собой набор событий, которые были созданы и/или определены к заданному моменту времени T0. Если каждый участник будет в итоге синхронизироваться с каждым из остальных участников бесконечное число раз, то с вероятностью, равной 1, в итоге будет существовать момент времени T1, к которому события в S0 распространятся каждому участнику, так что каждый участник будет осведомлен обо всех событиях. Это конец первого периода передачи. Допустим, что S1 представляет собой набор событий, которые существуют на момент времени T1 и которые еще не существовали на момент времени T0. Тогда с вероятностью, равной 1, в итоге будет существовать момент времени T2, к которому каждый участник примет каждое из событий в наборе S1, которое является существующим на момент времени T1. Это конец второго периода передачи. Подобным образом, T3 представляет собой момент времени, когда все события в S2, существующие к моменту времени T2, но не до момента времени T1, распространились всем участникам. Следует отметить, что каждый период передачи в итоге заканчивается с вероятностью, равной 1. В среднем каждый период будет продолжаться столько, сколько необходимо для выполнения log2(n) синхронизаций, если имеется n участников.
К моменту времени T1 каждый участник примет каждое событие в S0.
К моменту времени T2 заданный участник Алиса примет запись каждого из остальных участников, принимающих каждое событие в S0. Следовательно, Алиса может вычислить ранг для каждого действия в S0 для каждого участника (который представляет собой порядок, в котором этот участник принял это действие), а затем отсортировать события по медиане рангов. Полученный в результате общий порядок не меняется для событий в S0. Это объясняется тем, что полученный в результате порядок является функцией порядка, в котором каждый участник впервые принял указание о каждом из этих событий, который не меняется. Возможно, что порядок, вычисленный Алисой, будет иметь несколько событий из S1, рассеянных среди событий S0. Эти события S1 могут все еще меняться, где они попадают в последовательность событий S0. Но относительный порядок событий в S0 не будет меняться.
К моменту времени T3 Алиса узнает общий порядок на объединении S0 и S1, и относительный порядок событий в этом объединении меняться не будет. Кроме того, она может найти в этой последовательности самое раннее событие из S1 и может прийти к выводу, что последовательность событий до S1 не будет меняться, даже посредством вставки новых событий не из S0. Следовательно, к моменту времени T3 Алиса может определить, что консенсус был достигнут для порядка событий в истории до первого события S1. Она может подписать с помощью цифровой подписи хеш состояния (например, зафиксированного переменной состояния базы данных, определенной Алисой), являющийся результатом этих событий, происходящих в этом порядке, и отправить подпись в виде части следующего события, которое она создает и/или определяет.
К моменту времени T4 Алиса примет подобные подписи от других участников. На этом этапе она может просто сохранить этот список подписей вместе с состоянием, свидетельством которого они являются, и она может удалить события, которые она сохранила до первого события S1. Что и требовалось доказать.
Системы, описанные в настоящем документе, описывают распределенную базу данных, которая достигает консенсуса быстро и безопасно. Она может быть полезным структурным блоком для многих приложений. Например, если транзакции описывают перевод криптовалюты с одного кошелька криптовалюты на другой, и если состоянием является простой показатель текущей суммы в каждом кошельке, то эта система будет представлять собой систему криптовалюты, которая избегает дорогого доказательства выполнения работы, используемого в существующих системах. Автоматическое соблюдение правил позволяет добавлять признаки, которые не являются общераспространенными в текущих криптовалютах. Например, утерянные монеты могут быть восстановлены во избежание дефляции посредством исполнения правила, гласящего, что, если кошелек ни отправляет, ни принимает криптовалюту в течение определенного периода времени, то этот кошелек удаляется, и его содержимое распределяется на другие существующие кошельки пропорционально сумме, которую они содержат на текущий момент. Таким образом, запас денег не будет расти или сокращаться, даже если утерян закрытый ключ для кошелька.
Другим примером является распределенная игра, которая действует подобно массовой многопользовательской онлайн-игре (MMO), в которую играют на сервере, но достигает этого без применения центрального сервера. Консенсус может быть достигнут без какого-либо центрального сервера, осуществляющего управление.
Другим примером является система для социальных сетей, которая построена поверх такой базы данных. Поскольку транзакции подписываются с помощью цифровой подписи, и участники принимают информацию о других участниках, это обеспечивает преимущества, заключающиеся в безопасности и удобстве, над текущими системами. Например, может быть реализована система электронной почты со строгой антиспам политикой, поскольку электронные письма не могут иметь фальшивых обратных адресов. Такая система может также стать объединенной социальной системой, сочетающей в одной распределенной базе данных функции, в настоящее время выполняемые электронной почтой, твит-сообщениями, текстовыми сообщениями, форумами, вики и/или другими социальными сетями.
Другие приложения могут включать более сложные криптографические функции, такие как групповые цифровые подписи, при которых группа действует как единое целое для подписания контракта или документа. Эти и другие формы многостороннего вычисления могут быть эффективно реализованы с использованием такой системы распределенного консенсуса.
Другим примером является система открытого реестра. Кто угодно может заплатить, чтобы сохранить некоторую информацию в системе, уплачивая при этом небольшую сумму криптовалюты (или реальной валюты) за байт в год для хранения информации в системе. Эти денежные средства могут затем быть автоматически распределены участникам, которые хранят эти данные, и участникам, которые постоянно синхронизируются, чтобы работать над достижением консенсуса. Участникам может автоматически переводиться небольшая сумма криптовалюты каждый раз, когда они синхронизируются.
Эти примеры показывают, что распределенная база данных с консенсусом является полезной в качестве компонента многих приложений. Поскольку база данных не использует затратное доказательство выполнения работы, по возможности используя вместо него менее затратное доказательство доли владения, база данных может работать с полным узлом, работающим на менее мощных компьютерах или даже мобильных и встроенных устройствах.
Хоть выше и описано, что событие содержит хеш двух предыдущих событий (один собственный хеш и один чужой хеш), в других вариантах осуществления участник может синхронизироваться с двумя другими участниками для создания и/или определения события, содержащего хеши трех предыдущих событий (один собственный хеш и два чужих хеша). В еще других вариантах осуществления в событие может быть включено любое количество хешей событий предыдущих событий от любого количества участников. В некоторых вариантах осуществления разные события могут включать разные количества хешей предыдущих событий. Например, первое событие может включать два хеша событий, и второе событие может включать три хеша событий.
Хоть события и описаны выше как включающие хеши (или значения криптографических хешей) предыдущих событий, в других вариантах осуществления событие может быть создано и/или определено таким образом, чтобы включать указатель, идентификатор и/или любую другую подходящую ссылку на предыдущие события. Например, событие может быть создано и/или определено таким образом, чтобы включать серийный номер, связанный с предыдущим событием и используемый для его идентификации, таким образом связывая события. В некоторых вариантах осуществления такой серийный номер может включать, например, идентификатор (например, адрес управления доступом к среде (MAC), адрес Интернет-протокола (IP-адрес), присвоенный адрес и/или т.п.), связанный с участником, который создал и/или определил событие, и порядком события, определенным этим участником. Например, если участник имеет идентификатор, равный 10, и событие является 15-ым событием, созданным и/или определенным этим участником, то он может присвоить этому событию идентификатор, равный 1015. В других вариантах осуществления любой другой подходящий формат может быть использован для присвоения идентификаторов событиям.
В других вариантах осуществления события могут содержать полные криптографические хеши, но только части этих хешей передаются во время синхронизации. Например, если Алиса отправляет Бобу событие, содержащее хеш H, и J является первыми 3 байтами H, и Алиса определяет, что из всех событий и хешей, которые она сохранила, H является единственным хешем, начинающимся с J, то она может отправить J вместо H во время синхронизации. Если Боб затем определяет, что у него есть другой хеш, начинающийся с J, то он может отправить ответное сообщение Алисе с запросом полного H. Таким образом хеши могут быть сжаты во время передачи.
Несмотря на то, что примерные системы, показанные и описанные выше, описаны со ссылкой на другие системы, в других вариантах осуществления любая комбинация примерных систем и связанных с ними функциональных возможностей может быть реализована для создания и/или определения распределенной базы данных. Например, примерная система 1, примерная система 2 и примерная система 3 могут быть объединены для создания и/или определения распределенной базы данных. В качестве другого примера, в некоторых вариантах осуществления примерная система 10 может быть реализована вместе с примерной системой 1, но без примерной системы 9. В качестве еще одного примера, примерная система 7 может быть объединена и реализована вместе с примерной системой 6. В еще других вариантах осуществления могут быть реализованы любые другие подходящие комбинации примерных систем.
Хоть выше и были описаны различные варианты осуществления, следует понимать, что они были представлены исключительно в качестве примера, а не ограничения. В случае если способы, описанные выше, указывают на то, что определенные события происходят в определенном порядке, упорядоченная последовательность определенных событий может быть изменена. Дополнительно некоторые из событий могут быть выполнены одновременно в параллельном процессе, когда это возможно, а также выполнены последовательно, как описано выше.
Некоторые варианты осуществления, описанные в настоящем документе, относятся к продукту в виде запоминающего устройства с энергонезависимым машиночитаемым носителем (который также может называться энергонезависимым считываемым процессором носителем), на котором хранятся инструкции или компьютерный код для выполнения различных реализуемых компьютером операций. Машиночитаемый носитель (или считываемый процессором носитель) является энергонезависимым в том смысле, что он по существу не содержит временно распространяющихся сигналов (например, распространяющейся электромагнитной волны, несущей информацию по передающей среде, такой как пространство или кабель). Носители и компьютерный код (который также может называться кодом) могут быть выполнены и созданы для конкретной цели или целей. Примеры энергонезависимых машиночитаемых носителей включают, помимо прочего: магнитные запоминающие устройства, такие как жесткие диски, гибкие диски и магнитная лента; оптические запоминающие устройства, такие как компакт-диск / цифровые видеодиски (CD/DVD), постоянные запоминающие устройства на компакт-дисках (CD-ROM) и голографические устройства; магнитооптические запоминающие устройства, такие как оптические диски; модули обработки сигнала несущей частоты; и аппаратные устройства, которые специально приспособлены для хранения и исполнения программного кода, такие как интегральные схемы специального назначения (ASIC), программируемые логические интегральные схемы (PLD), постоянные запоминающие устройства (ROM) и оперативные запоминающие устройства (RAM). Другие варианты осуществления, описанные в настоящем документе, относятся к компьютерному программному продукту, который может включать, например, инструкции и/или компьютерный код, обсуждаемые в настоящем документе.
Примеры компьютерного кода включают, помимо прочего, микрокод или микроинструкции, машинные инструкции, такие как созданные компилятором, код, используемый для создания веб-службы, и файлы, содержащие инструкции более высокого уровня, которые исполняются компьютером с использованием интерпретатора. Например, варианты осуществления могут быть реализованы с использованием императивных языков программирования (например, C, Fortran и т. д.), функциональных языков программирования (Haskell, Erlang и т. д.), логических языков программирования (например, Prolog), объектно-ориентированных языков программирования (например, Java, C++ и т. д.) или других подходящих языков программирования и/или инструментов разработки. Дополнительные примеры компьютерного кода включают, помимо прочего, сигналы управления, зашифрованный код и сжатый код.
Хоть выше и были описаны различные варианты осуществления, следует понимать, что они были представлены исключительно в качестве примера, а не ограничения, и различные изменения могут быть выполнены в отношении формы и деталей. Любая часть устройства и/или способов, описанных в настоящем документе, может быть объединена в любой комбинации, за исключением взаимоисключающих комбинаций. Варианты осуществления, описанные в настоящем документе, могут включать различные комбинации и/или подкомбинации функций, компонентов и/или признаков разных описанных вариантов осуществления.
Изобретение относится к области вычислительной техники. Техническим результатом является обеспечение системы распределенной базы данных. Раскрыто устройство для реализации распределенной базы данных, содержащее: память первого вычислительного устройства, содержащую часть экземпляра распределенной базы данных на первом вычислительном устройстве, приспособленном для включения во множество вычислительных устройств, которые реализуют посредством сети, функционально соединенной с множеством вычислительных устройств, распределенную базу данных, которая содержит первую запись, находящуюся в логической связи с первым открытым ключом, связанным с первым вычислительным устройством; и процессор первого вычислительного устройства, функционально соединенный с памятью, при этом процессор приспособлен для: приема со второго вычислительного устройства из множества вычислительных устройств первого открытого ключа, связанного со вторым вычислительным устройством, и (1) зашифрованного с помощью первого открытого ключа, связанного с первым вычислительным устройством, и (2) находящегося в логической связи со второй записью распределенной базы данных; расшифровки на первом вычислительном устройстве первого открытого ключа, связанного со вторым вычислительным устройством, с помощью закрытого ключа, находящегося в паре с первым открытым ключом, связанным с первым вычислительным устройством; отправки на второе вычислительное устройство второго открытого ключа, (1) связанного с первым вычислительным устройством, (2) находящегося в логической связи с третьей записью распределенной базы данных и (3) зашифрованного с помощью второго открытого ключа, связанного со вторым вычислительным устройством и находящегося в логической связи с четвертой записью распределенной базы данных; определения команды передачи путем выполнения лексикографического сравнения между вторым открытым ключом, связанным с первым вычислительным устройством, и первым открытым ключом, связанным со вторым вычислительным устройством; и отправки сигнала для внесения в распределенную базу данных команды передачи, приспособленной для передачи значения из каждой исходной записи из множества исходных записей, включая первую запись и четвертую запись, в другую целевую запись из множества целевых записей, включая вторую запись и третью запись, при этом команда передачи подписана с помощью закрытого ключа и приспособлена для исполнения таким образом, чтобы скрыть идентификатор вычислительного устройства, связанного с каждой целевой записью из множества целевых записей, среди набора вычислительных устройств, содержащего первое вычислительное устройство и второе вычислительное устройство. 2 н. и 13 з.п. ф-лы, 16 ил.
1. Устройство для реализации распределенной базы данных, содержащее:
память первого вычислительного устройства, содержащую часть экземпляра распределенной базы данных на первом вычислительном устройстве, приспособленном для включения во множество вычислительных устройств, которые реализуют посредством сети, функционально соединенной с множеством вычислительных устройств, распределенную базу данных, которая содержит первую запись, находящуюся в логической связи с первым открытым ключом, связанным с первым вычислительным устройством; и
процессор первого вычислительного устройства, функционально соединенный с памятью,
при этом процессор приспособлен для:
приема со второго вычислительного устройства из множества вычислительных устройств первого открытого ключа, связанного со вторым вычислительным устройством, и (1) зашифрованного с помощью первого открытого ключа, связанного с первым вычислительным устройством, и (2) находящегося в логической связи со второй записью распределенной базы данных;
расшифровки на первом вычислительном устройстве первого открытого ключа, связанного со вторым вычислительным устройством, с помощью закрытого ключа, находящегося в паре с первым открытым ключом, связанным с первым вычислительным устройством;
отправки на второе вычислительное устройство второго открытого ключа, (1) связанного с первым вычислительным устройством, (2) находящегося в логической связи с третьей записью распределенной базы данных и (3) зашифрованного с помощью второго открытого ключа, связанного со вторым вычислительным устройством и находящегося в логической связи с четвертой записью распределенной базы данных;
определения команды передачи путем выполнения лексикографического сравнения между вторым открытым ключом, связанным с первым вычислительным устройством, и первым открытым ключом, связанным со вторым вычислительным устройством; и
отправки сигнала для внесения в распределенную базу данных команды передачи, приспособленной для передачи значения из каждой исходной записи из множества исходных записей, включая первую запись и четвертую запись, в другую целевую запись из множества целевых записей, включая вторую запись и третью запись, при этом команда передачи подписана с помощью закрытого ключа и приспособлена для исполнения таким образом, чтобы скрыть идентификатор вычислительного устройства, связанного с каждой целевой записью из множества целевых записей, среди набора вычислительных устройств, содержащего первое вычислительное устройство и второе вычислительное устройство.
2. Устройство по п. 1, отличающееся тем, что экземпляр распределенной базы данных представляет собой первый экземпляр распределенной базы данных, при этом второй экземпляр распределенной базы данных на третьем вычислительном устройстве из множества вычислительных устройств содержит множество записей, включая первую запись, вторую запись, третью запись и четвертую запись,
при этом первый экземпляр распределенной базы данных не содержит каждую запись из множества записей.
3. Устройство по п. 1, отличающееся тем, что команда передачи приспособлена для идентификации того, что каждая исходная запись из множества исходных записей имеет по меньшей мере значение, прежде чем передавать значение из каждой исходной записи из множества исходных записей в другую целевую запись из множества целевых записей.
4. Устройство по п. 1, отличающееся тем, что команду передачи вносят в распределенную базу данных в момент времени,
когда каждая исходная запись из множества исходных записей не имеет по меньшей мере значения в момент времени, при этом команда передачи приспособлена для отсрочки передачи до тех пор, пока каждая запись из множества исходных записей не будет иметь по меньшей мере значение.
5. Устройство по п. 1, отличающееся тем, что команда передачи связана с периодом времени, при этом команда передачи приспособлена для передачи значения из каждой записи из множества исходных записей в другую целевую запись из множества целевых записей, если каждая запись из множества исходных записей имеет по меньшей мере значение в момент времени в пределах периода времени.
6. Устройство по п. 1, отличающееся тем, что команда передачи представляет собой первую команду передачи, вторая запись представляет собой первую целевую запись, и набор вычислительных устройств представляет собой первый набор вычислительных устройств,
при этом процессор приспособлен для отправки сигнала для внесения в распределенную базу данных, прежде чем исполнять первую команду передачи, второй команды передачи, приспособленной для передачи значения из первой целевой записи во вторую целевую запись таким образом, чтобы скрыть идентификатор вычислительного устройства, связанного с закрытым ключом, соответствующим открытому ключу, находящемуся в логической связи со второй целевой записью, среди второго набора вычислительных устройств, содержащего первый набор вычислительных устройств,
при этом вторая команда передачи приспособлена для передачи значения из первой целевой записи во вторую целевую запись, если первая целевая запись имеет значение в момент времени в пределах периода времени.
7. Устройство по п. 1, отличающееся тем, что процессор дополнительно приспособлен для:
отправки на второе вычислительное устройство первого открытого ключа, связанного с первым вычислительным устройством, и числового значения, подлежащего вычитанию из первой записи и объединению с каждой целевой записью из множества целевых записей, посредством исполнения команды передачи.
8. Устройство по п. 1, отличающееся тем, что команда передачи дополнительно приспособлена для:
включения порога времени, обусловливающего аннулирование команды передачи при недостижении конвергенции посредством протокола консенсуса до наступления порога времени.
9. Устройство по п. 1, отличающееся тем, что значение соответствует сумме цифрового актива.
10. Устройство для реализации распределенной базы данных, содержащее:
память первого вычислительного устройства, содержащую часть экземпляра распределенной базы данных на первом вычислительном устройстве, приспособленном для включения во множество вычислительных устройств, которые реализуют посредством сети, функционально соединенной с множеством вычислительных устройств, распределенную базу данных, которая содержит первую запись, находящуюся в логической связи с первым открытым ключом, связанным с первым вычислительным устройством; и
процессор первого вычислительного устройства, функционально соединенный с памятью,
при этом процессор приспособлен для:
приема со второго вычислительного устройства из множества вычислительных устройств (1) первого открытого ключа, связанного со вторым вычислительным устройством, и (2) значения, запрошенного для передачи из второй записи, находящейся в логической связи с первым открытым ключом, связанным со вторым вычислительным устройством;
шифрования второго открытого ключа, связанного с первым вычислительным устройством, с помощью первого открытого ключа, связанного со вторым вычислительным устройством, для определения зашифрованного второго открытого ключа, связанного с первым вычислительным устройством;
отправки на второе вычислительное устройство зашифрованного второго открытого ключа, связанного с первым вычислительным устройством;
определения команды передачи путем выполнения лексикографического сравнения между вторым открытым ключом, связанным с первым вычислительным устройством, и вторым открытым ключом, связанным со вторым вычислительным устройством; и
отправки сигнала для внесения в распределенную базу данных команды передачи, приспособленной для передачи значения из каждой исходной записи из множества исходных записей, включая первую запись и вторую запись, в другую целевую запись из множества целевых записей, включая третью запись, находящуюся в логической связи со вторым открытым ключом, связанным с первым вычислительным устройством, и четвертую запись, находящуюся в логической связи со вторым открытым ключом, связанным со вторым вычислительным устройством, при этом команда передачи подписана с помощью закрытого ключа, находящегося в паре с первым открытым ключом, связанным с первым вычислительным устройством, и приспособлена для исполнения таким образом, чтобы скрыть идентификатор вычислительного устройства, связанного с каждой целевой записью из множества целевых записей, среди набора вычислительных устройств, содержащего первое вычислительное устройство и второе вычислительное устройство.
11. Устройство по п. 10, отличающееся тем, что экземпляр распределенной базы данных представляет собой первый экземпляр распределенной базы данных, при этом второй экземпляр распределенной базы данных на третьем вычислительном устройстве из множества вычислительных устройств содержит множество записей, включая первую запись, вторую запись, третью запись и четвертую запись,
при этом первый экземпляр распределенной базы данных не содержит каждую запись из множества записей.
12. Устройство по п. 10, отличающееся тем, что команда передачи связана с периодом времени, при этом команда передачи приспособлена для передачи значения из каждой исходной записи из множества исходных записей в другую целевую запись из множества целевых записей, если каждая исходная запись из множества исходных записей имеет по меньшей мере значение в момент времени в пределах периода времени.
13. Устройство по п. 10, отличающееся тем, что команда передачи представляет собой первую команду передачи, третья запись представляет собой первую целевую запись, и набор вычислительных устройств представляет собой первый набор вычислительных устройств,
при этом процессор приспособлен для отправки сигнала для внесения в распределенную базу данных, прежде чем исполнять первую команду передачи, второй команды передачи, приспособленной для передачи значения из первой целевой записи во вторую целевую запись таким образом, чтобы скрыть идентификатор вычислительного устройства, связанного с закрытым ключом, соответствующим открытому ключу, находящемуся в логической связи со второй целевой записью, среди второго набора вычислительных устройств, содержащего первый набор вычислительных устройств,
при этом вторая команда передачи приспособлена для передачи значения из первой целевой записи во вторую целевую запись, если первая целевая запись имеет значение в момент времени в пределах периода времени.
14. Устройство по п. 10, отличающееся тем, что команда передачи дополнительно приспособлена для:
включения порога времени, обусловливающего аннулирование команды передачи при недостижении конвергенции посредством протокола консенсуса до наступления порога времени.
15. Устройство по п. 10, отличающееся тем, что значение соответствует сумме цифрового актива.
| Токарный резец | 1924 |
|
SU2016A1 |
| Способ и приспособление для нагревания хлебопекарных камер | 1923 |
|
SU2003A1 |
| Приспособление для суммирования отрезков прямых линий | 1923 |
|
SU2010A1 |
| КРУПНОМАСШТАБНАЯ СИСТЕМА ХРАНЕНИЯ ДАННЫХ | 2012 |
|
RU2595493C2 |
