Replay Attacks and Defenses against Cross-shard Consensus in Sharded Distributed Ledgers.

We present the first replay attacks against sharded distributed ledgers. These attacks target cross-shard consensus protocols allowing an attacker to double-spend or lock resources with minimal efforts. The attacker can act independently without colluding with any nodes, and succeed even if all nodes are honest; most of the attacks also work under asynchrony. These attacks are effective against both shard-led and client-led cross-shard consensus approaches. We present byzcuit---a new cross-shard consensus protocol that withstands those attacks.