Questions about the consensus mechanism

General
1

Hi! I’m a developer from Argentina, currently working on a simulator for the Algorand protocol. I have some questions about the underlying consensus mechanism.

1-I read in the 2017 SOSP paper that in the BinaryBA* step there’s a “common coin” solution, implemented to prevent a very specific kind of attack scenario.
However, I have not seen anything referring to this in the specs nor in the node go code. Is it not a thing anymore?

2-Suppose that a node observes a proposal, soft votes and certifies it, but it has for some reason not received the full block up to that point (only the block hash).
What happens then? What if the rest of nodes in the network have received it, voted to certify and commited it. How does this node manage to catch up?

3-In the proposal step (s=0), what is the exact value used to select a proposal over others? I’ve seen some contradicting information with regards to this.
Is it the VRF hash of the proposer, the hash of the block, or is it Min{H(ProposerVRF || 0…j)} (where j is the result of sortition for that account and H is
a cryptographic hash function -supposedly SHA512/256 according to specs-) as is described in the SOSP paper?

4-What specifically happens on the redo and down steps?. From what I understand, redo is a last attempt at certifying a given block, while down is an attempt at certifying an
empty block. Is that correct? If so, what happens if there is no quorum on a down step?

That would be all for now. I’m having a great time implementing a version of the protocol! I hope the sim I finally come up with turns out to be useful for the community as a whole :grin:
Thanks for your attention!

2

Answering below to the best of my knowledge:

I don’t believe it is used.
The protocol implemented is slightly different from the SOSP paper.

A node soft votes only after seeing the full block proposal, not just the hash.

The function is written here:

This is Min{H(ProposerVRF || 0…(j-1))} where j is the weight of the party in the sortition.

Late/redo/down are used for the fast recovery system.
From my understanding, if removed, you would still have a secure BA. The only difference is that if you have a x hours network partition, recovery would take x hours instead of being almost immediate.

1 Like
3

To complement the above response, if you want to see the specs of the protocol as implemented, the best place is GitHub - algorandfoundation/specs: Algorand Specifications (overview and then dev/abft).

The SOSP paper has several differences with the actually implemented protocol. In particular, it does allow for empty blocks and does not have a notion of period. The paper https://eprint.iacr.org/2018/377.pdf is closer to the implementation albeit it does not explain the sortition part.

You may also be interested in the formal proof from Formally Verifying Algorand: Reinforcing a Chain of Steel (Modeling and Safety) and https://arxiv.org/pdf/1907.05523.pdf (and the links therein, including a model in Coq where the sortition is abstracted away).

1 Like
4

Thanks for the reply! I had not seen any formal proof of the protocol itself, looks very interesting. Will be looking further into that as well.