Hi @pierrechevalier83 @digipl @anon86652309 and others,
Hi 
The "Signature-Free Asynchronous Byzantine Consensus with t<n/3 and O(n^2) " paper by Achour Mostefaoui, Moumen Hamouna, Michel Raynal , which RFC 49 refers to as the “ABA” paper, appears to be unclear in its own right.
I don’t blame you for thinking so. It took me a number of reads to fully understand it. I also had the benefit of being able to brainstorm things with @AndreasF which helped a lot to figure out the subtleties. Only from the abstract, though, I knew it was worth the effort because they claimed to achieve asynchronous binary consensus in O(n^2) communications with optimal byzantine resilience (t < n/3) with a broadcast model which is pretty awesome 
Note: I’m going to be using some jargon. My aim is to use as plain english as possible to help make these things as clear as possible; but jargon helps to concisely describe things sometimes, like in the paragraph above. If the jargon is unclear, feel free to ignore it and come back to it with more context later. It takes a lot of reading various papers etc. to get properly familiar with the recurring themes of consensus and being able to identify the concepts that may help you just from reading an abstract
Since Parsec’s consensus is a derivation or expansion about ABA, let’s discuss the ABA paper here in its own right.
Let’s, indeed 
First unclarity: Section 3.1 page 4: “The content of a message m is 0 or 1 (hence the term “binary-value” in the name of this communication abstraction).”
The ABA discusses at any point how you are supposed to map a general consensus question to a yes-no question.
The reason they don’t spend a lot of energy to explain this is because that is not the objective of their paper. They are focused on one task: creating a good binary consensus mechanism. They are assuming that the reader is familiar with the field and will be able to sift through the literature for ways to get from there to a general consensus if they need to (which by the way is not as simple as they imply it; but PARSEC is an example of how you can generalise from binary consensus to general consensus ← I digress: that’s a topic for a different thread).
To convince you that this is not their goal, re-read the section about content of the paper, page 3:
[…] This value-oriented broadcast abstraction is then used to solve asynchronous Byzantine binary consensus is asynchronous systems enriched with a common coin.
Parsec goes on with also not discussing this whatsoever ever, which amplifies the unclarity.
I beg to differ. The entire aim of PARSEC is to explain how to go obtain general consensus by building on the concepts in ABA. I get that it is pretty hard to read without a lot of established knowledge, so I understand your confusion and will do my best to help you wrap your brain around it (probably in another thread as we’re discussing ABA here)
Let’s discuss how to yes-no answer at the level of the ABA paper:
Is Mostefaoui’s idea that the ABA algorithm is used in a place where the parties have already AGREED to a question WHICH they are interested in answering and also agreed to the outcome options, in such a way that an 1-0 answer is possible ?
And then you could answer more complex questions for instance by running more consensus questions in a series, or running say THREE yes-no questions concurrenlty in order to get total FOUR options zero, one, two, three?
Mostefaoui et al. are simply trying to solve binary consensus which they assume the reader is already familiar with. It’s not really about any practical application in particular: it’s more a building block that could be fitted in various applications.
Here is an explanation of the binary consensus problem in plain english:
N participants want to reach agreement on a binary value (yes or no). The context is irrelevant to this problem. That’s up to users of the protocol to find a use case for it.
t participants are byzantine (i.e malicious) and trying to subvert the process. They may collude. They may vote for any value in a dishonest fashion.
The honest participants will only ever vote for “correct” values. In the same round, the true and the false value may both be correct (in that they have been voted for by honest participants).
The malicious participants may vote for any value they want.
After running a binary consensus protocol, all participants must decide one binary value: either true or false, not both (ABA calls this one shot). That value must be correct (i.e, originally have been voted for by a honest participant. ABA calls this validity). That value must be common amongst all honest participants which decided it (ABA calls this agreement). The protocol must terminate in a finite number of rounds of communications (finality, aka as ABA calls it termination).
This is all of it. Any protocol that gives you these 4 properties is a binary byzantine consensus protocol. It’s an abstract maths problem, but it’s well defined. In the case of ABA, they give one solution to this problem. One that happens to be asynchronous and resilient to t < N/3 and some other properties, but this is the gist. There are other solutions (see some of the papers given as references) with other trade-offs and there are other ways to express the problems, but all ways to express the problem are mathematically equivalent (the solutions are not).
Second unclarity: Page 5, remarks below figure 1: “It is important to notice that no correct process pi can know when its set bin_valuesi has obtained its final value. (Otherwise,
consensus will be directly obtained by directing each process pi to deterministically extract the same value from bin_valuesi). This impossibility is due to the net effect of asynchrony and process failures [17].”
So, the author has just showed the basic binary value gossip algorithm in figure 1, and then he says, “oopsie you know what, just please remember that this is incomplete, you don’t actually know that finality was reached here”.
It’s not exactly a “oopsie”. It’s more: we’ve gone one part of the way, but be aware we need to do more work to solve the full scope of the problem.
I would like to bring your attention again to the “content of the paper” section:
The paper first introduces a simple broadcast abstraction suited to binary values, that we call BV-broadcast.
[…]
This value-oriented broadcast abstraction is then used to solve asynchronous Byzantine binary consensus is asynchronous systems enriched with a common coin.
So section 3.1 defines what a BV-Broadcast algorithm accomplishes, and section 3.2 gives you a specific BV-Broadcast algorithm. Now at the end of section 3.2, they give you some context to explain what’s missing between BV-Broadcast and Binary consensus.
Can you here on the forum please help clarify the parameters of WHAT was NOT final here.
Sure! From a specific node (or as they call it in this paper, process)'s point of view, there are 3 possible outcomes of the BV-Broadcast:
- A set of binary values containing only the true value.
- A set of binary values containing only the false value.
- A set of binary values containing both the true and the false value.
It the nodes were able to determine that BV-Broadcast was terminated (final) and the set wouldn’t get any more value at any time, this would be enough to get binary value consensus:
Here would be the steps:
- Perform BV-Broadcast until finality is reached
- If set contains only true, decide true
- If set contains only false, decide false
- If set contains both, decide true
The reason consensus isn’t that trivial is that you never know whether you’ve got all the binary values, so when you have the set that contains only false, you can never be sure that you won’t get a true value later. (Never ever, not after waiting for a specific number of communications or a specific amount of time because of the asynchronous property.)
My best direct interpretation is that one peer cannot know that OTHER peers reached finality, and that that’s the weakness.
It’s definitely about a node not being able to ensure that they themselves have reached finality. They could learn more information later that adds one value to their set of binary value and they are never sure that this won’t happen.
And then - while he does not say it here, you could get the idea from the subsequent section 4.1. that one lack with figure 1 is if you get… 50-50% voting situations, that’s why 4.1. comes to aid with the enhancement of a coin - actually exactly what’s the problem.
Hopefully, the two paragraphs above make this clear. Let me know if it still isn’t.
But maybe there’s more? In either case Raynal missed to clarify this here, this is too deep jargon.
I feel you man. There is a lot of jargon, and also every author kind of uses their own vocabulary so you need to take the time to really understand what every term means to make sense of the paper. It just takes a lot of patience, but you’ll get there
In other words, 3.2. is unclear about what it does not solve, kindly help clarify this, thereby bringing light to the rest of the paper.
See above.
Also the ABA paper does not have any slides, videos or example implementations online, given this degree of surrounding obscurity I am impressed that you guys found it in the first place.
That’s kind of how academic research is presented in general: you read a paper, you read all its references etc. Once you’ve done that a few times, you start to have covered the state of the art in this area of research. Also, by reading many papers in the same area, you get a feel for the jargon etc. so it becomes easier and easier to read the next paper. I read ABA from following a reference from the Honey-Badger BFT paper (which is a bit more widely advertised in the crypto space).
Third unclarity: Section 4.1, page 6: “From binary to multivalued Byzantine consensus Interestingly, asynchronous multivalued Byzantine consensus (i.e., when
more than two values can be proposed) can be solved on top of binary Byzantine consensus. Such constructions are described in [13, 30, 36] (see [39] for synchronous systems).”
The author makes the claim that ABA can be applied to voting for more than just yes/no to one single question, but does not detail and instead refers to some other papers. Those papers would take many days to try to decipher.
That’s what academics do: they take the days it takes to read the literature. If every paper tried to explain every aspect of the area of research, it would be very hard to understand what this new paper brings to the table. Here, they focus on binary consensus and tell you: if you want to know how to use this to do more than binary consensus, please refer to these other works.
How do you understand that the author intends ABA to be used for multivalue consensus?
It’s not really their area of focus, so they would indicate that you can use the references. I could dig in and read the 3 references they quote to try and give you a richer reply, but I won’t invest that time because I don’t think it’s core to the paper.
Also how does he likely define multivalue consensus in the first place?
I’m not sure, but I would assume it’s about picking a value from an unknown set (like PARSEC does) because if it’s simply to pick one of a finite number of values (as in one out of 10 or 10000), it would be trivial to do: Just encode each of the value in binary and reach binary consensus on each bit.
Fourth unclarity: In figure 2, is the colon a typo and should be a semicolon?
I think you’re right and it should be a semicolumn. In general, I found it really difficult when I read the pseudo-code to get what they meant (partly because they’re using a bit of a weird syntax) and it took me many hours of reading the pseudo-code and the text and trying it with pen and paper and making examples and debating it with some of my colleagues before I had a good grasp of what they meant.
In other words is line 5 a loop that involves line 5 only, or are lines 6-11 iterator code for the line 5 loop?
Definitely: line 5 is you wait until that condition (you receive supermajority of auziliary values). Then comes line 6: you flip a common coin. Lines 6-11 are not the content of a loop starting at line 5.
Fifth unclarity: Figure 2, what’s the point with the phases
It looks to me as follows:
- Lines 0 to 3: Broadcast your vote, and wait for SUPERMAJORITY FOR ANY VOTE (either 0 or 1).
Lines 0-3: BV-Broadcast and wait to get bin_values containing either {0}, {1} or {0, 1}.
Refer to section 3.1 for explanation of BV-Broadcast. At this time, you haven’t reached finality but you know that any value in the set of bin_values has been proposed by a honest node. You’ve filtered out estimates given by only malicious nodes.
- Lines 4 to 5: Rebroadcast the supermajority vote (0 or 1) that you received, to the others, too - the point with doing this is to ensure that others will reach consensus also ??
Line 4: rebroadcast the first value that made it to your bin_values. (you call it auxiliary value) Assuming your set of bin_values is {0, 1}, you’ve received a supermajority for both values so that wouldn’t be a
distinction.
Line 5: wait till you receive a supermajority of auxiliary values that are also present in your bin_values (filtering out byzantine auxiliary values)
- Lines 6 to 11: For the heck of it & irrationality, let’s flip the coin and… what?
Line 6: Very important detail that is unclear (imho) in the paper: line 6 is not just “flip a random coin”, it’s “flip a random common coin”. That’s a whole other protocol that takes some effort to understand, but what matters is that it’s random-ish looking, unpredictable and gives the same value for all participants.
Line 7: what they call values is the set of auxiliary values you received a supermajority of and that were present in your bin_values… Because you want to have seen a supermajority of auxiliary values and honest nodes only voted for one auxiliary value, this set is either the empty set, the set: {0} or the set: {1}. Unlike the set: bin_values, it can’t be the set {0, 1}. This set is not guarenteed to be common between all nodes, which is why we need to use the common coin.
Line 8: if the set is not empty, it must be empty (I received a supermajority of auxiliary values but there was no agreeing supermajority for 0 or for 1) or contain a single value (I received a concording supermajority of auxiliary values). If that’s the case, if that value matches the common coin, decide it.
If I received a supermajority that agrees and that doesn’t match the common coin, switch your estimate to that value and try again.
If the set of values is empty, pick the common coin as my next estimate and try again.
Sixth unclarity: decide(v) in Figure 2 means what
Also is the “v” variable in decide(v) the same as the vi propose() argument?
No. The v variable is the only variable contained in the set: values
Also the v comparison on line 7 tries to do what?
If the set values == {v} i.e: if the set of values has size 1 (as opposed to zero), and by the way let’s name its content v for the next couple of lines.
I guess this sums it up - the paper lacks context, and then leads up to a peak in Figure 2 with a sudden surprise end of the paper and not much was communicated.
I totally empathise: it takes a lot of effort to understand these papers, especially in the beginning when you aren’t familiar with the rest of the research in that field. Don’t feel bad about it being a hard process. It is so for everyone. My team and I spent months reading these papers before we understood them enough to formulate PARSEC.
If you can help clarify what the ABA paper is actually showing or proving, would be greatly appreciated, thanks!
I hope this help. I focused only on answering your questions. It leaves gaps, such as: how does this prove that binary consensus is reached. I will let you digest my answers. Maybe it will be enough for you to fill in the gaps with the ABA paper. If not, feel free to ask follow up questions (although I don’t promise I will have enough time for prompt answers, but I will try to help when I can).
I really hope these answers are good enough to clear most of your doubts, but if anything remains unclear, keep asking. Understanding ABA is definitely an achievable goal and I can see from the questions you’re asking that you aren’t too far from that goal. Once you understand ABA, understanding PARSEC adds a few layers; but let’s keep these discussions to other threads
