# 29 - Randomness Beacon For LLMQ Selection 
  DIP: 0029
  Title: Randomness Beacon For LLMQ Selection
  Author(s): Virgile Bartolo
  Special-Thanks: Odysseas Gabrielides
  Comments-Summary: No comments yet.
  Status: Proposed
  Type: Standard
  Created: 2023-08-09
  License: MIT License
## Table of Contents 1. [Abstract](#abstract) 1. [Prior Work](#prior-work) 1. [Motivation](#motivation) 1. [Previous system](#previous-system) 1. [Decentralized Random Beacons](#decentralized-random-beacons) * [Introduction](#introduction) * [Randomness creation](#randomness-creation) * [Change to the coinbase transaction](#change-to-the-coinbase-transaction) * [Change to the quorum initialization phase](#change-to-the-quorum-initialization-phase) * [Light clients](#light-clients) 1. [Deployment](#deployment) 1. [Reference Implementation](#reference-implementation) 1. [References](#references) 1. [Copyright](#copyright) ## Abstract This DIP proposes leveraging DVRFs (Decentralized [Verifiable Random Functions](https://en.wikipedia.org/wiki/Verifiable_random_function)) to create decentralized randomness inside the Dash ecosystem in a secure, verifiable manner. ## Prior work * [DIP-0004: Simplified Verification of Deterministic Masternode Lists](https://github.com/dashpay/dips/blob/master/dip-0004.md) * [DIP-0006: Long-Living Masternode Quorums](https://github.com/dashpay/dips/blob/master/dip-0006.md#building-the-set-of-deterministic-connections) * [DIP-0007: LLMQ Signing Requests / Sessions](https://github.com/dashpay/dips/blob/master/dip-0007.md) * [DIP-0008: ChainLocks](https://github.com/dashpay/dips/blob/master/dip-0008.md) * [DIP-0024: Long-Living Masternode Quorum Distribution and Rotation](https://github.com/dashpay/dips/blob/master/dip-0024.md) ## Terminology **Decentralized Verifiable Random Functions (DVRF):** A decentralized function which provides proof that its calculations are correct **Decentralized Random Beacon (DRB):** A decentralized source of a stream of randomness ## Motivation When selecting members for LLMQs, a pseudorandom ordering of the masternode list is necessary. Currently, this is achieved using a hash derived from mining, leading to several downsides: * LLMQs are dependent on steady Proof of Work to provide persistent services * An attacker with high hash power can gain an unfair advantage in quorum member selection * The hash rate must be high for mining-based entropy to be secure To overcome these challenges, this DIP introduces a decentralized source of pseudorandomness to procure the entropy required to pseudorandomly order the masternode list. By transferring finality of the randomness creation from Proof of Work to this randomness beacon, an attacker with high hash power can no longer gain an unfair advantage in quorum member selection. Although very costly (see the [DIP-24 addendum](./dip-0024/dip-0024-addendum-parameter-choices.md)), this attack did have a non-negligible influence in the context of rotation as defined in DIP-24. If not resolved, this could have made double sign attacks possible on InstantSend LLMQs; however, this DIP eliminates that possibility. The provided design also softens cross-dependencies within the system, increasing modularity and resilience. The creation of bias presented in the DIP-24 addendum is now impossible: the percentage of byzantine nodes in the whole system is the sole parameter an attacker could manipulate to attain targeted thresholds of presence in quorums. Finally, securing this system does not require a high hash rate but merely a functioning masternode system. ## Previous system Quorum members used to be chosen by ordering a list of masternodes by calculating SHA256(SHA256(proTxHash, confirmedHash), SHA256(SHA256(llmqType, **_quorumHash_**))). The `quorumHash` is the hash of the first block in the [distributed key generation (DKG) process](./dip-0006.md#llmq-dkg-network-protocol). It was used to provide entropy (i.e., disorganization). Since miners had partial control over the `quorumHash`, they could have a semblance of control on quorum creations. ## Decentralized Random Beacons ### Introduction This DIP proposes using the signature of a quorum as a randomness beacon instead of the quorumHash. Using a quorum signature eliminates the possibility of miners or masternodes skewing the selection process: * Miners will no longer be directly relied on to create the entropy necessary for perennial LLMQs. Instead, the hashes they find will be signed. Thus, they will have no control over the resulting entropy itself as it will be unpredictably modified. The hashes will also act as a fallback in case of long-term ChainLock failure. * Masternodes (quorum members) will not be able to control the randomness unless a number of nodes greater than the quorum threshold colludes. ### Randomness creation Creating decentralized randomness beacons is not a novel idea [[1]](https://eprint.iacr.org/2016/1067.pdf) [[2]](https://github.com/cloudflare/cloudflare-docs/blob/production/content/randomness-beacon/cryptographic-background/randomness-generation.md). Similarly, utilizing Decentralized Random Beacons (DRBs) to select particular members of interest in blockchain systems is an existing concept [[3]](https://cdn.hackaday.io/files/10879465447136/Mauve%20Paper%20Vitalik.pdf). BLS-based randomness beacons have also been explored [[4]](https://github.com/corestario/tendermint) [[5]](https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8418625) [[6]](https://dfinity.org/pdf-viewer/library/dfinity-consensus.pdf). For our scheme to be considered secure, we will require standard pseudorandomness as defined in [[7]](https://eprint.iacr.org/2020/096.pdf), bias resistance, unpredictability, and verifiability. Although stronger properties have been outlined in recent years, implementing them would significantly increase complexity while bringing no additional value to the system. The changes necessary to meet these requirements are minimal as we will utilize ChainLocks as sources of randomness. A ChainLock is a signature of a block hash by two LLMQs as specified in DIP-7 and DIP-8. The quorums already do this work; thus, this scheme adds almost no burden on the network besides storing ChainLocks on the blockchain long-term, which amounts to around a hundred bytes per block. Once a [qfcommit](./dip-0006.md#6-finalization-phase) has been mined, the corresponding quorum’s private and public quorum keys are effectively immutable. Thus, all subsequent signatures of incoming data will act as a pseudorandom beacon which is bias resistant, unpredictable, verifiable, and standard pseudorandom in the sense of [[7]](https://eprint.iacr.org/2020/096.pdf): * **Bias resistant:** The keys used to sign are set before the signature challenge, leaving only one signature possible per challenge. * **Unpredictable:** Signatures are known to be unpredictable without knowledge of the private key. No one can have this knowledge without control of at least as many nodes in a quorum as the threshold. This makes the scheme unpredictable as long as the number of colluding masternodes does not exceed the quorum threshold. * **Verifiable:** The created randomness is trivially verifiable with the public keys of the quorums. * **Standard pseudorandom:** Standard pseudorandomness comes from the [computational Diffie-Hellman assumption](https://en.wikipedia.org/wiki/Computational_Diffie%E2%80%93Hellman_assumption) in the random oracle model. **Note:** A similar formal argument can be made for the standard pseudorandomness of this scheme as the proof of pseudorandomness for DFNITY’s DRB, which can be found here [[7]](https://eprint.iacr.org/2020/096.pdf). While the schemes differ, both rely on a DKG process and then a later occurrence of a BLS signature on a message. In their case, the evaluations on the challenge plaintext cannot be done during the DKG due to consensus rules and, in our case, due to the unpredictability of the challenge during the DKG as quorums always sign blocks created after the DKG. To be able to bias this value toward a desired value, an attacker would need to be able to: 1. Have as many nodes in a ChainLock quorum as the threshold in two separate ChainLock quorums. 2. Be able to propose a hash reliably. 3. Check that a block’s ChainLock would be beneficial. 4. Publish that block. 5. Sign the block. ### Change to the coinbase transaction Since quorum member calculation will now depend on ChainLocks, performing verification of historical ChainLocks during blockchain synchronization will be necessary. Thus, ChainLock information must be included in the coinbase. More precisely, the newest ChainLock signature known by a miner will now be included in the coinbase alongside a `varint` called `bestCLblockdiff` indicating the number of blocks between the current block and the last known block with a ChainLock. The most recent known ChainLock can be equal to the newest ChainLock stored in the chain if it is also the newest known ChainLock. A block missing this information is invalid and must be rejected. Let us call `bestCLblockdiff(h)` the difference written in the block at height `h`. When verifying block validity, the block is rejected if either of the following conditions is true: 1. `bestCLblockdiff(h) < 0` 2. `bestCLblockdiff(h)> bestCLblockdiff(h-1)+1` (it refers to an older block than the last recorded ChainLock) 3. The signature doesn’t verify against the block hash of the block at the indicated height. **Note:** if the node is up to date with the chain and `bestCLblockdiff(h) = bestCLblockdiff(h-1)+1`, then step 3 can be simplified to check equality with the ChainLock signature of the previous block. This is because they can only point to the same block signature and the first one was already verified against the block. #### Examples Several small examples below demonstrate conditions that trigger failure. The following parameters will be used in the examples: * Let `h` be the height of the block. * Let `CL(h)` be the ChainLock of the block at height `h`. * Let `CB_CL(h)` be the ChainLock included in the coinbase of the block at height `h`. * Let `H_diff(h)` be the height difference included in the coinbase of the block at height `h`. Relevant block information is specified in the format: ```cpp [h, CB_CL(h), H_diff(h)] = [h, CL(h -H_diff(h) -1), H_diff(h)]. ``` `[h, CB_CL(h), H_diff(h)]`, `[h+1, CB_CL(h+1), H_diff(h+1)]` is a valid succession as long as `H_diff(h+1)` refers to a block that is newer than the one referred to by `H_diff(h).` In other terms, if: `H_diff(h+1) ≤ H_diff(h)+1`, `CB_CL(h)=CL(h-H_diff(h)-1)`, and `CB_CL(h+1)=CL(h+1-H_diff(h+1)-1)`. `[15, CL(10), 4], [16, CL(10), 5]` is a valid succession of blocks. They both point to the block at height `15 -4 -1 = 16 -5 -1 = 10`. `[15, CL(10), 4], [16, CL(10), 4]` is an invalid succession of blocks. The second `CB_CL` does not point to a proper block; therefore, the ChainLock doesn’t verify. `[15, CL(10), 4], [16, CL(13), 2]` is a valid succession of blocks. It provides newer randomness ( `CL(13)`) that verifies against the block hash. `[15, CL(10), 4], [16, CL(9),6]` is an invalid succession of blocks. It refers to an older block (9) than what the on-chain information already contains (10), indicating incorrect behavior. ### Change to the quorum initialization phase Introducing this update requires a small modification to the DKG initialization phase to order the masternode list based on new parameters. The modification is described below in terms of the following variables: | Variable | Description | | - | - | | `quorumHeight` | Height of the first block of the DKG | `cycleHeight` | Height of the first block of the first DKG of the cycle in the context of DIP-24 | `quorumBaseBlockHash` | Hash of the block at height `quorumHeight` | `cycleBaseBlockHash` | Hash of the block at height `cycleHeight` | `quorumBaseBlockMinus8Hash` | Hash of the block at height `quorumHeight-8` | `cycleBaseBlockMinus8Hash` | Hash of the block at height `cycleHeight-8` | `quorumChainSig` | ChainLock contained in the block at height `quorumHeight-8` | `cycleChainSig` | ChainLock contained in the block at height `cycleHeight-8` In the initialization phase of every DKG, the masternode list is now respectively ordered by: * **Standard quorums:** SHA256(SHA256(proTxHash, confirmedHash), SHA256(SHA256(llmqType, **_quorumHeight-8_**, **_quorumChainSig_**))) * **Rotation quorums:** SHA256(SHA256(proTxHash, confirmedHash), SHA256(SHA256(llmqType, **_cycleHeight-8_**, **_cycleChainSig_**))) Instead of: * **Standard quorums:** SHA256(SHA256(proTxHash, confirmedHash), SHA256(SHA256(llmqType, **_quorumBaseBlockHash_**))) * **Rotation quorums:** SHA256(SHA256(proTxHash, confirmedHash),SHA256(SHA256(llmqType, **_cycleBaseBlockHash_**))) A hard fork will be introduced to change to the new mechanism. Upon its activation, if no proper ChainLock signature can be selected for masternode list ordering, the following algorithm will be used instead: * **Standard quorums:** SHA256(SHA256(proTxHash, confirmedHash), SHA256(SHA256(llmqType, **_quorumBaseBlockMinus8Hash_**))) * **Rotation quorums:** SHA256(SHA256(proTxHash, confirmedHash),SHA256(SHA256(llmqType, **_cycleBaseBlockMinus8Hash_**))) ### Light clients SPV clients adhere to DIP-4 specifications and verify quorum membership composition by requesting MNLISTDIFFs using the GETMNLISTDIFF P2P message. With the change introduced by this DIP, light clients will require the ChainLocks used to shuffle the entries in the `newQuorums` field. Consequently, the MNLISTDIFF will be enriched with the following fields, which will be inserted immediately after the existing `newQuorums` field: | Field | Type | Size | Description | - | - | - | - | | quorumsCLSigsCount | compactSize uint | 1-9 | Number of `quorumsCLSigs` elements | quorumsCLSigs | quorumsCLSigsObject[] | variable | ChainLock signature used to calculate members per quorum indexes (in `newQuorums`) The content of `quorumsCLSigsObject`: | Field | Type | Size | Description | - | - | - | - | | signature | BLSSig | 96 | ChainLock signature | indexSetCount | compactSize uint | 1-9 | Number of quorum indexes using the same `signature` for their member calculation | indexSet | uint16_t[] | variable | Quorum indexes indicating which `newQuorums` entries use this `signature` for their member calculation The same information is returned in the **protx diff** RPC. Example of the new field: ```json "quorumsCLSigs": [ { "b5998c1b7797c49b...0161189171b57935": [ 6 ] }, { "8f7a352321dca373...9366a2c40bbf6c56": [ 1, 3, 4, 5 ] }, { "983c9479cb6a6afa...6ab8e49bb6415c79": [ 0, 2 ] }, { "0000000000000000...0000000000000000": [ 7, 8, 9 ] } ] ``` In this example, quorums in `newQuorums` at indexes 1, 3, 4, and 5 will use the same ChainLock signature for shuffling. Quorums in `newQuorums` at indexes 7, 8, and 9 on the hand will use the standard way to shuffle based on block hash. **Note:** * Upon activation of this change, the standard shuffle algorithm will use a shifted blockHash as described in the [Change to the quorum initialization phase](#change-to-the-quorum-initialization-phase) section. * In both P2P and RPC messages, the new fields will be empty until after activation. ## Deployment This DIP will be deployed by “version bits” [BIP-9](https://github.com/bitcoin/bips/blob/master/bip-0009.mediawiki) with the name “v20” and using bit 9. ## Reference implementation Randomness beacon for LLMQ selection is implemented in Dash Core v20.0. The initial implementation is available at [dashpay/dash#5262](https://github.com/dashpay/dash/pull/5262), [dashpay/dash#5366](https://github.com/dashpay/dash/pull/5366), and [dashpay/dash#5377](https://github.com/dashpay/dash/pull/5377). ## References [1] E. Syta _et al_., "Scalable Bias-Resistant Distributed Randomness," _2017 IEEE Symposium on Security and Privacy (SP)_, San Jose, CA, USA, 2017, pp. 444-460, doi: 10.1109/SP.2017.45. [2] Cloudflare, 1st august 2022, _Cloudflare Randomness Generation_, last accessed january 2023, <>. [3] Buterin, V., 2016, Ethereum 2.0 Mauve Paper. [4] Corestar, march 31th 2020, _Corestar Arcade_, last accessed january 2023, <>. [5] E. Kokoris-Kogias, P. Jovanovic, L. Gasser, N. Gailly, E. Syta and B. Ford, "OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding," _2018 IEEE Symposium on Security and Privacy (SP)_, San Francisco, CA, USA, 2018, pp. 583-598, doi: 10.1109/SP.2018.000-5. [6] Hanke, T., Movahedi, M., & Williams, D. (2018). Dfinity technology overview series, consensus system. _arXiv preprint arXiv:1805.04548_. [7] D. Galindo, J. Liu, M. Ordean and J. -M. Wong, "Fully Distributed Verifiable Random Functions and their Application to Decentralised Random Beacons," _2021 IEEE European Symposium on Security and Privacy (EuroS&P)_, Vienna, Austria, 2021, pp. 88-102, doi: 10.1109/EuroSP51992.2021.00017. ## Copyright Copyright (c) 2023 Dash Core Group, Inc. [Licensed under the MIT License](https://opensource.org/licenses/MIT)