A Secure Shard Reconfiguration Protocol for Sharding Blockchains Without a Randomness

In permissionless blockchains, due to the corruption attack of an adversary, nodes participating the protocol need to be updated regularly. In the process of node selection and committee reconfiguration, there may exist some problems. First, a complicated secure randomness generation protocol is in need. Besides, an adversary might obtain a mining puzzle in advance and start mining in ahead of honest nodes. Moreover, an adversary usually has an advantage of network delay. In order to solve the above problems, we conduct the following research. Firstly, we propose a PoW solution withhold attack against PoW-based member selection methods. An adversary might withhold his mining results in an epoch to obtain the mining puzzle of the next epoch in advance of honest nodes. Secondly, a secure shard reconfiguration protocol is designed, which does not rely on any complicated randomness generation protocol. Our shard reconfiguration protocol is proved rigorously to be secure, which means that in each selected committee, the honest node fraction exceeds a predefined target value. Thirdly, we implement our shard reconfiguration protocol. By carefully setting related system parameters, our protocol could be applied easily to most sharding blockchains. To our best knowledge, the shard reconfiguration protocol proposed in this paper is the first protocol that could safely implement node selection and committee reconfiguration of a sharding blockchain without using a secure randomness, which greatly reduces the communication and time overhead caused by the generation of a randomness.