SNARE: A TRAP for Rational Players to Solve Byzantine Consensus in the 5f+1 Model
This work addresses consensus in distributed systems for applications like blockchain, offering incremental improvements in robustness and efficiency over prior protocols.
The paper tackles the problem of achieving Byzantine consensus in the 5f+1 model by adapting the TRAP protocol to SNARE, proving robustness for coalitions up to approximately 73% with minimal deposits and up to 60% without deposits, using a single broadcast round to handle deceitful players.
The TRAP protocol solves rational agreement by combining accountable consensus with a one-shot BFTCR finalization phase. We present SNARE (Scalable Nash Agreement via Reward and Exclusion), the adaptation of TRAP to $n=5f{+}1$, and prove $ε$-$(k,t)$-robustness for rational agreement tolerating coalitions up to ${\approx}73\%$ with deposits under $0.5\%$ of the gain. A central finding is that appending a single all-to-all broadcast round with the $4f{+}1$ threshold after predecisions yields $ε$-$(k,t)$-robustness for coalitions up to $3f$ (${\approx}60\%$) without any deposit: we need not model or know the utility function of deviating players, only that they participate in the protocol. These players can be \emph{deceitful} (arbitrary unknown utility), not just rational, and the finalization structure prevents disagreement regardless of their motivation. This observation is protocol-agnostic, applies to any $5f{+}1$ protocol at the cost of one message delay that runs concurrently with the next view, and does not require commit-reveal mechanisms. Above $60\%$, the full baiting mechanism with deposits under $0.5\%$ extends tolerance to ${\approx}73\%$. A second finding is that valid-candidacy, the property preventing reward front-running, holds unconditionally regardless of the quorum threshold, removing both the $n>2(k{+}t)$ and $n>\frac{3}{2}k{+}3t$ constraints from the original TRAP. This retroactively extends the $3f{+}1$ bound from $C<n/2$ to $C<5n/9$. The binding constraint in both models is the winner consensus operating on $2f$ residual players after excluding $3f{+}1$ detected equivocators. We explore avenues for relaxing this limit.