# A Scalable and Trust-Value-Based Consensus Algorithm for Internet of Vehicles
## 5 Theoretical Analysis
### Honest Majority of the Committee  
**Lemma 1**: _Among the elected members, more than half of the nodes are honest, except for the negligible probability \(\delta(m)\)._  
Proof.: In the worst case, all nodes have a reputation value of 1. The committee election can be viewed as an independent random sampling problem, and the probability that node \(p_{i}\) is elected to the committee is  
\[\Pr[p_{i}\text{ is elected }]=\frac{m\mu_{j}}{\sum_{i=1}^{n}\mu_{i}}=\frac{m}{n} \tag{12}\]where \(m\) is the committee size, \(k\) is the node number, and \(\mu_{j}\) is the reputation value of each node \(p_{i}\).  
Suppose that the probability that the node representing the election is an honest node and the probability that the node representing the election is a Byzantine node, the random variable \(A\) represents the number of honest nodes in the committee, and the random variable \(B\) represents the number of Byzantine nodes in the committee. The random variables \(A\) and \(B\) satisfy the following binomial distribution:  
\[\Pr[A=k] =\left(\begin{array}{c}n\\ k\end{array}\right)\Big{(}\alpha\frac{m}{n}\Big{)}^{k}\Big{(}1-\alpha\frac{m}{ n}\Big{)}^{n-k} \tag{13}\] \[\Pr[B=k] =\left(\begin{array}{c}n\\ k\end{array}\right)\Big{(}\beta\frac{m}{n}\Big{)}^{k}\Big{(}1-\beta\frac{m}{ n}\Big{)}^{n-k} \tag{14}\]  
Let \(X\) and \(Y\) be denoted as  
\[X=\Big{\{}A:0\leq A\leq\Big{\lfloor}\frac{m}{3}\Big{\rfloor}\Big{\}} \tag{15}\]  
\[Y=\Big{\{}B:\Big{\lceil}\frac{m}{3}\Big{\rceil}\leq B\leq n\Big{\}} \tag{16}\]  
When neither \(X\) nor \(Y\) holds, the nature of the honest majority of the committee holds. \(\Pr[X\cup Y]\) represents the probability that at least one of \(X\) and \(Y\) holds:  
\[\Pr[X\cup Y] =\Pr[X]+\Pr[Y]-\Pr[X\cap Y] \tag{17}\] \[\leq\Pr[X]+\Pr[Y]\] \[=\Pr\Big{[}A\leq\Big{\lfloor}\frac{m}{3}\Big{\rfloor}\Big{]}+ \Pr\Big{[}B\geq\Big{\lceil}\frac{m}{3}\Big{\rceil}\Big{]}\] \[=F\Big{(}\Big{\lfloor}\frac{m}{3}\Big{\rfloor},n,\alpha\frac{m} {n}\Big{)}+F\Big{(}n-\Big{\lceil}\frac{m}{3}\Big{\rceil},n,1-\beta\frac{m}{ n}\Big{)}\]  
where \(F(k,n,p)=\Pr[X\leq k]\) is the cumulative distribution function (CDF) of the random variable \(X\sim B(n,p)\). Note: \(\Pr[X\geq k]=F(n-k,n,1-p)\). By the Binomial Tail Inequality [28], it follows that:  
\[F(\big{\lfloor}\frac{m}{3}\big{\rfloor},n,\alpha\frac{m}{n})+F(n -\big{\lceil}\frac{m}{3}\big{\rceil},n,1-\beta\frac{m}{n}) \tag{18}\] \[\leq\exp\left(-2n\Big{(}\alpha\frac{m}{n}-\big{\lfloor}\frac{m}{ 3}\big{\rceil}\Big{)}^{2}\right)+\exp\left(-2n\Big{(}(1-\beta\frac{m}{n})- \frac{n-\big{\lceil}\frac{m}{3}\big{\rceil}}{n}\Big{)}^{2}\right)\] \[=2\exp(-2n\Big{(}\big{\lfloor}\frac{m}{3}\big{\rfloor}-\beta m \Big{)}^{2})=\delta(m)\]  
where \(n\) and \(\beta\) are constants. Thus, in the worst case, except for the negligible probability, the committee honest nodes will be in the majority.  
Under normal conditions, the reputation values of all honest nodes and a few Byzantine nodes are close to 1, while the reputation values of the remaining Byzantine nodes are smaller than the reputation values of honest nodes. This indicates that the reputation value of a node basically correctly reflects the probability of a node being an honest node. According to the probability of each node being elected to the committee as \(\frac{m\mu_{j}}{\sum_{l=1}^{n}i_{l}}\), it is clear that nodes with higher credibility are more honest and more likely to become committee members. Therefore, there are  
\[\Pr[\text{ Dishonestmajority }]_{\text{Normal-case}}<\Pr[\text{ Dishonestmajority }]_{\text{Worst-case}}=\delta(m) \tag{19}\]  
It shows that, in the process of election committee, the probability of honest majority is higher in normal circumstances than in the worst case.