ALGORAND: Pixel: Multi-signatures for Consensus

ALGORAND: Pixel: Multi-signatures for Consensus

Algorand (ALGO) is a cryptocurrency network focused on payments and smart contracts that has a solid foundation in scientific research.
Backed by a highly educated and experienced team, the Algorand platform has received investment from major entities and shows great promise as a next generation cryptocurrency.
Algorand (ALGO) was founded in 2017 by MIT professor and Turing Prize winner Silvio Micali in 2017.
Chief Executive Officer (CEO) of the project is Steve Kokinos, a Boston-based technology executive who is co-founder and former CEO of Fuze. The company behind the development of the project is Algo Capital.
Algorand has a fundamental purpose for its existence: to improve the foundations of the current blockchain paradigm to provide what the team believes will be the most suitable base layer for the future of blockchain-related development. First, it intends to do this with a consensus algorithm that it defines as Proof-of-Stake (an improved Proof-of-Stake model).
The name of the project derives from the “algorithmic randomness it uses… to choose a set of verifiers who are in charge of building the next block of valid transactions”.
Algorand is a direct response to the computational inefficiency and the Proof-of-Work trend of Bitcoin, which could lead to the centralization of mining.
The Algorand team has published several white papers, with the original as the basis for the network. Other white papers focus on scaling, governance, the aforementioned blockchain compression, and digital signatures. All these documents have been peer reviewed. The Algorand code is available for the more tech savvy.
Below we link a video on Youtube where Cosimo Bassi, alias Cusma, a few months ago became Algorand Developer Ambassador, held a popular meetup on Algorand technology on April 15, 2020 (in Italian).
Algorand is dedicated to fostering constant evolution to anticipate and fulfill future technology needs on our platform. Our researchers represent some of the best and brightest in blockchain and cryptocurrency. Recent research that has been peer reviewed and edited is found below.
Dec 03, 2019
Pixel: Multi-signatures for Consensus

By Manu Drijvers, Sergey Gorbunov, Gregory Neven and Hoeteck Wee
In Proof-of-Stake (PoS) and permissioned blockchains, a committee of verifiers agrees and signs every new block of transactions. These blocks are validated, propagated, and stored by all users in the network. However, posterior corruptions pose a common threat to these designs, because the adversary can corrupt committee verifiers after they certified a block and use their signing keys to certify a different block. Designing efficient and secure digital signatures for use in PoS blockchains can substantially reduce bandwidth, storage and computing requirements from nodes, thereby enabling more efficient applications.
We present Pixel, a pairing-based forward-secure multi-signature scheme optimized for use in blockchains, that achieves substantial savings in bandwidth, storage requirements, and verification effort. Pixel signatures consist of two group elements, regardless of the number of signers, can be verified using three pairings and one exponentiation, and support non-interactive aggregation of individual signatures into a multi-signature. Pixel signatures are also forward-secure and let signers evolve their keys over time, such that new keys cannot be used to sign on old blocks, protecting against posterior corruption attacks on blockchains. We show how to integrate Pixel into any PoS blockchain. Next, we evaluate Pixel in a real-world PoS blockchain implementation, showing that it yields notable savings in storage, bandwidth, and block verification time. In particular, Pixel signatures reduce the size of blocks with 1500 transactions by 35% and reduce block verification time by 38%.
This paper was peer-reviewed and will appear at USENIX Security 2020. The paper can be viewed here.
Feb 24, 2019

Vault: Fast Bootstrapping for the Algorand Cryptocurrency
By Derek Leung, Adam Suhl, Yossi Gilad, Nickolai Zeldovich

Abstract: Decentralized cryptocurrencies rely on participants to keep track of the state of the system in order to verify new transactions. As the number of users and transactions grows, this requirement becomes a significant burden, requiring users to download, verify, and store a large amount of data to participate. Vault is a new cryptocurrency design based on Algorand that minimizes these storage and bootstrapping costs for participants. Vault’s design is based on Algorand’s proof-of-stake consensus protocol and uses several techniques to achieve its goals. First, Vault decouples the storage of recent transactions from the storage of account balances, which enables Vault to delete old account state. Second, Vault allows sharding state across participants in a way that preserves strong security guarantees. Finally, Vault introduces the notion of stamping certificates, which allow a new client to catch up securely and efficiently in a proof-of-stake system without having to verify every single block. Experiments with a prototype implementation of Vault’s data structures show that Vault’s design reduces the bandwidth cost of joining the network as a full client by 99.7% compared to Bitcoin and 90.5% compared to Ethereum when downloading a ledger containing 500 million transactions.
The peer reviewed white paper can be viewed here.
Aug 28, 2018

Algorand Agreement – Super Fast and Partition Resilient Byzantine Agreement
By Jing Chen, Sergey Gorbunov, Silvio Micali, Georgios Vlachos
Abstract: We present a simple Byzantine agreement protocol with leader election, that works under> 2/3 honest majority and does not rely on the participants having synchronized clocks. When honest messages are delivered within a bounded worst-case delay, agreement is reached in the expected constant number of steps when the elected leader is malicious, and is reached after two steps when the elected leader is honest. Our protocol is resilient to arbitrary network partitions with unknown length, and recovers fast after the partition is resolved and bounded message delay is restored. We will briefly discuss how the protocol applies to blockchains in a permissionless system. In particular, when an honest leader proposes a block of transactions, the first voting step happens in parallel with the block propagation. Effectively, after the block propagates, a certificate is generated in just one step of voting.
This white paper has been published here.

Oct 31, 2018

Algorand: Scaling Byzantine Agreements for Cryptocurrencies
By Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, Nickolai Zeldovich
Abstract: Algorand uses a new Byzantine Agreement (BA) protocol to reach consensus among users on the next set of transactions. To scale the consensus to many users, Algorand uses a novel mechanism based on Verifiable Random Functions that allows users to privately check whether they are selected to participate in the BA to agree on the next set of transactions, and to include a proof of their selection in their network messages. In Algorand’s BA protocol, users do not keep any private state except for their private keys, which allows Algorand to replace participants immediately after they send a message. This mitigates targeted attacks on chosen participants after their identity is revealed.
We implement Algorand and evaluate its performance on 1,000 EC2 virtual machines, simulating up to 500,000 users. Experimental results show that Algorand confirms transactions in under a minute, achieves 125x Bitcoin’s throughput, and incurs almost no penalty for scaling to more users.
This whitepaper has been peer edited and reviewed and is published here.
May 26, 2017

Algorand Theoretical Paper
By Jing Chen, Silvio Micali

Abstract: A public ledger is a tamper proof sequence of data that can be read and augmented by everyone. Public ledgers have innumerable and compelling uses. They can secure, in plain sight, all kinds of transactions —such as titles, sales, and payments— in the exact order in which they occur. Public ledgers not only curb corruption, but also enable very sophisticated applications —such as cryptocurrencies and smart contracts. They stand to revolutionize the way a democratic society operates. As currently implemented, however, they scale poorly and cannot achieve their potential. Algorand is a truly democratic and efficient way to implement a public ledger. Unlike prior implementations based on proof of work, it requires a negligible amount of computation, and generates a transaction history that will not “fork” with overwhelmingly high probability.
This whitepaper has been peer edited and reviewed and is published here.
About UsTeamSilvio MicaliNewsCareersCommitment to TransparencyBrand Usage & Media Kit
Financial PrimitivesCore ProtocolResearchWhite PapersAlgorand WalletFAQs