Chronicle
I conceived the initial spark of this concept while conversing with Janislav Malahov in Berlin during Spring 2014. Regrettably, the initial article I crafted was lost alongside my laptop when it was pilfered in Vienna. After discussing the foundational principles with Vitalik more recently, we implemented several modifications and formalizations, primarily regarding the validation and the sub-state separation methods. What follows is a relatively comprehensive depiction of one specific potential strategy for blockchain scalability in a subsequent iteration of Ethereum.
As this is by no means a conclusive suggestion, there exists a GitHub Wiki page that will monitor the developments regarding this unique concept.
Summary
The fundamental notion of Chain-Fibers remains unchanged from a year prior; divide the state-space into layers and designate distinct transaction collators that specialize in one or several state sub-spaces. Transactions necessitating interactions from various subspaces would consequently incur higher costs (as collators would be required to coexist on multiple chains) and have longer execution times (due to a diminished likelihood that any random block would encompass a superset of the transaction’s subspaces). The validity of a transaction can be verified independently through the provision of thorough Merkle proofs to its inputs included within the block in which it is recorded.
The nuances hinge on precisely what dictates the partitioning of subspaces (my original suggestion incorporated automated splitting, merging, and rotation of subspace divisions to optimally ensure internal coherence), how security is upheld within comparatively lesser-value subspaces, and how this can integrate well with Proof-of-Stake (the initial concept was based on a master PoW chain, inspired by an idea proposed by Max Kaye in early 2014 to dissociate blockchain archiving from transition semantics).
The principal idea is to have several chains (e.g., N), each depicting the state transitions for merely a layer of the comprehensive system state (i.e., a state subspace). Borrowing from programming terminology, these could be labeled “fibers”. Accounts thus belong to a subspace and therefore a singular fiber; the fiber to which they are attached can easily be identified from the initial log2(N) bits of the address. N can fluctuate, and is a value preserved within the housekeeping data on the “Master Chain”.
The Master Chain is upheld by a collection of bonded Validators V, with the number of validators proportional to N. A random selection of validators confirms each block created, and validators eventually vote to reach consensus over the Master Chain. Every block of the Master Chain keeps a reference to the header of each fiber.
Transaction collators generate blocks (receiving fees from transactors) and remunerate Validators a portion of the fees gathered to include the hash of their block in the primary chain. Blocks are produced across a designated “home set” of fibers; this is essentially the group of fibers of which they maintain the State Trie. Their blocks may encompass transactions over one or several of these fibers, yet none outside their designated “home set”.
“Fishermen” is a term designated for independent verifiers. Since block validation and availability are crucial, and given that it is conceivable for groups of validators to be contractually incentivized, it becomes vital to have a system that engages additional rational individuals to act as “whistle-blowers” to prevent burdening the other validators unnecessarily by checking all blocks. The fishermen essentially compensate to persuade a quorum of validators that a previously validated block is indeed invalid (or unavailable, which we assume is equivalent). Should a fisherman illustrate that a validator (or, more likely, a subset of validators) acted unethically, they have the right to claim all their bonds. To avoid spamming the validators with baseless challenges, a fee is required.
Schematic Representation
I apologize for the not-quite ASCII-art. I’m not quite as skilled at Inkscape as Vitalik.
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
Transactors
Transactors are essentially identical to those in Ethereum 1.0 – they are the system’s users.
Transactors: make transaction
Transactors perform a transaction much like they do in the current Ethereum framework. With one or two slight distinctions – addresses can function as a distance metric; those sharing the same initial bits are deemed “closer,” indicating a higher likelihood that they will persist within the same state subspace in the future. Contracts are naturally formed within the same state subspace as their creator.
Transactions, similar to Collators, operate over multiple fibers; potentially one or perhaps all, likely somewhere in between. Submission to collators may be guided through fiber sub-network overlays.
The submission and remuneration to the collators occurs similarly to how transaction submissions to miners take place in Ethereum 1.0.
Collators
Collators ensure their presence across at least two peer sub-network overlays; namely, the Validators overlay and one or more fiber overlays. The fiber overlays may enable directed transaction propagation. Collators “collate” over a set of fibers. They maintain an entire fiber-chain for each fiber over which they collate, and can accept all transactions involving any assortment of their fiber set. The broader this assortment, the larger their “transaction net,” though this also increases their overall disk/memory footprint.
Collators: validate transaction
Upon receiving a transaction, they perform the standard Ethereum 1.0 rituals of confirming adequate payment, initial balances, etc. Once preliminary validation is completed, they endeavor to execute it, discarding it if it interacts with any fiber that does not belong to the collator’s fiber set.
Collators: produce Comprehensive Merkle Proof and Post State Root
Collators provide each post-state-root (found in the transaction receipt of Ethereum 1.0) and append to the block Merkle proofs and associated hints (such as contract code) for all inputs (balance, nonce, state, code) from all subspaces necessary for evaluating each transaction from a previously known post-state-root.
This enables an auditor to ascertain the validity of the block, using only the previous post-state-root for each fiber.
Collators: collate into X-fiber Block
A Cross Fiber Block is generated from all the collated information. This encompasses transactions, transaction receipts (post-state-roots), Comprehensive Merkle-Proofs, and associated hash-hints. This block does not encompass any consensus-specific details like timestamping, uncles, etc.
Validators
Validators (who might be better referred to as auditors) are bonded participants, chosen regularly from the highest bidders, who charge a nominal fee for the ultimate maintenance of the network. Their collective role is to serve as a judiciary and the ultimate authority on the validity and transaction details of the chain. It is typically assumed that they are largely benevolent and cannot all be bribed. Being bonded, validators can also be called upon to audit and stake their bond on an opinion regarding validity or information availability.
Validators: all placed in PoS-consensus master block
They maintain signing authority over the Master Chain. The Master Chain (MC) encodes all PoS/consensus information such as timestamping, and includes its own small state root for recording validator bond balances, ongoing challenges, fiber block header-hashes, and other housekeeping details.
Within each master block (MB), a collection of collated X-Fiber Blocks (XBs) are compiled; these must not overlap, ensuring that each fiber belongs to just one XB.
Validators: random selection chosen to audit TX/PSR/CMP contents & availability
For each MB, there exists a number of XSBs referenced from the MB’s Trie. Each fiber is assigned a randomly chosen group of validators, who must assess whatever XB contains their designated fiber. Validation includes acquiring the XB, locating the previous PSRs for each of the fibers (included in the MB), and ensuring that the proofs in its CMP cover all required inputs for the transactions collated therein and that the PSR indeed represents the final state root when executed.
A block is deemed valid if all assigned validators sign it. Signing it is regarded as an assertion that the block contents are both valid and available for a probabilistically substantial “challenge period” during which a Fisherman may contest. Any challenge to the block’s validity, ultimately upheld by a full consensus of a randomly chosen grupo of validators (culminating with a majority vote, should it be contested), will result in the instant forfeiture of the bond.
Fishermen
Fishermen (who might be referred to as bounty hunters) serve as the freelance error-checkers for the system. They observe the validators with the hope of uncovering misconduct. To promote engagement, rewards are structured to be substantial. The costs associated with initiating challenges are minimal but not negligible.
Fishermen: search for invalid or unavailable X-fiber blocks
They scrutinize the X-fiber blocks for validity errors and/or data unavailability. Upon discovering an invalid block or unavailable data, they initiate a challenge (for a small fee, rewarded to validators) in the hope that a considerable portion of validators will agree. If successful and validators eventually uphold the challenge, they gain the bonds of all validators who had previously claimed validity/availability of the information.
Fishermen’s Challenge
- The Fisherman identifies an invalid/unavailable block still within its “challenge period” (10-30 blocks); pays a fee and submits a challenge transaction into the master chain;
- A randomly chosen group of validators (e.g., of order such as sqrt(N)) plus any validators that self-select (by doubling their bond), review the block that was contested; each votes Y or N on the block’s validity;
- If N, the validator receives a small payment Pn.
- If Y, the validator stakes their bond, though receives a larger payment Py (potentially Py = 2Pn).
- The result of the challenge (likely aggregated into the subsequent block) is:
- If over 66% of validators vote Y (valid), the challenge concludes. The Fisherman forfeits their fee but may initiate another challenge.
- If at least one validator votes Y (valid), the challenge proceeds with a second, larger group of randomly selected validators. All bonds are staked.
- If all validators vote N (invalid), the block is recorded as invalid, and the Fisherman receives the bonds of all validators who asserted the block’s validity. This is a substantial payout.
- NOTE: If the set includes all validators, a simple majority-carries rule is applied.
Other distinctions
All addresses are contained in a lookup table that is unique to each state subspace; this allows them to be referenced through a limited number of bits while minimizing excess entropy in the RLP for proofs, etc.
Notes
Once a block exits the challenge period, it is regarded as unassailable. If it is later revealed to be faulty, then it must be rectified similarly to a protocol upgrade. Thus, it is anticipated that validators and other major stakeholders would act as Fishermen to safeguard their investments.
