The protocol has two components: an absolute consensus component, and then a way to calculate thresholded consensus, and finally an efficiency improvement on the thresholded consensus.
N voters want to determine if they all agree on a binary proposition.
Each participant p_i constructs a set of N different numbers, V_i,
for vote i, such that the sum of V_i is equal to 0. Each number
in V_i is distributed secretly to each participant, including p_i,
themself.
After everyone has received a number from all other participants, they have a
set of N received numbers. Participant p_i has the set of received numbers
R_i. Each participant p_i than calculates the sum of R_i and publishes
that number publicly. Call this number t_i for the tally of p_i's numbers.
If a participant wishes to BLOCK consensus, they simply have to distribute a set of numbers which does not sum to 0. Since the end tally depends on all of the secret numbers collectively, no individual can be caught out as the blocker without revealing a secret that only they have, and the can lie without being caught.
a_0 a_1 ... a_n -> sum a's = 0
b_0 b_1 ... b_n -> sum b's = 0
... ...
k_0 k_1 ... k_n -> sum k's = 0
| | | |
v v v v
sum sum sum sum
= = = =
x_0 x_1 x_n -> sum x's
=
0
To get M-of-N consensus, we can try all M-sized subsets of N to see if
there is consensus there. If there are any M-sized consensing groups at all,
they will find each other.
If there is a consensus of greater than M, then running all the M subsets
will reveal multiple consensing groups, and everyone who agreed will
eventually know everyone else who agreed. The ideal case is where you pick a
size to test that is equal to the number of consensing people. We can do this
by iteratively shrinking the size of the consensus set starting from N, for
absolute consensus, and stopping at M, for threshold consensus. If there is
any consensus above threshold, we will discover that first, before trying the
smaller threshold consensus.
For a binomial distribution that's large enough, and for a consensus threshold that's high enough, the cost of doing all or most of the consensi >M (or >M+1 or >M+2 etc) will be cheaper than the consensus for M itself, because the binomial distribution has long tails. This means we can try the more efficient approach first and not waste too much time in case there is a very wide consensus.