HIP-1200: The hinTS threshold signature scheme

Abstract

Hiero networks sign blocks in the V6 record stream by each node in the network publishing an RSA signature on the hash of every block it produces as specified in HIP-415. The network’s aggregate signature on block N is any combination of valid RSA partial signatures from nodes holding at least 1/3 of the network weight.

This scheme is simple but inefficient. Verifiers must track the node RSA keys published in the network state. Consequently, a state signature must attest to the chain of address books since genesis, which is costly. Assuming a roughly uniform stake distribution, the aggregate signature size and verification work needed both grow linearly with the number of nodes in the network. Moreover, verifying RSA signatures on EVM chains is impractical, due to linear number of signatures, and the lack of native precompile support for RSA.

We propose that Hiero networks adopt the hinTS threshold signature scheme (TSS) from [1] in tandem with adopting the block stream proposed in HIP-1056. The hinTS scheme provides a constant-size signature that can be cheaply verified (including by an EVM smart contract via gas-efficient precompiles). That is, hinTS achieves two properties that are crucial for many Hiero use cases:

1. Constant-size signatures, no matter the number of nodes in the network or the details of its weight distribution; and,
2. Constant-time verification work for every signature in the network’s history.

Motivation

Most consumers of a Hiero network’s block stream will need to verify the blocks they receive by checking the network’s signature on the block Merkle tree. Many network clients will also want to verify state proofs by checking the same signature (since the state Merkle tree is a subtree of the block Merkle tree). It follows that the cost of verifying block signatures has a large effect on a Hiero network’s usability, especially as the network size grows and its history includes many roster and weight changes. For example, suppose a decentralized finance (DeFi) application wants to respond as soon as possible to state changes that represent onchain market signals. It must be able to verify each block’s signature quickly and cheaply. As another example, consider inter-ledger communication between Hiero networks and EVM chains. Any such inter-ledger protocol will need to be based on an efficient threshold signature scheme to keep gas costs low.

Rationale

The appeal of the hinTS scheme is described extensively in [1], so we will not repeat each reason to adopt it in this HIP. The main benefit we do want to emphasize, other than efficiency, is that hinTS lets nodes be assigned exact weights, even at the resolution of 64-bit stake weights. Moreover, it uses a silent setup, avoiding the communication and computation heavy protocols often associated with DKG-based threshold signature schemes.

The support for exact weights is attractive because, for an aBFT proof-of-stake blockchain, the access structure needed to form a network signature is the agreement of any set of nodes holding at least 1/3 of the total consensus weight. In a Hiero network, consensus weights are the whole number of HBARs staked to each node, and the network’s HBAR supply can be configured with 64-bit precision. It follows that the weights in a Hiero threshold access structure also need 64-bit precision.

Thus, adopting hinTS lets Hiero networks impose exactly the access structure that is most natural for the aggregate signatures of a proof-of-stake blockchain.

User stories

• As a Hiero network user, I want to be able to verify the signature of any block proof created by the network without keeping the full address book history and the signing (RSA) key of every node throughout that history.
• As a Hiero network user, I want to do constant-time work to verify each block proof.
• As a Hiero block node operator, I want concise network signatures to reduce the amount of information I need to store and serve to block proof consumers.

Technical Overview

The hinTS signature on any block N attests to the statement that the block’s content has been signed (via the BLS algorithm) by nodes constituting 1/3 of the network weight, according to the address book in use for block N. However, since the network can adopt different address books over time, the statement above must also imply that the address book being used in block N is a descendent of the genesis address book, wherein each address book rotation is authorized via signatures from 1/3 (in weight) of the members of the active address book.

We label each address book with a (public) verification key, which is used to verify that the aggregate BLS signature (computed by aggregating the BLS partial signatures) is derived from a threshold fraction of the nodes by weight. Starting with the genesis address book, each time the network adopts a new address book, it will publish a recursive SNARK proof in the block stream that proves the new address book’s verification key belongs to the network’s chain of trust – the witnesses to this recursive SNARK prover algorithm is the prior recursive SNARK proof, and a set of Schnorr signatures from members of the prior address book, representing 1/3 amount of weight. Therefore, in hinTS, each block signature contains the following components:

1. a BLS aggregate signature, resulting from combining the partial BLS signatures over that block;
2. a lightweight SNARK proof proving that the signers in the above BLS aggregate signature comprise 1/3 of the active address book by weight – this proof is verified w.r.t. the verification key of the active address book;
3. a recursive SNARK proof proving that the active address book is a descendent of the genesis address book;

Specification

Our specification has four parts.

1. First, we define the TSS address book and how we can use proof keys to link one address book to the next in a cryptographic chain of trust that binds arbitrary metadata to each address book in the chain.
2. Next, we outline the information flow in the construction of a hinTS scheme, emphasizing that the main external output of each hinTS scheme, its verification key, is exactly the metadata bound to the corresponding address book in the chain of trust.
3. Third, we discuss the special case of the genesis block that initializes the chain of trust.
4. Finally, we tie everything together by specifying the BlockProof protobuf message a Hiero network uses to externalize its block signatures.

Important: This specification is for developers working on the core protocol, block nodes, and mirror nodes. We confine ourselves to just what is needed to correctly produce and consume the TSS protocol outputs in the block stream, taking as given a cryptography library that provides the API of the HintsLibrary and HistoryLibrary interfaces in the reference implementation in [4].

Readers interested in thoroughly understanding the reference implementation should refer to its design documentation. Readers interested in the deeper details of the cryptography should consult [1].

Schnorr proof keys and the address book chain of trust

Users of a Hiero network must apriori trust a large majority of the originators of the network, which forms the root of trust rather than some cryptographic proof. This is obvious since the originators will, by definition, hold the entire stake weight; and, even the gold standard of aBFT security is mathematically limited to a corruption threshold of strictly less than a third of the weight.

But users should never have to extend their trust beyond the aforementioned root (and the limits of aBFT fault tolerance and other cryptographic assumptions within hinTS). Every future change to the membership of the network must come with cryptographic proof that at least one third of the weight (and hence at least one honest node) voted for that membership change.

We propose a recursive proof mechanism that uses a succinct non-interactive argument of knowledge (SNARK) based on honest nodes contributing signatures to address book. These signatures are computed using Schnorr private keys whose public keys are gossiped to the network and stored within the address book. The message used to gossip a Schnorr public key is,

message HistoryProofKeyPublicationTransactionBody {
  /**
   * The public key the submitting node intends to use when
   * contributing signatures for use in proving history
   * belongs to the chain of trust for the ledger id.
   */
  bytes history_public_key = 1;
} 

The network membership is characterized by a TSS address book made up of (nodeId, history_public_key, weight) triples; where the history_public_keys are the Schnorr public keys gossiped as above; and the nodeId and weight fields are identical to those in a current or candidate consensus roster.

It follows that every recursive proof construction derives from a source roster (and address book), and aims to prove a trustworthy transition to a target roster (and address book). The first time that TSS is enabled on a Hiero network is a special case in which the same roster serves as both source and target; the TSS address book for this special roster is called the genesis address book. From that point forward, the SHA-256 hash of the genesis address book is the ledger id.

ledgerId = <genesisAddressBookHash>

In the reference implementation, as soon as the ledger id is computed, it is set in a singleton with the State API key HistoryService.LEDGER_ID with StateIdentifier ordinal 42. This singleton has the simple type,

message ProtoBytes {
    bytes value = 1;
}

Any block stream consumer that wants to validate signatures should keep the value of this singleton readily available, since it is an ingredient in every chain-of-trust proof. The consumer might extract it from the genesis block, or fetch it from a trusted registry of chain ids.

The honest nodes in the network prove every subsequent address book change — with respect to the above ledger id — by first using a deterministic policy to determine the hash of the target address book, then gossiping their Schnorr signatures on the hash of that address book after being concatenated with arbitrary metadata that should be trusted for that address book. The message used to gossip these signatures is,

message HistoryProofSignatureTransactionBody {
  /**
   * The id of the proof construction this signature is contributing to.
   */
  uint64 construction_id = 1;

  /**
   * This node's signature on its computed history.
   */
  com.hedera.hapi.node.state.history.HistorySignature signature = 2;
}

Where we have,

/**
 * A piece of new history in the form of an address book hash and
 * associated metadata.
 */
message History {
  /**
   * The address book hash of the new history.
   */
  bytes address_book_hash = 1;
  /**
   * The metadata associated to the address book.
   */
  bytes metadata = 2;
}

/**
 * A node's signature blessing some new history.
 */
message HistorySignature {
  /**
   * The new history the node is signing.
   */
  History history = 1;
  /**
   * The node's signature on the canonical serialization of
   * the new history.
   */
  bytes signature = 2;
}

The honest nodes then use another deterministic policy to take a sufficient set of the valid signatures as inputs to the recursive SNARK prover; compute the proof; and then gossip their vote for that proof as the evidence the roster transition is trustworthy.

The arbitrary metadata concatenated with the address book is the bridge between the address book chain of trust and the hinTS signing scheme actually used to create TSS signatures, as we see next.

hinTS BLS keys and TSS signatures

When faced with a new candidate address book, the honest nodes in the network must work together to setup the hinTS scheme for that address book. The first step is to gossip a special, cryptographically “extended” form of the public BLS key – called the hinTS key – that they have generated for their individual use.

message HintsKeyPublicationTransactionBody {
  ...
  /**
   * The party's hinTS key.
   */
  bytes hints_key = 3;
}

Unlike simple BLS keys, these extended hinTS keys have information that can be preprocessed into an aggregated verification key. Given a verification key VK that aggregates the hinTS keys { k_1, k_2, ..., k_n }, the hinTS scheme lets us replace (1) a linear-size list of partial signatures { s_1, s_2, ... s_n } that verify under the respective keys; with (2) a single aggregate signature S (with claimed aggregate weight) that verifies under VK.

The honest nodes use a deterministic policy to choose which of the published hinTS keys they will aggregate into the verification key for the target address book, then gossip a vote on the resulting preprocessing output. The honest nodes adopt the VK from the preprocessing output that receives votes from at least a third of the stake weight in the source address book for the construction.

The genesis block

We discussed above how the VK for the hinTS scheme of an address book is included in the chain-of-trust proof that links that address book to the previous one. However, chain must have a beginning—that is, a genesis address book with an initial hinTS scheme.

For the genesis hinTS VK, there is no recursive proof. The genesis block itself must be trusted. Specifically, the Hiero protocol guarantees the genesis block of a network will include,

1. A HistoryProofKeyPublicationTransactionBody for strictly more than 2/3 of the weight in the genesis roster.
2. The ledger id derived from the hash of the address book with these keys.
3. A HistoryProofSignatureTransactionBody on the History formed from this ledger id and the genesis hinTS VK for at least 1/3 of the weight in the genesis roster.

If a stream consumer trusts it knows the ledger id for a network, it can then, given the genesis block, verify the Schnorr keys and roster in that block hash to the ledger id. Since this proves the Schnorr keys are trustworthy, their signatures in the genesis block then establish the genesis hinTS key.

Verifying BlockProofs as a stream consumer

A Hiero network externalizes its signatures in the following message.

message BlockProof {
  /**
   * The number of the block being proven via TSS signature.
   */
  uint64 block = 1;
  /**
   * If not the genesis block, the previous block root hash.
   */
  bytes previous_block_root_hash = 2;
  /**
   * The state hash at the start of the block.
   */
  bytes start_of_block_state_root_hash = 3;
    
  /**
   * If non-empty, the Merkle path from the root of this block to
   * a successor block whose root hash this signature applies to.
   */
  repeated MerkleSiblingHash sibling_hashes = 4;

  /**
   * The hinTS signature proving the block.
   */
  bytes hints_signature = 5; 
  /**
   * The hinTS verification key the signature verifies under.
   */
  bytes hints_verification_key = 6;

  /**
   * Proof the hinTS verification key is trustworthy.
   */
  oneof {
    /**
     * If this is the genesis block, a convenient listing of the contained
     * Schnorr signatures on the concatenation of the ledger id and genesis
     * hinTS verification key.
     */
    ListOfSchnorrSignatures schnorr_signatures = 7;
    /**
     * If this is not the genesis block, an uncompressed SNARK proof proving
     * the chain of trust from the ledger id to this hinTS verification key;
     * approximately 1.5MB.
     */
    bytes wraps_proof = 8;
    /**
     * If this is not the genesis block, a ZK-compressed SNARK proof proving
     * the chain of trust from the ledger id to this hinTS verification key;
     * approximately 1KB.
     */
    bytes wraps_proof_compressed = 9;
  }
}

message ListOfSchnorrSignatures{
    repeated bytes schnorr_signature = 1;
}

The verification procedure consists of the following steps in order:

1. verify the chain-of-trust proof using the SNARK verification key (hard-coded in the verifier). Note that the proof can take one of three forms: schnorr_signatures, wraps_proof or wraps_proof_compressed. The proof contains (as part of the SNARK statement) metadata, including the 256-bit hash of hints_verification_key.
2. assert that the SHA-256 hash of hints_verification_key equals the value from the proof above.
3. use the hinTS verification method to verify hints_signature with respect to hints_verification_key.

Backwards Compatibility

Because we propose to enable hinTS TSS in tandem with the block stream detailed in HIP-1056, this change will be one just more part of a sharp and permanent discontinuity in the Hiero protocol. (Hedera may choose to publish TSS block proofs for all historical mainnet blocks; but that is not part of the scope of this HIP.)

Security Implications

The attack surface for forging hinTS signatures is essentially the same as already exists with the V6 record stream today. If an attacker can steal the private keys of nodes that hold at least 1/3 of the stake weight, they can forge network signatures on arbitrary blocks (whether that means listing RSA signatures or aggregating BLS signatures). Node operators must therefore remain vigilant and follow best practices to ensure the physical and cyber security of their machines.

How to Teach This

For a HIP that adds new functionality or changes interface behaviors, it is helpful to include a section on how to teach users, new and experienced, how to apply the HIP to their work.

Reference Implementation

Please refer to the HintsService and HistoryService in the Hiero consensus node repository for the reference implementation.

Rejected Ideas

Before adopting hinTS, there was lengthy consideration of an inexact-weight threshold scheme that would approximate each node’s stake weight by granting it a number of BLS key pairs called shares. Nodes with more stake would get more shares, and nodes with less stake would get fewer shares. Although this approach offered at least equal or better space and time efficiency than hinTS, the complexity and compromises inherent with inexact weights made hinTS the better choice for Hiero networks.

Open Issues

No known issues are currently under discussion.

References

1. Garg, S., Jain, A., Mukherjee, P., Sinha, R., Wang, M., & Zhang, Y. (2023). hinTS: Threshold Signatures with Silent Setup. Cryptology ePrint Archive, Paper 2023/567. Retrieved from https://eprint.iacr.org/2023/567
2. HIP-415: Introduction of Blocks
3. HIP-1056: Block Streams
4. Hiero consensus node
5. Reference implementation design doc
6. SNARK construction state change ordinals
7. hinTS construction state change ordinals
8. Ledger id state change ordinal.

Copyright/license

This document is licensed under the Apache License, Version 2.0 — see LICENSE or https://www.apache.org/licenses/LICENSE-2.0.

Citation

Please cite this document as: