Block Life Cycle and Difficulty Adjustment

The overall process of creating new blocks on a single chain is:

      createPayload   wait   mine   validate   createPayload   wait   mine   validate
... |-------------->|----->|----->|--------->|-------------->|----->|----->|--------->| ...

where

• createPaylaod is the call to pact newBlock that assembles a new payload and executes Pact on it,
• wait indicates that the chain is waiting for the parent headers on adjacent chains to become available and may be of zero length,
• mine means that miners are working to resolve the POW challenge, and
• validate is the time it takes to propagate the and validate the block in the consensus network.

In a Chainweb, the beginning of the mine phase on a chain is synchronized with then end of validate phase of all adjacent chains, because it is only possible to mine a new block if all adjacent parents are available.

The wait phase is making up for any variance in the other phases between chains.

For the purpose of DA, we assume that createPayload and the validate phase are more or less constant across chains and we will refer to them jointly as latency

Preliminaries

In diagrams we draw different phases of the block live cycle using different arrows: --> for latency, ~~> for wait, and ==> for mine. If the wait phase is of zero length we don't show it. c0 is chain 0 and c1 is chain 1, and so on. The vertical bars between chains indicate synchronization.

c0: ... |=========>-->|==========>-->~>|========> ...
c1: ... |===>-->~~~~~>|~~~~~>|=====>-->|~~~~~>|=> ...
c2: ... |================>-->|============>-->|=> ...

Synchronization doesn't necessarily correspond to the same absolute real world time on different nodes, since blocks arrive add remote nodes at different times and also the times for creating payloads differ. But in the context of difficulty adjustment we can ignore those differences.

In the example diagram above the chain c1 is consistently faster in mining then c0 and c2, which results in longer wait times, during which the chain is blocked.

Mining targets are integral values with a maximum of maxTarget = 2²⁵⁶ - 1. The difficulty and the mining target are related as follows:

For the purpose of this document we omit all numerical aspects like type and encoding of numbers and rounding. In the actual implementation those are important details and require great care.

Global Difficulty Adjustment

The goal of difficulty adjustment is to maintain a targeted block rate on each chain and also globally.

Global difficulty Adjustment works by measuring the time that it takes to process a fixed number (120 on mainnet) of those block cycles, which is called an Epoch and adjusting the POW difficulty such that the expected time of an epoch matches the targeted time.^[1]

When the measure epoch time is too short the new target is lower, and, conversely, when the measure epoch time is too big the target is increased. Without going into all details, the formula is roughly

Because chains synchronize with their adjacent chains during each block cycle, the wall-clock time for an epoch is mostly the same. The difference between chains are only in the order of the differences for a single block cycles time the diameter of the network. Assuming uniform distribution over the time of the epoch, on mainet with 10 chains the expected global difference is roughly 2/120 of the expected accumulated local differences.

Discrepancies in the hash power or the targets between different chains takes a long time to adjust. Generally, that isn't an issue, because miners have an interest in accurate difficulties and are expected to distributed their hash power accordingly: If the relative difficulty between chains is too much off, chains become blocked often which increases the number of orphans and thus decreases the efficiency of mining. Also mining on chain with too low difficulty becomes a lottery with the actual hash power being less relevant for the outcome. Because of this the current mining coordination algorithm is very good in balancing hash power and preventing discrepancies in first place.

This is what is currently implemented in the Kadena Mainnet. It has been tested extensively and proven to be robust, both, in production Chainweb instances, as well as in numerous simulations of a wide range of conditions.

Per-Chain Difficulty Adjustment

The ideas in this section are not yet deployed on a public chainweb network. There exist prototypes that are currently tested.

The goal of per chain difficulty adjustment is to minimize the time that chains are in the wait phase. This is achieved by allowing for larger differences in the adjustments between chains. There are two approaches to per chain adjustments:

1. If all chains use the same hash algorithm, there is no reason why chains should have a different difficulty because hash power is automatically balanced between chains.^[2]

   In this case the goal is to adjust difficulty such that (a) the target epoch time is met and (b) and the difference of the difficulty between chains is minimized.

2. If chains use different hash algorithms Difficulty adjustment must be able to measure the time that chains are in the wait phase relative to other chains. Difficulty adjustment needs this information in order to be able to minimize the wait times.

During block creation and validation the following relevant block information is available:

1. creation times of parent andadjacent parents,
2. target of parent and adjacent parent,
3. epoch start time of current chain and adjacent chains, and
4. block height of current chain and adjacent chains.

In the first case, it is enough to compute the target using the global difficulty adjustment algorithm for the current and all adjacent chains and use the average.

The second case is more interesting and we focus on it in the following.

Miner a free to select a creation time for a new block at any time in any phase of a block cycle as long as

1. the creation time of a block is strictly larger than the creation time of the parent and all adjacent parents and
2. the creation time is not in the future, or more precisely is not in the future during validation.

From the second point it follows that the creation time can be from the validation phase of the previous block but not in the validation phase of the block itself. Actually, depending on where the previous block picked its validation time it can go back even further.

The current mining coordination code of a chainweb node picks the end of the wait phase (start of the mining phase) as block creation time. But it's important to not that miners are free to change/update that.

c0: ... |====>-->~~~~>|========>-->~~~~~>|======>-->~~~~>| ...
     ........> 
             ..................>
                               .................> 
                                                .............
        ^             ^                   ^              ^
    creationTime  creationTime        creationTime    creationTime

The dots indicate the possible choices for miners (within the mentioned constraints). Note that the intervals are open to the left. The bottom two lines indicate the choice by the current node implementation.

What value should a miner choose? A rational miner will choose whatever results in the largest difficulty, for the above mentioned reasons. So, the difficulty adjustment algorithm must take this into account and must align its goals with the this objective of the miners. Note, that there is no lower bound block times with respect to real world time. There is only an upper bound.

In order to minimize the wait time, we need a way to measure the accumulative length of the wait phase during an epoch. We don't have enough information to measure an absolute value for a single chain. We only have the creation times of the blocks and the epoch start time. Let n be the size of an epoch. For a given epoch the sum of the differences of the creation times is the wall-clock time since epoch start with :

This does even hold if miners make pathological choices for block creation times, like only increasing block times by microseconds starting from genesis. However, difficulty would become very low and thus there is an incentive for miners to choose values that result in long epoch times.

So, we can't measure the absolute value of the wait time on a chain. We can, however, measure the difference in creation times between chains. We use this in difficulty adjustment as follows:

For each block b, with and , we define

and

where x is some constant that depends on the properties of the exponential distribution, the targeted block rate, and the number of chains. The algorithm is supposed to increase the difficulty of "fast" chains and reduce the time that chains are blocked. Ideally, the added difficulty is compensated by hash power that is gained due to the lower amount of orphans because mining is distributed more evenly across chains.

Let's consider an example:

c0: ... |=========>-->|==========>-->~>|========> ...
c1: ... |===>-->~~~~~>|~~~~~>|=====>-->|~~~~~>|=> ...
c2: ... |================>-->|============>-->|=> ...

blocks: b0            b1     b1        b2     b2

The wait times per chain and per block are ordered as follows:

• b1: c1 > c0 == c1,
• b2: c1 > c0 > c2

Let consider what happens with different choices of creation time in this example:

1. Start of mine (current behavior): b1: c0 < c1 == c2, b2: c0 < c1 == c2.
2. Start of wait: b1: c1 < c0 < c2, b2: c0 < c1 < c2.
3. Start of validate: b1: c1 < c0 < c2, b2: c0 < c1 < c2.

On obvious observation is that the current behavior (start of mine) is not a good basis for measuring wait times, because of the fixed synchronization between chains. (It may be a measure for latency but that not what we are interested in here.) Actually, we should measure differences between chains based on the how long mining and/or waiting takes relative to those (relatively) fixed synchronization points.

Another observation is that we can not hope to get a perfect result with this approach, because a chain being slower or faster than one adjacent chain depends not only on the chain itself but also on other adjacent chains. Since we can only observe the "speed" of a chain relative to synchronization points and chains synchronize with different chains at different times the measurement/difference between two chains is transitively affected by indirect neighbors.

That indicates that the lower bound of the number of adjustment steps needed in worst case to reach a global adjustment depends on the diameter of the graph. Luckily, this number is small for Chainweb and a dependency on this number would fit smoothly into the overall Chainweb consensus algorithm.

Which solution should we pick:

1. Start of mine, as already discussed isn't a good measure.
2. Start of wait, has the problem that it can be only picked if all miners agree to use it. If a miner picks a later time for a parent block, say start of validate, the start of wait would violate the validation constraints. Only values after start of mine are reliable, because at that time all adjacent parent exist and thus it's guaranteed that the time is strictly larger than the creation time of dependencies.
3. This solution is guaranteed to produce valid values independent on the the creation times of the parent headers. It has the disadvantage that miners have to inject updated values during the mining processes, in order of produce POW solutions for creation times that are close to the actual solve time. However with targeted expected block times in the order of 30 seconds it should be fine to update the time value in the work header, say, every second.

Is this solution sound? The question can be rephrased as: assuming that at least 50% of the miners try to maximize the difficulty, will difficulty adjustment succeed to keep the actual block rate close to the target block rate?

We'd have to show that the differences in epochBlockTime at the and of the epoch are proportional to the differences in the accumulative wait times. We'd also want to show that for each block epochBlockTime < creationTime(parent). Assuming all miners use the same strategy for setting the creation time, it is clear that for a chain that is always the slowest chain difficulty adjustment is the same as with the global adjustment algorithm (except for the constant factor which accounts for the fact that under normal circumstances no chain is expected to always be the slowest). This provides an upper bound on the new target.

Fully describing the properties of this algorithm, in particular in the presence of different strategies for choosing creation time values, is subject to ongoing research that is beyond the scope of this wiki page.

---

[1]

Chainweb uses a rather simple algorithm that just does an linear adjustment. There are more sophisticated approaches, like adjustments based on moving average or PID controllers. We found that the our approach works well enough and has the benefit of being simpler and more efficient.

[2]

Generally, one can think of other reason, beside the hash algorithm, why chains might be more or less efficient and should thus use different difficulties, but that does not apply to Chainweb in its current form.