Byzantine Agreement

 Hi Folks !

Hope you are doing well ! 😉

This Blog is regarding Byzantine attack or means Byzantine agreement. 

What is Byzantine ?? 😬

A friend having capricious behavior is called byzantine. This can be your imagination also. 

Example: Not sending correct message to the fellow friends, sending no message to the fellow friends or lying about the input.

Note: Byzantine nature also includes collusion, i.e., all byzantine friends are controlled by the same adversary.

What is Byzantine Problem ??

Lets us consider through example. Suppose in a class of Algorithm there are 20 friends and they are planning for mass bunk but in 20 friends there are some fellow friends who are not planning for mass bunk. In this situation it is quite difficult to take decision. This Problem is called as a Byzantine Problem. 

This Problem is solvable if an only if atleast two third fellows friends are loyal. 

Can you solve Byzantine Problem with 3 friends ??

Answer is obvious No. But Why ???

Now consider a scenario, Out of 3 friends 1 of them is Class Representative (CR) and Other are normal students of the class say (F1, and F2).

Consider the following predefined assumptions: 

Condition A: All Fellow friends obey the same order.

Condition B: If the CR is Loyal, then every loyal fellow friend obeys the orders he sends.

A and B can be called as an interactive consistency conditions. Note that if the CR is loyal, then A follows from B. However, the CR need not be loyal.  

Case Study 1 :  

If we consider the Scenario where any one fellow friend is not loyal (as shown in Fig. 1) , will break the condition B. 


Fig. 1: F2 is not Loyal.

Case Study 2 : 

Consider a scenario where CR is not loyal (as shown in Fig. 2). 

CR sends Mass Bunk message to F1 but No Mass Bunk Message to F2. Now F2 sends No Mass Bunk message to F1. In that scenario, it is quite difficult to F1 to know about who is traitor, and he can not tell what actual message was sent by CR to F2. This situation breaks the condition A. 


Fig. 2: CR is not Loyal

So Both Case study 1 and 2 fails because it fails to achieve a > 2/3rd supermajority. 

As we saw in 3 friends it is quite difficult now we will increase the group size by 1 so we can say that total number of friends are 4. 

Now again consider two case study. 

Consider Mass Bunk as : Y, and No Mass Bunk as : N=M.

Case Study 3 : 

Since as shown in Figure 3, F3 is not loyal so he wants to confuse F2 by sending him as a wrong message but F2 receives the set of messages as : {Y,Y,N} so according to 2/3 rd majority, F2 concludes that the correct message is Y. 

So now according to this situation if teacher comes to the class then he finds mass bunk 😂.

So we can see that if one friend is not loyal then entire system can take place.


Fig. 3: F3 is not Loyal

Case Study 4: 

Folks, in this case CR is corrupt so each fellow student receives : {Y,Y,M}. Since this majority again wins so we can say that today is mass bunk.


Fig. 4: CR is not Loyal

In Both case study 3 and 4 we can say that the system will work if there is more than 3 friends which follows that atleast 2/3 rd friends should be loyal. 

Hope you enjoyed the Journey of Byzantine attack. 

Please Note your learning is not stops here. This is a very wide concept. It is recommended to visualize the concept and think the different different possible test cases. 

If still you have any Idea or Doubt then fill the comment section. 😛

Thanks to Author Roger Wattenhofer (The Science of the Blockchain).


*********************************************************************************************************

Comments

Post a Comment

Popular posts from this blog

Homomorphic Encryption: A Basic Idea

Image
Homomorphic encryption has the same aim as other encryption-decryption mechanisms: maintaining confidentiality, security, privacy, etc.  In this blog, we will see homomorphic encryption and its type.  Homomorphic Encryption (HE):  It is an encryption that computes operations over encrypted data without decrypting it (or without the need for a secret key).  Mathematically speaking in a client-server architecture: client has message 'm' and function f. The task of client is to compute f(m). Due to computational expensiveness (maybe one of the reason) client sends encryption of message (say Enc(m)) and 'f' to the server. Server will compute function over encrypted message, that is, f(Enc(m)), and return the result to the client, that is, Enc(f(m)). Client will decrypt it Dec(Enc(f(m)), that is, f(m). Hence, client achieves f(m).  Let's understand HE with our daily life (Tea making process): Figure 1. Here m is message, Enc is encryption, f is function, and Eval in...
Read more

Fast Base Conversion and Its Application

Image
Fast Base Conversion (FBC) is a technique used to convert a number from one modulus space to another. For example, if we have 14 m o d     77 14 \mod 77  and want to convert it to x m o d     390 x \mod 390 , FBC is widely used. Mathematically, it can be represented as follows: Here, the above equation represents an integer x x  in modulus q q , and FBC converts this integer into the modulus space t t . The modulus q q  is the product of small coprime moduli (i.e., q = q 1 q 2 … q k q = q_1 q_2 \dots q_k ​ ), and x x  is an integer such that x ∈ [ 0 , q ) x \in [0, q) . We also note that q q  and t t  are coprime numbers. Here, we remark that it is not necessary for the above equation to produce the exact result for x x . Instead of x m o d     t x \mod t , it will provide x ′ m o d     t x' \mod t . Thus, the output of the above equation is as follows: FBC ( x , q , t )  =  x  +  A q  mod  t , where A ∈ [ 0 , k − 1 ] A \in [0,...
Read more

Brakerski-Fan-Vercauteren (BFV) Homomorphic Encryption

Image
Homomorphic encryption means computation over encrypted data without secret key.  How this is possible  ?? 😴 In this blog, we will explore the types of Homomorphic Encryption and demonstrate how computations can be performed on encrypted data without the secret key. In 2009, Gentry proposed Fully Homomorphic Encryption. In 2012, Brakerski proposed a leveled homomorphic encryption scheme that works over integer arithmetic, which later became known as the BFV scheme. BFV is an encryption scheme. Thus, as an encryption scheme, it is expected to be secure. To date, under certain conditions, it is assumed that the scheme is safe, and its security is based on the Learning With Errors (LWE) assumption.. Learning-with-error (LWE): Given a pair of a, b and the task is to recover secret key (s), such that b = a.s  + e  Here e is error mostly picked from gaussian distribution, and a, s are selected from Rq (known as ring module R) The above problem is HARD. The proof is not si...
Read more