Coincident Blocks

A coincident block is a block that is valid in multiple Quai blockchains. Coincident blocks are a naturally occurring, beneficial byproduct of merged mining that Quai Network utilizes to derive subordinate chain security from dominant chains, and to transition state between chains.
When mining Quai, each miner checks every nonce against three difficulty thresholds. Due to the nature of difficulty thresholds, a possibility will always exist that a single nonce will fulfill multiple of these difficulty thresholds. When this occurs, the nonce is considered valid in multiple contexts, creating a hashlinked reference between a dominant and a subordinate chain. This hash linked reference allows for cross-chain transactions and contract interactions between chains.

Why Do Coincident Blocks Occur?

To successfully mine a block, a miner must meet or exceed the difficulty threshold of a blockchain. Miners often find nonces that exceed the difficulty threshold by one or more zeros. A coincident block is a block with a nonce that randomly has enough zeros to also meet a secondary threshold value.
# of extra leading 0s (binary)
Coincident blocks allow a non-interactive proof of proof-of-work (NIPoPoW) to be created by including a hash referencing the previous coincident block. The totality of work represented by two consecutively linked coincident blocks is statistically equivalent to or greater than the amount of work done in all intermittent subordinate blocks. Therefore, all that is required to demonstrate the total sum of work done on top of the previous coincident block is the newest coincident block, creating a concise proof.
For these NIPoPoWs to be useful for the network, there must be increasing work thresholds moving up the hierarchy. The greater the increase in work thresholds, the more powerful NIPoPoWs become. Quai achieves this by targeting different block times at different levels of the hierarchy. Each level in the hierarchy is an order of magnitude slower than its subordinate chains, allowing for a 10x delta in work threshold between a single subordinate chain and a dominant chain. However, since Quai Network maps three subordinate chains to each dominant chain, this delta in work threshold is increased to 30 times. This significant statistical separation of work thresholds ensure that it is extremely unlikely for a dominant coincident NIPoPoW to ever have less work than the subordinate chain.
These NIPoPoWs also allow for the creation of a "skip list." A skip list is a data structure that allows for efficient compressed representation by skipping over certain elements. In the context of Quai, it is possible to create a list of blocks that skips over subordinate blocks while still maintaining the total work of subordinate blockchains. These skip lists only require each chain to have knowledge of its own context to provide a proof of subordinate work. Thus minimizing network and computation latency and increasing throughput.
Further, each Quai block contains a cumulative rollup (referred to as an external rollup root) of all external transactions (ETXs) that have occurred since the last coincident block. This rollup can be forward propagated to coordinate contexts, with delayed referencing dependent on consensus. These forward propagated rollups allow for highly compressed hash linked references and precomputed transition sets, trading slight increases in I/O latencies at origin chains for significant reductions in computation latencies at destination chains.
Critically, the production of coincident blocks (and thus the hash linked references between chains) relies only upon the objective, thoroughly tested mechanism of Proof-of-Work consensus. This differentiates Quai from other multichain solutions, which introduce new, subjective, non-atomic mechanisms to facilitate cross-chain transfers.

Rules of Coincident Blocks

  1. 1.
    All dominant blocks must be coincident with all directly subordinate blocks.
  2. 2.
    Subordinate blocks can be mined asynchronously without being included in a coincident block.
  3. 3.
    For a coincident block to be valid, it must be valid in all pertinent contexts.
  4. 4.
    Coincident blocks must be synchronously appended to ensure Rule #3.
  5. 5.
    Coincident blocks have the same hash in all contexts in which they are valid, which provides cross-chain hash linked references.
Due to the nature of blockchain mining difficulty, all Prime and Region blocks are considered coincident blocks. Consequently, to produce a Prime block the nonce must exceed the difficulty threshold of Prime, Region, and Zone, and to produce a Region block the nonce must exceed the difficulty threshold of Region and Zone. Prime is coincident with Region and Zone while Region is coincident with just Zone. Prime blocks act as a "knot" pegging all Region and Zone blocks to the Prime blockchain. Zone blocks are the only blocks in Quai Network which are not coincident.
While all Quai blockchains advance independently and asynchronously, they are stochastically synced together by the production of coincident blocks. At the point of coincident block production, all chains linked together by a coincident block are both simultaneously committing to the validity of that block, and appending that block to their context. If a coincident block would be valid in Region and Zone but not Prime, it would not be appended to any chain. Similarly, if a coincident block would be considered valid in Prime and Region but not Zone, it would not be appended to any chain.
All coincident blocks must be appended simultaneously in all contexts, causing coincident blocks to slow subordinate chains to the performance of the most dominant chain for that block. In an extreme example, if Prime, Region, and Zone chains had the same target block times, Zone blockchains would see no improvement in performance as each Zone block would be delayed to the performance of Prime. Quai Network increases target block times by an order of magnitude in each of the dominant levels in order to create better performing subordinate chain subnets.
The smallest segment of the network that a node or miner can run is a "slice," which consists of the Prime chain, a Region chain, and a Zone chain subordinate to the selected Region chain. A slice is the smallest set a node can run trustlessly, as all data in a slice is trusting data from another part of the slice to validate and append blocks.