BUIP024: Extension Blocks with Address Sharding
Proposer: Andrew Stone
Submitted: 2016-08-03
Status: draft
Proposal for your critical review, I’m not formally submitting this yet.
Please respond with any comments you may have.
Part 1:
INTRODUCTION
If a hard fork becomes possible, we need technologies to be ready to
take advantage of the opportunity. Today, the network is hobbled because
every full node must receive and process every block and transaction. If
M is the number of transactions, then every node’s bandwidth, CPU and
memory requirements are O(M). Since, every node must process all the
data flowing through the entire network, the speed of the network is
necessarily limited to the speed of the average node. This BUIP proposes
a technology that will allow the Bitcoin network to scale to any level
of use, by enabling O(log(M)) scaling by splitting (sharding) the
network into regions where data does not need to be shared.
Current sharding proposals fail because they conflate the physicality of
a node with a single trusted entity, and assume that every node should
be capable of mining. In other words, in today’s Bitcoin a node trusts
only itself. This proposal separates these concepts into a physical
machine (a node) with O(log(M)) requirements and a mining “trust entity”
with O(M) requirements. The outcome of a breach of trust is not
problematic to the network as a whole – it is just punishing to the
trust entity since the effect is that an invalid block is mined with the
resulting loss of revenue.
If a node is not mining, there is no need to be part of a larger trust
entity. Therefore, this proposal is no worse than Bitcoin today with
respect to scalability of the mining trust entity, and much better for
individual non-mining nodes and individual mining hardware.
This proposal does not address how trust entities can be formed because
the formation mechanism does not affect the proper execution of this
algorithm. The simplest mechanism is that a single individual or
corporation can run multiple nodes. While some people may feel that this
will encourage centralization of the network, this is already the
reality of Bitcoin mining and mining pools today. And so it is foolish
to limit Bitcoin’s growth in an attempt to win a battle that has already
been lost. One cannot fail-to-grow your way to success. However, other
trust creation mechanisms are possible, such as mining at lower
difficulty or block revenue sharing. Exploration and game-theoretic
analysis of these organization mechanisms may result in algorithms that
help decentralize the transaction validation and mining network by
allowing trust entities to form by mutual self-interest.
Finally, arguably the most important aspect of Bitcoin’s trustless
nature is permissionless partcipitation. The property is preserved. If
an individual cannot afford the hardware necessary to validate the
entire network and mine blocks he/she can form a group and do so without
the permission of the other participants in the network.
ARCHITECTURE
A new block header format is created that contains the SHA-256 hash of
up to 8 shard-blocks. Any transaction may be found in the root block,
but shard-block 0 may only contain transactions that contain addresses
that (in binary) begins with bX000, shard-block 1’s transactions’
addresses begins with bX001, 2 bX010, and so on, where X is the prefix 1
for normal addresses and 3 for multisig addresses. This is simply a way
of sharding the data, so it makes sense to ignore the common prefix in
addresses. This proposal covers common address formats, but other
address formats would have their own sharding algorithm which would be
similar to what is described here.
Shard-blocks may contain shard-shard-blocks (shard-2-block) with a
further specialization of address, recursively. Blocks MAY contain no
shard-blocks at all, and do not need to contain shard-blocks across the
entire address range. If an attacker creates a gigantic tree of
shard-chains with few transactions, this will slow down validation so
the block risks being orphaned. An option is to require that parent
blocks be at least 75% full (say). However, this approach creates a
parallelism problem where a machine working on a child shardchain cannot
proceed until it knows which transactions the parent shardchain has used
to fill its block. With no parent block fill requirement, transactions
can be delivered to the machine working on a child shardchain as they
come in.
When a transaction contains addresses with the same prefix, the
transaction can be located within the shard-block designated for that
prefix, or within any parent block.
Therefore paying across address prefixes requires a transaction in the
common parent, which could ultimately be the root block for transactions
with no common prefix.
Transactions may be sorted in the merkle tree (to implement fraud
proofs) and the transaction format may be flex transactions depending on
the status of those BUIPs. Anything not covered will default to the root
block to ensure that this proposal can handle anything unanticipated in
the submitted transactions.
P2P Network
Nodes will need to discover and keep track of where to access data for
particular shardchains. This resource discovery problem in a
peer-to-peer network is a well known problem solved by distribute hash
table protocols like Chord, Tapestry, and Pastry. However, the number of
shardchains is anticipated to be so much smaller than that of nodes and
node (for the foreseeable future) that a simpler “degenerate” approach
of every node simply storing the shardchain metadata of every other node
it knows about is possible. A simple flood query protocol can be used to
allow a node to request sources for shardchains.
Nodes will only relay transactions only to nodes that track the relevant
shardchain, unless the node has no data about that chain. In that case,
the node will relay the transaction to all its connected nodes.
Part 2:
CONSEQUENCES
Non-mining Nodes (Individuals and Merchants)
A node could limit itself to storing a particular set of shard
blockchains (shardchains) and all parents. It would therefore act as a
“full” (fully validating) node for all addresses that fall into a
shardchain that it stores. A double spend must exist in that shardchain
or a parent so is easily detected by the node. The node would act as an
“SPV” wallet for all shardchains that is is not storing. However at any
time the node can start requesting blocks of a given shardchain
(preferably from most recent to oldest) and thereby build confidence in
the correctness of address ranges in that new shardchain. Therefore, the
security model is the same as Bitcoin for all blocks that the
individual’s wallet chooses to download the shard’s complete history.
By generating appropriately prefixed addresses just like we generate
vanity addreses today, personal wallets can keep their addresses within
a few shardchains.
An entity that handles a lot of transactions might have addresses in
many shard blocks so that users can pay with addresses convenient for
them.
Let us assume 3 main payment models in the world – P2P, fan-in (high
volume low value retail – a coffee shop, for example), and fan-out (ad
networks, for example). Individuals commonly typically engange in P2P
use models (pay a friend) and fan-in models (buy things from a store).
It is likely that a typical individual’s daily P2P payment use is highly
localized – its a network of friends, family, and localized “yard-sale”
like transactions. In these cases, if the shard-blocks were more-or-less
localized with a specific economic sphere (this may happen naturally, or
it may happen with some “help” via human’s self-organizing), most of the
P2P transactions would occur within a shardchain (remember that a single
shardchain can handle the ENTIRE bitcoin economic activity happening
today).
Companies with fan-in or fan-out models that could afford higher
performance hardware or multiple nodes could keep track of and hold
balances in many or all of the shardchains, and in the fan-in case, the
QR code (or payment protocol) could be extended to offer several
recipient address choices, allowing the sender’s wallet to automatically
choose a shardchain that he has a balance in. With these strategies,
most of the transactions can occur in shardchains. This is not a
requirement – we will allow transactions to cross blocks as described
next – but companies might do this for efficiency reasons.
But there will be times when a transaction must cross blocks. These
transactions will be stored in the shardchain that encompasses all
address in the transaction. But the transaction’s inputs may reference
an output in a shardchain that the receiving node does not have. In this
case, the receiving node can behave as a SPV wallet or start downloading
that shardchain’s blocks. If “Fraud Proofs” are deployed, the receiving
node has even more validation ability – it can selectively request
blocks in a shardchain to ensure that the transaction exists within it.
It would be the individual’s choice as to how deeply he wants to
validate the coin history in a shard that his client is not tracking. He
could rely entirely on miners for validation, he could trace N weeks
back in the blockchain, or he could have a trust relationship with a 3rd
party service that is doing the tracking, similar to many mobile wallets
today.
Miners/Mining Pools
Miners must validate all shardchains within a block or risk mining on an
invalid block. However, miners can decompose this task onto multiple
nodes that can even be geographically located near the majority of the
activity on the shardchain, receive transactions for that shardchain
directly from other nodes on the bitcoin P2P network, only forward the
hash of the shard block to the “root” mining node, and serve the shard
block locally. So as described above, although trust entity scope is
O(M), the computing and network resource requirements only that of a
portion of the tree of shardchains or O(log(M)).
Miners can delegate the validation of a shardchain to a third party that
tracks that shardchain relatively safely (since most blocks will be
valid, as an invalid block would cause loss of revenue for the miner of
that block).
Fee Market
Competition for space within shardchains will increase as one moves
towards the root because blocks closer to the root encompass a larger
scope of transactions, and transactions that move coins between
shard-chains MUST be placed closer to the root. Also, blocks closer to
the root will be generated more often then blocks on the edge, if some
miners only validate shardchain blocks or cannot generate a deep shard
soon enough. A high transaction fee will encourage a miner to place the
transaction in his blocks even if it is not mining the deepest
shardchain that that transaction could be placed into.
CONCLUSION
Nearly infinite scalability
User clients do not require more bandwidth than today. They can be
“full nodes” for regional transaction and SPV nodes (or full nodes if
they want) for others.
Competition for cross block space or faster confirmation creates
demand for transaction space closer to the root node, resulting in
higher transaction fees -> fee market
Encouraging mining pools to start generating blocks in a new
shardchain creates higher transaction fees -> fee market
Miners (hashers) do not need a higher bandwidth than today
Mining pools can distribute the validation work across multiple
servers, and move the servers to the regions using different
shardchains, rather then the transactions to the servers.
User clients with a lot of activity (corporations, exchanges, etc)
can validate any/all shardchain “regions” and can delegate this
validation to a network of machines.