Permalink
Find file Copy path
444890b Jan 12, 2019
4 contributors

Users who have contributed to this file

@janx @doitian @Keith-CY @u2
243 lines (144 sloc) 31.8 KB
Number Category Status Author Organization Created
2
Informational
Draft
Jan Xie
Nervos Foundation
2018-01-02

Nervos CKB: A Common Knowledge Base for Crypto-Economy

Abstract

Nervos is a layered crypto-economy network. Nervos separates the infrastructure of crypto-economy into two layers: a verification layer (layer 1) serving as trust root and smart custodian, and a generation layer (layer 2) for high-performance transacting and privacy protection.

This document provides an overview of the Nervos Common Knowledge Base (CKB), a public permissionless blockchain and layer 1 of Nervos. CKB generates trust and extends the trust to upper layers, making Nervos a trust network. It's also the value store of Nervos network, provides public, secure and censorship-resistant custody services for assets, identities and other common knowledge created in the network.

Contents

  1. Motivation
  2. Overview
  3. Consensus
  4. Programming Model
    1. State Generation and Verification
    2. Cell
    3. VM
    4. Transaction
  5. Economic Model
  6. Network
  7. Summary
  8. References
  9. Appendix

1. Motivation

We want a peer-to-peer crypto-economy network.

In such a network, people not only can collaborate but also have incentives to do so. We need the ability to define, issue, transfer, and own assets in a peer-to-peer network to create such incentives. The blockchain technology brings us the last piece of the puzzle.

Bitcoin[1] is the first public permissionless blockchain of them all, designed to be used solely as peer-to-peer cash. Ethereum[2] extends the use case of blockchain to general purpose trust computing platform on which people built all kinds of decentralized applications. The booming applications in Bitcoin and Ethereum network have been proving the concept of future's crypto-economy. However, they also suffer from the notorious scalability problem, that their transaction processing capability cannot scale with the number of participants in the network which limits their potential severely.

The blockchain community has proposed many scalability solutions in recent years. In general, we can divide these solutions into two categories, on-chain scaling and off-chain scaling. On-chain scaling solutions are those trying to scale at the same layer where consensus runs. Consensus process is the core of a blockchain protocol, in which nodes exchange network messages and reach agreements eventually. A consensus is slow almost by definition, because message exchange on a public and open network is slow and uncertain, which requires nodes to wait and retry during the process. To scale at this layer, we can either "scale up" by increasing the processing ability and network bandwidth of nodes but sacrificing decentralization because it incurs high cost, or "scale out" by sharding. The idea of sharding is to divide nodes into many small "shards", and ask each shard to process only a fraction of network transactions. Sharding is widely adopted by Internet giants as they face the same scalability issues when serving millions of users. However sharding is well known for its complexity of shards coordination and cross-shard transaction, even in a trusted environment, which leads to performance degradation as the number of shards grows.

In contrast, off-chain scaling solutions acknowledge the inherent complexity of the consensus process. They recognize that consensus with different scopes have different costs, and global consensus created by a public permissionless blockchain is the most expensive one. While it's hard to scale a global consensus, we can use it wisely. Most transactions between two or more parties don't need to be known by every node in the network, except when they need to be settled down and kept secure, in other words, when users want to turn them into common knowledge of the network. The network scales by offloading most of the work, with no limit on the scalability. Processing transactions off-chain also bring extra benefits, such as lower latency and higher privacy.

While we agree with the general ideas of off-chain scaling, we found that there's no existing blockchain are designed for this. For example, although the lightning network is one of the earliest explorers in off-chain scaling, it takes years to launch its testnet and is still far from mass-adoption due to the limitations of the underlying Bitcoin protocol. Ethereum provides powerful programming ability, but its computation oriented economic model doesn't fit well with off-chain scaling, as off-chain participants handle most of the computation, and what they need is a blockchain that can keep their assets in secure custody and moving assets according to the final state of their computation. The computation oriented design of Ethereum also makes it's difficult to execute transactions in parallel which is harmful to scalability.

The economic models of current blockchains also face challenges. With more users and applications moving to blockchain platforms, the data stored on blockchains also increases. Current blockchain solutions care more about the cost of consensus and computation, making it possible for a user to pay once, and have their data occupy full nodes’ storage forever. Cryptocurrency prices also are highly volatile. Users may find it difficult to pay for high transaction fees as the price of the cryptocurrency increases.

We propose Nervos CKB, a public permissionless blockchain designed for a layered crypto-economy network.

2. Overview

Nervos CKB (Common Knowledge Base) is a layer 1 blockchain, a decentralized and secure layer providing common knowledge custody for the network. Common knowledge refers to states verified by global consensus. Crypto-assets is an example of common knowledge.

In Nervos, the CKB and all the other layer 2 protocols work together to serve the crypto-economy. CKB or layer 1 is the place to define and store state, and layer 2 is the generation layer (or computation layer, these two terms are interchangeable) that processes most transactions and generates new states. Participants on layer 2 submit generated states to CKB eventually at the time they deem needed. If those states pass corresponding verification performed by nodes in a global network, CKB stores and keeps them in a peer-to-peer node securely.

The layered architecture separates state and computation, giving each layer more flexibility and scalability, for example, blockchains on generation layer may use different consensus algorithms. CKB is the bottom layer with the broadest consensus, and it's the most secure consensus in Nervos network. However, different applications might prefer different consensus scopes. Thus, forcing all applications to use CKB’s consensus is inefficient. Applications can choose appropriate generation methods based on their particular needs, and the only time they need to submit states to CKB, to get a broader agreement, is when they need to make them common knowledge verified by CKB global consensus.

Possible state generation methods include (but are not limited to) the following:

  • Local generators on the client: Generators run directly on the client’s devices. Developers can implement the generator in any programming languages.
  • Web services: Users may use traditional web services to generate new states. All current web services may work with CKB in this way, to gain more trust and liquidity for the generated states. For example, game companies may define in-game props as assets in CKB, having the game itself function as a web service to generate game data which is verified and stored in CKB.
  • State channels: Two or more users may use peer to peer communication to generate new states.
  • Generation chains: A generation chain is a blockchain that generates new states and stores them in CKB. Generation chains may be permissionless blockchains or permissioned blockchains. In each generation chain, nodes reach the consensus in smaller scopes, which gives better privacy and performance.

Figure 1. Layered Architecture Figure 1. Layered Architecture

CKB consists of a Proof-of-Work based consensus, a RISC-V instruction set based virtual machine, a state model based on cells, a state-oriented economic model, and a peer-to-peer network. The Proof-of-Work based consensus makes the CKB a public and censorship-resistant service. The combination of CKB VM and Cell model creates a stateful Turing-complete programming model for developers, making state generation (or layer 2) on CKB practical. CKB economic model is designed for common knowledge custody to make it long-term sustainable. CKB peer-to-peer network provides secure and optimal communications between different type of nodes.

3. Consensus

CKB consensus is an improved Nakamoto consensus based on Proof-of-Work, it aims to achieve openness, correctness and high performance in distributed environments with network delay and Byzantine node faults.

Permissionless blockchains run in open networks where nodes can join and exit freely, and there is no certainty when they are online. Those are severe problems for traditional BFT consensus algorithms to solve. Satoshi Nakamoto introduced economic incentives and probabilistic consensus to solve these problems. Nakamoto consensus in Bitcoin uses blocks as votes, which takes longer (up to 10 minutes to an hour) to confirm transactions, and leads to inferior user experiences.

CKB consensus is a Nakamoto consensus variant, which means it allows nodes to join and exit the network freely. Every node can participate in the consensus process either by mining (running a specific algorithm to find the Proof-of-Work) to produce new blocks or by verifying new blocks are valid. CKB uses ASIC-neutral Proof-of-Work function, with a goal to distribute tokens as even as possible and to make the network as secure as possible.

Correctness includes eventual consistency, availability, and fairness. Eventual consistency guarantees every node see identical copies of state. Availability makes sure the network respond to user’s requests within a reasonable time. Fairness ensures mining nodes to get fair returns for their efforts to keep the network securely functioning.

High performance includes transaction latency which is the time between the submission of a request and the confirmation of its execution results, and transaction throughput as the number of transactions the system is capable of processing per second. Both of them depends on block time, which is the average time between two consecutive blocks. CKB consensus improves both transaction latency and throughput by using network bandwidth more efficiently without sacrificing security and decentralization.

Please check the CKB Consensus Paper for more details.

4. Programming Model

CKB provides a stateful Turing-complete programming model based on CKB VM and cell model.

Bitcoin Ethereum CKB
Instruction Set Script EVM RISC-V
Cryptographic Primitive Opcode Precompile Assembly
Stateful No Yes Yes
State Type Ledger General General
State Model UTXO Account Cell
State Verification On-chain On-chain On-chain
State Generation Off-chain On-chain Off-chain

Table 1. Comparison of Bitcoin, Ethereum and CKB Programming Model

The CKB programming model consists of three parts:

  • state generation (off-chain)
  • state verification (CKB VM)
  • state storage (Cell model)

In this model, decentralization application logic is split into two parts as generation and verification, running at different places. State generation logic runs off-chain at the client side, new states are packaged into transactions and broadcasted to the entire network. CKB transaction has an inputs/outputs based structure as in Bitcoin. The client puts generated new state in transaction outputs, which is called cells in CKB. Cells are the primary state storage units in CKB. Transaction inputs are references to previous outputs, along with proofs to unlock them. Cells are assets owned by users and must follow associated application logic specified by scripts. CKB VM executes those scripts and verifies proofs in inputs to make sure the user is permitted to use referenced cells, and state transition is valid under specified application logic. In this way, all nodes in the network verify new states are valid and keep them in custody.

State in CKB are first-class citizens, they are included in transactions and blocks and synchronized directly among nodes. Although the programming model is stateful, scripts running in CKV VM are pure functions with no internal state, which makes CKB scripts deterministic, parallel execution friendly and easy to compose.

4.1 State Generation and Verification

The decentralized applications in Nervos separate the generation and verification of state, do these things at different places, with either same or different algorithms.

Use the same algorithms at both places is a straightforward choice that works for general problems. In this model, the same algorithm has two implementations, one runs off-chain in any execution environments the application targeting, and the other one runs on-chain in CKB VM. New states are generated off-chain with this algorithm based on previous states and user inputs, packaged as a transaction and broadcasted to the network. CKB nodes run this same algorithm on-chain, provide it the same previous states and user inputs, and verify the result matches transaction outputs.

There are several advantages to this separation of state generation and validation:

  • Deterministic transaction: Certainty of transaction execution is one of the core pursuits of decentralized applications. If transactions only include user input and new states are the results of computation on nodes as in Ethereum, the transaction creator cannot be in certain about the computation context, which may lead to unexpected results. In CKB, users generate new states on the client side. They can confirm the new states before broadcasting it to the network. The transaction outcome is in certain: either the transaction passes on-chain verification and make new state accepted, or the transaction is deemed invalid and make no state changes to CKB (Figure 1).

  • Parallelism: If transactions only include user inputs and new states are generated by nodes, then nodes don't know what state is going to be accessed by the verification process beforehand, and they cannot determine the dependencies between transactions. In CKB, because transactions include previous states and new states explicitly, nodes can see dependencies between transactions before verification, and process transactions in parallel.

  • Higher resource utilization: As the application logic is split and run at different places, the network distributes computation workload more evenly on nodes and clients, thus utilizes system resources more efficiently.

  • Flexible state generation: Even when the algorithms are the same, developers can implement generation and validation in different ways. The client side has the flexibility to choose the programming language for better performance and fast development.

In some scenarios, state verification can use a different (but associated) algorithm and be much more efficient than state generation. The most typical example is the Bitcoin transaction: Bitcoin transaction construction is mainly a searching process looking for appropriate UTXOs to use, while its verification is the addition of numbers and simple comparison. Other interesting examples include sorting and searching algorithms: the computational complexity for quicksort, one of the best sorting algorithms for the average case, is O(Nlog(N)), but the algorithm to verify the result is just O(N); searching for the index of an element in a sorted array is O(log(N)) with binary search, but its verification only takes O(1). The more complex business rules, the higher probability that there can be asymmetric generation and validation algorithms with different computational complexity.

The system throughput can improve by this asymmetry between state generation and validation. Putting details of computation to the client side is also good for algorithm protection or privacy. With the advancement of technologies like zero-knowledge proof, we may find efficient generation and verification solutions to general problems, and CKB is a natural fit for them.

We call programs that generate new states and create new cells Generators. Generators run locally on the client side (off-chain). They utilize user input and live cells as program inputs, to create new cells with new states as outputs. The inputs that generators use and the outputs they produce together form a transaction.

Figure 2. Separation of state generation and verification Figure 2. Separation of state generation and verification

4.2 Cell

Cells are the primary state units in CKB, and users can put arbitrary states in them. A cell has the following fields:

  • capacity - Size limit of this cell. A cell's size is the total size of all fields in it.
  • data - State data stored in this cell. It could be empty. Total bytes used by a cell, including data, must always be less than or equal to its capacity.
  • type: State verification script.
  • lock: Script that represents the ownership of the cell. Owners of cells can transfer cells to others.

A cell is an immutable object, as no one can modify it after creation. Every cell can only be used once - it cannot be used as inputs for two different transactions. Cell ‘updates’ mark previous cells as history and create new cells with the same capacity to replace them. By construct and send transactions, users provide new cells with new states in it and invalidate previous cells storing old states atomically. The set of all current (or live) cells represents the latest version of all common knowledge in CKB, and the set of history (or dead) cells represents all histories versions of common knowledge.

CKB allows users to transfer cell capacity all at once, or transfer only a fraction of a cell's capacity, which leads to more cells created (e.g., a cell with capacity=10 becomes two cells with capacity=5).

Type and lock are both scripts to be executed in CKB VM. CKB VM executes the type script when a cell is created in output, to guarantee the state in the cell is valid under specific rules. CKB VM executes the lock script with proofs as arguments when the cell is referenced by an input, to make sure the user has correct permission to update or transfer it. Users need to provide the necessary proof within transaction inputs to the lock scripts. If the execution of lock scripts returns true, the user is allowed to transfer the cell or update its data according to validation rules specified by type script.

This type and lock script pair allows all kinds of possibilities, for example:

  • Upgradable cryptography - Anyone can deploy useful cryptography libraries written in languages like C or C++ and use them in type and lock scripts. In CKB VM, there're no hardcoded cryptography primitives, and users are free to choose any cryptographic signature scheme they like to sign transactions.
  • Multisig - Users can easily create M-of-N multisig or more complex lock scripts.
  • Lending - Cell owner can lend cell for others to use while still keep its ownership.

The Cell model is a more generic state model compared to the UTXO or the Account model. Both of the UTXO and the Account model can express relationships between assets and their owners. The UTXO model defines ownership on assets (with the lock script), while the Account model defines ownership of assets on owners (with the balance). The UTXO model makes the ledger history more clear, but its lack of generic state storage makes its already inexpressive scripts harder to use. The Account model is easy to understand and can support authorizations and identities well, but it is not easy to process transactions in parallel. The Cell model with lock and type scripts, takes the best of both models to provide a more generic state model.

4.3 VM

CKB VM is a RISC-V instruction set based VM for executing type and lock script. It uses standard RISC-V instructions only, to maintain a standard compliant RISC-V software implementation which can embrace the broadest industrial support. CKB implements cryptographic primitives as ordinary assembly running on its VM, instead of customized instructions in VM. It supports syscall by which scripts can read metadata such as current transaction and general blockchain information from CKB. CKB VM defines cycles for each instruction, and provides total cycles executed during transaction verification to help miners determine transaction fees.

Existing blockchains hardcode cryptographic primitives in the protocol, for example, Bitcoin has special cryptographic opcodes such as OP_CHECK*, and Ethereum use special 'precompiled' contract located at special address (e.g. 0000000000000000000000000000000000000001) to support cryptographic operations such as ecrecover. To add new cryptographic primitives to these blockchains, we can only soft-fork (as Bitcoin re-use opcodes to support new primitive) or hard-fork.

CKB VM is a crypto-agnostic virtual machine. There are no special cryptographic instructions hardcoded in CKB VM. New cryptographic primitives can always be deployed and used by scripts like using an ordinary library. Being a RISC-V standard compliant implementation means existing cryptographic libraries written in C or other languages can be easily ported to CKB VM and used by cell scripts. CKB even implements the default hash function and public-key cryptography used in transaction verification this way. Being crypto-agnostic allows decentralized application developers in Nervos to use any new cryptography (such as Schnorr signature, BLS signature, and zkSNARKs/zkSTARKs) they like without affecting other users, and CKB users to keep their assets secure even in the post-quantum era.

CKB VM chooses a hardware targeting ISA because blockchain is a hardware-like software: its creation is as easy as software, but its upgrade is as hard as hardware. As an ISA designed for chips, RISC-V is very stable, and its core instruction set is implausible to change in future. The ability to keep compatibility with the ecosystem without the need of hard-fork is a key feature of a blockchain virtual machine like CKB VM. The simplicity of RISC-V also makes runtime cost modeling easy, which is crucial for transaction fee calculation.

Please check RFC 0003 for more details of CKB VM.

4.4 Transaction

Transactions express state transitions, they cause cell transfer, update, or both. In a single transaction, users can update data in one or more cells, or transfer their cells to other users, and all state transitions in this transaction are atomic, in the sense that they will either all succeed or all fail.

A transaction includes the following:

  • deps: Dependent cell set, provides read-only cells needed by transaction verification. They must be references to living cells.
  • inputs: Cell references and proofs. Cell references point to live cells that are transferred or updated in this transaction. Proofs (e.g., signature) prove that the transaction creator has the permission to transfer or update those cells.
  • outputs: New cells created in this state transition.

The design of the CKB cell model and transactions is friendly to light clients. Since all the states are in blocks, block synchronization also accomplishes state synchronization. Light clients only need to synchronize blocks and do not need additional state synchronization or state transition computations. If we only stored events in blocks, we would have needed full nodes also to support state synchronization. State synchronization can be difficult for large deployments because the incentive to do so is weak. That is different from block synchronization in which miners are incentivized to broadcast blocks as widely as possible. No need for extra state synchronization protocol makes light nodes and full nodes more equal peers, leading to a more robust and decentralized system.

Figure 3. Transaction Parallelism and Conflict Detection Figure 3. Transaction Parallelism and Conflict Detection

The deps and inputs in CKB transactions make it easier for nodes to determine transaction dependencies and perform parallel transaction processing (Figure 4). Different types of cells can be mixed and included in a single transaction to achieve atomic operation across types.

5. Economic Model

A well-designed economic model should incentivize all participants to contribute to the success of the crypto-economy and maximize the utility of the blockchain.

The CKB economic model is designed to motivate users, developers and node operators to work towards the common goal of common knowledge custody. The subject of CKB economic model is state instead of computation, by using cell capacity and transaction fees as incentives for stakeholders.

5.1 State Cost and Cell Capacity

The creation and storage of states on the CKB incur costs. The creation of new states needs to be verified by full nodes, incurring computational cost; the storage of states needs full nodes to provide storage space on an ongoing basis. Current permissionless blockchains only charge one-time transaction fees, but they allow states to be stored on all full nodes, occupying storage space forever.

In CKB, cells are basic storage units of states. Cell owner can use it to store state himself or lend it out to others. At any time, the same cell capacity can only be occupied by no more than one user. If an owner uses the capacity himself, it means he would give up the opportunity to earn interests by lending it out (either to CKB or other users), which incurs an opportunity cost to him. In this case, users pay for storage with a cost that is proportional to both space and time - the larger capacity and the longer time they occupy, the higher cost they pay. The advantage of CKB's implicit state cost model, comparing with upfront payment model such as storage rent discussed in Ethereum community, is that it avoids the problem that upfront payments could be used up, and the system would have to recycle the state and break any applications or contracts depend on it.

Cell metadata (capacity, type and lock) are states, so they occupy users' cell capacity and incur state cost as well. This meta cost would incentivize users to create as fewer cells as possible to increase capacity efficiency.

5.2 Computation Cost and Transaction Fee

Updating cell’s data or transferring their ownership incur transaction fees. Miners can set the transaction fee level that they are willing to accept, based on CKB VM cycles used and state changes in transaction verification. The market determines transaction fees. With the programming model described above, cell owners can also pay transaction fees on behalf of their users.

Cell capacity as the only native asset in CKB is the most convenient asset users can use to pay transaction fees. However, users can also use any other user-defined assets as long as miners accept them since there's no hard-coded payment method in CKB transaction. That is allowed in CKB because its economic model and its native asset is not about computation but states. Although cell capacity can be used as transaction fee payment, its primary function is secure common knowledge storage which can store state and hold in a long time. Payment method competition in fee market does not compromise its value.

Restrict transaction fee payment method to the native asset is a significant obstacle preventing blockchains' mass adoption. It requires users to acquire native assets before using any of the services, raising the barrier of use. By allowing cell owners to pay on behalf of their users and payment with any user-defined assets, CKB can provide a better experience to users and more business model choices to developers.

Please check the Nervos CKB Economic Paper for details of the economic model.

6. Network

We can categorize CKB nodes into three types:

  • Mining Node: They participate in the CKB consensus process. Mining nodes collect new transactions, package them into blocks and produce new blocks when they found a Proof-of-Work. Mining nodes do not have to store the entire transaction history, but only the current cell set.
  • Full Node: They verify new blocks and transactions, relay blocks and transactions, and select the chain fork they agree. Full nodes are verifiers of the network.
  • Light Node: They trust full nodes, only subscribe and store a subset of cells that they care. They use minimal resources. Users are increasingly relying on mobile devices and mobile apps to access the Internet, and the light node is designed to run on mobile devices.

Uniform blockchain network in which every node has the same role, does the same thing is currently facing severe challenges. Full nodes validate all blocks and transaction data, requiring minimum external trust, but they incur a higher cost and are inconvenient to run. Light clients trade minimum trust for the substantial cost reduction on transaction verification, leading to much better user experiences. In a mature crypto-economy network, the number of light nodes would be the largest, followed by full nodes and mining nodes. Because light nodes depend on full nodes to verify and provide state, a large number of light nodes requires a large number of full nodes to serve. With CKB's economic model, both computation and storage resource required by a full node can be controlled at a reasonable level, and the barrier of running a full node can be kept at a low level, leading to a large service provider group for light nodes and a highly decentralized network.

7. Summary

We envision a layered crypto-economy and CKB is the base layer in it. CKB is the decentralized trust root of this crypto-economy, it ensures the trustless activities in upper layers. It's a common knowledge custody network, in which states are verified by global consensus and stored in a highly available peer-to-peer network. CKB is designed from scratch to meet the needs of a layered architecture, and its design focuses on states rather than computation. In CKB, users and developers can define, issue, transfer and store crypto-assets, they can also create digital identities and use those identities in the crypto-economy, our own imagination is the only bounds of its use.

8. References

  1. Satoshi Nakamoto, “Bitcoin A Peer-to-Peer Electronic Cash System”, 2008
  2. Vitalik Buterin, "Ethereum A Next-Generation Smart Contract and Decentralized Application Platform", 2014

9. Appendix

Common Knowledge is the knowledge that’s accepted by everyone in a community. Participants in the community not only accept the knowledge themselves but know that others in the community also accept the knowledge.

In the past, the common knowledge is scattered in people’s heads, and its formation requires repeated communication and confirmation. Today with the advancement of cryptography and distributed ledger technology, algorithms and machines are replacing humans as the medium for the formation and storage of common knowledge. Every piece of data in the blockchain, including digital assets and smart contracts, is a piece of common knowledge.

Blockchains are common knowledge bases. Participating in a blockchain network implies accepting and helping validate the common knowledge in it. Blockchains store transactions with their proofs and users can trust the validity of the transactions and know other users trust it too.

The various ways in which the knowledge on which people base their plan is communicated to them is the crucial problem for any theory explaining the economic process, and the problem of what is the best way to utilizing knowledge initially dispersed among all the people is at least one of the main problems of economic policy - or of designing an efficient economic system.

- The Use of Knowledge in Society, Friedrich A. Hayek, 1945