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
- Abstract
- Prior Work
- Motivation
- Previous system
- Decentralized Random Beacons
- Deployment
- Reference Implementation
- References
- Copyright
This DIP proposes leveraging DVRFs (Decentralized Verifiable Random Functions) to create decentralized randomness inside the Dash ecosystem in a secure, verifiable manner.
- DIP-0004: Simplified Verification of Deterministic Masternode Lists
- DIP-0006: Long-Living Masternode Quorums
- DIP-0007: LLMQ Signing Requests / Sessions
- DIP-0008: ChainLocks
- DIP-0024: Long-Living Masternode Quorum Distribution and Rotation
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
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), 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.
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. 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.
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.
Creating decentralized randomness beacons is not a novel idea [1] [2]. Similarly, utilizing Decentralized Random Beacons (DRBs) to select particular members of interest in blockchain systems is an existing concept [3]. BLS-based randomness beacons have also been explored [4] [5] [6].
For our scheme to be considered secure, we will require standard pseudorandomness as defined in [7], 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 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]:
- 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 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]. 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:
- Have as many nodes in a ChainLock quorum as the threshold in two separate ChainLock quorums.
- Be able to propose a hash reliably.
- Check that a block’s ChainLock would be beneficial.
- Publish that block.
- Sign the block.
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:
bestCLblockdiff(h) < 0bestCLblockdiff(h)> bestCLblockdiff(h-1)+1(it refers to an older block than the last recorded ChainLock)- 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.
Several small examples below demonstrate conditions that trigger failure. The following parameters will be used in the examples:
- Let
hbe the height of the block. - Let
CL(h)be the ChainLock of the block at heighth. - Let
CB_CL(h)be the ChainLock included in the coinbase of the block at heighth. - Let
H_diff(h)be the height difference included in the coinbase of the block at heighth.
Relevant block information is specified in the format:
[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.
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)))
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:
"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 section.
- In both P2P and RPC messages, the new fields will be empty until after activation.
This DIP will be deployed by “version bits” BIP-9 with the name “v20” and using bit 9.
Randomness beacon for LLMQ selection is implemented in Dash Core v20.0. The initial implementation is available at dashpay/dash#5262, dashpay/dash#5366, and dashpay/dash#5377.
[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, <https://github.com/cloudflare/cloudflare-docs/blob/production/content/randomness-beacon/cryptographic-background/randomness-generation.md>.
[3] Buterin, V., 2016, Ethereum 2.0 Mauve Paper.
[4] Corestar, march 31th 2020, Corestar Arcade, last accessed january 2023, <https://github.com/corestario/tendermint>.
[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 (c) 2023 Dash Core Group, Inc. Licensed under the MIT License