  Byzantine reliable broadcast is a primitive that allows a set of processes to
agree on a message broadcast by a dedicated source process, even when some of
them are malicious (Byzantine). It guarantees that no two correct processes
deliver different messages, and if a message is delivered by a correct process,
every correct process eventually delivers one. The primitive is known not to
scale, as it requires $\Omega(n^2)$ message exchanges, where $n$ is the number
of system members. The quadratic cost can be explained by the inherent need for
every process to relay a message to every other process.
  In this paper, we explore ways to overcome this limitation, by casting the
problem to the probabilistic setting. We propose a solution in which every
broadcast message is validated by a small set of witnesses, which allows us to
maintain low latency and small communication complexity. In order to tolerate a
slow adaptive adversary, we dynamically select witnesses through a novel use of
locality-preserving hash functions. Our simulations demonstrate significant
scalability gains of our solution with respect to existing protocols.
