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.
If let’s say there are 4 clients, one of which is malicious, called Trudy. Trudy has a significant stake in the system compared to the others. Now, during stages of committee selection, voting, and sortition, let’s say Trudy gets selected and generates a large number of winning tokens(because it had a large stake) and decides to vote for blocks that were not winning. Or vote for its own block. Since the total votes depend not on the number of clients, but on the total number of winning tokens in favour of the block hash, Trudy successfully tricks the system into achieving FINAL consensus on a wrong block.
Is this possible, however low the chances there may be?
I want to demonstrate byzantine behaviour and I started off with trying to achieve a fork but realised it is difficult to do that. I then realised tricking the network can also be a good byzantine demonstration. What do you think?
How does Algorand prevent against both - a fork and malicious activity by clients with huge stakes?
To ensure Trudy’s block is voted, Trudy would most likely need to have more seats in the certification committee than the threshold (what you call winning tokens). For that to happen with high probability, Trudy would need to have about 66% of the total online stake (this is very approximate - but you can do exact computation - this is probabilities). And yes, in that case, Trudy would be able to certify / mark FINAL any block of their choice, and can even fork the blockchain.
This is unavoidable in any consensus algorithm: if the attacker has 66% of the stake, then there is no way you can get a secure consensus.
Algorand is proven secure when only 20% online stake is held by malicious players.
I’ve heard a lot of good thing about the lectures by Tim Roughgarden: Foundations of Blockchains (Lecture 1.1: Focus of Lecture Series (+ a Little Hype)) - YouTube which would explain consensus amongst other blockchain things. In particular, see Foundations of Blockchains (Preview of Lectures 2--7: A Bootcamp on Classical Consensus) - YouTube
Perfect. I will check them out, thanks!
I have another scenario. This may be true about all blockchain networks but again I need confirmation on Algorand.
Suppose you have 3 clients - A, B, and C. Due to network partition, you get two groups. Group 1 has clients A and B and Group 2 has node C. We’ll assume 66% requirement is met. Now both these groups are working in isolation and publishing blocks - basically divergent from each others chain. Network resolves and they have connected again and now they realize they are stuck in a fork and resolve it - choose the longest chain or whatever the resolution thing is.
Is this possible? If yes, how does Algorand handle this?
If no, which states of the scenario are possible and which ones aren’t?
This scenario is impossible: if A and B have 66% of the stake, then C has only 34% << 66% of the stake.
So C will just be stuck and not be able to produce blocks nor see new blocks.
When the partition stops, C will just catch up.
You are right. But what I meant was, due to network partition you get 2 sets of nodes. Now due to the reduced voting power and inability to meet the threshold, they both publish blocks tentatively. When the connection reestablishes, they realize it’s a fork.
Is this scenario possible? I am assuming all other parameters as normal.
No, the Algorand protocol does not allow that.
There will be block proposals on both side.
But they will never gather enough cert votes to be finalized.
So there will be no block actually added to the block chain on either side.
Not even empty blocks?
Not even empty blocks.
Blocks without transactions are still blocks on Algorand.
They still need to be certified.