wChain: A Fast Fault-Tolerant Blockchain Protocol for Multihop Wireless Networks
Minghui Xu, Chunchi Liu, Yifei Zou, Feng Zhao, Jiguo Yu, Xiuzhen Cheng
Abstract
This paper presents <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathit {wChain}$ </tex-math></inline-formula> , a blockchain protocol specifically designed for multihop wireless networks that deeply integrates wireless communication properties and blockchain technologies under the realistic SINR model. We adopt a hierarchical spanner as the communication backbone to address medium contention and achieve fast data aggregation within <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(\log N\log \Gamma)$ </tex-math></inline-formula> slots where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula> is the network size and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Gamma $ </tex-math></inline-formula> refers to the ratio of the maximum distance to the minimum distance between any two nodes. Besides, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathit {wChain}$ </tex-math></inline-formula> employs data aggregation and reaggregation as well as node recovery mechanisms to ensure efficiency, fault tolerance, persistence, and liveness. The worst-case runtime of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathit {wChain}$ </tex-math></inline-formula> is upper bounded by <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(f\log N\log \Gamma)$ </tex-math></inline-formula> , where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$f=\lfloor \frac {N}{2} \rfloor $ </tex-math></inline-formula> is the upper bound of the number of faulty nodes. To validate our design, we conduct both theoretical analysis and simulation studies. The results not only demonstrate the nice properties of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathit {wChain}$ </tex-math></inline-formula> , but also point to a large new space for the exploration of blockchain protocols in wireless networks.