# Coalition Formation Game for Cost-Efficient Multiparty Payment Channel in Payment Channel Networks
## 4 Multiparty Payment Channel
### MPC Consensus Algorithm  
In contrast to the legacy PC, in which interest is a conflict between two users, the MPC needs a consensus algorithm as users can collude in their own interests against other participants. Majority-based consensus algorithms for the public blockchain are infeasible since securing more than 50% users in such a small group is easy. For the small-sized private blockchain, Byzantine Fault-Tolerant (BFT) protocols, such as Practical BFT (PBFT) [46; 47; 48], are popularly considered. However, this permission-based approach in which all users are admitted by a certificate authority is inapplicable for the MPC, which is a permissionless off-chain network, as with the legacy PC. The MPC consensus algorithm has to resolve the following two challenges: \begin{table}
\begin{tabular}{l l} \hline \hline
**Symbol** & **Description** \\ \hline \(\mathcal{I}\), \(l\) & A set of users and its size \\ \(\mathcal{L}\), \(L\) & A set of directional PCs and its size \\ \(ij\), (\(ij\)) & A directional PC from \(i\) to \(j\) \\ \(k_{i}^{p},k_{i}^{s}\) & A public key and private key of a user \(i\) \\ \(B_{t}(i,j)\) & A transaction block of a SPC \((i,j)\) at round \(t\) \\ \(A\) & Transaction amount \\ \(\mathcal{H}\) & Hashed transaction message \\ \(U\), \(u\) & A set of PBT flows and a PBT flow (s, d) \\ \(\mathcal{N},N\) & A set of MPC users and its size \\ \(\mathcal{V}\), \(V\) & A SPC set and its size \\ \(\mathcal{M}\) & A MPC state \\ \(x\) & PBT flow rate \\ \(D\) & Payment delay \\ \(p\) & A PBT path \\ \(C_{ij}\) & Initial channel \((i,j)\) deposit \\ \(T_{exp}\) & PBT time lock duration \\ \(\Delta\) & Transaction process and propagation delay \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Symbols of payment channel network model. State update of the MPC, from \(\mathcal{M}(t)\) to \(\mathcal{M}(t+1)\). * Transaction serialization in the local chain of the MPC. All users should form a consensus for the MPC state update by signing on a new transaction that changes the channel state. This consensus procedure requires heavy peer-to-peer communication that causes a considerable delay, especially with many MPC members, \(N\). A unique round count should be assigned to each transaction sequentially for serialization. Simultaneous payments fork the local chain with multiple transactions having the exact round count. Unfortunately, the MPC cannot resolve the dependency between concurrent transactions based on the majority. Therefore, we introduce a time-slotted sub-channel or sub-PC (SPC) concept for the MPC. At each time slot denoted by the round count \(t\), only two MPC users, called SPC users, can create a new transaction with the given round count. Figure 4 illustrates an example of the MPC with four users, \(\mathcal{N}=\{\) A, B, C, D \(\}\). Maximum \(N(N-1)/2\) bidirectional SPCs can exist in the MPC; each bidirectional SPC is denoted by \(v_{ij}=v_{ji}\) for \(ij\in\mathcal{V},\mathcal{V}\subseteq\mathcal{L}\). Each SPC has a time slot (i.e., round count) periodically, with the value of \(v_{ij}\in[0,V-1]\), as shown in Figure 4; a time slot \(t\) is assigned for a SPC \(v_{ij}\) if \(v_{ij}\equiv t\mod V\), where and \(t\in\mathbb{Z}^{+}\). For example, in the figure, payments in the SPC \(v_{BD}\) will be conducted only at the time slot \(t_{v_{BD}}=\{1,7,13,19,...\}\). The duration of each time slot varies with the state update delay from message propagation between SPCs. Once the users of an SPC receive a local chain from anyone of a previous SPC, they must verify the blocks in terms of balance and a round count signed by the previous SPC users to update the MPC state. After this, they add a new block for their transaction to the local chain and send it to the following SPC users. For example, users A and B exchange their BPs (e.g., A: 100, B: 70), including the round count \(t=0\), which are signed by their private keys at \(v_{AB}\), which leads to the update of the MPC state as \(\mathcal{M}(t=0)\).