Byzantine agreement using communications having linear complexity

A non-transitory computer-readable storage medium having stored thereon computer executable instructions, which when executed among a plurality of computer devices that constitute a replicated state machine, cause the plurality of computer devices to update state in the replicated state machine using a fault tolerant state machine replication protocol, including:

• receiving, by a primary among the plurality of computing devices, a plurality of client requests sent from one or more clients separate from the plurality of computing devices;
• broadcasting, by the primary among the plurality of computer devices, a decision block to the plurality of computer devices, the decision block comprising the plurality of client requests;
• receiving, by a first collector among the plurality of computer devices, a plurality of decision block signature shares from the plurality of computer devices;
• broadcasting, by the first collector, a commit proof message to the plurality of computer devices produced using the received decision block signature shares, wherein each computer device that receives the commit proof message executes the plurality of client requests in said each computing device's received decision block thereby updating said each computing device's state;
• receiving, by a second collector among the plurality of computer devices, a plurality of digest signature shares from the plurality of computer devices, each digest signature share generated by a respective one of the plurality of computer devices based on an updated state of said respective one of the plurality of computing devices using a threshold signature signing technique;
• and
• broadcasting, by the second collector, an execution acknowledgement message to the plurality of computer devices and to each client that sent one of the client requests, each such client receiving the execution acknowledgement message only once.

A replicated state machine comprising:

• a plurality of computing devices;
• and
• each computing device having a computer-readable storage medium comprising instructions for controlling the computing device to be operable to update state in the replicated state machine using a fault tolerant state machine replication protocol, including:
• receiving, by a primary among the plurality of computing devices, a plurality of client requests sent from one or more clients separate from the plurality of computing devices;
• broadcasting, by the primary among the plurality of computing devices, a decision block to the plurality of computing devices, the decision block comprising the plurality of client requests;
• receiving, by a first collector among the plurality of computing devices, a plurality of decision block signature shares from the plurality of computing devices;
• broadcasting, by the first collector, a commit proof message to the plurality of computing devices produced using the received decision block signature shares, wherein each computing device that receives the commit proof message executes the plurality of client requests in said each computing device's received decision block thereby updating said each computing device's state;
• receiving, by a second collector among the plurality of computing devices, a plurality of digest signature shares from the plurality of computing devices, each digest signature share generated by a respective one of the plurality of computing devices based on an updated state of said respective one of the plurality of computing devices using a threshold signature signing technique;
• and
• broadcasting, by the second collector, an execution acknowledgement message to the plurality of computing devices and to each client that corresponds to one of the client requests, each such client receiving the execution acknowledgement message only once.