Skip to content

Latest commit

 

History

History
299 lines (244 loc) · 13.2 KB

qip-0008.md

File metadata and controls

299 lines (244 loc) · 13.2 KB
Raw
 QIP: 8
 Layer: Consensus (hard fork)
 Title: Dynamic Tree Expansion
 Author: wizeguyy <[email protected]>
 Comments-Summary: No comments yet.
 Comments-URI: https://github.com/quainetwork/qips/wiki/Comments:QIP-0008
 Status: Draft
 Type: Standards Track
 Created: 2024-01-26
 License: BSD-2-Clause

Abstract

This QIP defines an algorithm by which different chains within the Quai tree of chains may agree to expand the tree and activate new chains. This algorithm provides a deterministic decision based on hash measurements in each section of the tree.

Motivation

The Quai protocol achieves high transactional throughput by dividing transactional processing into independent shards. Each shard achieves shared total security via merged-mining. Adding more chains into the tree enables higher throughput, at the cost of increased cross-chain settlement times. Therefore, it is desirable for the network to activate only as few chains as are necessary to satisfy the users' demand for transactions.

As the number of transactions processed by the network increases, block propagation & processing time will increase (a.k.a. block acceptance time). This increase in block acceptance time results in higher probability of competing blocks produced within the same time, and thus short reorganizations (a.k.a. uncleed uncles) as the networks decides on the canonical set of blocks. The ratio of work committed to blocks that ultimately do not get accepted, can be measured as wasted work performed by miners. By measuring this waste, we can objectively determine the efficiency with which miners secure the network, which we refer to as "security efficiency".

This specification provides a mechanism for measuring the security efficiency of the network, so that when security efficiency becomes unacceptably low, the network can agree to add more chains to increase transactional capacity (at the expense of cross-chain settlement times) to improve security efficiency.

Specification

Measuring Entropy Lost To Uncle Blocks

To measure the security efficiency of the network, nodes will need to compute the ratio of the amount of entropy which gets lost to uncle blocks vs the amount of entropy which gets accepted by canonical blocks. To facilitate this, each block needs to record these entropy measurements.

PoEM already describes the method of computing and recording entropy reduction in each block. That calculation is repeated below for completeness:

$$ S_i = 256 - log(hash(block_i)) $$

Uncle entropy calculation is slightly different. Since each block may reference multiple parallel uncles, the entropy for each should be accumulated.For N uncles, the uncle entropy of a block shall be computed by summing the entropy of each uncle hash:

$$ S_{i,uncles} = \sum_{j=0}^N (256 - log(hash(uncle_{i,j}))) $$

where $uncle_{i,j}$ is the $j^{th}$ uncle recorded in $block_i$.

Computing Security Efficiency Score $f$

Each node shall record recently uncled entropy and recently accepted entropy values for each chain it is participating in. Recentness of this measurement is achieved by applying an exponentially weighted moving average to the accepted/uncled entropy observed at each new block. This score can be computed iteratively with each new block added to the chain. First, the node will compute an exponentially weighted moving average of the uncle_entropy and accepted_entropy.

The weighted accepted & uncled entropies must be recorded in each chain, so that an aggregate security score can be computed in the prime chain of any node, regardless of which subordinate chains a node participates in.

Computing Cumulative Accepted & Uncled Entropies in Zone Chains

In accordance with PoEM consensus, each node already measures the cumulativ entropy reduction achieved by the work performed on every block. This entropy is accumulated and referred to as $S$. Additionally, in the Quai protocol, dominant chains record the cumulative entropy reduction achieved by each subordinate chain, referred to as $\Delta S_{sub}$. Each of these values are recorded in the header for their parent block, as ParentS and ParentSubDeltaS.

In order for dominant chains to compute a security score across the network, each chain will additionally need to record the uncled entropy and cumulative uncled entropy, $S_{uncle}$ & $\Delta S_{sub, uncles}$ respectively. These values shall be calculated identically to the accepted entropies, except that the computation will be measured on the uncle blocks instead of the accepted blocks.

Necessary Zone Chain Data In Block Header

In addition to as $S$ & $\Delta S_{sub}$, which are already recorded in the header, each chain shall record $S_{uncle}$ & $\Delta S_{sub, uncles}$. The four values recorded in the header (except in the case of zones, which do not have subordinate chains to record), are given as follows:

type Header {
    ...
    // The accepted entropy measurements are already a requirement from PoEM
    ParentAcceptedS[3]: bigint,         // prime/region/zone parent *accepted* entropy
    ParentAcceptedSubDeltaS[2]: bigint, // prime/region subordinate cumulative *accepted* entropy

    // This spec additionally requires uncled entropy measurements
    ParentUncledS[3]: bigint,           // prime/region/zone parent *uncled* entropy
    ParentUncledSubDeltaS[2]: bigint,   // prime/region subordinate cumulative *uncled* entropy
    ...
}

Computing a Network-Wide Security Score

Before computing a security score, we must exponentially weight the cumulative entropies, to prevent the score from becoming overwhelmingly biased by old blocks. We can then use these weighted measurements to compute a security score.

Computing Exponentially Weighted Entropies

First compute an error value $\epsilon_i$, as the exponentially weighted uncle entropy at block[i]:

$$ \epsilon[i] = S_{uncle}[i-1] * \alpha + S_{uncle}[i]*(1 - \alpha) $$

Next compute the exponentially weighted accepted entropy, $S_{exp}$ at block[i]:

$$ S_{exp}[i] = S[i-1] * \alpha + S[i]*(1 - \alpha) $$

Note, for efficiency S values are recorded and computed in their log2 form, rounded to the nearest integer (aka bits).

In the above computations, $\alpha$ is a smoothing factor (also referred to as TREE_EXPANSION_FILTER_ALPHA), which should be selected to filter our short term perturbances in network efficiency.

Computing A Security Score

The following equation can be used to compute the security score, $f$:

$$ f[i] = \epsilon[i] / S_{exp}[i] $$

$f$ may be used as an inverse indication of the network's security efficiency. The protocol should seek to minimize $f$ in each zone, which it can do by expanding the tree to create more zones. Larger $\alpha$ will increase the total magnitude of uncled entropy required to increase $f$. This effectively reduces the protocol's eagerness to expand the tree.

A security score can be computed in the same way for any chain, but this protocol is only interested in the global score, denoted as $f_{global}$, to decide when to expand the tree of chains. The global score is the $f$ score computed on the prime chain.

Activating New Chains

When $f_{global}$ exceeds a certain threshold for a long enough time, the network can agree that it is time to add more chains to increase the transactional capacity of the network. The process for deciding when and how to add more chains, is described in the sections below.

When to Expand

The network will agree to add more chains to the tree, once all of the following conditions are met:

  1. all active chains have mined consecutive prime blocks confirming $f_{global}$ exceeds the TREE_EXPANSION_THRESHOLD
  2. TREE_EXPANSION_TRIGGER_WINDOW consecutive prime blocks confirm $f_{global}$ after condition 1.

Once the expansion criteria have been met, the network will schedule expansion to occur in the future. After TREE_EXPANSION_WAIT_COUNT blocks have elapsed since the block which finalized the decision to expand, blocks from the new chains will be accepted by the network. The last prime block of the wait period TREE_EXPANSION_WAIT_COUNT will be refered to here on as the prime activation block.

How Many Chains To Add

The Quai protocol defines a tree of blockchains of order 2. Initially, the tree is of degree 1: prime chain, with a single subordinate region chain, which has a single subordinate zone chain. As the network decides to add new chains, it will use the following algorithm to decide how many chains to add, and in which branches of the tree:

Algorithm to decide which chains to add:
1: if degree(zone) <= degree(region) then
2:   add 1 chain to each zone
3: else then
4:   add 1 region under prime
5:   add degree(zone) zones under the new region
6: end if

For example, the table below gives the tree ontology after the first few expansions

Expansion no. # regions in prime # zones in each region
0 (genesis) 1 1
1 1 2
2 2 2
3 2 3
4 3 3
5 3 4
6 4 4
. . .
. . .
. . .
30 15 15
31 15 16
32 16 16

Old Zones Wait To Send ETXs

To mitigate migration challenges to the new chains, its important for the blockchains to stabilize and merge mine together for some time, before processing cross-chain transactions. To achieve this, we add a few constraints that must be satisfied before cross-chain transactions can be sent to these new chains.

First, the following sequence of events must occur:

  1. first, the new chain must mine a prime block that gets accepted by the network
  2. then the sending chain must mine a prime block committing to the new chain as an ancestor.

Additionally, at least TRANSACTION_WAIT_COUNT prime blocks must have been mined on-top of the new chain's first prime block.

Once these two conditions occur, the old chain may begin to process external transactions destined to the new chain. These conditions must be satisfied for any chain wishing to send to any of the newly added chains.

Genesis Block for New Chains

Once new chains have been activated, the activation block will be treated as the genesis block for all newly activated chains. The first block after genesis is built as an extension, with zone and optionally region parameters reset for the new chain.

The initial difficulty in each new chain shall be the difficulty of the genesis block divided by the number of chains in the network.

Note: the genesis block of the very first chain in the network can be viewed as the first expansion from a degree-0 tree to degree-1. All expansion logic is identical, even in this special case.

Example

< TBD example diagram >

Security Statement

This specification works as long as miners record the uncles they witness. If miners choose not to record uncles, then the protocol cannot effectively measure uncled entropy. Therefore the incentive structure of the network should make sure that the dominant strategy for a miner is to record uncles, in lieu of any incentive they may have to prevent the network from expanding. This should not be difficult, but incentive mechanisms will be left for another QIP.

Choosing Expansion Parameters

The above protocol for tree expansion is defined around a few adjustable parameters, given below:

TREE_EXPANSION_FILTER_ALPHA

This is the smoothing factor (range 0-1) used by each zone in its low-pass filter to gather a long running average of the zone's security efficiency score. Choosing a larger $\alpha$ will make the filter less responsive; the tree expansion algorithm will be less susceptible to short term variations in the efficiency score, but will take longer to decide to trigger an expansion when one becomes necessary.

Choose TREE_EXPANSION_FILTER_ALPHA = 0.9

TREE_EXPANSION_THRESHOLD

This is the threshold (range 0-1) above which the $f_{global}$ score will begin the tree expansion decision process. This threshold should be chosen high enough to not be easily triggered by minor changes in node operating behavior, but not so high that the security efficiency becomes unacceptably low.

Choose TREE_EXPANSION_THRESHOLD = 0.5

TREE_EXPANSION_TRIGGER_WINDOW

Once all chains have confirmed $f_{global}$ above TREE_EXPANSION_THRESHOLD, this is the number of consecutive prime blocks that $f_{global}$ must remain above the threshold to confirm the decision to expand the tree.

Choose TREE_EXPANSION_TRIGGER_WINDOW = 144 prime blocks (apprx 24hrs at 10m prime block time)

TREE_EXPANSION_WAIT_COUNT

Once the network has confirmed the decision to expand the tree, this is the number of prime blocks to wait until the expansion is activated. This should be chosen to give node operators some time to adjust their infrastructure, if needed, to account for the upcoming network change.

Choose TREE_EXPANSION_WAIT_COUNT = 1024 prime blocks (apprx 1 week at 10m prime block time)

TRANSACTION_WAIT_COUNT

Once a new chain has been added to the network, no chain may sent cross-chain transactions to it, until it has at least TRANSACTION_WAIT_COUNT blocks built upon the new chain's first coincident prime block.

Choose TRANSACTION_WAIT_COUNT = 1024 prime blocks (apprx 1 week at 10m prime block time)

Copyright

This QIP licensed under the BSD 2-clause license.