Questions about the consensus mechanism

ArgimiroArgimiro del PozoFeb 6, 2023

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
Thanks for your attention!

✔ Solved by fabrice in post #2

fabriceFabrice BenhamoudaFeb 6, 2023

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:

github.com

algoradam/go-algorand/blob/db5c6d560eb89b15a7660878d0eb6cf31708270b/data/committee/credential.go#L160


      
          func (cred Credential) Equals(otherCred Credential) bool {
          	return cred.VrfOut == otherCred.VrfOut
          }
          
          // Selected returns whether this Credential was selected (i.e., if its weight is
          // greater than zero).
          func (cred Credential) Selected() bool {
          	return cred.Weight > 0
          }
          
          func (cred Credential) lowestOutput() *big.Int {
          	var lowest big.Int
          
          	h1 := cred.VrfOut
          	for i := uint64(0); i < cred.Weight; i++ {
          		var h crypto.Digest
          		if cred.DomainSeparationEnabled {
          			cred.Hashable.Iter = i
          			h = crypto.HashObj(cred.Hashable)
          		} else {
          			var h2 crypto.Digest

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.

fabriceFabrice BenhamoudaFeb 6, 2023

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).

ArgimiroArgimiro del PozoFeb 7, 2023

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.