System and Method for Scalable Proof-of-Work Based Decentralized Crypto Ledgers
Publication Date: 2016-May-19
The IP.com Prior Art Database
In this disclosure, we describe a PoW-based cryptocurrency protocol that is designed to allow for parallelism (i.e., forks) in the transaction ledger as well as merges of parallel forks --- and, consequently, scale well. In a nutshell, our new ledger is a directed acyclic graph (DAG) data structure that allows for forks and merges, in contrast to a linear blockchain which does not allow forks, or tree-based blockchains that allow forks but do not allow merges (and hence have limited practical appeal). In case of conflicting transactions, our solution, unlike previous solutions based on DAGs, uses a solution to the classical Maximum Weight Independent Set problem (MWIS) to select the subgraph without conflicts - therefore preserving the maximum number of non-conflicting transactions on the ledger.
Page 01 of 11
of- System and Method for Scalable Proof -
This invention solves the problem of scaling-out proof-of-work (PoW) based cryptocurrencies (such as Bitcoin). Currently, Bitcoin and similar PoW-based cryptocurrencies fundamentally rely on a blockchain that represents a transaction ledger. The blockchain basically totally orders all transactions, as forks in blockchain are explicitly disallowed, with the goal of preventing double spending attacks. This total order across all transactions, however, poses severe limitations on scalability (in the number of transactions per time unit) these cryptocurrencies can sustain. Fortunately, in practice, establishing total order across all transactions is not at all necessary: for example, there is no reason why the transaction record of Alice buying a coffee in her favorite Paris' café would necessarily need to be ordered with the transaction record corresponding to Bob's visit to a restaurant in New York.
Scaling cryptocurrencies such as Bitcoin is a major problem, very often cited as a critical impediment to future adoption of virtual cryptocurrencies. Our invention allows for a scalable proof-of-work based cryptocurrency ledger.
In this invention, we describe the first PoW-based cryptocurrency protocol that is designed to allow for parallelism (i.e., forks) in the transaction ledger as well as merges of parallel forks --- and, consequently, scale well.
In a nutshell, our new ledger is a directed acyclic graph (DAG) data structure that allows for forks and merges, in contrast to a linear blockchain which does not allow forks, or tree-based blockchains that allow forks but do not allow merges (and hence have limited practical appeal). Forks in our new ledger are tolerated (and encouraged) so long as they contain non-conflicting transactions. Only transactions that conflict, such as the double-spending attempts (where Alice tries to spend her virtual coins in two places at approximately the same time), are required to be totally ordered by the our new ledger. In case blocks (i.e., sets of transactions) containing conflicting transactions are mined (i.e., included in the ledger) on different forks, our ledger resorts to a generalized variant of the classical Bitcoin conflict resolution protocol, favoring ``heavier'' blocks, i.e., those that subsume higher amount of previous work. In contrast, the classical variant of this conflict resolution protocol is applied today in Bitcoin for all forks .
The core idea of the invention is the scheme that allows merges of different forks. In short, a miner merging two (or more) forks would not extend a hashchain on a particular fork (like in previous proposals) but would extend two (or more) forks at the same time with a merge block which includes a hash tree that effectively merges the input forks extending every tail block of input forks. The merge block however would work only if there are non-conflicting transactions on the merged forks. The "weigh...