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.