# 4 - Simplified Verification of Deterministic Masternode Lists

<pre>
  DIP: 0004
  Title: Simplified Verification of Deterministic Masternode Lists
  Author: Alexander Block, Samuel Westrich, UdjinM6, Andy Freer
  Comments-Summary: No comments yet.
  Status: Final
  Type: Standard
  Created: 2018-04-30
  License: MIT License
</pre>

## Table of Contents

1. [Abstract](#abstract)
1. [Motivation](#motivation)
1. [Prior Work](#prior-work)
1. [History of the Coinbase Transaction](#history-of-the-coinbase-transaction)
1. [Coinbase Special Transaction](#coinbase-special-transaction)
1. [Requesting the masternode lists](#requesting-the-masternode-lists)
1. [Tracking/Updating and verifying masternode lists based on MNLISTDIFF](#trackingupdating-and-verifying-masternode-lists-based-on-mnlistdiff)
1. [Copyright](#copyright)

## Abstract

This DIP provides SPV (Simplified Payment Verification) clients the ability to verify the correctness of a network provided deterministic masternode list. This assumes that DIP2 and DIP3 have been deployed or are deployed at the same time as this DIP.

## Motivation

A verifiable and correct masternode list is foundational to many Dash features, including verification of an InstantSend transaction, mixing in PrivateSend and many features of Evolution. The deterministic masternode lists introduced by DIP3 enable full derivation and verification of a masternode list via on-chain data. This, however, requires the full chain to be available to construct or verify this list. A SPV client does not have the full chain and thus would have to rely on a list provided by one or more nodes in the network. This provided list must be verifiable by the SPV client without needing the full chain. This DIP proposes additions to the block’s coinbase transaction and new P2P messages to get and update a masternode list with additional proof data.

## Prior Work

* [DIP 0002: Special Transactions](https://github.com/dashpay/dips/blob/master/dip-0002.md)
* [DIP 0003: Deterministic Masternode Lists](https://github.com/dashpay/dips/blob/master/dip-0003.md)
* [BIP 34: Block v2, Height in Coinbase](https://github.com/bitcoin/bips/blob/master/bip-0034.mediawiki)

## History of the Coinbase Transaction

Before v14 of Dash Core coinbase transactions were just classical transactions with a single input that has the “prevout” and “index” (hash and index of previous transaction output) fields set to zero and 0xffffffff, respectively, and at least one output which generates new coins (the miner/masternode reward and budget payments). Initially, the “scriptSig” field of the coinbase input could contain arbitrary data, but it was later changed to at least include the block’s height as the first item in order to guarantee some variation in the coinbase. Without this variation, a miner could have created a coinbase which resulted in the same hash as an older coinbase transaction. This change was enforced by the deployment of BIP34.

More data could have been potentially added the same way as defined in BIP34, however changing the coinbase to a special transaction became preferable with the introduction of special transactions (DIP2). This is because it provided a much cleaner solution and allowed future changes to be deployed in an easier, more consistent way.

## Coinbase Special Transaction

Coinbase Transactions are special transactions (DIP2) that are mandatory and unique in each block. We abbreviate this transaction as CbTx. Miners must calculate the correct values for each field of the CbTx while all other nodes must verify correctness of these fields. If a node receives a block with an invalid CbTx, it must reject the block.

This DIP proposes adding multiple fields to the CbTx. Future DIPs might add additional fields to the CbTx.

The special transaction type used for Coinbase Transactions is 5.

The transaction consists of the following data in the payload area:

| Field | Type | Size | Description |
| ----- | ---- | ---- | ----------- |
| version | uint16_t | 2 | CbTx version number. Currently set to 1. |
| height | uint32_t | 4 | Height of the block |
| merkleRootMNList | uint256 | 32 | Merkle root of the masternode list |

Starting with version >= 2, the following fields are added:

| Field | Type | Size | Description |
| ----- | ---- | ---- | ----------- |
| merkleRootQuorums | uint256 | 32 | Merkle root of currently active LLMQs |

Starting with version >= 3, the following fields are added:

| Field | Type | Size | Description |
| ----- | ---- | ---- | ----------- |
| bestCLHeightDiff | compactSize uint | 1-9 | Number of blocks between the current block and the block locked with `bestCLSignature`. |
| bestCLSignature | BLSSig | 96 | Newest ChainLock signature known by the miner. |
| creditPoolBalance | int64_t | 8 | Total amount DASH currently locked as of this block height. |

More information on the `bestCLHeightDiff` and `bestCLSignature` fields can be found in [DIP0029 - Randomness Beacon For LLMQ Selection](https://github.com/dashpay/dips/blob/master/dip-0029.md#change-to-the-coinbase-transaction).
More information on the `creditPoolBalance` field will be described in a future document.

### Height in CbTx and deprecation of BIP34

The CbTx contains the “height” field. It acts as a guaranteed variance in the CbTx so that each block’s CbTx gets a different hash. This is meant as a replacement for the height value currently found in the coinbase input (BIP34). With the deployment of this DIP, BIP34 becomes obsolete for new blocks and nodes should not enforce the presence of the block height in the coinbase input's “scriptSig” anymore.

Miners must set this field to the block height of the current block being generated. Other nodes should validate that the CbTx of received blocks contains the correct block height.

### Calculating the merkle root of the Masternode list

The CbTx contains the “merkleRootMNList” field. This is the merkle root of all the hashes of the Simplified Masternode List (SML) entries. A [SML entry](#sml-simplified-masternode-list-entry) is defined in the next section.

To calculate the merkle root:

  1. Get the full masternode list (including PoSe-banned) of the current block. This list must also include all the updates which would have been performed by the data (DIP3 special transactions, PoSe verification, etc.) in the current block.
  2. Sort this list in ascending order by the hash of the ProRegTx of each entry.
  3. For each entry in the list, create a SML entry and calculate the hash of this entry and add the hash into a new list.
  4. Calculate the merkle root from this list of hashes in the same way it is done when calculating the merkle root of the block transactions.

### SML (Simplified Masternode List) entry

A SML entry is used to calculate the hashes for the merkleRootMNList. It is also used in the new P2P messages when a SPV client requests a full masternode list or updates to a masternode list.

A SML entry consists of the following fields:

| Field | Type | Size | Description |
| --- | --- | --- | --- |
| proRegTxHash | uint256 | 32 | The hash of the ProRegTx that identifies the masternode |
| confirmedHash | uint256 | 32 | The hash of the block at which the masternode got confirmed |
| ipAddress | byte[] | 16 | IPv6 address in network byte order. Only IPv4 mapped addresses are allowed (to be extended in the future) |
| port | uint_16 | 2 | Port (network byte order) |
| pubKeyOperator | BLSPubKey | 48 | The operators public key |
| keyIDVoting | CKeyID | 20 | The public key hash used for voting. |
| isValid | bool | 1 | True if a masternode is not PoSe-banned |

Clients with protocol version greater than or equal to 70227 will receive the following fields just after `isValid`.

| Field               | Type | Size | Description                       |
|---------------------| ---- | ---- |-----------------------------------|
| type | uint_16 | 0 or 2 | Masternode type. 0 for regular masternode, 1 for HPMN. |
| platformHTTPPort | uint_16 | 0 or 2 | TCP port of Platform HTTP/API interface (network byte order). Only present for masternode type 1. |
| platformNodeID | byte[] | 0 or 20 | Dash Platform P2P node ID, derived from P2P public key. Only present for masternode type 1. |

The new `type`, `platformHTTPPort` and `platformNodeID` fields will be serialised only when v19 activates and only for entries with `nVersion` equals to 2.

Clients with protocol version greater than or equal to 70228 will receive the following field just before `proRegTxHash`.

| Field               | Type     | Size | Description                       |
|---------------------| -------- | ---- |-----------------------------------|
| nVersion            | uint16_t | 2    | Version of the SML entry          |

The `nVersion` field indicates which BLS scheme is used to serialise each SML entries' `pubKeyOperator` field.

| Version | Value Description                                       |
|---------|-----------------------------------------------------------|
| 1       | Serialisation of `pubKeyOperator` using legacy BLS scheme |
| 2       | Serialisation of `pubKeyOperator` using basic BLS scheme  |


### Calculating the merkle root of the active LLMQs

The CbTx contains the “merkleRootQuorums” field. This is the merkle root of all the hashes of the final quorum commitments
of all active LLMQ sets.

To calculate the merkle root:

  1. Collect all final commitments from all LLMQs which are in the active set at the given block height. All LLMQ types need
     to be collected.
  2. Calculate the hash of all these commitments and collect the hashes in a list.
  3. Sort this list in ascending order by the previously calculated hash.
  4. Calculate the merkle root from this list of hashes in the same way it is done when calculating the merkle root of the block transactions.

Please refer to [DIP6 - Long-Living Masternode Quorums](https://github.com/dashpay/dips/blob/master/dip-0006.md) for more details on LLMQs
and final commitments. The final commitment referred to multiple times in this DIP is the `qfcommit` message found in
DIP6.

## Requesting the masternode lists

The P2P message `GETMNLISTDIFF` is introduced to request a full masternode list or an update to a previously requested masternode list. It expects a serialized object with the following structure as arguments:

| Field | Type | Size | Description |
| --- | --- | --- | --- |
| baseBlockHash | uint256 | 32 | Hash of a block the requestor already has a valid masternode list of. Can be all-zero to indicate that a full masternode list is requested. |
| blockHash | uint256 | 32 | Hash of the block for which the masternode list diff is requested |

After receiving the `GETMNLISTDIFF` P2P message, a node is required to respond with a new P2P message called `MNLISTDIFF`, which is described later.

To request a full masternode list, a SPV client would set the “baseBlockHash” field of `GETMNLISTDIFF` to an all-zero hash. In this case, the `MNLISTDIFF` response would not contain any “deletedMNs” entries. After receiving an initial full masternode list, the SPV client can then send a `GETMNLISTDIFF` message with the “baseBlockHash” field set to the block hash of the last known masternode list.

The `MNLISTDIFF` message contains a serialized object with the following structure:

| Field | Type | Size | Description | Minimum Protocol Version |
| --- | --- | --- | --- | --- |
| nVersion | uint16_t | 2 | Version of the `MNLISTDIFF` reply (For now, `nVersion` is always 1) | 70229 |
| baseBlockHash | uint256 | 32 | Hash of the block on which this diff is based on | --- |
| blockHash | uint256 | 32 | Hash of the block for which the masternode list diff is returned | --- |
| totalTransactions | uint32_t | 4 | Number of total transactions in blockHash | --- |
| merkleHashesCount | compactSize uint | 1-9 | Number of Merkle hashes | --- |
| merkleHashes | uint256[] | variable | Merkle hashes in depth-first order | --- |
| merkleFlagsCount | compactSize uint | 1-9 | Number of Merkle flag bytes | --- |
| merkleFlags | uint8_t[] | variable | Merkle flag bits, packed per 8 in a byte, least significant bit first | --- |
| cbTx | CTransaction | variable | The fully serialized coinbase transaction of blockHash | --- |
| deletedMNsCount | compactSize uint | 1-9 | Number of ProRegTx hashes which were deleted after baseBlockHash | --- |
| deletedMNs | uint256[] | variable | A list of ProRegTx hashes for masternode which were deleted after baseBlockHash | --- |
| mnCount | compactSize uint | 1-9 | Number of SML entries which were added or updated since baseBlockHash | --- |
| mnList | SMLEntry[] | variable | The list of SML entries which were added or updated since baseBlockHash | --- |
| deletedQuorumsCount | compactSize uint | 1-9 | Number of LLMQs which were deleted from the active set after baseBlockHash | --- |
| deletedQuorums | (uint8_t+uint256)[] | variable | A list of LLMQ type and quorum hashes for LLMQs which were deleted after baseBlockHash | --- |
| newQuorumsCount | compactSize uint | 1-9 | Number of new LLMQs which were added to the active set since baseBlockHash | --- |
| newQuorums | qfcommit[] | variable | The list of LLMQ commitments for the LLMQs which were added since baseBlockHash | --- |
| quorumsCLSigsCount | compactSize uint | 1-9 | Number of entries in quorumsCLSigs field | 70230 |
| quorumsCLSigs | quorumsCLSigsObject[] | variable | ChainLock signature used to calculate members per quorum indexes (in newQuorums) | 70230 |

The format of the `quorumsCLSigsObject` object introduced in the [DIP29 Randomness Beacon For LLMQ Selection](dip-0029.md#light-clients) is:

| 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

## Tracking/Updating and verifying masternode lists based on MNLISTDIFF

With DIP3, each block in the chain might result in a different masternode list. SPV clients are required to keep track of these multiple masternode lists so they can properly verify quorum related messages when the lists change. Very old masternode lists can be pruned as it is very unlikely that they are necessary.

To achieve this, It is suggested to first request a full masternode list from an old block, and then request a diff for each subsequent block that specifies the last processed block as baseBlockHash. Each `MNLISTDIFF` message received can be processed and verified in the same way (including non-continuous ones):

  1. Create a copy of the masternode list which was valid at “baseBlockHash”. If “baseBlockHash” is all-zero, an empty list must be used.
  2. Delete all entries found in “deletedMNs” from this list. Please note that “deletedMNs” contains the ProRegTx hashes of the masternodes and NOT the hashes of the SML entries.
  3. Add or replace all entries found in “mnList” in the list
  4. Calculate the merkle root of the list by following the “Calculating the merkle root of the Masternode list” section
  5. Compare the calculated merkle root with what is found in “cbTx”. If it does not match, abort the process and ask for diffs from another node.
  6. Calculate the hash of “cbTx” and verify existence of this transaction in the block specified by “blockHash”. To do this, use the already received block header and the fields “totalTransactions”, “merkleHashes” and “merkleFlags” from the `MNLISTDIFF` message and perform a merkle verification the same way as done when a “MERKLEBLOCK” message is received. If the verification fails, abort the process and ask for diffs from another node.
  7. Store the resulting validated masternode list identified by “blockHash”

## Tracking/Updating and verifying the active LLMQ sets based on MNLISTDIFF

With the introduction of version 2 CbTx special transactions, a merkle root for the currently active LLMQ sets was added
to the coinbase. This merkle root allows (SPV) clients to maintain the active LLMQ sets without the full chain.

It is suggested to couple the house-/bookkeeping of active LLMQ sets with the masternode list bookkeeping described in
the previous section and perform the following additional steps:

  1. Create a copy of the active LLMQ sets which were given at "baseBlockHash". If “baseBlockHash” is all-zero, empty sets must be used.
  2. Delete all entries found in "deletedQuorums" from the corresponding active LLMQ sets.
  3. Verify each final commitment found in "newQuorums", by the same rules found in [DIP6 - Long-Living Masternode Quorums](https://github.com/dashpay/dips/blob/master/dip-0006.md).
     If any final commitment is invalid, abort the process and ask for diffs from another node.
  4. Add the LLMQ defined by the final commitments found in "newQuorums" to the corresponding active LLMQ sets.
  5. Calculate the merkle root of the active LLMQ sets by following the “Calculating the merkle root of the active LLMQs” section
  6. Compare the calculated merkle root with what is found in “cbTx”. If it does not match, abort the process and ask for diffs from another node.
  7. Store the new active LLMQ sets the same way the masternode list is stored.

## Copyright

Copyright (c) 2018 Dash Core Group, Inc. [Licensed under the MIT License](https://opensource.org/licenses/MIT)