history
I came up with the first seeds of this idea during a conversation with Janislav Malahov in Berlin in the spring of 2014. Unfortunately, when my laptop was stolen in Vienna, my original articles were lost along with it. After a recent conversation with Vitalik about the principles, I made several changes and formalizations, mainly to the verification and substate truncation mechanisms. Here is a fairly complete picture of one possible specific plan for blockchain scalability in the latest version of Ethereum.
Because this is by no means a final proposal. GitHub wiki page Track the progress of this specific idea.
outline
The basic idea of Chain-Fibers remains the same as it was a year ago. Split the state space into hierarchies and have separate transaction collators that specialize in one or more state subspaces. Transactions that require the interaction of many subspaces are correspondingly more expensive (since the collator must maintain a presence on multiple chains) and take longer to execute (a given block will contain a superset of transaction subspaces). Because it is unlikely). The validity of a transaction can be separately verified by providing a comprehensive Merkle proof of the input of the block containing the transaction.
The subtlety is precisely controlling the subspace partitioning (my original proposal included automated splitting, merging, and rotation of the subspace partitioning to best convey internal consistency), and security within the relatively useless subspace. Here’s how it holds up and how it can work well. Proof of Stake (originally based on a master PoW chain, based on an idea presented by Max Kaye in early 2014 to separate blockchain archives from transition semantics).
The basic idea is to have multiple chains (e.g. N). Each chain details the state transitions of one layer (i.e., state subspace) of the overall system state. In programming terminology, we might call this “fiber.” Therefore, the account belongs to subspaces and single fibers. Which fiber they belong to can be determined simply from the first log2(N) bits of the address. N can be increased or decreased, and is a value maintained within the housekeeping information of the “master chain”.
The master chain is maintained by a set of connected validators, V, with the number of validators proportional to N. A random selection of validators verifies each block produced, and validators ultimately vote to form consensus on the master chain. Each block in the master chain maintains a reference to the header of each fiber.
The transaction collator generates the block (receiving a fee from the transactor) and pays a portion of the collected fee to the validator for including the hash of the block in the main chain. Blocks are produced from specific fiber “home sets”. This is basically a set of fibers that holds the State Trie. Their blocks may contain transactions on one or more of these fibers, but no transactions outside the “home set”.
“Fisherman” is the term given to a freelance checker. Since block verification and availability are both important, and a set of validators may be subject to contractual bribes, it is important to have mechanisms to enlist additional reasonable individuals in the role of “whistleblower” to avoid unnecessary harassment of other validators. Check all blocks. Fishermen essentially pay a fee to convince a quorum of validators that a previously verified block is invalid (or unusable, assuming they are identical). If the fisherman proves that the verifier (or set of verifiers) acted in a dishonorable manner, he or she will claim all bonds. A fee is paid to prevent DoSing to validators due to spurious issues.
schematic
Sorry for the non-ASCII art. I’m not as 1337 as Vitalik in Inkscape.
Transactors ==TX+FEE==> Collators ==BLOCK+FEE==> Validators
make transaction validate transaction, random selection chosen to audit
produce Comprehensive Merkle TX/PSR/CMP contents & availability,
Proof and Post State Root, all placed in PoS-consensus master block
collate into X-fiber Block
Fishermen ==CHALLENGE+FEE==> Validators
search for invalid or a selection adjudicate challenge
unavailable X-fiber blocks
trader
Transactions are almost identical to Ethereum 1.0. They are users of the system.
Trader: Make a deal
Traders perform transactions just as they would in the traditional Ethereum system. One or two minor differences – addresses can be used as a distance metric. Bits that share the same number of initial bits are considered “closer.” This means there is greater confidence that it will continue to be contained in the same state subspace in the future. Contracts are naturally created in the same state subspace as their creator.
Transactions like Collator operate over multiple fibers. Maybe it’s one, maybe it’s all, maybe it’s somewhere in between. Submissions to collators can be routed over a fiber subnetwork overlay.
In Ethereum 1.0, submissions and payments to collators occur much like traditional transaction submissions to miners.
collator
Collator maintains presence on at least two peer subnetwork overlays. A validator overlay and one or more fiber overlays. Fiber overlays can provide direct transaction propagation. Collator “collates” a series of fibers. They maintain an entire fiber chain for each fiber they collate and can accommodate all transactions involving any combination of fiber sets. The larger this combination, the larger the “transaction net” but also the larger overall disk/memory footprint.
Collator: Transaction Verification
Once a transaction is received, it goes through the usual Ethereum 1.0 procedures, including payment confirmation, initial balance &c. Once basic verification is complete, it attempts to run and discards it if it hits a fiber that is not part of the collator’s fiber set.
Collator: Generates comprehensive Merkle Proof and Post State Root.
Collator provides each post-state-root (found in transaction receipts in Ethereum 1.0) and Merkle proofs for every input (balance, nonce, state, code) in every subspace and associated hints (e.g. contract code). Add to block. This is necessary to evaluate each transaction in a previously known post-state root.
This allows the auditor to determine the validity of a block without anything other than the previous post-state root for each fiber.
Collator: collated with X-fiber blocks
Cross Fiber Block is created from all collected information. This includes the transaction, transaction receipt (post-state root), comprehensive Merkle proof, and associated hash hints. This block does not contain any consensus-related information such as timestamp, uncle, and c.
validator
Validators (better named auditors) are collateral participants who are regularly selected from among the highest bidders and receive a small fee for the ultimate maintenance of the network. Overall, their mission is to form the judiciary and final authority over the validity of the chain and the content of transactions. We generally assume that they are mostly benevolent and not all can be bribed. Endorsed validators may also be asked to audit and stake bonds based on their opinions on validity or information availability.
Validators: All placed in the PoS consensus master block.
They maintain signature control over the master chain. The Master Chain (MC) encodes all PoS/consensus items such as timestamps and contains its own small state root to record validators’ bond balances, open issues, fiber block header hashes, and other governance information.
For each master block (MB), a set of collated X-Fiber blocks (XBs) is used. They must not overlap so that each fiber belongs to only a single XB.
Verifier: Randomly selected to audit TX/PSR/CMP content and availability
Each MB has multiple XSBs that are referenced in the MB’s Trie. Each fiber is assigned a randomly selected set of verifiers, and the verifiers must review all XBs that contain the assigned fiber. Verification involves obtaining the Everyone is executed.
A block is considered valid if it is signed by all assigned validators. Signing this constitutes an assertion that the block contents are valid and usable for a probabilistically long “challenge period” during which fishermen can challenge them. Any challenge to the validity of a block, which is ultimately upheld by full consensus of a randomly selected set of validators (ultimately finalized by a majority vote if a strong challenge is raised), means immediate loss of bonds.
fishermen
Fishermen, called bounty hunters, are the system’s freelance error checkers. Monitor validators in the hope that they will spot any bad behavior. To ensure presence, the payouts are designed to be huge. The cost of the challenge is small but insignificant.
Fisherman: Search for invalid or unusable X-fiber blocks
Check X-fiber blocks for validation errors and/or data availability. When an invalid block or unusable data is found, a challenge is launched (by paying a small fee to the validators) in the hope that enough validators will agree. If successful and the validator ultimately disputes it, it will receive the bonds of all validators who previously asserted the validity/availability of the information.
Fisherman’s Challenge
- Fisherman discovers invalid or unusable blocks that are not yet outside the “challenge period” (10-30 blocks). Pay the fee and submit the challenge transaction to the master chain.
- A randomly selected set of validators (e.g. sqrt(N) order) ++ self-selecting validators (doubling the bond) verify the challenged blocks. Each votes Y or N on the validity of the block.
- If N, the verifier receives a small payout Pn.
- If Y, the validator stakes the bond but receives more Py (probably Py = 2Pn).
- The results of the challenge (possibly cumulative to the next block) are:
- The challenge ends when more than 66% of validators vote Y (valid). The fisherman loses his fee but can restart the challenge.
- If at least one validator votes Y (valid), the challenge continues with a larger set of randomly selected second validators. All bonds are staked.
- If all validators vote N (invalid), the block is recorded as invalid and the fishermen receive bonds from all validators who asserted the block’s validity. This is a very big reward.
- Note: If the set contains all validators, this is a simple majority rule.
Other differences
All addresses are contained in a lookup table that is unique to each state subspace. This means that it can be referenced via a small number of bits and avoids a large amount of entropy wasted in RLP for proof and c.
note
If a block falls outside the challenge period, it is considered unattackable. If found to be defective, it must be corrected in the same manner as a protocol upgrade. Therefore, validators and other large stakeholders are likely to act as fishermen to protect their investments.