Algorand Consensus Protocol

(developer.algorand.org)

63 points | by nemoniac 8 days ago

6 comments

  • vessenes 7 days ago

    Written as someone who knows a reasonable amount about crypto system design, I would like this page to be written with a fixed audience in mind. It’s frustrating to read because it is at once ‘high level’ with cute diagrams, and then technical (“private key plus data into VRF gives a lottery”).

    At any rate, it would be nice to see something written for a more technical user that’s not just a formal spec (although that would be okay, too.)

    One salient question I have is: during the account choosing phase in which the VRF is applied to each account held in a given wallet, what is the precise mechanism by which some accounts are chosen? Is it a difficulty mechanism, where the VRF(account, some blockheader data) must be less than a given number? If so, how and why does the number change?

    • josh2600 7 days ago

      I mean you can just read Silvio’s paper: https://arxiv.org/abs/1607.01341

      My understanding on how the accounts are chosen is that they have a global list of users that have opted in to validate and they pick one person at random to create the block and then 1000 people at random to validate it. If you get 501 validations back, then you have a block.

      The attack I always thought about but never got an answer to was: what if you pay for the lottery winners to collude? Certainly if you offer some amount of money for the block producers only on the condition that you get 501+the block creator in a given block you could probably sign a bad block, right? It’s unclear what the consequences of that would be if the block’s signatures still have to be valid but you could maybe craft something bad.

      I don’t know, all of this thinking is from when I first talked to Silvio at IACR so it’s been a long time. It’s possible all of my knowledge is way out of date or wrong.

      Anyways, I wish them luck, they’ve certainly got a big thing going.

      • brianolson 4 days ago

        The sortition process isn't quite like centrally listing everyone and picking from the list. The Verifiable Random Function (VRF) allows you to know "I was picked!" and create a short quickly verifiable certificate to prove that to someone else. Is a distributed fashion all the nodes run their own check to see if it's their turn to propose or verify and then take network actions based on that.

        Algorand allows more than one node to propose a block to make sure that >=1 nodes propose a block with high reliability. The distributed consensus process picks one block to be the block.

        The number of validators is more like 30-50 but that's a global tunable depending on what kind of system properties you want. Fewer can be faster and more can be more secure, but there's diminishing returns and 30-50 is so far secure-enough and quite fast (5 second round times on the current global network).

        • forgotmypw17 4 days ago

          I saw Jing Chen present in SF, and address this question.

          It is very difficult to buy votes on the network because you don't know who the next voter will be.

          If I understand correctly, the voter is chosen based on pseudo-random hash prefix?

          • vessenes 6 days ago

            Generally Bitcoin has solved this by social and denominative means — definitionally if a majority of miners sign a stream of blocks that ‘break the rules’ then, that is the truth and the miners have chosen new rules.

            Socially if this is signing a block with a bug, miners have historically colluded to rewrite history.

            If on the other hand the new blocks embed protocol changes, then we move to names: is it still ‘Bitcoin’? If not then there is a hard fork with a new community. This is the BCH, BSV and ETC story.

            The answer to your question about Algorand is probably similar, unless the scheme has some novel mechanism to prune hard forks, or a way to radically include them.

            • quantum_state 7 days ago

              I am very curious to know about this as well ... hope someone in the know would provide some clue ... :-)

          • aeternum 7 days ago

            This does not address the bootstrapping problem. Without some existing peer or root to trust, how do I know which is the real Algorand blockchain?

            Some other group could follow this exact protocol and also call their blockchain Algorand.

            • tromp 7 days ago

              Just as with Bitcoin, you have to know the genesis block.

              Which is generally hardcoded in the client you run. So in that sense you trust the binaries you download, or the source code that you compile. The advantage of PoW consensus is that it's much easier to tell the real chain from a fake one, as the latter will not have much more work performed on it.

              Even with the genesis block fixed, control of the initial keys embedded in it allows you to generate arbitrary alternative blockchain histories that without PoW are difficult to distinguish from the "real" one.

              • aeternum 7 days ago

                With a PoW blockchain you do not need to trust the genesis block. You can calculate the total amount of work represented by any blockchain which provides an independent measure of trust. Total proof of work can be calculated with just a copy of the blockchain data without trusting the software client. Nothing like that exists with proof-of-stake.

                If the assumption is that downloaded binaries must be trusted, one could simply use a key embedded inside that binary to verify the identity of a centralized database. No need for proof-of-stake.

                • lostmsu 5 days ago

                  The statement about trusted binaries is incorrect. Having a key to a central database in no way guarantees the data in it has not been tampered with.

            • mmahut 7 days ago

              I really like Algorand, too bad for all the patents surrounding the protocol, it could have been the next standard.

              • einarvollset 8 days ago

                Nice to see applied to a different domain, but this is a reasonably standard randomized Byzantine fault tolerant consensus protocol, or? Nothing wrong with that of course, just curious why it was deemed newsworthy.

                • AlexCoventry 8 days ago

                  Which prior protocol does it seem most similar to, to you?

                  • brynb 8 days ago

                    Oh, hey there, Coventry :) I’d be curious to know the same, as well as to hear a comparison between Algorand and: 1) recent work on aBFT protocols, many of which don’t seem to require any kind of staking, and... 2) Chainlink’s off-chain aggregation protocol’s consensys mechanism

                • ncmncm 7 days ago

                  Is this the first example of a blockchain-related algorithm that is of actual, practical use?

                  • exdsq 7 days ago

                    I assume, if this algorithm is of actual use to you, the algorithm used by Cardano and Tezos are also of actual practical use. These are my three favourite projects (including Algorand). I am particularly biased though as I work on Cardano.

                    • josh2600 7 days ago

                      Does cardano do on-chain governance? On-chain governance scares me.