  This paper introduces a new way to incorporate verifiable secret sharing
(VSS) schemes into Byzantine Fault Tolerance (BFT) protocols. This technique
extends the threshold guarantee of classical Byzantine Fault Tolerant
algorithms to include privacy as well. This provides applications with a
powerful primitive: a threshold trusted third party, which simplifies many
difficult problems such as a fair exchange. In order to incorporate VSS into
BFT, we introduced sAVSS, a framework that transforms any VSS scheme into an
asynchronous VSS scheme with constant overhead. By incorporating Kate et al.'s
scheme into our framework, we obtain an asynchronous VSS that has constant
overhead on each replica -- the first of its kind. We show that a key-value
store built using BFT replication and sAVSS supports writing secret-shared
values with about a 30% - 50% throughput overhead with less than 35 millisecond
request latencies.
