Pixel-signatures: Efficient and Secure Digital Signatures for Proof-of-Stake Blockchains

We at Algorand are committed to continuous innovation. Recently, our cryptography group announced some exciting news on our efforts to standardize BLS signature scheme. The signature scheme can, for example, be used to compress many transaction signatures into a single signature. But what signature scheme should users use to sign blocks during consensus? Unfortunately, BLS signatures and variants there-of would not work, as they do not provide security against adaptive attacks on the blockchain.

I’m excited to share more news from the cryptography group. A few weeks ago at the Swiss Blockchain School in Interlaken, I presented a new signature scheme that Hoeteck Wee and I worked on that can be used to compress signatures in the consensus and simultaneously provides security against adaptive attacks. (The scheme can also be used as a forward-secure multi-signature on transactions.).

Let me first explain the general architecture of Proof-of-Stake (PoS) blockchains. Generally, PoS-based blockchains share the following structure:

1. A committee of selected users runs a consensus sub-protocol to agree on what block B to be added next.
2. Each committee member then signs that block B.
3. Each node then appends a block B to their view of the ledger if it sees sufficiently many committee member signatures on the block B.

We refer to this collection of committee signatures on block B as the block certificate. The way in which the committees are selected and the consensus sub-protocol varies quite substantially amongst the various designs.

In recent work, we designed a new signature scheme that is the common cryptographic core of all PoS-based blockchains — namely, the signature scheme used by the committee. The scheme tries to optimize for efficiency and security:

• In terms of efficiency, the main cost of PoS protocols is bandwidth and space needed to propagate committee signatures and to store the block certificate, as well as the computational resources needed for signature verification of these certificates.

• In terms of security, we require that the signatures be forward-secure (property similar to forward secrecy satisfied by key-agreement protocols). That is, each signature is associated with the current time period in addition to the signed message, and after each time interval, a user’s secret key can be updated in such a way that it can only be used to sign messages for future time periods, but not previous ones. The use of forward-secure signatures prevents adaptive attacks on a PoS-based blockchain.

Using our construction, the set of committee signatures (S_1, … , S_n) can be compressed (aggregated) into a single efficiently verifiable signature S. Moreover, after signing on a block for round r, users can rotate their keys to satisfy forward-secrecy as explained above. Put together, the scheme can be used to build scalable and secure consensus in blockchains.

You can view the white paper here, which also describes additional details such as how we can use proofs of possessions to provide protection against rogue-key attacks, key rotation algorithms, and performance estimates.

Building cryptographic schemes is a complex process that involves theoretical design, standardization, integration, and deployment. Algorand cryptography group is excited to continue exploring advanced cryptography to optimize the performance and security of blockchains.