Collaborative transaction notarization in a Byzantine computing environment
View Patent ↗A collaboration of miners cooperatively notarizes transactions to be added to a distributed ledger. A solution space is identified for notarizing the transactions, such as an integer space that may contain a nonce that, when hashed with the transactions or block, yields a hash value that satisfies specified criteria. The solution space is apportioned so that each miner has a discrete slice of the space in which to search for the nonce: different slices may be of equal or different sizes. All miners search their slices in parallel. If no miner announces success (e.g., within a specified time period), the solution space shifts so that each miner becomes responsible for a different slice. All miners may be rewarded when a solution is found, but a miner that failed to discover the nonce, despite searching a slice that contained it, is penalized and may not share in the reward.
1 . A method, comprising:
receiving a set of digital transactions at a collaboration of multiple miners, wherein each miner comprises one or more computer systems;
assigning to each miner a distinct slice of a solution space for discovering a solution for notarizing the set of digital transactions, each slice of the solution space being non-overlapping with the slices of the solution space assigned to other miners such that each miner is responsible for searching only its assigned slice of the solution space;
during each of one or more rounds:
at each miner, searching for a solution only in the assigned slice of the solution space by: generating candidate values within the assigned slice, hashing each candidate value with the set of digital transactions or a representation of the set of digital transactions to obtain a hash value, and determining whether the hash value meets predetermined criteria for notarizing the set of digital transactions;
when one of the miners discovers the solution, communicating a message identifying the solution to the other miners;
when one of the miners completes searching its assigned slice without discovering the solution, communicating a failure message to the other miners;
for each miner, determining whether the solution was discovered during the round based on receipt of the message identifying the solution from another miner or discovery of the solution locally, and, when the solution is not discovered during the round and after receipt of the failure message from at least a majority of the miners or expiration of a timer that limits a duration of the round, shifting the solution space by reassigning to each miner a different slice of the solution space for a next round; and
when the solution is discovered and verified by the miners based on the message identifying the solution:
storing the set of digital transactions in a distributed ledger; and
if the solution space was shifted at least once before the solution was discovered, penalizing one or more miners that failed to discover the solution while working in slices of the solution space that contained the solution.
2 . The method of claim 1 , wherein penalizing a miner comprises one or more of:
omitting the miner from a share of a reward resulting from discovery of the solution; and
withdrawing from a monetary reserve associated with the miner.
3 . The method of claim 1 , further comprising, during each of the one or more rounds:
at each miner, searching for the solution only in the assigned slice of the solution space.
4 . The method of claim 1 , further comprising, when the solution is discovered:
distributing a reward among some or all of the multiple miners.
5 . The method of claim 1 , wherein receiving a set of digital transactions comprises:
receiving the set of digital transactions from a source selected by a current leader of the collaboration.
6 . The method of claim 1 , wherein receiving a set of digital transactions comprises:
receiving the set of digital transactions from a group of authenticators that executed a consensus protocol to commit the digital transactions; and
receiving proof of commitment of the digital transactions.
7 . The method of claim 1 , wherein a slice of the solution space assigned to a given miner is proportional to the given miner's stake in the collaboration.
8 . The method of claim 1 , wherein all miners' assigned slices are equal in size.
9 . The method of claim 1 , wherein the candidate values comprise a nonce that, when hashed with the set of digital transactions or the representation of the set of digital transactions, yields the hash value meeting the predetermined criteria for notarizing the set of digital transactions.
10 . A non-transitory computer-readable medium storing instructions that, when executed by a processor, cause the processor to perform a method comprising:
receiving a set of digital transactions at a collaboration of multiple miners, wherein each miner comprises one or more computer systems;
assigning to each miner a distinct slice of a solution space for discovering a solution for notarizing the set of digital transactions, each slice of the solution space being non-overlapping with the slices of the solution space assigned to other miners such that each miner is responsible for searching only its assigned slice of the solution space;
during each of one or more rounds:
at each miner, searching for a solution only in the assigned slice of the solution space by: generating candidate values within the assigned slice, hashing each candidate value with the set of digital transactions or a representation of the set of digital transactions to obtain a hash value, and determining whether the hash value meets predetermined criteria for notarizing the set of digital transactions;
when one of the miners discovers the solution, communicating a message identifying the solution to the other miners;
when one of the miners completes searching its assigned slice without discovering the solution, communicating a failure message to the other miners;
for each miner, determining whether the solution was discovered during the round based on receipt of the message identifying the solution from another miner or discovery of the solution locally, and, when the solution is not discovered during the round and after receipt of the failure message from at least a majority of the miners or expiration of a timer that limits a duration of the round, shifting the solution space by reassigning to each miner a different slice of the solution space for a next round; and
when the solution is discovered and verified by the miners based on the message identifying the solution:
storing the set of digital transactions in a distributed ledger; and
if the solution space was shifted at least once before the solution was discovered, penalizing one or more miners that failed to discover the solution while working in slices of the solution space that contained the solution.
11 . The non-transitory computer-readable medium of claim 10 , wherein penalizing a miner comprises one or more of:
omitting the miner from a share of a reward resulting from discovery of the solution; and
withdrawing from a monetary reserve associated with the miner.
12 . The non-transitory computer-readable medium of claim 10 , the method further comprising, during each of the one or more rounds:
at each miner, searching for the solution only in the assigned slice of the solution space.
13 . The non-transitory computer-readable medium of claim 10 , the method further comprising, when the solution is discovered:
distributing a reward among some or all of the multiple miners.
14 . The non-transitory computer-readable medium of claim 10 , wherein receiving a set of digital transactions comprises:
receiving the set of digital transactions from a source selected by a current leader of the collaboration.
15 . The non-transitory computer-readable medium of claim 10 , wherein receiving a set of digital transactions comprises:
receiving the set of digital transactions from a group of authenticators that executed a consensus protocol to commit the digital transactions; and
receiving proof of commitment of the digital transactions.
16 . The non-transitory computer-readable medium of claim 10 , wherein a slice of the solution space assigned to a given miner is proportional to the given miner's stake in the collaboration.
17 . The non-transitory computer-readable medium of claim 10 , wherein all miners' assigned slices are equal in size.
18 . The non-transitory computer-readable medium of claim 10 , wherein the candidate values comprise a nonce that, when hashed with the set of digital transactions or the representation of the set of digital transactions, yields the hash value meeting the predetermined criteria for notarizing the set of digital transactions.
19 . A distributed computing system, comprising:
multiple collaborative miner systems, each miner system comprising:
one or more processors; and
memory storing instructions that, when executed by the one or more processors, cause the miner system to:
receive a set of digital transactions;
adopt for each miner system a distinct slice of a solution space for discovering a solution for notarizing the set of digital transactions, each slice of the solution space being non-overlapping with the slices of the solution space assigned to other miner systems such that each miner system is responsible for searching only its assigned slice of the solution space;
during each of one or more rounds:
at each miner system, search for a solution only in the assigned slice of the solution space by: generating candidate values within the assigned slice, hash each candidate value with the set of digital transactions or a representation of the set of digital transactions to obtain a hash value, and determine whether the hash value meets predetermined criteria for notarizing the set of digital transactions;
when one of the miner systems discovers the solution, communicate a message identifying the solution to the other miner systems;
when one of the miner systems completes searching its assigned slice without discovering the solution, communicate a failure message to the other miner systems;
for each miner system, determine whether the solution was discovered during the round based on receipt of the message identifying the solution from another miner or discovery of the solution locally, and, when the solution is not discovered during the round and after receipt of the failure message from at least a majority of the miners or expiration of a timer that limits a duration of the round, shift the solution space by adopting for each miner system a different slice of the solution space for a next round; and
when the solution is discovered and verified by the miner systems based on the message identifying the solution:
store the set of digital transactions in a distributed ledger; and
if the solution space was shifted at least once before the solution was discovered, penalize one or more miner systems that failed to discover the solution while working in slices of the solution space that contained the solution.
20 . The distributed computing system of claim 19 , wherein penalizing a miner comprises one or more of:
omitting the miner from a share of a reward resulting from discovery of the solution; and
withdrawing from a monetary reserve associated with the miner.
21 . The distributed computing system of claim 19 , wherein each miner system memory further stores instructions that, when executed by the one or more processors, cause the miner system to, during each of the one or more rounds:
at each miner, search for the solution only in the assigned slice of the solution space.
22 . The distributed computing system of claim 19 , wherein each miner system memory further stores instructions that, when executed by the one or more processors, cause the miner system to, when the solution is discovered:
distribute a reward among some or all of the multiple miners.
23 . The distributed computing system of claim 19 , wherein receiving a set of digital transactions comprises:
receiving the set of digital transactions from a source selected by a current leader of the collaboration.
24 . The distributed computing system of claim 19 , wherein receiving a set of digital transactions comprises:
receiving the set of digital transactions from a group of authenticators that executed a consensus protocol to commit the digital transactions; and
receiving proof of commitment of the digital transactions.
25 . The distributed computing system of claim 19 , wherein a slice of the solution space assigned to a given miner is proportional to the given miner's stake in the collaboration.
26 . The distributed computing system of claim 19 , wherein all miners' assigned slices are equal in size.
27 . The distributed computing system of claim 19 , wherein the candidate values comprise a nonce that, when hashed with the set of digital transactions or the representation of the set of digital transactions, yields the hash value meeting the predetermined criteria for notarizing the set of digital transactions.