> For the complete documentation index, see [llms.txt](https://cvnnt.gitbook.io/documentation/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cvnnt.gitbook.io/documentation/algorithms-and-cryptography/eigentrust++.md). # EigenTrust++ ### EigenTrust++ algorithm description EigenTrust++ algorithm general logic flow described below. #### Attack resilient local trust value computation Each node starts with a set $$P$$ of verifiably reputable nodes that are supplied in a configuration file and can be edited by the user to their own needs. The node then asks the nodes in $$P$$ set for other existing nodes in the distributed system. Knowing about $$n$$ nodes in the system each node can build an initial trust vector $$\vec{p}$$ by setting: $$p\_j=\begin{cases}\dfrac{1}{|P|}\text{, if }j\in P\0 \text{, otherwise}\end{cases}$$ , $$p\_j$$ indicates how much trust a node initially has in node $$j$$. The node periodically updates its local trust values by calculating transaction-based local trust formula using the total number of transactions as the denominator: $$s\_{ij}=\begin{cases}\dfrac{sat(i,j)}{sat(i,j)-unsat(i,j)}\text{, if }sat(i,j)-unsat(i,j)>0\ 0\text{, otherwise}\end{cases}$$ , where the number of satisfactory interactions from node $$i$$ to node $$j$$ is denoted by $$sat(i,j)$$ and the number of unsatisfactory interactions is denoted by $$unsat(i,j)$$. To facilitate the comparison among different local trust values, the local trust values is also normalized to define the local trust vector $$\vec{c\_i}$$ with components $$c\_{ij}$$: $$c\_{ij}=\begin{cases}\dfrac{max(s\_{ij},0)}{\displaystyle\sum\_{m}max(s\_{im},0)}\text{, if }\displaystyle\sum\_{m}max(s\_{im},0)\neq0\p\_j\text{, otherwise}\end{cases}$$\ ,where $$p\_j$$ represents the set of pre-trusted peers $$P$$ , $$p\_j=\dfrac{1}{|P|}$$ if $$j\in P$$ and $$p\_j=0$$ otherwise. #### **Local trust value aggregation using feedback credibility** A feedback vector of size $$N$$ is assigned for each peer, where $$N$$ is the total number of participants of the distributed system. The feedback similarity between between two vectors (peers) $$u$$ and $$v$$ is computed using the standard deviation-based method: $$sim(u,v)=1-\sqrt{\dfrac{\displaystyle\sum\_{w\in b(u,v)}(tr(u,w)-tr(v,w))^2}{|b(u,v)|}}$$ $$tr(u,w)={\displaystyle\sum\_{i=1}^{|R(u,w)|}\dfrac{tr(u,w)}{|R(u,w)|}}$$ $$tr(v,w)={\displaystyle\sum\_{i=1}^{|R(v,w)|}\dfrac{tr(v,w)}{|R(v,w)|}}$$ , where $$b(u, v)$$ denotes the subset of the nodes that have had interaction with both node $$u$$ and node $$v$$, $$R(u, w)$$ is the number of transactions between node $$u$$ and node $$w$$. Based on the feedback similarity, the feedback credibility $$f\_{ij}$$ is calculated: $$f\_{ij}=\dfrac{sim(i,j)}{\displaystyle\sum\_{m=1}^{R(i)}{sim(i,m)}}$$ , where $$R(i)$$ is a set of the nodes that have had transactions with peer $$i$$. The $$fc\_{(ij)}$$ , feedback credibility that peer $$i$$ places on peer $$j$$, is calculated as follows: $$fc\_{(ij)}=f\_{ij}\cdot c\_{ij}$$ , and is then normalized: $$l\_{ij}=\begin{cases}\dfrac{max(fc\_{ij},0)}{\displaystyle\sum\_{m=1}^{R(i)}max(fc\_{im},0)}\text{, if }\displaystyle\sum\_{m=1}^{R(i)}max(fc\_{im},0)\neq0\0\text{, otherwise}\end{cases}$$
The initial trust $$t\_{ij}$$, that peer $$i$$ place on peer $$j$$, by the local trust values received by peer $$j$$ from other peer $$k$$, weighted by the feedback credibility peer $$i$$ places on peer $$k$$: $$t\_{ij}=\displaystyle\sum\_{k}{l\_{ik}c\_{kj}}$$ With iterative computation of global reputation, the iteration $$(k+1)$$ is computed using the trust values computed at round $$k$$ using formula with proportion factor $$\alpha$$ to restrain the positive ratings from malicious peers via similarity-based feedback credibility: $$t\_i^{(k+1)}=(1-\alpha)(l\_{1i}\sdot t\_1^{(k)}+l\_{2i}\sdot t\_2^{(k)}+\ldots+l\_{ni}\sdot t\_n^{(k)})+\alpha p\_i$$ #### Probabilistic trust propagation through circle of friends **Combination of local trust and feedback similarity** Each edge between two peers has two weights: local trust and feedback similarity. Node' acquaintance nodes become inactive in terms of trust propagation if they have not enough local trust rating and/or a low similarity with the active nodes. Only the active nodes are regarded as the circle of node' friends to propagate for a node, which also means to cut off the trust propagation path to inactive nodes. As an edge weight for trust propagation between two peers, a weighted combination of local trust and feedback similarity is used: $$w( i,j)=(1 - \beta)\times c\_{ji}+\beta\times sim(j,i)$$ , where $$\beta$$ is proportion factor used to balance the two factors, with $$\beta$$ probability using feedback similarity and $$1-\beta$$ probability using local trust between two peers that have direct transactions (e.g. $$\beta = 0.85$$). **Threshold-based probabilistic trust propagation** The edge weight is subjected to: $$\displaystyle\sum\_{u\in V}w(u,v)\leq1$$ , where $$V$$ denotes the set of participating vertices (nodes), $$w( u, v)$$ denotes the weight on the edge of $$(u, v)$$. With an initial active node seed set $$S\subseteq V$$, the other nodes that are not in this set would be regarded as inactive. Each node has a threshold $$\theta \leq1$$, representing the weighted fraction of $$v$$'s neighbour nodes that must become active in order for $$v$$ to become active. Then, the propagation process unfolds deterministically. At step $$i$$ all $$v$$'s active neighbours at least $$\theta\_v$$ activated: $$\displaystyle\sum\_{u\in AN\_{(v)}}w(u,v)\leq\theta\_v$$ , where $$AN\_{(v)}$$ denotes the set of active neighbours of node $$v$$. **Local trust aggregation** The local trust ratings are aggregated by nodes asking their acquaintance nodes about other peers in the system. E.g., peer $$i$$ should ask its friends, its friends' friends, and then propagate trust among these nodes: $$\vec{t\_i}=(C^T)^2\vec{c\_i}$$ , where $$C$$ is a matrix $$\begin{bmatrix}c\_{ij}\end{bmatrix}$$, $$\vec t\_i$$ represents trust values for the node $$i$$. The relationship of trust propagation over the network can be expressed via the $$C$$, and $$AC$$ the activation matrix of weight: $$AC=\begin{bmatrix}a\_1^1\cdot c\_{11}& a\_2^1\cdot c\_{12}&\ldots\&a\_n^1\cdot c\_{1n}\\\[6pt]a\_1^2\cdot c\_{21}\&a\_2^2\cdot c\_{22}&\ldots\&a\_n^2\cdot c\_{2n}\\\[6pt]\vdots\hspace{1em}&\ddots\hspace{-2.em}&&\vdots\\\[6pt]a\_1^n\cdot c\_{n1}\&a\_2^n\cdot c\_{n2}&\ldots\&a\_n^n\cdot c\_{nn}\\\end{bmatrix}$$ $$a\_j^i =\begin{cases}1\text{, if }i\text{ makes }j\text{ active}\0,\text{otherwise}\end{cases}$$ $$AC$$ is normalized: $$ac\_{ij}=\begin{cases}\dfrac{a\_j^i\cdot c\_{ij}}{\displaystyle\sum\_{m}a\_m^i\cdot c\_{im},}\text{, if }a\_m^i\cdot c\_{im}\neq0\0\text{, otherwise}\end{cases}$$ The trust vector $$\vec{t\_i}$$ is: $$\vec{t\_i}=(AT^T)^{(n)}\cdot\vec{ac\_i}$$ To balance the direct and indirect trust during iterative computation, proportion factor $$\gamma$$ is applied: $$t\_{ik}^{(k+1)}=(1-\gamma)(ac\_{i1}^{(1k)}\sdot ac\_{1k}+ac\_{i2}^{(2k)}\sdot ac\_{1k}+\ldots+ac\_{in}^{(k)}\sdot ac\_{nk})+\gamma ac\_{ik}$$