# US 10,503,614 B2 · Byzantine agreement using communications having linear complexity > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,503,614 B2 - Document ID: US10503614B2 - Status: Granted - Kind: B2 - Application number: 15/653,178 - Filed: 2017-07-18 - Published: 2018-10-25 - Granted: 2019-12-10 - Earliest claimed: 2017-04-21 - Assignees: VMware, Inc. - Applicants: VMware, Inc. - Inventors: Ittai Abraham; Dahlia Malkhi; Alexander Spiegelman; Guy Golan Gueta - Web page: https://patentgrep.com/patent/US10503614B2 ## CPC - G06F 11/2028: {eliminating a faulty processor or activating a spare} - G06Q 20/065: {using e-cash} - G06F 11/1479: Generic software techniques for error detection or fault masking - G06F 11/2048: {where the redundant components share neither address space nor persistent storage} - G06Q 20/06: Private payment circuits, e.g. involving electronic currency used among participants of a common payment scheme - G06Q 20/382: {insuring higher security of transaction} - H04L 9/0618: {Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation} - H04L 9/3239: {involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD} - H04L 9/3255: {using group based signatures, e.g. ring or threshold signatures} - G06F 11/202: {where processing functionality is redundant (redundant communication control functionality G06F11/2005, redundant storage control functionality G06F11/2089)} - G06F 11/2041: {with more than one idle spare processing component} - G06Q 2220/00: Business processing using cryptography - H04L 2209/56: Financial cryptography, e.g. electronic payment or e-cash - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract 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. ## Claims ### Claim 1 A method of using a fault tolerant state machine replication protocol to update state in a replicated state machine comprising a plurality of computing devices, the method comprising: 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, each of the decision block signature shares being generated when one of the computing devices signs the decision block using said one of the computing devices' respective share of a private signing key; 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 sent one of the client requests, each such client receiving the execution acknowledgement message only once. ### Claim 2 (depends on 1) The method of claim 1, wherein each decision block signature share is generated by a respective one of the plurality of computing devices based on a received decision block of said respective one of the plurality of computing devices using a threshold signature signing technique. ### Claim 3 (depends on 1) The method of claim 1, further comprising the second collector broadcasting the execution acknowledgement message only when a predetermined number of the plurality of computing devices reach agreement as to their respective updated states. ### Claim 4 (depends on 1) The method of claim 1, further comprising the second collector generating the execution acknowledgement message using the plurality of digest signature shares received from the plurality of computing devices. ### Claim 5 (depends on 1) The method of claim 1, wherein the plurality of computing devices comprises 3f+2c+1 computing devices, where f is the number of allowable computing devices that are byzantine faulty and c is the number of allowable computing devices that have crashed or are slow. ### Claim 6 (depends on 5) The method of claim 5, wherein the commit proof message is produced based on 3f+c+1 distinct decision block signature shares. ### Claim 7 (depends on 5) The method of claim 5, wherein the execution acknowledgement message is based on f+c+1 distinct digest signature shares. ### Claim 8 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. ### Claim 9 (depends on 8) The non-transitory computer-readable storage medium of claim 8, wherein each decision block signature share is generated by a respective one of the plurality of computing devices based on a received decision block of said respective one of the plurality of computing devices using a threshold signature signing technique. ### Claim 10 (depends on 8) The non-transitory computer-readable storage medium of claim 8, wherein the computer executable instructions, which when executed by the second collector, further cause the second collector to broadcast the execution acknowledgement message only when a predetermined number of the plurality of computing devices reach agreement as to their respective updated states. ### Claim 11 (depends on 8) The non-transitory computer-readable storage medium of claim 8, wherein the computer executable instructions, which when executed by the second collector, further cause the second collector to generate the execution acknowledgement message using the plurality of digest signature shares received from the plurality of computing devices. ### Claim 12 (depends on 8) The non-transitory computer-readable storage medium of claim 8, wherein the plurality of computing devices comprises 3f+2c+1 computing devices, where f is the number of allowable computing devices that are byzantine faulty and c is the number of allowable computing devices that have crashed or are slow. ### Claim 13 (depends on 8) The non-transitory computer-readable storage medium of claim 8, wherein the commit proof message is produce based on 3f+c+1 distinct decision block signature shares. ### Claim 14 (depends on 8) The non-transitory computer-readable storage medium of claim 8, wherein the execution acknowledgement message is based on f+c+1 distinct digest signature shares. ### Claim 15 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. ### Claim 16 (depends on 15) The replicated state machine of claim 15, wherein each decision block signature share is generated by a respective one of the plurality of computing devices based on a received decision block of said respective one of the plurality of computing devices using a threshold signature signing technique. ### Claim 17 (depends on 15) The replicated state machine of claim 15, wherein the computer-readable storage medium in the second collector further comprises instructions for controlling the second collector to be operable to broadcasting the execution acknowledgement message only when a predetermined number of the plurality of computing devices reach agreement as to their respective updated states. ### Claim 18 (depends on 15) The replicated state machine of claim 15, wherein the computer-readable storage medium in the second collector further comprises instructions for controlling the second collector to be operable to generate the execution acknowledgement message using the plurality of digest signature shares received from the plurality of computing devices. ### Claim 19 (depends on 15) The replicated state machine of claim 15, wherein the plurality of computing devices comprises 3f+2c+1 computing devices, where f is the number of allowable computing devices that are byzantine faulty and c is the number of allowable computing devices that have crashed or are slow.