US-12626231-B2 - Collaborative transaction notarization in a Byzantine computing environment

US12626231B2US 12626231 B2US12626231 B2US 12626231B2US-12626231-B2

Abstract

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.

Inventors

Mohammad Sadoghi Hamedani

Assignees

THE REGENTS OF THE UNIVERSITY OF CALIFORNIA

Dates

Publication Date: 20260512
Application Date: 20220914

Claims (20)

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.

Description

RELATED APPLICATION(S) This application claims priority to U.S. Provisional Patent Application 63/245,699, filed Sep. 17, 2021, which is incorporated herein by reference. BACKGROUND This disclosure relates to the field of distributed computing. More particularly, systems and methods are provided for collaboratively notarizing transactions in a distributed ledger within a Byzantine computing environment. Distributed ledger data systems such as blockchains provide ordered histories of transactions in the form of linked blocks. Each block memorializes one or more transactions in a manner that makes the recorded transactions secure, immutable, and non-repudiable, and a transaction is added to a block only after being notarized. Blocks of transactions are cryptographically linked to form a chain, thereby making it is extremely difficult to replace an existing block or alter a transaction recorded within a block. Currently, notarization of a transaction or a block of transactions is often conducted in a competitive manner using a protocol such as Proof-of-Work (PoW), wherein multiple participants simultaneously attempt to perform the notarization, but only one entity is successful. That participant may receive a monetary reward in the form of digital currency. The PoW protocol requires the participants to perform a great deal of computer processing and consume significant energy, most of which is wasted because only one participant is successful and is rewarded. Thus, performing notarization with a protocol such as PoW is very inefficient. Further, distributed ledger systems are often implemented within a Byzantine computing environment. In this type of environment, a malicious participant may attempt to prevent a particular client entity from accessing the distributed data, prevent initiation or completion of some transactions (e.g., transactions of a particular client entity), obstruct the processing of a transaction, and/or cause inconsistency or disruption within the distributed data. A faulty but not necessarily malicious participant may also impede the processing of transactions. Data may be replicated to enhance system integrity and resiliency, but complexity may increase commensurately in order to keep all replicas current. In addition, full replication of a set of data may provide significant resiliency but will be difficult to scale as the amount of stored data grows. Thus, there is a need for an efficient manner of notarizing great numbers of transactions while ensuring data integrity within a Byzantine environment. In particular, there is a need for notarizing transactions with high throughput yet without wasteful consumption of computing resources. SUMMARY In some embodiments, systems and methods are provided for collaboratively notarizing or settling transactions for addition to a distributed ledger. In these embodiments, a Power-of-Collaboration (PoC) protocol is provided in which entities (e.g., miners) that attempt to solve the notarization do so in a cooperative manner. All participants may be rewarded when a solution is found, although a participant that fails to cooperate may be penalized or punished. In a typical notarization problem, the goal is to identify a nonce that, when hashed with other information to be included in a new ledger block, yields a hash value having a specified number of leading zeros. Other types of compute-intensive problems may be employed in other notarization environments. In these embodiments, the solution space in which the nonce is searched for is divided into N slices in an environment in which N miners collaborate. Slices may be of equal size or different sizes. Each miner attempts to solve the notarization using its slice and, if successful, broadcasts the result (e.g., the nonce, the completed block) to all miners to allow verification. Assuming its success is verified, the block is added to a distributed ledger to record the set of transactions, all miners share a reward (e.g., in digital currency), and the client or source of the set of transactions is notified. Also, if a default or specified source of transactions is not already specified, the successful miner becomes titular leader of the miners and has the option of selecting the next set of transactions. Transactions may be received by a collaboration of miners directly from clients and/or from other sources. For example, a commitment protocol such as Practical Byzantine Fault Tolerance (PBFT) may be conducted on a transaction or set of transactions in order to obtain consensus as to the authenticity or validity of the transactions (and add the transaction(s)) to a first ledger), after which they may be forwarded to the PoC miners for notarization and minting (to add the transaction(s) to a second ledger). A participant in the commitment process may also act as a miner, and vice versa, depending on the computing power and resources of the entities. However, a participant in the commitment process must b