History
The first seed of this idea came to me while chatting with Janislav Malahov in Berlin in the spring of 2014. Unfortunately, the original article I wrote was lost along with my laptop when it was stolen in Vienna. After discussing the principles with Vitalik more recently, we made a number of modifications and formalizations, mainly to the validation and substate slicing mechanisms. What follows is a fairly comprehensive illustration of a particular possible plan for blockchain scalability in a later version of Ethereum.
Since this is by no means a final proposal, there is a GitHub wiki page which will track the progress of this particular idea.
General description
The basic idea of Chain-Fibers hasn’t changed for a year; divide the state space into strata and have separate transaction collectors that specialize in one or more state subspaces. Transactions that require interactions of many subspaces would therefore be more expensive (since collectors would have to maintain their presence on multiple chains) and take longer to execute (since there is less chance that a given block would contain a superset of the subspaces). transaction subspaces). The validity of a transaction can be verified in isolation by providing comprehensive Merkle proofs to its inputs along with it in the block in which it is included.
The subtleties lie precisely in what governs the division of subspaces (my original proposal included automated division, merging, and rotation of subspace divisions for best internal consistency), how security is maintained within the comparatively worthless subspaces and how this can work well. with Proof-of-Stake (the original was based on a master PoW chain, fueling an idea put forth by Max Kaye in early 2014 to disassociate the file from the blockchain from transition semantics).
The basic idea is to have a series of strings (eg, N), each of which details the state transitions for only one stratum of the state of the entire system (ie, a state subspace). Following programming terminology, these could be called “fibers”. The beads thus belong to a subspace and as such to a single fiber; 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 that is held within the cleanup information in the “Master String”.
The MasterChain is maintained by a set of linked Validators V, with a number of validators proportional to N. A random selection of validators validates each block produced, and ultimately the validators vote to form a consensus on the MasterChain. Each block of the Master Chain maintains a reference to the headend of each fiber.
Transaction collectors produce blocks (they accept fees from transactors) and pay validators some of the fees charged to include their block hash on the main chain. The batts are produced through a particular “home pool” of fibers; this is basically just the set of fibers that maintain the Trie State. Your blocks may involve transactions over one or more of these fibers, even if none outside of your “source set.”
“Fishermen” is a term given to self-employed inspectors. Since both validation and block availability are important, and since it is possible that sets of validators could be bribed by contract, it is important to have a mechanism to involve more rational people acting as “informants” to avoid bogging down to the other validators unnecessarily. Checking all the blocks. Anglers basically pay to try to convince a quorum of validators that a previously validated block is invalid (or unavailable, which we assume is equivalent). If an angler proves that a validator (or, more likely, a set of validators) acted dishonorably, then he can claim all of her bonuses. To prevent DoSing validators with fake challenges, a fee is paid.
Schematic
Sorry about the not quite ASCII art. I’m not as 1337 in 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 pretty much the same as in Ethereum 1.0: they are the users of the system.
Transactors: make transaction
Transactors perform a transaction much like they do in the existing Ethereum system. One or two minor differences: addresses can be used as a distance metric; those that share the same number of initial bits are considered “closer”, meaning greater certainty in the future that they will still be contained in the same state subspace. Contracts are naturally created in the same state subspace as the creator.
Transactions, like Collators, operate on a series of fibers; maybe one maybe all, probably somewhere in between. Sending to matchers can be routed across fiber subnet overlays.
Sending and paying to matchers happens much like sending existing transactions to miners in Ethereum 1.0.
Matchers
Collectors maintain their presence in at least two peer subnet overlays; the validator overlay and one or more fiber overlays. Fiber overlays can provide targeted transaction propagation. The lifters “collate” on a set of fibers. They maintain a complete fiber chain for each fiber they collate and can accept all transactions involving any combination of their fiber pool. The higher this combination, the higher your “net transaction” will be, but the higher your total disk/memory footprint will be.
Matchers: validate transaction
Upon receiving a transaction, they go through the usual Ethereum 1.0 rites of checking that the payment is sufficient, initial balances, etc. Once the basic validation is done, they try to run it and throw it away if it touches any fiber that is not part of the interleaver fiber set.
Sorters: produce full Merkle proofs and post-state roots
Collectors provide each post-root-status (as found in the Ethereum 1.0 transaction receipt) and add to the block Merkle proofs and associated hints (e.g. contract code) for all inputs (balance, nonce, status). , code) of all the subspaces that are required for the evaluation of each transaction from a previously known root-post-state.
This allows an auditor, with nothing more than the previous post-state root for each fiber, to determine the validity of the block.
Classifiers: collate in fiber block X
A cross fiber block is created from the total information collected. This includes transactions, transaction receipts (post-state-roots), Comprehensive Merkle-Proofs, and associated hash-hints. This block does not include any consensus specific information such as timestamp, uncles, etc.
validators
Validators (which might be better called auditors) are tied participants, regularly chosen from the highest bidders, who charge a small fee for the final maintenance of the network. Its job, as a whole, is to form a judicial and maximum authority on the validity and content of the chain’s transactions. We usually assume that they are mostly benevolent and that not all of them can be bribed. By being linked, validators may also be called upon to audit and stake their link on an opinion on the validity or availability of the information.
Validators: all placed in the PoS consensus master block
They maintain signature control over the Master Chain. Master Chain (MC) scrambles all the PoS/consensus stuff like timestamp and includes its own little state root to record validator bonus balances, ongoing challenges, fiber block header hashes, and any other maintenance information.
From each master block (MB), a set of collated X-Fiber Blocks (XB) is taken; these should not overlap, so that each fiber belongs to a single XB.
Validators: random selection chosen to audit the contents and availability of TX/PSR/CMP
For each MB, we have a number of XSBs that are referenced from the MB Trie. Each fiber is assigned a set of randomly selected validators, and the validators must review any XB that contains their assigned fiber. Validation includes reaching the XB, finding the previous PSRs for each of the fibers (located in the MB), and verifying that the tests in your CMP cover all required inputs for the transactions matched within and that the PSR is in fact the root. of the final state when all are executed.
The block is considered valid if all assigned validators sign it. Signing it is considered an assertion that the contents of the block are valid and available during a probabilistically long “contest period” in which a Fisher can contest. Any challenge to the validity of the block that is ultimately confirmed by a full consensus of a randomly selected set of validators (ultimately ending with a majority vote, should it be stubbornly challenged) will mean instant forfeiture of the bonus.
fishermen
Fishermen (who could be called bounty hunters) are the system’s independent bug checkers. They keep an eye on validators in the hope that they can find irregularities. To help ensure presence, the payouts are designed to be huge. The costs of challenging are small but not negligible.
Anglers: Search for Invalid or Unavailable X Fiber Blocks
They check the X fiber blocks for validity errors and/or data unavailability. When they find an invalid block or unavailable data, they issue a challenge (for a small fee, paid to the validators) in the hope that a large enough portion of the validators will agree. If they are successful and the validators finally accept the challenge, they receive the bonuses of all the validators who had previously asserted the validity/availability of the information.
angler challenge
- Fisherman finds an invalid/unavailable block that is not yet out of its “challenge period” (10-30 blocks); pay a fee, send a challenge transaction to the master chain;
- A set of randomly selected validators (eg, of order, eg sqrt(N)) ++ any validator that self-selects (by doubling its binding), check the block that was challenged; each one votes Y or N to the validity of the block;
- If N, the validator receives a small payment Pn.
- If Y, the validator bets his bonus, although he receives a higher payout Py (perhaps Py = 2Pn).
- The result of the challenge (probably accumulated in the next block) is:
- If more than 66% of the validators vote Y (valid), the challenge ends. The Fisherman loses his fee, but can restart a challenge.
- If at least one validator votes Y (valid), then the challenge continues with a second, larger set of randomly selected validators. All bonuses are wagered.
- If all validators vote N (invalid), then the block is recorded as invalid and Fishers are bailed out by all validators who have affirmed the validity of the blocks. This is a very big reward.
- NOTE: If the set includes all validators, it is a simple majority rule.
other differences
All addresses are contained in a unique lookup table for each state subspace; this means they can be referenced via a small number of bits and avoid large amounts of wasted entropy in the RLP for testing etc.
notes
Once a block is out of the challenge period, it is considered impregnable. If it turns out to be bad, then it should be fixed in the same way as a protocol update. As such, validators and other major stakeholders are likely to act like fishermen to protect their investment.
