Byzantine agreement using communications having linear complexity

Abstract

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.

1 . A method comprising:
 selecting, by a client, a replica from among a plurality of replicas that provides a replicated service to the client;   transmitting, by the client, a query to the selected replica;   in response to the transmitting, receiving, by the client, a read certificate from the selected replica that includes a sequence number, an answer to the query, a proof indicating that the answer is correct with respect to a state of the replicated service that is associated with the sequence number, and a signature digest for the state;   upon verifying the proof, accepting, by the client, the answer as a valid response; and   upon failing to verify the proof, re-transmitting, by the client, the query to each of the plurality of replicas.   
     
     
         2 . The method of  claim 1  wherein the query is a read-only query that does not change any state information maintained by the replicated service. 
     
     
         3 . The method of  claim 1  wherein the proof is a Merkle-based proof and wherein the signature digest is a Merkle hash of the state. 
     
     
         4 . The method of  claim 1  wherein the selected replica is chosen randomly from among the plurality of replicas. 
     
     
         5 . The method of  claim 1  wherein the sequence number corresponds to a latest sequence of requests executed by the plurality of replicas. 
     
     
         6 . The method of  claim 1  wherein the proof further indicates that the query was executed as part of a sequence of requests identified by the sequence number that resulted in the state. 
     
     
         7 . The method of  claim 1  wherein verifying the proof comprises:
 verifying that the proof indicates that the query was executed in a decision block identified by the sequence number; 
 verifying that the signature digest is a valid digest of the state; and 
 verifying that the answer is a valid return value of the query. 
 
     
     
         8 . A non-transitory computer readable storage medium having stored thereon program code executable by a client, the client being communicatively coupled with a plurality of replicas providing a replicated service, the program code embodying a method comprising:
 selecting a replica from among the plurality of replicas;   transmitting a query to the selected replica;   in response to the transmitting, receiving a read certificate from the selected replica that includes a sequence number, an answer to the query, a proof indicating that the answer is correct with respect to a state of the replicated service that is associated with the sequence number, and a signature digest for the state;   upon verifying the proof, accepting the answer as a valid response; and   upon failing to verify the proof, re-transmitting the query to each of the plurality of replicas.   
     
     
         9 . The non-transitory computer readable storage medium of  claim 8  wherein the query is a read-only query that does not change any state information maintained by the replicated service. 
     
     
         10 . The non-transitory computer readable storage medium of  claim 8  wherein the proof is a Merkle-based proof and wherein the signature digest is a Merkle hash of the state. 
     
     
         11 . The non-transitory computer readable storage medium of  claim 8  wherein the selected replica is chosen randomly from among the plurality of replicas. 
     
     
         12 . The non-transitory computer readable storage medium of  claim 8  wherein the sequence number corresponds to a latest sequence of requests executed by the plurality of replicas. 
     
     
         13 . The non-transitory computer readable storage medium of  claim 8  wherein the proof further indicates that the query was executed as part of a sequence of requests identified by the sequence number that resulted in the state. 
     
     
         14 . The non-transitory computer readable storage medium of  claim 8  wherein verifying the proof comprises:
 verifying that the proof indicates that the query was executed in a decision block identified by the sequence number; 
 verifying that the signature digest is a valid digest of the state; and 
 verifying that the answer is a valid return value of the query. 
 
     
     
         15 . A client that is communicatively coupled with a plurality of replicas provided a replicated service, the client comprising:
 a processor; and   a non-transitory computer readable medium having stored thereon program code that, when executed, causes the processor to:
 select a replica from among the plurality of replicas; 
 transmit a query to the selected replica; 
 in response to the transmitting, receive a read certificate from the selected replica that includes a sequence number, an answer to the query, a proof indicating that the answer is correct with respect to a state of the replicated service that is associated with the sequence number, and a signature digest for the state; 
 upon verifying the proof, accept the answer as a valid response; and 
 upon failing to verify the proof, re-transmit the query to each of the plurality of replicas. 
   
     
     
         16 . The client of  claim 15  wherein the query is a read-only query that does not change any state information maintained by the replicated service. 
     
     
         17 . The client of  claim 15  wherein the proof is a Merkle-based proof and wherein the signature digest is a Merkle hash of the state. 
     
     
         18 . The client of  claim 15  wherein the selected replica is chosen randomly from among the plurality of replicas. 
     
     
         19 . The client of  claim 15  wherein the sequence number corresponds to a latest sequence of requests executed by the plurality of replicas. 
     
     
         20 . The client of  claim 15  wherein the proof further indicates that the query was executed as part of a sequence of requests identified by the sequence number that resulted in the state. 
     
     
         21 . The client of  claim 15  wherein the program code that causes the processor to verify the proof comprises program code that causes the processor to:
 verify that the proof indicates that the query was executed in a decision block identified by the sequence number; 
 verify that the signature digest is a valid digest of the state; and 
 verify that the answer is a valid.