An explicit approach using mimblewimble and sharding for high throughput and security
Abstract — Since the advent of cryptocurrencies and their popularity, key factors of adoption remain the same over the years, namely security, decentralization, and scalability. Bitcoin — the most widely accepted cryptocurrency in recent years– has been able provide a permissionless environment and security yet has failed drastically to scale. Bitcoin’s blockchain has grown outrageously in size while processing around 7 transactions per second. With this low throughput and inability to scale, people have also understood that the Bitcoin network has failed on another front maintain the anonymity of the user, which has given businesses another reason to wait until the technology matures enough for any adoption. The growing trend of new technologies such as smart contracts and the recent drive of businesses to use blockchain requires serious changes to the current infrastructure for any real-world applications. In this paper we discuss about the recent projects working towards this problem with different scalability and security solutions, later we draw a comparison between these solutions. Finally we propose our solution whose core design is based on mimblewimble and sharding, an explicit approach using mimblewimble and sharding for high throughput and security.
Keywords — Blockchain, Bitcoin, Mimblewimble, Sharding, Inspector Node.
I. INTRODUCTION
The Bitcoin blockchain has limitations amounted to it’s on- chain settlement capacity, and the community around the world has proposed various on- chain and off- chain methods to improve on these limitations. But all these proposals come with certain tradeoffs that won’t be a long shot solution for the problems in hand. Generally, these solutions fall into categories that require either a hard fork, a soft fork, a sidechain implementation, or off- chain channels. But the risk of centralization, outdated nodes, empty blocks, and overly complex architecture are some acceptable tradeoff that comes with these methods. However, we see that combining some of these methods can minimize the tradeoffs and reduce the limitations of the system. In this paper, we introduce one such proposal that combines mimblewimble and sharding to improve scalability, as well as provide a platform for confidential transactions. We approach scalability not just as a throughput issue, but also as a storage pruning issue.
In section II, we discuss what is mimblewimble and how it works., We further discuss some of the implementations of this protocol. We will discuss sharding in section V, how sharding works, and what popular proposals are in the market. Both Mimblewimble and sharding solve different problems, so we drive a comparison between the two by looking at the functionality and tradeoffs in section VIII. Further, in section IX, we discuss how the combination of mimblewimble and sharding produces a more functional protocol with fewer tradeoffs.
II. WHAT IS MIMBLEWIMBLE ?
Mimblewimble was introduced in July 2016 with a paper dropped on the #bitcoin-wizards IRC Channel published by an anonymous user with the pseudonym Tom Elvis Jedusor. Mimblewimble is a protocol that proposes a functional way to carry out confidential transactions while minimizing the blockchain size. The paper combines the core concepts of Coin-Join and cut-through transactions proposed by Dr. Greg Maxwell in the protocol with strong cryptographic primitives. GRIN came out as an open source project implementing Mimblewimble as the core protocol to provide better scalability, privacy, and fungibility. Since then only one other project, Beam, has attempted to build on Mimblewimble while trying to improve the basic limitations with the protocol and improve it with better functionality. The name of this protocol comes from the ‘Harry Potter’ book series by J.K. Rowling. Mimblewimble is a “Tongue-Tying Curse” used to stop someone from spilling out secrets. This serves as an analogy for confidential transactions used in the blockchain implementation of mimblewimble.
III. HOW DOES IT WORK?
A. Confidential Transactions
Confidential Transactions ensures the privacy of the user by hiding and binding individual transactions, making it impossible for someone to find out any information about a single transaction. Such kind of validation of transactions in mimblewimble depends on
I. Zero- sum proofs –- The difference between the sum of all the outputs and all the inputs is always zero, hence proving that no new funds are produced from thin air.
II. Possession of private keys –- Private keys used for validation in mimblewimble are not the keys used for signing the transactions, called “transaction kernel” and will be discussed later.
Let’s suppose Bob wants to send 3 BTC to Alice from the 4 BTC he received earlier from John, we know that for any transaction to be valid the sum of outputs minus the sum of inputs should be zero, implying no new coins were generated. We express the outputs and inputs in the above transaction
OAlice + OBOB — IJohn = 0, as v1,v2, v3 respectively.
Now we see in this example that v1*H +v2*H= v3*H, where H is an elliptic curve,
In this case, if one of the transaction values is guessed by someone, it would completely jeopardize the privacy of the user. That is why it is suggested in the original Bitcoin whitepaper to change private keys for every transaction in order to preserve anonymity. But this is a long and tiresome process which requires a continuous effort from the user, which is far from common user behavior. This can be solved with Mimblewimble, by introducing another private key ‘r’ (also called the “blinding factor”) and another elliptic curve F. Considering the above example the new equation is
(r1*G+v1*H) + (r2*G+v2*H) = (r3*G+v3*H)
This particular expression used here i.e r*G+ v*H is called “ Pedersen Commitment”. Using public key r*G makes it impossible for someone to guess r or v individually, following the elliptic curve .
Mimblewimble introduces signatures attached to each transaction which needs to be validated by all transacting parties, these signature are the excess sum of the blinding factors, and are known as the “transaction kernel.” The transaction kernel protect users from fraud by other transacting parties.
There are two other important terms in mimblewimble that we won’t be discussing in detail in this paper which are namely “kernel offset” and “range proofs.”
I. Kernel offset protects someone from guessing a transaction using the outputs, the inputs, and the transaction kernel., It is just another private key that is added to the transaction kernel to verify the zero sum.
II. Range proofs are used to verify that transaction value i.e ‘v’ is non-negative and hence no funds are generated during the transactions.
B. Cut Through
Cut through facilitates a smaller blockchain size and faster syncing of new nodes joining the network. Cut through removes all the transaction structure by combining multiple transaction into a single transaction. With this, all intermediate transactions are represented by their transaction kernels, while all outputs are so large that they can’t be differentiated/excluded from the constituent outputs.
IV. IMPLEMENTATIONS OF MIMBLEWIMBLE
A. Beam
Beam came into existence in early 2018 and is delivers scalable confidential blockchain based on Mimblewimble. Beam provides an infrastructure for the user with
1. Control over privacy
2. No additional setup
3. Equihash proof-of-work for mining
4. Atomic swaps, escrow transactions, and time locked transaction support
5. Improved scalable due to its more compact blockchain size.
During its first year beam has launched its position paper and testnets with cross- platform support.
B. Grin
Grin is the first project that came into existence, after mimblewimble was introduced to the world. Grin is based on Mimblewimble and has recently launched its fourth testnet.
Grin is a project in-progress, dedicated towards providing:
1. A clean and minimal implementation
2. A smooth curve for difficulty adjustment
3. Cuckoo cycle proof- of- work
4. Faster block time
5. A fixed block reward with a decreasing dilution.
V. WHAT IS SHARDING?
Ethereum developers proposed another method to scale the blockchain by sharding, dividing the network and transactions into shards, where every shard has its own history of transactions and states. That is, the nodes in the network are responsible for validating only those transactions that are assigned to their shard. Such an arrangement allows parallel processing of the transactions in different shards,. hence increasing the overall throughput of the system. Since the introduction of sharding in blockchain certain new proposals have been made to implement sharding. We will see some of these proposal later in section VII.
VI. HOW SHARDING WORK?
Network Sharding
All the nodes in the network are assigned to different shards by a random function, avoiding any majority from being formed. Once the nodes are allocated to different shards, nodes are responsible to process transactions allocated to that shard and to maintain the shard’s current state and history of transactions. The nodes also needs to have 2⁄3 rd signatures from other shards in order to prove their legitimacy . The nodes are shuffled among other shards after a certain period of time to avoid any kind of malicious activity.
After all the transactions are processed in a certain shard, the transaction data and state history for a that shard is updated on the main chain by specific nodes called “supernodes.” This is a continuous process that updates all transaction data and state history from all the shards on the main chain.
Cross- Shard Transactions
Another important feature of sharding is cross- shard transactions, that are possible by using “receipts” to handles the whole process with ease. Receipts are generated when party 1 in shard 1 wants to transact with party 2 in another shard. To carry out such an transaction, the first transaction is sent to shard 1, and party 1 balance is updated and a receipt is generated and added to the merkle root of the shard. This receipt is then shared with shard 2, which checks the receipt for “spent” or “unspent” values, if unspent the balance is updated in the party 2 account and the receipt is marked as spent and added to merkle root of shard 2.
VII. SOME IMPLEMENTATION OF SHARDING
A. Omniledger
Omniledger implements sharding in its design to provide a scalable blockchain with the same capability as centralised systems like Visa, without compromising security, and in a permissionless environment. Omniledger use the unique function “RandHound” to generate randomness for nodes assignment to shards. A different BFT- like consensus mechanism, “ByzcoinX,” is used by Omniledger to achieve consensus in the network.
B. Zilliqa
Zilliqa uses sharding with unique consensus protocol called “PBFT” that provides quick finality without confirmation. It uses a unique model of using two different kind of actors in sharding for better security: nodes assigned in shards, and nodes in the Directory Service Committee (DSG), responsible for final block submission. It uses EC-Schnorr multisig to combine multiple signatures and reduce block size.
VIII. COMPARISON BETWEEN MIMBLEWIMBLE AND SHARDING
Tradeoffs in Mimblewimble
1) With mimblewimble, the blockchain size decreases drastically but the throughput of the network is limited. Hence even after significant storage pruning, Mimblewimble doesn’t have any comparable transaction rates to centralized systems like Visa. This limits the use of Mimblewimble- based currencies to as a store-of for value use instead of a means of exchange.
2) Mimblewimble doesn’t come with any scripting language, hence smart- contract functionality is unavailable. This is a big setback when everyone is moving towards DApps and DAO’s.
3) Mimblewimble introduces strong measures for privacy, but simultaneously requires a method to regulate identities to avert any illegal use of the network.
4) The CoinJoin property of Mimblewimble happens when the miner combines all the transactions before any of that all of these transactions are passed from one node to another. If a malicious node is placed in the network, it can figure out the inputs and outputs before CoinJoin is executed.
5) Using proof- of- work (POW) as the consensus method for Mimblewimble, has significant performance deficiencies associated with it.
Tradeoffs with sharding
1) With sharding parallelization is possible in different shards (i.e transactions can be processed parallely across shards) hence improving the overall throughput of the network. Even though with high throughput, the size of the blockchain remains the same, thus storage pruning remains a problem with sharding.
2) Business logic in smart contracts and access pattern of users are not private, for this reason intellectual property and privacy of users remain at stake.
3) Sharding doesn’t support cross- chain transactions and applications
4) Inefficient consensus methods like proof-of-work are used in sharding, producing overall latency in the network.
5) Cross- shard transactions and processing are still a challenge with major implementation with sharding.
IX. OUR SOLUTION
Both Mimblewimble and sharding are solutions that provide great functionality and increase the efficiency of the current blockchain infrastructure. Yet we saw certain tradeoffs with these proposals that make them less attractive.
In our solution we combine Mimblewimble and sharding, reducing the problems with these individual proposals significantly while providing same or better functionality.
We propose a sharded blockchain that runs with the Mimblewimble protocol.
Network Sharding
Network sharding divides the network of mining nodes into shards. In our solution, first a set of nodes called the “inspector nodes” are elected by solving a proof-of-work problem. These inspectors nodes then allocate nodes to the shards, and are eventually themselves allocated to different shard (i.e one inspector node in each shard) by using a cryptographic random function.
Inspector nodes
As explained above, inspectors nodes are elected by solving a proof-of-work puzzle, and eventually forming an inspector chain block. Once the nodes are able to find the valid nonce, the first node to do so proposes the block header that is broadcasted among the nodes in the inspector node network, and validated by all the nodes in the inspector node network. If the block gets more than 2⁄3 rd acceptance , the block is published. All other nodes that mined that block successfully up to a certain fixed number n –that is the number of shards– are elected as the part of inspector node network. The first one to mine the inspector chain block is the leader of the inspector node network.
Once the inspector nodes are elected, they are responsible to assign nodes to different shards. As there are a fixed number of the shards and same number of nodes in each shard,. assigning of nodes is done by using another proof-of-work puzzle. All the nodes up to a certain number that successfully find its nonce are assigned to different shards.
After all the nodes are assigned to shards, each inspector node is required to be distributed to each shard. For this we use a “Verifiable Random Function” (VRF) of inspector nodes to randomly assign them to the next shard, every time a node needs to move to its next shard it needs to compute its VRF output by using the outputs of the previous computation. All new inspector nodes are required to stake a certain amount of tokens before computing VRF output for their assignment to a shard.
Adding new nodes to the inspector network and shards
After every Ipn(Inspector node network) epoch, a new proof-of-work puzzle is introduced so that nodes cannot compute it in advance. All new nodes that want to join the inspector node network, have to solve this puzzle to find a valid nonce. The first node first to solve the puzzle is elected as the leader and new member of the inspector node network. And the oldest member of the network is phased out. Such a model ensures that no majority is formed and the inspector nodes continuously change. Similarly all new nodes for the shards are elected by solving another proof-of-work puzzle.
Transaction sharding and privacy
Once a new transaction is originated, it is assigned to a certain shard using a cryptographic random function. After a shard is identified, the transaction is multicasted to some of the nodes of this shard. The nodes on the shard follow the Mimblewimble protocol and verifies the signatures and zero- sum of all the transactions. When the consensus among the shard is reached the inspector node proposes a temporary “micro” block with at least 2⁄3 rd acceptance from all nodes in the shard.
All these micro blocks are proposed by inspector nodes in the inspector node network, where all the nodes verify the transactions and the final block is proposed by the inspector node leader. The final block should have at least 2⁄3 rd signature of the inspector nodes before it is added to the main chain. Apart from this, the inspector node is responsible to keep check on whether a majority is being formed inside a shard, and monitor for any malicious activity to take over a shard.
Cut through of final block
The final block uses the “cut through” property of Mimblewimble to significantly reduce the blockchain size i. e the final block proposed consists of :
● A block header.
● The list of inputs remaining after cut-through.
● The list of outputs remaining after cut-through.
● A single kernel offset to cover the full block.
● The transaction kernels containing, for each transaction:
○ The public key r*G obtained from the summation of all the commitments.
○ The signatures generated using the excess value.
○ The mining fee.
The final block once accepted is gossiped back to some of nodes in each shard. The nodes verifies the final block against the transaction content they have and update state of the shard in sync with the global state.
If the nodes are not able to verify the final block, the shard state is not updated until it is brought to sync with the global state.
Easy sync up for new nodes
Compacted block information provides higher privacy, as no input can be matched with any output, and intermediate transactions are only expressed using transaction kernels. Such a structure makes it easy for new nodes to sync up information when added to shards and the inspector- node network. Using a compact transaction history reduces latency as nodes can sync up quickly and overall throughput remains high.
Cross shard transactions
For cross- shard transactions we use the UTXO model with Mimblewimble, which allows us to carry confidential transactions across different shards easily.
1. Initialize
A user creates a cross- shard transaction, spending UTXO’s of some input shards and creating new UTXO’s at the output shard.
2. Lock
All input shards associated with cross-shard transaction first validates the transaction in their shard, whether it can be spent or not, by checking zero- sum for the transaction. Once it is verified, the inspector node adds the transaction to its merkle proof and broadcast an “accept” message to the inspector- node network. The funds of the user sending the transaction are locked.
3. Unlock.
Once the accept message is received from all the input- shard- inspector nodes, it is verified by the inspector node network. If it is accepted by at least 2⁄3 of all inspectors nodes, the output- shard- inspector nodes accepts the transaction and add it to its own state history. The following transaction is updated in the global state when the final block is published.
Consensus Layer
We use the Ethash proof-of-work as the consensus protocol introduced in Ethereum 1.0 to avoid Sybil attacks on the network.
Ethash is a memory- hard hash function designed to make it easy to mine with GPUs but inefficient with specialized computing hardware such as ASICs. To achieve this, Ethash computation requires a considerable amount of memory (in GBs) and I/O bandwidth such that the function cannot be parallelized on specialized computing hardware.
Incentive Model
Miners will receive fixed block rewards which reduce over time. Further research is being done to manage rewards in an efficient manner to keep the network appealing to miners.
For Inspector Nodes:
1. An inspector node, who finds the malicious activity inside his shard, will be rewarded with all the funds involved in the malicious transaction, and the funds will be cut from suspect node’s account (which will be divided accordingly in a ratio if there’ is more than one node involved).
2. Apart from that, Inspector nodes will be paid “inspection fees” in addition to verification fees as well if there’ is not any malicious activity happening in the network, and the inspection fees will be cut from the block reward of every node in a specific ratio, as network operation and maintenance fee, which would be minimal, as the number of inspector nodes will be much less than validating nodes.
3. If any other validating node finds malicious activity and submits it, the inspector nodes will reward that node with all the funds involved in that transaction, to keep competition among nodes.
4. If the inspector node is corrupt, it will lose all the funds it staked during its assignment to the shard (mentioned earlier). And the malicious inspector node will also be churned out.
X. CONCLUSION
There are multiple proposals are being developed in order to provide a more functional blockchain infrastructure. But combining and working on the right proposals can definitely bring more functionality together and reduce tradeoffs significantly. We proposed one such solution in this paper that solves major scalability problems while bringing in more functionality with confidential transactions, and new incentive models. Still, our solution has some challenges that need further research in order to support various use cases in the market.
This paper is written in collaboration with Beam, read more about Beam @Beam Privacy and https://beam.mw
