# r²PoS - A Relay-friendly Proof of Stake

**r²PoS** is a **R**elay-friendly, unbiasedly **R**andomized **P**roof **o**f **S**take consensus, developed for side-chain with 2-way relay with another smart-contract platform.

* Validators can be registered by staking consensus token and interact with the governance contract.
* The validator queue is constantly shuffled by an [unbiasable VDF setup](#Randomness).
* Secure stateless fast-sync, light-client, and can be relayed efficiently to any other smart-contract platform.

## Cross-chain Data Relay

Relay data from one blockchain to another is expensive, mostly because the protocol of each involving blockchain does not actively support it. Relaying chain data and lightclient both require a protocol for the client to easily verify any data contained in the blockchain with only a small part of the chain data. A relay contract is also a light-client with even more limited resource.

BTCRelay contract is abandoned due to low activity. Relaying a single transaction requires all previous block headers from the last relayed one. PeaceRelay is not practical because it's costing too much gas to verify an Ethash in the Ethereum contract platform itself.

Major blockchains have no support for trustless SPV/Lightclient protocol with optimal data and computation. That is, proving a transaction finality in an arbitrary block $n$ require relaying much less data than $n$ block headers.

Related works:
* [Non-Interactive Proofs of Proof-of-Work](https://eprint.iacr.org/2017/963.pdf)
* [Light Clients and Proof of Stake](https://blog.ethereum.org/2015/01/10/light-clients-proof-stake/)

## Header-chain Protocol

Proof of Stake relies on the running state of the chain, which is not available in fast and light synchronization. The **r²PoS** protocol is designed for securing header-chain verification without the chain state. There is no epoch nor checkpoint, the validator queue is constantly changed over each block, so the consensus depends on no single point of vulnerability nor performance bottleneck.

### Validator Application Confirmations

To participate in the validator queue, one must have enough amount governance token, which stays in the chain state. The required stake is verified by the governance contract, which also only available to full-state nodes. For secure stateless header-chain verification, each validator application need $\tau=128$ confirmations to active. The stake requirement is verified by validators, which are full-state nodes. After more than half of the queue confirm the application, it's fully verified. Then the state-less clients can trust that application, having access to no chain state at all.


### Inactivity Leakage

To keep the validator queue healthy with the ever-changing validators set, if a validator hasn't publish any block in $\lambda=1024$ blocks, it will be *leaked* out of the active queue. To join the queue again, token holder must re-apply the validator in the governance contract.

### Validator Queue

Given a header chain is verified up to block $n-1$, the set of authorized validators for the block $n$ can be determined by:

$S=\{s_i\big|n-\lambda\le i<n\} \cup \{a^+_j\big|n-\lambda-\tau\le j<n-\tau\} \setminus \{a^-_j\big|n-\lambda-\tau\le j<n-\tau\}$

Where $s_i$ is the validator of block $i$; $a^+_j$ and $a^-_j$ are the validator *joining* and *leaving* application set of block $j$.

That is:
* All validator of the last 1024 blocks $[n-1024, n-1]$.
* And any validator join application in $[n-1024-128, n-1-128]$
* Exclude any validator leave application in $[n-1024-128, n-1-128]$

**Sealing Queue** can be deterministically reconstructed at any point in the header-chain, where the last $n+\lambda+\tau$ headers are verified. Reconstruction does not require any checkpoint, nor scanning more than $\lambda+\tau$ blocks.

### Finality and Recentness

A block in **r²PoS** is finalized after $\dfrac{|S|}2+1$ confirmations, the chain can progress with just more than $\dfrac{|S|}2$ active validators.

To increase the rate of unique confirmation for [anchor chain protocol](#Anchor-chain), the last $\dfrac{2}3|S|$ block validators are the recent signers and cannot publish the next block; hence the chain can only progress with more than $\dfrac{2}3|S|$ active validators.

### Randomness

The order and priority of the active validator queue is shufled using the VDF calculation output as random **seed**. Input of the next VDF is the hash of the block containing the last VDF output. (See [Unbiasable Randomness](https://hackmd.io/@Zergity/UnbiasableRNG))


The VDF output can be included in any block to be available to the network as soon as possible. The block with the valid VDF output is prioritized by the protocol, allow it to override any other non-VDF block.

There's no explicit incentive to calculate and publish the VDF output. But as one of the most valuable attributes of VDF, it requires only a single honest participant to secure the whole network, i.e. the randomization works even with only one validator running the VDF calculation.

This setup prevents any kind of stake grinding or biasing. The only weakness is that it's not realtime. As for every random seed, there's a small time window that a specific sequence of validators is known to authorize the upcoming blocks. What is not known is the order of the next sequence after a new random seed available.

## Light-client/Relay Protocol

**r²PoS** is designed for trustless and efficient light client verification, allow relaying data from arbitrary block $n$ with $O(m)$ data complexity, where $m$ is the number of validator applications up to block $n$.

### Cross-link chain

Cross-link is a block that contains consensus metadata necessary to verify the blocks followed. Every block is cryptographically linked to a cross-link, and each cross-link is linked to the last cross-link. A cross-link block is created when there's an active change in the validator queue, e.g. validator join or leave.

This chain of cross-link blocks allows the light-client to skip all the blocks that has no affect to the consensus.


In the example diagram above, the cross-link chain only contains block number 6, 8 and 11. All other blocks in between have no effect on the consensus and can be ignored by light-clients.

### Anchor chain

Anchor is the cryptographic link between cross-link blocks that share the super-majority common validators. Anchor chain allows any block $n$ can be relayed, or verified by light client with much less data than $n$ headers.

With conflicted messages are assumed to be provable slashing condition, PoS requires $|C| > \dfrac{|S|}2$ of unique confirmations for block finality. Blocks anchoring to the same anchor share the common validator set of $G$. To verify the finality of a block using the continuity anchor, only a set $H$ of active validator can be missing or left out. So we have:

$|G|-|H|>|C|>\dfrac{|S|}2$
$|H|<|G|-\dfrac{|S|}2$

So the set of header confirmations $R = S \setminus H$ must be relayed with:

$|R| = |S\setminus H| > \dfrac{3}2|S|-|G|$

Picking $|R|$ and $|G|$ is a matter of trading off between the consensus and relay protocol liveness. If we pick $|G| = \dfrac{2}3|S|+1$ (super majority), then we have:

$|R| \ge \dfrac{5}6|S|$

That means, the blocks with the same anchor must share more than $\dfrac{2}3$ common validators (a.k.a. majority continuity), and relaying a block requires $\dfrac{5}6$ confirmations from the anchored validator set.

### Majority continuity

Let $S_i$ and $S_j$ is the validator set of block $i$ and $j$. The majority continuity between the two blocks is preserved when $|S_i \cap S_j| > \dfrac{2}3 \max\{|S_i|,|S_j|\}$. This allows the validity and finality of block $j$ can be verified with any $\dfrac{5}6$ confirmations from the $S_i$ validator set.

Whenever the majority continuity is broken, a new anchor must be created, and the following blocks must anchor to this new anchor.


In the diagram above, block 8 and 11 shares the majority common validators with block 6, so they are anchored to block 6. Block 13 breaks the continuity, even if it's not a cross-link block, it will be turned into one and linked to the new anchor - block 11.

### Chain size

The anchor chain grows at most 1 block for each $\dfrac{1}3|S|$ validator application (i.e. join or leave). There's no probability in (this version of) PoS, so logarithmic growing rate like PoPOW is not possible. Realistically, from the past data of PoS chains, the anchor chain size is often less than 1 over a millions of block headers. This is extremely optimal for PoS chain with quick block time and less frequent change of validators.

## Future Development

### Signature chain

The header chain can be optimized for lightclient and relay, using multiple layers hashing. The first hashing layer must reveal only data for the consensus, just enough to verify the header chain and nothing else. All other block content will be hashed in the second layer.

BlockHash = Hash(ParentHash + ContentHash + Signagure)

That reduces the data size for each header from 573 bytes + 5 scalars to 129 bytes + 5 scalars. Without 5 scalars, that is about 77% data size saved for each block header.

The *ContentHash* is only verified when the block content is needed.

### Off-chain Signature Service

Another approach to optimize the data size and calculation for header confirmations is to provide a layer 2 relay signature service. This service only works for relaying the latest part of the chain, which luckily, is most of the relay cases.

Active validators can serve this service by signing the past block on request and providing the signature to the relayer. After collecting $\dfrac{2}3|S|$ signatures, relayer can submit them to the relay contract to prove finality of a block header, without bother with the header destructuring and chaining confirmations.

Ignoring 5 scalars, this methods save up to 88.6% of the data size for each block confirmations.

### Threshold Signature

Theashold signature can be utilized for block finality, when such signature scheme is supported in major foreign chains.

## Implementation
(In Progress)

### Confirmation

A $Conf$ object is identified by its hash and can be either:
* A block header
* Signed consensus fields (forward support for off-chain signature service) (TODO)

A $Conf$ has one of the following states:
* not available (not yet relayed)
* available (relayed, but the validator is not verified, used for chaining confirmations)
* authorized (the validator is authorized, by either cross-linked or anchored block)
* finalized (has enough authorized $Conf$s stacked after)

The (new) genesis block is hardcoded into the contract as the first *finalized* $Conf$.

### Queue

A $Queue$ is the ordered list of validator addresses, recorded in the header extra. The $Queue$ of a $Conf$ is relayed and verified only if the $Conf$ is finalized.

As the consensus, only cross-linked and anchored block has the queue digest to be verified. A $Conf$ can only be linked or anchored, if it's finalized.

### Verification

A $Conf$ can be verified with its anchor or linked block, when its validator is in the respective $Queue$.

Note that, a verified $Conf$ alone is not a reliable data source, but a sequence of consecutive $Conf$s with enough threshold of unique authorized validators is collectively used for finalize relayed data.

### Finalization

A $Conf$ can be finalized with its anchor or linked block.

Anchor finalization requires:
* its anchored $Queue$ is verified
* there are at least $\dfrac{5}6|Queue|$ authorized $Conf$s in the following consecutive $Conf$s (including the verifing $Conf$)

Link finalization requires:
* its linked $Queue$ is verified
* there are at least $\dfrac{|Queue|}2$ authorized $Conf$s in the following consecutive $Conf$s (including the verifing $Conf$)

In case of the anchor and cross-link majority continuity is broken, there's a fail-back method to finalize a $Conf$ by consequently apply each validator applications by relaying governance contraction interaction txs and their signatures. (TODO)

With forward support for off-chain signature service, a $Conf$ can be finalized only with bare signatures provided by the validator in the $Queue$. (TODO)

### Block Header Structure

#### Cross Link

Cross link hash is recorded in every header's $MixDigest$ (exclusive field for Ethash), which is the hash of the block that this header is linked to.

#### Anchor Link

Anchor is recorded in the header's Extra, and only for the cross-link header.

#### Header Extra
* Vanity (32 bytes)
* Extended (optional)
* AnchorData (optional)
* SignatureByte = `0xFF`
* DestinationHash (32 bytes)
* $QueueDigest$ (32 bytes)
* ValidatorApplication (optional/repeated)
* Join = `0xF0`
* Address (20 bytes)
* ValidatorApplication (optional/repeated)
* Leave = `0xF1`
* Address (20 bytes)
* ValidatorApplication (optional/repeated)
...
* RandomData (optional)
* SignatureByte = `0x01`
* VDFOutput (32 bytes)
* PriceData (optional)
* SignatureByte = `0x02`
* RLP(BigInt, BigInt)
* Signature/Seal (65 bytes)

#### Queue Digest

$\langle{QueueDigest}\rangle = Keccak256(ValidatorAddress\cdot SealerAddress\cdots)$

The queue validators is sorted alphabetically.

### API

relayHeader(headerData...)
verifyQueue(headerHash, validators[])
verifyHeader(headerHash)
constructQueue(headerHash)
finalize(headerHash, lastConfirmation)