Contributions to Digital Signatures in Proof-of-Stake Blockchains

Abstract

Blockchain is a decentralised and distributed ledger technology that enables multiple participants to collectively maintain a secure and tamper-resistant record of transactions without relying on trusted central authorities. It has several potential features, including decentralisation, immutability, transparency and security. Beyond its original use in cryptocurrencies, blockchain has facilitated a diverse range of applications, including decentralised finance, supply chain tracking, digital identity management, secure voting systems and decentralised autonomous organisations, where transparency, trustlessness and data integrity are critical. Structurally speaking, a blockchain consists of an ordered sequence of blocks, each containing a set of validated transactions. Every block incorporates a cryptographic hash of its previous block, linking them into an immutable chain that maintains chronological ordering and prevents tampering. At its foundation, a blockchain relies on the consensus mechanism that ensures all untrusted participants agree on a consistent ledger state, despite network latency or malicious behaviour. Up to now, widely adopted consensus algorithms include proof-of-work (PoW), which relies on computationally intensive puzzles, and proof-of-stake (PoS), which utilises economic incentives based on stake ownership. Unlike PoW, PoS consumes less energy, achieves faster block finalisation with lower latency and lowers participation barriers, enhancing efficiency, scalability and decentralisation without compromising security.Digital signatures are fundamental cryptographic primitives essential for establishing trust and ensuring security in digital communications. By using a secret key to generate signatures on given messages, anyone who knows the corresponding public key can check the validity of signature candidates. This cryptographic process provides critical guarantees such as authentication, data integrity and non-repudiation, making them integral to secure communication and a wide range of cryptographic protocols. In PoS blockchain protocols, digital signatures play a crucial role not only in authenticating transactions but also in validating the participation of stakeholders in consensus processes, such as block proposals and block attestations. Advanced signature schemes, including forwardsecure signatures or puncturable signatures, are often employed to prevent long-range attacks caused by secret key leakage, preserving the immutability of PoS blockchain protocols. Furthermore, threshold or weighted threshold signatures are frequently deployed in PoS-based protocols to aggregate multiple block attestations into a single compact one efficiently, enhancing scalability while maintaining robust security guarantees.This thesis focuses on advanced digital signature schemes deployed in proof-of-stake blockchain protocols, with particular emphasis on puncturable signatures and weighted threshold signatures. To be more specific, the main contributions of this thesis are outlined as follows.First, we focus on puncturable signatures and propose the first generic construction derived from identity-based signatures by treating identities as to-be-punctured prefixes. Based on this framework, we give concrete puncturable signature instantiations over bilinear maps, lattices and multivariate polynomials, respectively. More specifically, the pairing-based instantiation is proven secure based on the computational Diffie-Hellman (CDH) assumption in the standard model. The lattice-based instantiation achieves provable security under the short integer solution (SIS) assumption in the random oracle model. The multivariate-based instantiation is analysed against some best-known attacks in multivariate public key cryptography. All of the proposed schemes support efficient puncture operations, while the lattice-based and multivariate-based ones additionally enjoy post-quantum security.Second, we adopt a different approach to constructing puncturable signatures supporting compact secret keys that serve as an effective mitigation against long-range attacks caused by secret key leakage in PoS blockchains. Specifically, we propose a new generic construction of puncturable signatures from delegated (key-policy) constrained signatures. Such a framework is inspired by an observation that matching between messages and constraints can be converted to equality tests between prefixes of to-be-signed messages and punctured prefixes. The key delegation property of (key-policy) constrained signatures enables repeated key puncture operations. Building on our framework, we give a concrete lattice-based instantiation that is proven secure based on the SIS assumption in the standard model. Our proposed scheme features small secret key sizes, particularly for the initial secret key, which is beneficial for users to join PoS blockchains without requiring a significant commitment in the initial phase.Third, we revisit the notion of puncturable signatures and find their vulnerability in mitigating long-range attacks caused by secret key leakage in PoS blockchains. Despite their key evolving property, compromising previous secret keys enable adversaries to forge branches in PoS blockchains, bypassing the security guarantees provided by puncturable signatures. It is essential to invalidate previous secret keys, regardless of whether they have been securely deleted. Therefore, we integrate key puncture and signing operations into a unified Sign-and-Pun algorithm. By publishing punctured prefixes and providing additional proofs, our strengthened puncturable signatures ensure that no malicious signers can generate valid signatures using previous secret keys. Furthermore, we propose a concrete lattice-based construction that is provably secure under the SIS assumption in the standard model.Finally, we focus on weighted threshold signatures for block attestations in PoS blockchain protocols, where validators are assigned different weights to reflect their varying impacts on consensus decisions. Specifically, we present the first weighted threshold signature scheme over lattices, which is a combination of multi-signature and non-interactive inner product arguments. In our proposed scheme, the weights of signers are public and work as a separate checking condition in threshold signature verification. We show that our scheme is provably secure under the module short integer solution (MSIS) assumption in the random oracle model. Furthermore, we demonstrate how to integrate our scheme into PoS blockchains for block attestation. Moreover, we implement our scheme in the C programming language and present an experimental evaluation of its practical efficiency.