# 7 - LLMQ Signing Requests / Sessions

<pre>
  DIP: 0007
  Title: LLMQ Signing Requests / Sessions
  Author(s):  Alexander Block
  Special-Thanks: Cofresi, Darren Tapp, Thephez, Samuel Westrich
  Comments-Summary: No comments yet.
  Status: Final
  Type: Standard
  Created: 2018-09-07
  License: MIT License
</pre>

## Table of Contents

1. [Abstract](#abstract)
1. [Motivation](#motivation)
1. [Prior Work](#prior-work)
1. [Signing request](#signing-request)
1. [Signing session](#signing-session)
1. [Choosing the active LLMQ to perform signing](#choosing-the-active-llmq-to-perform-signing)
1. [Validating recovered threshold signatures](#validating-recovered-threshold-signatures)
1. [Propagating signature shares](#propagating-signature-shares)
    1. [Recovered threshold signatures](#recovered-threshold-signatures)
1. [Internal high-level API](#internal-high-level-api)
1. [Copyright](#copyright)

## Abstract

This DIP defines how signing requests and sessions are performed by activated [DIP006 Long Living Masternode Quorums (LLMQs)](https://github.com/dashpay/dips/blob/master/dip-0006.md). A LLMQ is able to perform BLS threshold signing on arbitrary messages. If enough members have signed the same message, a valid recovered threshold signature can be created and propagated to the rest of the network. A successfully recovered threshold signature is strongly secure, as it is either created or not created with no in-between state that might result in different nodes seeing different/conflicting signing results.

## Motivation

We want to have a generalized method of signing arbitrary messages, which can be applied to all kinds of use cases. One use case is InstantSend, other use cases will come from new features in Evolution. We will only slightly handle InstantSend as an example in this DIP, more details can be found in the appropriate specialized DIPs.

All these use cases require unambiguous results from a signing request: It should either succeed or fail network-wide. It should not be possible to have two nodes in the network see conflicting messages with different valid signatures for the same request.

## Prior work

* [DIP 006: Long Living Masternode Quorums](https://github.com/dashpay/dips/blob/master/dip-0006.md)

## Signing request

A signing request is identified by a deterministically calculable, unique id which we will refer to as requestId in the remainder of the document. It can, for example, be the hash of an InstantSend transaction’s input.

Initiation of a signing request happens independently per LLMQ member. When and how to initiate the request depends on the use case. For InstantSend, this would be directly after receiving and validating a transaction.

The message hash must be supplied along with the requestId. For InstantSend, the message hash would be the hash of the full transaction. The combination of quorumHash, requestId and message hash forms the signing session.

A signing request can only be initiated once and should never be performed multiple times by the same masternode. This in turn results in “one vote per member” on each individual signing request and makes it impossible to have conflicting recovered signatures for the same signing request.

As a result of a (non-conflicting) signing request, the member must create a threshold signature share. It does this by calculating `SHA256(quorumHash, requestId, messageHash)` and then signing the resulting hash with the members individual threshold secret key share. After signing, the signature share must be propagated to all LLMQ members (explained later).

## Signing session

A signing session is identified by the LLMQ’s quorumHash, signing request id and the message hash. If any member of the LLMQ receives enough threshold signature shares for a signing session, it can create the final recovered threshold signature from these shares. This recovered signature is propagated to the whole network (including non-members) and can then be verified by all nodes based on the LLMQs quorum public key.

If different members signed the same request with differing message hashes, only one of the signing sessions will create enough signature shares to reach the threshold and thus only one valid recovered signature can be created. If not enough signature shares for the same signing session can be collected, no valid recovered threshold signature will be created. In the InstantSend use case, this would indicate a failed attempt to double spend transaction inputs.

## Choosing the active LLMQ to perform signing

As multiple LLMQs are active at the same time and masternodes might be members of multiple LLMQs as well, it’s important
that all masternodes agree on which LLMQ should service the signing request. Otherwise it would be impossible to collect
enough signature shares for the same signing session and thus recovery of the threshold signature would never succeed.

To calculate which LLMQ is responsible for a signing request, each masternode should perform the following:

1. Take the active LLMQ set from 8 blocks before the current chain tip. Active LLMQ sets are described in
   [DIP6 - Long-Living Masternode Quorums](https://github.com/dashpay/dips/blob/master/dip-0006.md) section "Active LLMQ sets".
2. For each LLMQ of the active set, calculate `SHA256(quorumType, quorumHash, requestId)`
3. Sort the list of LLMQs based on the result of step 2 in ascending order.
4. Use the first entry of the sorted list as the LLMQ to perform the signing request

After the responsible LLMQ is determined, the masternode should check if it is part of the chosen LLMQ. If it is not part of that LLMQ, it must completely skip the signing request.

## Validating recovered threshold signatures

Each node (including regular nodes) must verify the recovered signatures for each signing session before accepting and relaying them. This can be done by validating the recovered signature and `SHA256(quorumHash, requestId, messageHash)` against the LLMQ’s quorum public key.

If this succeeds, the signing request is considered successful. In the InstantSend example, this would mean that a single input of the transaction has been locked.

## Propagating signature shares

Propagation of signature shares is performed through the Intra-Quorum Communication mechanism described in [DIP006](https://github.com/dashpay/dips/blob/master/dip-0006.md). This means, that only the members of a LLMQ see and propagate signature shares belonging to this LLMQ. Watchers that connect and issue the `qwatch` message will also receive signature shares.

Propagation of signature shares however does NOT use the inventory system of Dash. Instead, signature shares are sent to other quorum members in a batched message. This is due to the overhead and latency in the inventory system that, while acceptable for other message types, is unsuitable for the low-latency requirement of the signature share system. Fortunately, signature shares can be batched in a way that keeps the overhead to a minimum compared to the inventory system (and might even reduce it). The most important advantage is the removal of the latency produced by the multiple round-trip (INV->GETDATA->MESSAGE) sequences, which would add up to unacceptable latencies when propagating hundreds of messages.

When a member has signed his own signature share or validated incoming signature shares, it must add these signature shares to a pending list of batched signature shares per other member in the deterministic connections (see [DIP06, Intra-Quorum Connections](https://github.com/dashpay/dips/blob/master/dip-0006.md#intra-quorum-communication)) set. It should then periodically (e.g. every 100ms) send out all pending batches.

On receipt of a batch, each included share must be validated individually.

Validation includes:

1. The `quorumHash` must belong to an activated LLMQ
2. `shareCount` must not be larger than the `quorumSize`
3. Each entry in `shareMembers` must be in the bounds of `quorumSize`
4. No duplicate entries in `shareMembers`
5. No duplicate entries in `shareSigs`
6. The individual shares must validate to the corresponding public key shares of the corresponding members

Valid shares from the batched message must be relayed even if other shares are invalid. If an invalid share is encountered, the sending node must be banned even if other shares were valid.

If an individual share was already received from another member, verification and relaying can be skipped (as both were already done before). It is safe to check duplicate shares by hash as BLS signatures cannot differ for the same message.

The internal Dash message name is `qbsigshares` and the format of the message is:

| Field | Type | Size | Description |
|--|--|--|--|
| quorumHash | uint256 | 32 | The quorum identifier |
| id | uint256 | 32 | The signing request id |
| messageHash | uint256 | 32 | The SHA256 hash of the message |
| shareCount | compactSize uint | 1-9 | The number of signature shares in this batch |
| shareMembers | uint32[] | 4 * shareCount | Member indexes of the shares in this batch |
| shareSigs | BLSSig[] | 96 * shareCount | The signature shares |

### Recovered threshold signatures

After a member of a LLMQ has received enough (`>= quorumThreshold`) shares for a signing session, it can create the final recovered threshold signature from the signature shares. If this succeeds, the recovered threshold signature must be relayed to the whole network (including non-members).

If a valid recovered threshold signature was already received before enough shares have been received, recovering can be skipped. The reason is that the custom-created recovered signature would always be identical to the received one, thanks to the uniqueness property of BLS signatures.

On receipt of a recovered signature, all nodes should perform the following verification:

1. The `quorumHash` should belong to an active LLMQ
2. The `thresholdSig` should validate against the LLMQ’s quorum public key and `SHA256(quorumHash, id, messageHash)`.

Propagation of recovered signature shares utilizes the inventory system.

The internal Dash message name is `qsigrec` and the format of the message is:

| Field | Type | Size | Description |
|--|--|--|--|
| quorumHash | uint256 | 32 | The quorum identifier |
| id | uint256 | 32 | The signing request id |
| messageHash | uint256 | 32 | The SHA256 hash of the message |
| thresholdSig | BLSSig | 96 | The final recovered threshold signature |

## Internal high-level API

Inside the Dash Core Node, we will implement a high-level API that can be leveraged by the individual use cases. The API will support the following operations:

### void SignIfMember(uint256 id, uint256 msgHash, int activeLLMQs)

Selects the correct LLMQ based on the last active LLMQs and performs the signing request if the caller is a member and only if it did not already sign another signing session for the same signing request.

### void Sign(uint256 quorumHash, uint256 id, uint256 msgHash)

Sign the given session if the caller is a member of the given quorum.

### bool HasRecoveredSig(uint256 id, uint256 msgHash, int activeLLMQs)

Returns true if a valid recovered threshold signature was received (or locally created) for the signing session and from the last active LLMQs. Please note that the `activeLLMQs` parameter must not necessarily be the same value as was previously given to `SignIfMember`. For some use cases it might be desirable to accept signatures from old/inactive LLMQs as well.

### bool IsConflicting(uint256 id, uint256 msgHash)

Returns true if any LLMQ created a valid recovered threshold signature for any signing session with a different message hash than the given one.

### bool IsMajorityPossible(uint256 id, uint256 msgHash, int activeLLMQs)

Returns true if a recovered signature has already been received (or locally created) or if it’s still possible for this to happen. This means, that it returns false if `>= quorumThreshold` members have already signed a different signing session for the same request.

### uint256 GetMostSignedSession(uint256 id, int activeLLMQs)

Returns the `msgHash` which was signed by most LLMQ members so far. Please note that the result is not final until `HasRecoveredSig` returns true.

These operations will also be made available through RPC APIs so that external applications can also use the LLMQ signing capabilities. This will especially be useful for Evolution, as non-core services (L2) can then simply call these RPCs and won’t have to deal with the internals.

## Copyright

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