HIP-1200: The hinTS threshold signature scheme

Abstract

This proposal introduces the hinTS threshold signature scheme (TSS), designed for Hiero networks to sign blocks within the block stream (HIP-1056). It replaces individual RSA signatures with constant-size, efficiently verifiable signatures that are seamlessly integrated into the block stream.

Currently Hiero networks use record signing in the V6 record stream to ensure integrity, as defined in HIP-415. Each node generates an individual RSA signature on the hash of every block it produces, verified independently by a majority of weighted nodes.

The current RSA-based signing is inefficient. Verifiers must verify RSA keys from multiple nodes which is computationally costly and will grow as nodes are added to the network. With uniform stake distribution, signature count and verification work scale linearly with node count. Verifying numerous RSA signatures on EVM chains is impractical due to linear scaling and lack of native RSA precompile support.

This HIP proposes the adoption of TSS be introduced alongside HIP-1056’s block stream. TSS will produce a constant-size signature per block, simplifying verification for block nodes, mirror nodes and other services, including via EVM smart contracts with gas-efficient precompiles.

TSS provides the following advantages: Constant-Size Signatures: Signature size remains fixed, regardless of node count or weight distribution, reducing storage and transmission overhead. Constant-Time Verification: Verification work is independent of network size, improving scalability and enabling efficient EVM integration.

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 greater than 1/2 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 of greater than 1/2 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 of greater than 1/2 (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 greater than 1/2 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 comprised of greater than 1/2 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;
}

For record stream legibility, when the ledger id is created the network also publishes a new synthetic transaction body,

message LedgerIdPublicationTransactionBody {
  /**
   * The new ledger id.
   */
  bytes ledger_id = 1;

  /**
   * The key to use when verifying recursive chain-of-trust proofs that extend
   * from this ledger id.
   */
  bytes history_proof_verification_key = 2;
}

where the history_proof_verification_key is the key used to verify the recursive proofs that extend the chain of trust from the ledger id through TSS address book changes.

Any block stream consumer that wants to validate signatures should keep the ledger id readily available, since it is an ingredient in every chain-of-trust proof.

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 greater than 1/2 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 the proof of each block in the following message.

message BlockProof {
    /**
     * The block this proof secures.<br/>
     * We provide this because a proof for a future block can be used to prove
     * the state of the ledger at that block and the blocks before it.<br/>
     * <p>
     * This value SHOULD match the block number of the current block,
     * under normal operation.
     */
    uint64 block = 1;

    /**
     * The hinTS key that this signature verifies under; a stream consumer should
     * only use this key after first checking the chain of trust proof.
     */
    bytes verification_key = 2;

    /**
     * Proof the hinTS verification key is in the chain of trust extending
     * from the network's ledger id.
     */
    ChainOfTrustProof verification_key_proof = 3;

    /**
     * The proof contents verifying the block's merkle root hash.<br/>
     * This is a `oneof` field that MAY contain one several types of
     * proofs.
     */
    oneof proof {
        /**
         * A TSS signature over the block's merkle root hash.<br/>
         * This signature SHALL be produced by a threshold signature scheme
         * that allows multiple nodes to contribute partial signatures that
         * can be aggregated into a single signature. This field MUST be
         * used when the current block is signed directly by the consensus
         * nodes with a TSS signature; otherwise it MUST be empty.
         */
        TssSignedBlockProof signed_block_proof = 4;

        /**
         * A proof of the block merkle tree's contents. This proof SHALL
         * contain the information necessary to validate the previous block's
         * hash, along with any information necessary to validate the current
         * block's hash.
         * <p>
         * Of necessity, the state proof MUST contain a set of hash values,
         * along with ordering information, that allows for reconstruction of the
         * block's hash. This list of hash values form the set of sibling hash values
         * needed to correctly reconstruct the parent hash, and all hash values
         * "above" that hash in the merkle tree.
         * <p>
         * A Block proof can be constructed by combining the sibling hashes for
         * a previous block hash and sibling hashes for each entry "above" that
         * node in the merkle tree of a block proof that incorporates that previous
         * block hash. This form of block proof may be used to prove a chain of
         * blocks when one or more older blocks is missing the original block
         * proof that signed the block's merkle root directly.
         * <p>
         * Such a list MUST be ordered from the sibling of the node that contains
         * this block's root node hash, and continues up the merkle tree to the
         * root hash of the signed block proof.
         * <p>
         * If this block proof has a "direct" signature, then any associated list
         * of siblings MUST be empty.<br/>
         * If said list is not empty, then this block proof MUST be verified by
         * first constructing the "block" merkle tree and computing the root hash
         * of that tree, then combining that hash with the values in this list,
         * paying attention to the first/second sibling ordering, until the root
         * merkle hash is produced from the last pair of sibling hashes. That
         * "secondary" root hash MUST then be verified using the value of
         * `block_signature`.
         */
        StateProof block_state_proof = 5;

        /**
         * A proof consisting of RSA signatures from consensus nodes.<br/>
         * This proof type exists for backward compatibility with blocks that
         * wrap historical record files.<br/>
         * This field MUST be set when the block wraps a record file signed by
         * individual RSA signatures from consensus nodes; otherwise it MUST be
         * empty.
         */
        SignedRecordFileProof signed_record_file_proof = 6;
    }
}

message ChainOfTrustProof {
    oneof proof {
        /**
         * If there is not yet a SNARK proving the chain of trust from ledger id to
         * the hinTS verification key, an aggregation of Schnorr signatures on
         * the concatenation of the ledger id and genesis hinTS verification key
         * that serve as witnesses for the SNARK prover algorithm.
         */
        AggregatedNodeSignatures aggregated_node_signatures = 1;
        /**
         * If known, a ZK-compressed SNARK proof proving the chain of trust from
         * the ledger id to this hinTS verification key.
         */
        bytes wraps_proof = 2;
    }
}

/**
 * An aggregation of node signatures on some data.
 * <p>
 * Can be used to prove the genesis hinTS verification key in a block proof; but
 * not succinct and not recursive; hence in normal operations with TSS, used only
 * until the first recursive proof is available.
 */
message AggregatedNodeSignatures {
  /**
   * The aggregated signature.
   */
  bytes aggregated_signature = 1;
  /**
   * In ascending order, the ids of the nodes that contributed signatures.
   */
  repeated uint64 signing_node_ids = 2;
}

/**
 * A proof containing a TSS signature for a single block.
 */
message TssSignedBlockProof {
    /**
     * A TSS signature for one block.<br/>
     * This is a single signature representing the collection of partial
     * signatures from nodes holding strictly greater than 2/3 of the
     * current network "weight" in aggregate. The signature is produced by
     * cryptographic "aggregation" of the partial signatures to produce a
     * single signature that can be verified with the network public key,
     * but could not be produced by fewer nodes than required to meet the
     * threshold for network stake "weight".
     * <p>
     * This message MUST make use of a threshold signature scheme like `BLS`
     * which provides the necessary cryptographic guarantees.<br/>
     * This signature SHALL use a TSS signature to provide a single signature
     * that represents the consensus signature of consensus nodes.<br/>
     * The exact subset of nodes that signed SHALL neither be known nor
     * tracked, but it SHALL be cryptographically verifiable that the
     * threshold was met if the signature itself can be validated with
     * the network public key (a.k.a `LedgerID`).
     */
    bytes block_signature = 1;
}

message StateProof {
    /**
     * The merkle paths that prove the nodes in the block merkle tree.
     * This field SHALL contain, in the following order:
     * - The merkle path from the previous block root (the "left-most"
     *   node on level 5) to it's (single) internal node parent (on level
     *   1, adjacent to the block's consensus timestamp).
     * - The merkle path from the consensus timestamp leaf to the root.
     * - The merkle path of the root of the entire block merkle tree.
     */
    repeated MerklePath paths = 1;

    oneof proof {
        /**
         * A proof containing a TSS signature for a single block. This field
         * SHALL contain the proof of a block with a block number greater
         * than or equal to the current block; otherwise this field MUST be
         * omitted.
         */
        TssSignedBlockProof signed_block_proof = 2;

        /**
         * A proof containing RSA signatures from consensus nodes for a record
         * file. This field MUST contain the proof of the record file only if
         * the state proof is being provided for a record file; otherwise it
         * MUST be omitted.
         */
        SignedRecordFileProof signed_record_file_proof = 4;
    }
}

/**
 * A proof containing RSA signatures from consensus nodes for a record file.
 */
message SignedRecordFileProof {
    /**
     * A collection of RSA signatures from consensus nodes.<br/>
     * These signatures validate the hash of the record_file_contents field.
     */
    repeated RecordFileSignature record_file_signatures = 1;
}

/**
 * A signature by a node on the SHA384 hash of the record file.
 */
message RecordFileSignature {
    /**
     * A single RSA signature.<br/>
     * This is the RSA signature of the node on the SHA384 hash of
     * the record file
     */
    bytes signatures_bytes = 1;

    /**
     * A unique node identifier.<br/>
     * This is the node id of the consensus node that created this signature.
     */
    int32 node_id = 2;
}

The verification procedure consists of the following steps in order:

1. Verify the chain-of-trust proof for the verification_key; if a wraps_proof, this is done using the SNARK verification key. published in the LedgerIdPublicationTransactionBody.
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 greater than 1/2 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: