I am working on a research project and couldn’t understand specifically what the Binary BA* algorithm does. The code presented in the original paper doesn’t seem intuitive to me at least. Can someone explain all the steps that BA* does?
Welcome to Algorand!
The protocol implemented on Algorand slightly differs from the ones of the paper.
The recommended place to learn about the implemented protocol is GitHub - algorandfoundation/specs: Algorand Specifications (overview and dev/abft.md)
I understand that. But I am simply implementing the original paper on top of an existing PoW blockchain to demonstrate pure-PoS. Can I still get some help on things in the original design?
Please feel free to ask any specific question about the protocol.
Great!
So, the original paper describes consensus as TENTATIVE or FINAL.
- FINAL means for that user, BinaryBA* and counting the votes for the FINAL step returned the exact same block hash.
- TENTATIVE means for that user, BinaryBA* and counting the votes for the FINAL step returned different block hashes, maybe a TIMEOUT.
What does tentative mean in terms of blockchain progression? Does it mean it will get resolved later?
What if the tentative consensus is reached on a different block hash? Is that possible?
I’m guessing you’re talking about https://eprint.iacr.org/2017/454.pdf
The protocol described there is actually not the one implemented.
There is no notion of “tentative” / “final” blocks in the implemented protocol.
Instead, there is a notion of periods.
If there is no certification of a block at a period p of round r, then you go to period p+1.
You continue until you get a certified block.
My understanding is that a “tentative” block essentially matches a period with not certified block (but still a next-vote agreement or equivalent using names from GitHub - algorandfoundation/specs: Algorand Specifications).
From this definition, only “final” blocks (that are those that are certified) are actually added to the blockchain.
You go to the next period (of the same round r) as long as you don’t have a final block.
But I did not check in detail and this may not be 100% exact.
Is it possible for a user, let’s say A, to have certified a block whereas a user, B has not?
Does A move to the next round?
If A and/or others have moved on the consequent rounds, how and when does B catch up?
Algorand cannot fork even if the network is asynchronous.
That is, it is not possible that two nodes see two different certified blocks for the same period.
When the adversary controls the network (aka makes it asynchronous), the adversary can always ensure that some nodes do not see any messages and in particular do not see certified blocks.
This is unavoidable (in the CAP theorem terminology, Algorand is CP).
When a node sees a certified block, it goes to the next round.
It is always possible some nodes are left behind and will catch up when the network becomes synchronous.
Any node can catch up by downloading certified blocks (and verifying them).
You may wonder why in your example B may not fork.
This is because it is possible to prove you cannot have both a cert-quorum (that is certified block) for a period p and a next-quorum (that I’m guessing you would call a tentative block in the original paper) for the same period p and the same round r.
So if some nodes see a certified block, all the other nodes will essentially see no quorum and will essentially be stuck, even if the adversary has full control of the network.
When the network becomes synchronous, all nodes will see the certified block and catch up.