This post takes note of key ideas in Algorand documents.

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. Algorand is based on (a novel and super fast) message-passing Byzantine agreement. For concreteness, we shall describe Algorand only as a money platform.

Algorand, because we use algorithmic randomness to select, based on the ledger constructed so far, a set of verifiers who are in charge of constructing the next block of valid transactions. Naturally, we ensure that such selections are provably immune from manipulations and unpredictable until the last minute, but also that they ultimately are universally clear.

One notable property of Algorand is that its transaction history may fork only with very small probability (e.g., one in a trillion, that is, or even 10^−18).

Bitcoin’s Assumption and Technical Problems:

Assumption: Honest Majority of Computational Power

Bitcoin assumes that no malicious entity (nor a coalition of coordinated malicious entities) controls the majority of the computational power devoted to block generation. Such an entity, in fact, would be able to modify the blockchain, and thus re-write the payment history.

Technical Problem 1: Computational Waste

Bitcoin’s proof-of-work approach to block generation requires an extraordinary amount of computation. This amount of computation would greatly increase, should significantly more users join the system.

Technical Problem 2: Concentration of Power

For computing a new block with an ordinary computer, the expected cost of the necessary electricity to power the computation exceeds the expected reward. Only using pools of specially built computers (that do nothing other than “mine new blocks”), one might expect to make a profit by generating new blocks. Accordingly, today there are, de facto, two disjoint classes of users: ordinary users, who only make payments, and specialized mining pools, that only search for new blocks.

Technical Problem 3: Ambiguity

Its latest portion often forks. Only after several blocks have been added to the chain, can one be reasonably sure that the first k + 3 blocks will be the same for all users. Thus, one cannot rely right away on the payments contained in the last block of the chain. It is more prudent to wait and see whether the block becomes sufficiently deep in the blockchain and thus sufficiently stable.

Algorand’s Property

Setting

• Algorand works efficiently and securely even in a totally permissionless environment, where arbitrarily many users are allowed to join the system at any time, without any vetting or permission of any kind. Of course, Algorand works even better in a permissioned environment.
• Algorand withstands a very powerful Adversary, who can
  1. instantaneously corrupt any user he wants, at any time he wants, provided that, in a permissionless environment, 2/3 of the money in the system belongs to honest user. (In a permissioned environment, irrespective of money, it suffices that 2/3 of the users are honest.)
  2. totally control and perfectly coordinate all corrupted users
  3. schedule the delivery of all messages, provided that each message m sent by a honest user reaches 95% of the honest users within a time λ_m, which solely depends on the size of m.

Main Properties

• The amount of computation required is minimal. Essentially, no matter how many users are present in the system, each of fifteen hundred users must perform at most a few seconds of computation.
• A New Block is Generated in less than 10 minutes, and will de facto never leave the blockchain. In Algorand the limiting factor in block generation is network speed. In addition, Algorand’s blockchain may fork only with negligible probability (i.e., less than one in a trillion), and thus users can relay on the payments contained in a new block as soon as the block appears.
• All power resides with the users themselves. There are no exogenous entities (as the “miners” in Bitcoin), who can control which transactions are recognized.

Algorand’s Techniques

1. A New and Fast Byzantine Agreement Protocol. Algorand generates a new block via a new cryptographic, message-passing, binary Byzantine agreement (BA) protocol, BA⋆. Roughly said, its binary-input version consists of a 3-step loop, in which a player i sends a single message m_i to all other players. Executed in a complete and synchronous network, with more than 2/3 of the players being honest, with probability > 1/3, after each loop the protocol ends in agreement.

2. Cryptographic Sortition. Algorand chooses the players of BA⋆ to be a much smaller subset of the set of all users. To avoid a different kind of concentration-of-power problem, each new block will be constructed and agreed upon, via a new execution of BA⋆, by a separate set of selected verifiers. Sortition is the practice of selecting officials at random from a large set of eligible individuals. In essence, we use a cryptographic function to automatically determine, from the previous block, a user, the leader, in charge of proposing the new block, and the verifier set, in charge to reach agreement on the block proposed by the leader.

3. The Quantity (Seed). We use the the last block in the blockchain in order to automatically determine the next verifier set and leader in charge of constructing the new block. The challenge with this approach is that, by just choosing a slightly different payment in the previous round, our powerful Adversary gains a tremendous control over the next leader. Even if he only controlled only 1/1000 of the players/money in the system, he could ensure that all leaders are malicious. To meet this challenge, we purposely construct, and continually update, a separate and carefully defined quantity, which provably is, not only unpredictable, but also not influentiable, by our powerful Adversary.

4. Secret Crytographic Sortition and Secret Credentials. Leaders and verifiers secretly learn of their role, but can compute a proper credential, capable of proving to everyone that indeed have that role. When a user privately realizes that he is the leader for the next block, first he secretly assembles his own proposed new block, and then disseminates it (so that can be certified) together with his own credential. This way, though the Adversary will immediately realize who the leader of the next block is, and although he can corrupt him right away, it will be too late for the Adversary to influence the choice of a new block.

5. Player Replaceability. Being in charge of certifying the new block with sufficiently many signatures, they must first run Byzantine agreement on the block proposed by the leader. During this processing time, powerful Adversary, although unable to corrupt 1/3 of all the users, can certainly corrupt all members of verfiers. The protocol correctly and efficiently reaches consensus even if each of its step is executed by a totally new, and randomly and independently selected, set of players. Thus, with millions of users, each small set of players associated to a step of BA⋆ most probably has empty intersection with the next set.

Achieve Consensus

1. Block Proposal: Accounts propose new blocks to the network
2. Soft Vote: Committee votes on proposals and filters down to one
3. Certify Vote: Separate committee votes to certify the block
4. Each node receives a certificate for the block and writes it to the ledger
5. New round is initiated and process starts over with new block proposers and voters

In Algorand, the power is in the hands of the users holding stake. Every user receives an amount of rewards proportional to their stake for every block that is committed to the chain. We do so to encourage users to join the Algorand platform and accelerate our path to decentralization.

Protocol Evolution

Algorand is rooted in the idea that the system should allow for changes and avoid inflexible policies—enabling both the community and the protocol to evolve.

1. Proposed changes are posted on the blockchain
2. The community uses Algorand’s consensus protocol to vote to accept or reject the change
3. When accepted, the community agrees on the block where the change happens
4. Everyone switches to the new protocol at the same time

Rekeying Feature

Public Address and Private Spending Key combos are used to protect accounts in blockchain. Public Address are publicly known and used for identification of an account, where Private Spending Keys are for security purposes and used for authentication and encryption of the Public Address. When a compromised Private Spending Keys needs to be changed, an entirely new account with Public Address and Private Spending Key need to be opened - and assets within that account have to be moved from the old Public Address to a new address representing a new account creating inefficiency and onerous operational overhead.

Rekeying, a feature of Algorand, solves for the existing Public Address and Private Spending key friction by allowing users to change their Private Spending key without the need to change their Public Address.