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

  2. Prior Work

  3. Motivation

  4. Previous system

  5. Decentralized Random Beacons

  6. Deployment

  7. Reference Implementation

  8. References

  9. Copyright

Abstract#

This DIP proposes leveraging DVRFs (Decentralized Verifiable Random Functions) to create decentralized randomness inside the Dash ecosystem in a secure, verifiable manner.

Prior work#

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), 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. 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] [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:

  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:

[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:

"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.

Deployment#

This DIP will be deployed by “version bits” BIP-9 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, dashpay/dash#5366, and dashpay/dash#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, <cloudflare/cloudflare-docs>.

[3] Buterin, V., 2016, Ethereum 2.0 Mauve Paper.

[4] Corestar, march 31th 2020, Corestar Arcade, last accessed january 2023, <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.