[cryptography] A secret sharing consensus protocol (or leader election protocol)

Natanael natanael.l at gmail.com
Fri Jul 19 07:07:33 EDT 2013

You might find my suggested scheme interesting:


It uses Secure Multiparty Computing plus Shamir's Secret Sharing Scheme
among a number of nodes with conflicting interests (in order to avoid
collusion) to securely create a keypair and distribute it among the the
nodes without any of them being able to recover the private key. It's used
to be able to run any number of rounds of Secure Multiparty Computing to do
things like count votes or whatever you might want to do, and you can have
the output results securely signed and non-node participants can use the
public key to send in data to process (including votes) while keeping it
secret from the other participants (assuming they trust the node owners to
not collude). While I'm only describing how to use it for standard
elections in that link, it can be generalized to work for all kinds of

I *think* this should work in practice, but I don't have the experience
needed to implement any of it (neither of programming or of cryptography).
I'm assuming I've understood the cryptograpy that's involved enough to not
introduce any gaping security holes. If anybody here would find a flaw in
it, please tell me about it. I haven't gotten much feedback on it yet, so
feel free to share any thoughts on it you might have.

2013/7/19 Tony Arcieri <tony.arcieri at gmail.com>

> Has there been any work with combining Shamir-style secret sharing with
> consensus protocols like Paxos and Raft (or leader election protocols like
> Omega Meets Paxos)?
> The idea would be to have a network of n peers, who share a secret where
> t=2 shares are required to reassemble the original secret. This secret is
> used to sign new values when a group consensus is reached via a Paxos-like
> protocol.
> In this scheme, a "proposer" would give its secret share, along with a
> proposed new value, to "acceptor" nodes, who can reassemble the entire
> secret. If they accept the new value, they can sign it with the secret,
> then immediately erase it. If we use a deterministic signature algorithm
> like Ed25519, every acceptor taking part in the consensus protocol can
> produce the same signed version of the proposed new value. They can then
> continue with the consensus protocol's accept phase. The result will be a
> quorum on a signed value (or a consensus failure if quorum can't be
> reached, of course)
> Let's assume a malicious entity gains control of one and only one of the
> nodes. They are now able to propose new values, so they can manipulate the
> peer network by proposing malicious values which will get accepted by the
> rest of the group.
> However, they do not *immediately* learn the private key. They would only
> learn the private key if any other node were to propose a value which
> contained their secret share.
> -- alternatively --
> Secret sharing could be combined with a leader election protocol. In this
> scheme, the leader and only the leader would learn the shared secret. All
> proposed values would have to be approved and signed by the leader.
> I'm not sure I like this as much though. The leader is a single point of
> failure, and an attacker could maliciously force a leader election through
> e.g. DoS, having compromised only one other host directly.
> --
> Tony Arcieri
> _______________________________________________
> cryptography mailing list
> cryptography at randombit.net
> http://lists.randombit.net/mailman/listinfo/cryptography
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20130719/0b43ef5d/attachment.html>

More information about the cryptography mailing list