Sublinear Consensus

I'm calling it sublinear consensus for lack of a better name. By sublinear, I mean that not every node needs to see and process every transaction for the network to know that everything is consistent. I'm proposing a (probably broken) system here that would achieve that goal using only POW. For the sake of reference I'll call this system scalecoin.

Motivation: Bitcoin may scale to thousands of transactions per second, but I'm looking for a system that will scale to billions of transactions per second. If you can achieve that, all sorts of applications might open up that weren't previously possible. If we didn't have to worry about small transactions or heavy transactions or heavy blocks on Bitcoin the same way we do today, many more things might become possible.

Scalecoin has a root blockchain with many children blockchains. For simplicity, we do not use a tree we merely have a parent with some abundant number of children.

I'm introducing the concept of static vs. dynamic consensus. Bitcoin POW is dynamic consensus. Anybody at all can produce a block without ever needing to have been seen by the network before. Static consensus is predetermined, and someone can only increase their voting power from within the system of consensus. Proof of Stake is a good example of static consensus. You can only increase how much power you have over consensus by buying coins, which can only happen as a result of new blocks being introduced to the network.

Scalecoin's root blockchain is a dynamic POW blockchain, operating in the same fashion of Bitcoin's dynamic POW blockchain. The root blockchain is used to dole out 'votes' of static consensus through POW commitments to nodes. A node will commit to some volume of POW in return for votes. To maintain its votes votes, it must provide proof that it has been doing as much POW as claimed. This can be done by having the node submit failed (or succeeded) blocks from trying to mine on the root blockchain that still satisfy some reduced difficulty, called 'vote blocks'. The node will need to provide n0 vote blocks in a transaction every n1 root blocks. The number of vote blocks is large to keep the variance low. If a node is getting unlucky and is unable to fulfill its obligation in time, it can outsource some hashes to catch up. Similarly if the node completes its vote blocks early, it can sell its hashes to nodes that are getting unlucky.

Because dishonest miners can exclude transactions with vote blocks, the number of root blocks that a miner has to provide n0 vote blocks is kept large, perhaps at 100 or so. As the miner gets more desperate to have its vote blocks seen by the network, it can increase the transaction fee.

Vote blocks cannot be resused, and must be less than 2 * n1 root blocks old, meaning that they were mined recently. They must also be mined on a block that is a valid part of the root blockchain history.

Using this vote block system enables nodes to claim responsibility for some portion of the mining power put towards the root blockchain, and then provide plausible proof to back up the claim. These votes are then used to create nodes that will participate in consensus in a child blockchain. Child blockchains are formed out of an explicit number of nodes, each of which is performing POW commitments on the root blockchain to demonstrate economic commitment and prevent sybil attacks.

To preserve security, child blockchains are randomly assembled from nodes, and each node is placed in exactly one child blockchain. The nodes in each blockchain compete to produce blocks. Each root block, every node on each child blockchain has one chance to submit a block that will advance the child blockchain. The hash of the previous root block is used as a random seed to create an ordering for the nodes in the child blockchain. The miner of the root block will get a greater reward for including a child that is earlier in the ordering. The root miner can only include one block from each child blockchain.

Each child block will point to a previous child block, which does not need to be the child block included in the previous root block. This leaves room for forks. The fork that has the most blocks is considered the true composition of the child blockchain, just as in the root. If a dishonest block is released, the honest nodes in the child blockchain will not acknowledge it, and will instead build upon an honest block. If the majority of nodes in the child blockchain are honest, then the longest representation of the child in the root will be composed of only honest blocks.

The requirement then is that every child blockchain be composed of a majority of honest nodes, which is a much stronger requirement than merely requiring a majority of nodes overall to be honest. We defend against this in two ways. The first is by having child blockchains be composed of a large number of nodes, such as 256, which requires the attacker to get lucky a large number of times in order to get a majority of nodes without having a network-wide majority. The second is by introducing a small amount of turbulence, such as randomly moving a node from each child blockchain to a different child blockchain every root block. This turbulence means that every blockchain will spend the majority of blocks with a majority of honest nodes, so long as the network as a whole has a majority of honest nodes.

To summarize: a traditional POW blockchain is used to create consensus on a root blockchain. Transactions can be submitted to this root blockchain in which nodes prove they are contributing some volume of POW to the root blockchain. These proofs are done with vote blocks, and give the nodes seats in child blockchains. Child blockchains are randomly assembled, and a low amount of turbulence is maintained to assure that each child blockchain spends a majority of time having a majority of honest nodes. Nodes within a blockchain compete to produce blocks. One child block from each child blockchain can be included into each root block (advancing some fork of the child blockchain). Each block, nodes within a child blockchain have a random ordering, and blocks created by children earlier in the ordering provide a greater reward to the host submitting the root block.

A dishonest miner with less than 50% of the network hashing power still has an opportunity to corrupt child blockchains, because whenever a dishonest miner mines a root block, the miner can choose to exclusively include dishonest child blocks. Honest miners will also sometimes include dishonest child blocks in the root block because they will be following the priority scheme, and dishonest children will sometimes have the highest priority. This is defended against using assumptions about network propagation. An honest miner can assume that if they see a child block, it will propagate the network within about 12 seconds. Therefore, if they see a child block of a certain priority and greater than 12 seconds later they see a root block that uses a lower priority child block, it can be assumed that that root block is dishonest. Honest miners will then ignore the root block for picking a lower priority child when a higher priority child was available.

==========

There's a lot more that could be hashed out, but the primary purpose of this post is to try and create a system where you can have child blockchains composed of a finite number of nodes (not all of them) that you can blindly trust. The goal, essentially, was to create a secure system where not every node needs to see every transaction. I don't know if I have done a good job, or if I've missed some obvious or subtle incetive sets, or if something else is broken entirely. Hoping for feedback.

Edit:

Just mentioning things that have been brought up in IRC, will integrate them into the above later.

+ "Consensus systems cannot have random"
The seed for a random number in a particular block is taken from the hash of the previous root block. This can only be manipulated by miners withholding blocks that they find which produce random numbers they dislike. We need to make sure that miners are discouraged from doing this, and that if they do participate in random number manipulation, it's self defeating unless they have greater than a majority of the hashing power on the network.

Making block withholding expensive requires fleshing out an incentive model a bit more.
Miners are rewarded for finding a root block, we'll say 50% of the newly minted coins.
Miners are rewarded for including child blocks, we'll say 10% is allocated towards that, though if non-max-priority child blocks are included, the full 10% is not going to be fulfilled.
Miners are also rewarded for finding a block in a child blockchain, though only if it is part of the longest chain. The reward for finding a child block is 4x the reward for it being included in the root block, or 40% total of the newly minted coins. Because of child forks, 40% may go substantially unfulfilled.

So miners have incentives to find root blocks, miners have incentives to include high priority child blocks, miners have disincentives to include less-than-highest priority child blocks (other miners will reject the block), and nodes within child blockchains have incentives to create and submit blocks.
Miners withholding blocks to manipulate random numbers will lose out on a large chunk of newly minted coins. This provides them with one reroll of the random number, and does not enable very strong corruption of the distribution of miners. They may be able to change things such that they can perform attacks at 49% instead of 50% (and I should at some point do math to be sure), but I don't think random number manipulation will be significant enough to severly disrupt the distribution of hosts. A dishonest party with only 45% hashing power should still be unable to take extended control of a child blockchain.

+ "These are similar to sidechains"
Yes I suppose they are. I dont' fully understand sidechains but one major difference seems to be that with this setup all possible forks are known to the root blockchain. The blockchain can accept the longest, and then after some number of confirmations it can 'cement' transactions that go between child blockchains, allowing children to accept as input transactions that other children have produced as output. Cementing a transaction would mean that the child blockchain could no longer fork from a block before the point where the transaction was cemented. If a dishonest fork gets long enough to be cemented, then the dishonest hosts win over that child blockchain and all the coins inside of it are at their mercy, because the root blockchain has no way of knowing that transactions are being submitted dishonestly.

+ "What is the trust/verification model, and why does it scale better than Bitcoin?"
The root blockchain would manage how many coins each child blockchain had, which keeps the total number of coins in the system honest. What happens within a child blockchain is completely unknown to anyone that's not verifying the child blockchain. Presumably, balances and transactions stay mostly internal to each child blockchain, with only a minimum number of transactions happening between child chains. Merchants could verify only the child blockchain that they care about plus the root blockchain. They can know that funds incoming from a different child blockchain are trustworthy once they have some number of confirmations. The number of confirmations can be known just by having the root blockchain.

+ "Are you planning on turning this into an altcoin?"
Not anytime soon, just throwing ideas around.

Problem: nodes mining on child blockchains have no apparent incentive to produce honest blocks that have been verified. Miners could lazily produce dishonest blocks and still reap the mining reward. This could potentially be rectified by some CoinWitness style proof that mandates blocks be honest. Dark blocks are no longer a problem because the honest miners will not be able to produce honest blocks unless they have all blocks in the system. Lazy miners cannot mine on dark blocks.