Vmware, Inc.

Verizon Media Inc.

Oath Inc.

Guy Golan Gueta

Ittai Abraham

Dahlia Malkhi

Edward Bortnikov

Eshcar Hillel

Alexander Spiegelman

Michael Reiter

Igor Golikov

Idit Keidar

Soumya Basu

Alin Tomescu

Maya Arbel

Adrian Seredinschi

Heidi Howard

Neil Giridharan

Ioan Alin Tomescu Nicolescu

Israel Cidon

Eyal Zohar

David Carmel

Alex Markuze

Avishay Yanai

Andrew Joseph Stone

Dmitry Basin

Anastasia Braginsky

Bryan Fink

Pranav Sharma

Maofan Yin

Toly Kournik

Tsvetomir Dimirov Dimitrov

Moshe Sulamy

The present disclosure is directed to a leader-based partially synchronous BFT SMR protocol that improves upon existing protocols by exhibiting two rounds of communication latency, linear authenticator complexity, and optimistic responsiveness. This is achieved through the novel use of an aggregate signature scheme as part of the protocol's view-change procedure.

Two-round byzantine fault tolerant (BFT) state machine replication (SMR) protocol with linear authenticator complexity and optimistic responsiveness

In some embodiments, a method sends first messages that request first information for a set of blocks of the blockchain to the N replicas. Each replica maintains a respective instance of the blockchain. Second messages is received from at least a portion of the N replicas. The second messages include the first information for the set of blocks from each respective instance of the blockchain that is maintained by the N replicas. The method analyzes the first information to determine whether a consensus on the first information is reached by a number of replicas. When consensus is reached, a request is sent to a replica for one or more blocks to back up to a backup blockchain and second information is received for the one or more blocks from the replica. The method uses the second information to back up the one or more blocks in the backup blockchain.

Byzantine fault tolerance protocol for backing up blockchains

In some embodiments, a method receives data for a block in a blockchain during a recovery process in which a recovering replica is recovering the block for a first instance of the blockchain being maintained by the recovering replica. The block is received from a second instance of the blockchain being maintained by a source replica. The method splits the data for the block into a plurality of chunks. Each chunk includes a portion of the data for the block; It is determined whether the recovering replica can recover a chunk in the plurality of chunks using a representation of the chunk. In response to determining that the recovering replica can recover the chunk, sending the representation of the chunk to the recovering replica. In response to determining that the recovering replica cannot recover the chunk, sending the data for the chunk to the recovering replica.

Traffic redundancy deduplication for blockchain recovery

In some embodiments, a method receives a share of a signature of a decision block from at least a portion of the plurality of replicas. The share of the signature being generated when a respective replica signs the decision block and the decision block includes a set of requests from a client for a service. A combined signature is created based on the share of the signature block from at least the portion of the plurality of replicas. The method broadcasts a message that includes the combined signature to the plurality of replicas. The plurality of replicas use the combined signature to determine whether to process the decision block for the service.

Byzantine agreement using communications having linear complexity

Techniques for implementing linear view-change in a Byzantine Fault Tolerant (BFT) protocol running on a distributed system comprising n replicas are provided. According to one set of embodiments, at a time of performing a view-change from a current view number v to a new view number v+1, a replica in the n replicas corresponding to a new proposer for new view number v+1 can generate a PREPARE message comprising a single COMMIT certificate, where the single COMMIT certificate is the highest COMMIT certificate the new proposer is aware of. The new proposer can then transmit the PREPARE message with the single COMMIT certificate to all other replicas in the n replicas.

Linear view-change BFT

A blockchain network include nodes that are configured as time sources. These time-source nodes broadcast respective updates of their local times to all nodes in the blockchain network. Each node computes a summary time value based on the received local time values so that each node uses the same summary time to maintain their respective copies of the blockchain.

Providing real-world time in a replicated state-machine environment

Techniques for implementing Byzantine fault tolerance with verifiable secret sharing at constant overhead are provided. In one set of embodiments, a client can determine a secret value s to be shared with N replicas in a distributed system, s being input data for a service operation provided by the N replicas. The client can further encode s into an f-degree polynomial P(x) where f corresponds to a maximum number of faulty replicas in the distributed system, evaluate P(x) at i for i=1 to N resulting in N evaluations P(i), generate at least one f-degree recovery polynomial R(x) based on a distributed pseudo-random function (DPRF) f(x), and evaluate R(x) at i for i=1 to N resulting in at least N evaluations R(i). The client can then invoke the service operation, the invoking comprising transmitting a message including P(i) and R(i) to each respective replica i.

Byzantine fault tolerance with verifiable secret sharing at constant overhead

The disclosure describes a failure-free execution agreement that includes n=3F+1 parties acting as replicas, and a number of parties acting as clients. One replica is designated as a primary. At most F replicas are presumed Byzantine faulty. The basic agreement protocol proceeds in three rounds: (1) client sends a request to the primary, who sends to all replicas; (2) each replica sends a threshold-part signature on hash to a first collector; (3) the collector combines the threshold-parts into a single signature and sends to all 3F+1 replicas which then commit and send to a second collector. The client proceeds when a signed block of requests arrives from the second collector.

The present teaching relates to concurrent database operation. In one example, a plurality of requests which includes a scan request to obtain first data associated with a plurality of first keys stored in a database is received concurrently. A global version number is updated upon receipt of the scan request. The first data associated with the plurality of first keys is obtained based on the updated global version number. The first data is provided in response to the scan request.

Method and system for concurrent database operation

In one embodiment, a search engine may generate and store a plurality of search index segments such that each of the search index segments is stored in a corresponding one of a plurality of heaps of memory. The plurality of search index segments may include inverted index segments mapping content to documents containing the content. A garbage collection module may release one or more heaps of the memory.

Recyclable private memory heaps for dynamic search indexes

In one embodiment, a set of lock and unlock instructions in a read phase of a computer-readable program is replaced with a first set of tracking instructions, wherein the first set of tracking instructions track a set of locked objects identifying objects that would have been locked by executing the set of lock and unlock instructions. A second set of tracking instructions is inserted into the read phase of the computer-readable program, wherein the second set of tracking instructions track a set of read objects indicating versions of objects that are read. Validation instructions are inserted into the computer-readable program, wherein the validation instructions validate that the versions of objects in the set of read objects have not changed since they were last read and lock the set of locked objects that would have been locked upon completing execution of the set of lock and unlock instructions. Update instructions are added to an update phase of the computer-readable program, where the update instructions increment a current version of an object each time a value of the object is updated or a lock of the object is released.

Automatic lock removal method for scalable synchronization in dynamic data structures

Techniques for implementing linear view-change with optimistic responsiveness in a BFT protocol running on a distributed system comprising n replicas are provided. According to one set of embodiments, the replicas can execute, during a view v of the BFT protocol, a first voting round comprising communicating instances of a first type of COMMIT certificate among the replicas. Further, when 2f+1 instances of the first type of COMMIT certificate associated with view v have been received by the replicas, the replicas can execute a second voting round comprising communicating instances of a second type of COMMIT certificate among the replicas. If 2f+1 instances of the second type of COMMIT certificate associated with view v are not received by the replicas within a predetermined timeout period, a view change can be initiated from view v to a view v+1.

Growing community of inventors

Holon, Israel

Guy Golan Gueta