A Peered Bulletin Board for Robust Use in Verifiable Voting Systems
This provides a formally verified solution for election authorities needing reliable and attack-resistant bulletin boards in verifiable voting systems, though it is incremental as it builds on existing distributed algorithms.
The paper tackles the problem of ensuring robustness in verifiable voting systems by proposing a new peered Web Bulletin Board protocol, showing that a threshold of t > 2n/3 correct peers is sufficient for correct behavior even with temporary dropouts.
The Web Bulletin Board (WBB) is a key component of verifiable election systems. It is used in the context of election verification to publish evidence of voting and tallying that voters and officials can check, and where challenges can be launched in the event of malfeasance. In practice, the election authority has responsibility for implementing the web bulletin board correctly and reliably, and will wish to ensure that it behaves correctly even in the presence of failures and attacks. To ensure robustness, an implementation will typically use a number of peers to be able to provide a correct service even when some peers go down or behave dishonestly. In this paper we propose a new protocol to implement such a Web Bulletin Board, motivated by the needs of the vVote verifiable voting system. Using a distributed algorithm increases the complexity of the protocol and requires careful reasoning in order to establish correctness. Here we use the Event-B modelling and refinement approach to establish correctness of the peered design against an idealised specification of the bulletin board behaviour. In particular we show that for n peers, a threshold of t > 2n/3 peers behaving correctly is sufficient to ensure correct behaviour of the bulletin board distributed design. The algorithm also behaves correctly even if honest or dishonest peers temporarily drop out of the protocol and then return. The verification approach also establishes that the protocols used within the bulletin board do not interfere with each other. This is the first time a peered web bulletin board suite of protocols has been formally verified.