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

Sergey Gorbunov
Mar 7, 2019 · 3 min read

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.

Algorand

Algorand Inc.

Sergey Gorbunov

Written by

Algorand

Algorand

Algorand Inc. built the world’s first open source, permissionless, pure proof-of-stake blockchain protocol for the next generation of financial products. This blockchain, the Algorand protocol, is the brainchild of Turing Award-winning cryptographer Silvio Micali.

Sergey Gorbunov

Written by

Algorand

Algorand

Algorand Inc. built the world’s first open source, permissionless, pure proof-of-stake blockchain protocol for the next generation of financial products. This blockchain, the Algorand protocol, is the brainchild of Turing Award-winning cryptographer Silvio Micali.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store