Scalability in blockchain

Most popular debate in bitcoin community is that blockchain do not scale properly. It doesn't scale because every full node has to verify every transaction. The scaling doesn't really work well because of fixed block time (time between two blocks creation). If there are more and more transaction (meaning system grows); then every single node has to process more transactions in that fixed time. The transactions in Ethereum are more complicated than Bitcoin. Though, it hasn't hit it's limit yet community is working on ways to deal with scalability issue.

In simple database system, the solution to the problem of scalability is adding servers which can take over the additional transactions and even up the system. Blockchain on the other hand is a distributed database, adding nodes doesn't help here because every node has to process every transaction, so it's not easing the problem. If we decide to distribute the additional transactions to few nodes only; then these nodes may cheat during verification as the transactions are not recorded with other nodes. Also, this is against the basic rule of blockchain system (trust) that every node has to process every transaction.

Scalability in Ethereum

Scalability issue in Ethereum is same as that of Bitcoin. The advantage Ethereum has over Bitcoin is that Ethereum team are aware of the issue since begenning and hence are ready for fork to deal with the problem, if needed.

There are three proposals to deal with scalability issue in Ethereum.

Casper is not just about POS, but also to scale the blockchain. In Casper the scaling is done based on a concept called Sharding, which is very much similar to concept of distributed database system to deal with scalability. In Sharding, the transactions are sent to certain nodes for verifying but because casper is more secure.
Raiden is the Ethereum analogy of Bitcoin's lightning network. In Raiden, the concept is to scale transactions by state channels. It means by grouping transactions into certain way and then moved to process into a different network (off chain). At the end, multiple similar transactions are grouped and put back on the blockchain network. It simply means, more transactions enclosed into a single extra transaction.
TrueBit is the third proposal to deal with the issue. In TrueBit, the concept is to scale computation through interactive verification.

Only Casper requires to fork because other two can be directly implemented using smart contract codes.

Overview - TrueBit

TrueBit uses interactive verification for offloading computations, providing help in scaling and giving a proper incentivisation scheme for doing computationally-intensive work. The idea is that large computations are proven to be faulty by chopping them up into smaller and smaller pieces until a tiny step remains that can be easily checked by smart contracts. The difficulty lies in motivating Verifiers to watch the process. Verifiers are hard to reward if they do not find an error and the desired situation is precisely the one where nobody cheats and thus no computation contains an error. TrueBit introduces an incentive layer that properly rewards verifiers "even" in the case where everyone is honest.

The technical white paper was released by Christian Reitwiessner (Ethereum) and Jason Teutsch (TrueBit Foundation) on March 7, 2017.

TrueBit involves:

Task Giver publishes "question" and provides fee.
Solvers provide solutions in commit/reveal manner. In order to participate as solver, they have to pay deposit. This deposit is slashed if fraud is detected else get rewards.
Majority solution is accepted. Any dispute is resolved in court (blockchain) using the Verification Game. Verification game will only be played in case of an attack due to incentives.

This is like blockchain with multiple miners who processes all transactions and verify each other on a blockchain. If there is disagreement, fork can be done. To convince the network of the correct version, over 50% of hashpower should be convinced in the blockchain. TrueBit differs with this idea of blockchain as here everyone must be convinced.

Properties - TrueBit

It has unanimous consent.
The computation results can be challenged, starting a "verification game". It means, if an honest verifier disagrees (after checking the computation), then he / she can post it on the blockchain and can outrule anyone if stands correct. It helps prevent attack by 99.9%. Single honest verifier suffices that nobody can cheat.
The honest actor will always win this game. Presence of honest verifier is ensured by economic incentives mechanism.
On-chain part: storing hashes plus tiny computation step.

There are few other projects which have similar concept like Golem / iExec / Sonm. But they focus on performing the computations or outsourcing the computation and not on the fact that they are done correctly. Other use blockchain to pay for cloud computation. TrueBit, on the other hand focuses on the correctness and not on the costs. It is really about scaling verified computation (about what can be done inside the single transaction).

How to scale computation?

The reason why blockchain can't scale computation is because every node has to compute everything.

So, the suggested solution is

Only few people perform computation off chain, where not everyone has to compute everything. Suppose there is a computational task for the blockchain then 2-3 people perform the computational task and post the result on the blockchain.
Majority answer is considered, but if there is any disagreement then the person can go to court (which is actually the blockchain). The smart contract judge of the blockchain (court) finds out the correct answer without any error. Simple solution here could be that the entire computation should be rerun by the smart contract, but it doesn't scale.
The on-chain checking (who is correct) must settle faster.

Key features - TrueBit

Ethereum has smart contracts, which means computations are running on the blockchains. But they are limited in complexity and resource usage because every full node has to process every transaction and stores all state (account balances, contract code and storage, etc).
TrueBit provides smart contracts without gas limits. (The amount of computations is measured in unit, called “gas”).

A contract can be written in any programming language and can be executed on blockchain with the help of its interpreter added to the blockchain.
It is driven by neural networks and hence we can have AI (artificial intelligence) on the blockchain with filesystem access to Swarm. It means that TB sized big files can be accessed and chunk can be read in there. It can even compute the big sums over all the gigantic file.

These smart contracts will not run directly on the blockchain, because it doesn't scale but the 'Trust' promise will be the same as on the blockchain.

Applications - TrueBit

It can link multiple blockchains. eg. Dogecoin Ethereum project. This project tries to create a bridge from Dogecoin to Ethereum and also way back from Ethereum to Dogecoin. The basic idea of this project is that one can take Doge (currency of Dogecoin) and move it around the Ethereum blockchain as an independent token and also move it back by destroying the token and releasing (generating) a new Doge on Dogecoin. To perform this transaction, we need light client for moving from one network to the other network and also for destroying token on Ethereum network. Since, it doesn't have gas limit, it can implement anything and verify the code for Dogecoin blockchain on Ethereum.
It can be used to verify Golem computations. Golem is a project to pay for other people to do computations. Its white paper mentions that it is actually too big to verify that their computations are actually correct.
It can also be used for project Livepeer. It is video streaming platform where people are paid to encode the videos. TrueBit can be used to verify that encoding done is correct.

It can be used for several other similar applications.

Verification Game (TrueBit as Decentralized Computational Court)

It is a concept used to settle the on-chain disagreement faster. It is done not by sampling but by binary search. Suppose, someone (challenger) disagrees with the result by another verifier (proposer) and decides to go to the smart contract judge of the blockchain, then the smart contract (judge) doesn't check each and every step or random sampling. It goes by binary search. Here, parties compute Merkle trees of full state (memory) at every single computation step and submit roots at certain step.

Truebit1

Fig: Binary Search

eg. In the fig. above we see that, the dispute is about a computational program of 1000000 steps. Both the parties compute and submit Merkle tree of full state (memory) at Step 1, Step 5000000, Step 750000, Step 625000 and so on. After 20 rounds, agreement changes to disagreement in one step (Step 638295 to Step 638296). Both submits the Merkle proof and smart contract verifies (re-compute just a single step) with no effort and finds the cheater. It took 20 rounds which is very small in comparison to 1000000 rounds and hence faster on chain than actually doing all the computation.

Benefits of the verification game

Number of rounds can be further reduced.
Cheater is found with certainty. Large disincentive to cheat. The part of deposit is destroyed of the guilty. The person who identifies it, gets the reward.
In reality, the game will never be played because cheater will be found if someone watches. But it has to be there in code and correct as fallback for this whole mechanism to work.

Problem: Verifier’s Dilemma

The verification game is well planned and there is very less probability of cheating. Solvers are aware of the mechanism and they would not want to lose their deposit on the blockchain. Verifiers may stop looking over the time because the way system works, nobody cheats yet they have to keep looking for the mistakes without any scope of incentive. This would be the perfect timing for the solver to cheat and the system will break. To avoid this problem, the proposed solution is Forced Errors.

Solution: Forced Errors

Concept of Forced Error states that inject the forced error into the system which can then be detected by the verifier and they get the reward. Since, this is not the actual error so solver is not punished if forced error is found. The reward received by the verifier is paid by the system. TrueBit system needs fee to solve the task. This fee is paid out in-part to person who posts the solution to the task and in-part is saved in an account called jackpot and if set of forced errors occurs and a verifier finds the error then the verifier is paid from the jackpot.

Problem: Information Sharing

A solver is forced to inject an error, so he is aware about the forced error. If he denies then he will be punished. This condition is verifiable by the smart contract. The reward is for every verifier who detects the error.
Consider a scenario,

solver notifies the verifiers about the error
verifiers can create multiple accounts
how to ensure computation was actually run?

Solution: Reduce reward with every challenge

Solver can also challenge
total error finding reward is halved for each report

Payouts:

1 challenge: 100 = 100
2 challenge: 25+25 = 50
3 challenges: 8.333+8.333+8.333 = 25
….

Rewards are decreased from 100 to 25, so nobody would like to share it.

In TrueBit, the system works as the task is post, solved by the solvers and verified by the verifiers. It always has multiple parallel tasks and verifier choose randomly between these tasks.

If you like the article, please share. For more updates, technical blogs and general discussion on Ethereum and blockchain technology, please follow us @ether_world (Twitter) and Ethereum Blockchain Technology (Facebook).