# r<sup>2</sup>PoS - A Relay-friendly Proof of Stake **r<sup>2</sup>PoS** is a **R**elay-friendly, unbiasedly **R**andomized **P**roof **o**f **S**take consensus, developed for the next upgrade of Nexty platform. * Sealers can be registered by staking [NTF](https://explorer.nexty.io/address/0x2c783ad80ff980ec75468477e3dd9f86123ecbda) token and interact with the governance contract. * The sealing 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<sup>2</sup>PoS** protocol is designed for securing header-chain verification without the chain state. There is no epoch nor checkpoint, the sealing queue is constantly changed over each block, so the consensus depends on no single point of vulnerability nor performance bottleneck. ### Sealer Application Confirmations To participate in the sealing queue, one must have enough amount [NTF](https://explorer.nexty.io/address/0x2c783ad80ff980ec75468477e3dd9f86123ecbda) 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 sealer application need $\tau=128$ confirmations to active. The stake requirement is verified by sealers, 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. ![](https://raw.githubusercontent.com/nextyio/nextydocument/docs-restructured/source/img/sealer-application-confirmation.svg?sanitize=true) ### Inactivity Leakage To keep the sealing queue healthy with the ever-changing sealers set, if a sealer hasn't seal any block in $\lambda=1024$ blocks, it will be *leaked* out of the active queue. To join the queue again, NTF holder must re-apply the sealer in the governance contract. ### Sealing Queue Given a header chain is verified up to block $n-1$, the set of authorized sealers 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 sealer of block $i$; $a^+_j$ and $a^-_j$ are the sealer *joining* and *leaving* application set of block $j$. That is: * All sealer of the last 1024 blocks $[n-1024, n-1]$. * And any sealer join application in $[n-1024-128, n-1-128]$ * Exclude any sealer 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<sup>2</sup>PoS** is finalized after $\dfrac{|S|}2+1$ confirmations, the chain can progress with just more than $\dfrac{|S|}2$ active sealers. To increase the rate of unique confirmation for [anchor chain protocol](#Anchor-chain), the last $\dfrac{2}3|S|$ block sealers are the recent signers and cannot seal the next block; hence the chain can only progress with more than $\dfrac{2}3|S|$ active sealers. ### Randomness The order and priority of the active sealing 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)) ![](https://raw.githubusercontent.com/nextyio/nextydocument/docs-restructured/source/img/VDF.svg?sanitize=true) 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 properties of VDF, it requires only a single honest participant to secure the whole network, i.e. the randomization works even with only one sealer 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 sealers 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<sup>2</sup>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 sealer 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 sealer queue, e.g. sealer 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. ![](https://raw.githubusercontent.com/nextyio/nextydocument/docs-restructured/source/img/Cross-chain%20Relay.svg?sanitize=true) 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 sealers. 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 sealer set of $G$. To verify the finality of a block using the continuity anchor, only a set $H$ of active sealer 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 sealers (a.k.a. majority continuity), and relaying a block requires $\dfrac{5}6$ confirmations from the anchored sealer set. ### Majority continuity Let $S_i$ and $S_j$ is the sealer 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$ sealer set. Whenever the majority continuity is broken, a new anchor must be created, and the following blocks must anchor to this new anchor. ![](https://raw.githubusercontent.com/nextyio/nextydocument/docs-restructured/source/img/Anchor-Cross-chain%20Relay.svg?sanitize=true) In the diagram above, block 8 and 11 shares the majority common sealers 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|$ sealer 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 sealers. ## 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 sealers 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 sealer is not verified, used for chaining confirmations) * authorized (the sealer 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 sealer 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 sealer 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 sealers 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 sealer 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 sealer 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) * SealerApplication (optional/repeated) * Join = `0xF0` * Address (20 bytes) * SealerApplication (optional/repeated) * Leave = `0xF1` * Address (20 bytes) * SealerApplication (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(SealerAddress\cdot SealerAddress\cdots)$ The queue sealers is sorted alphabetically. ### API ``` relayHeader(headerData...) verifyQueue(headerHash, sealers[]) verifyHeader(headerHash) constructQueue(headerHash) finalize(headerHash, lastConfirmation) ```