1

Arbitrary "M-of-N" secret-sharing protocols are a well-studied topic in cryptography, and are apparently so useful that Bitcoin Script devoted a whole opcode to them.

In this blog post, I write:

Suppose we run a bank, and suppose that our bank stores all its gold in one big safe. And suppose that we have three people on our board of directors. We want to ensure that a single unscrupulous director cannot open the safe and steal all the gold. Therefore, we cut three distinct keys, and we craft the safe so that it requires two of these three keys to be inserted simultaneously, in order to open the safe.

Fans of Sean Connery might recognize this as more or less the setup to The Great Train Robbery, except for our “two out of three” requirement. I have not been able to discover any real-world mechanical analogue to the “two-out-of-three” mechanism.

So I ask you!

There is certainly an easy way to construct an "N-of-N" locking mechanism, such that you can get the safe open only when all N keys are inserted. (You just stack the locks vertically down the door, and make sure any single bolt by itself is strong enough to keep the door shut.) "2-of-2" mechanisms are used in bank safety deposit boxes.

I imagine it isn't hard to construct a "1-of-N" locking mechanism, along the lines of the Borromean rings, but I haven't found any such mechanisms patented or for sale.

I have not found any references to "M-of-N" locking mechanisms in the real world, nor can I immediately imagine how to construct one (except the brute-force method of obtaining N-choose-M different key safes, each protected by an M-of-M mechanism). Has any inventor ever designed such a physical mechanism? Does any real-world use-case exist for such a mechanism?

Quuxplusone
  • 130
  • 4
  • Note that the original motivating example for a "2-of-3" `OP_CHECKMULTISIG` was [described in BIP-0011](https://github.com/bitcoin/bips/blob/master/bip-0011.mediawiki#Motivation) as "Three-party escrow (buyer, seller and trusted dispute agent). If the buyer and seller cannot agree, then the agent can, with the cooperation of either buyer or seller, decide what happens to the tied-up coins." – Quuxplusone Feb 13 '20 at 02:19
  • 2
    a simple way for say 2 of 3, you have a safe that requires 3 keys to unlock, and each holder has a different set of 2 keys from the 3 possible keys. In general in the real world it makes more sense to duplicate the keys than the safes. – Jack Feb 13 '20 at 02:52
  • @Jack: Ah, of course! That's worthy of posting as an answer, especially if you can flesh it out with a real-world example (or did you just come up with that off the top of your head?) – Quuxplusone Feb 13 '20 at 03:01

1 Answers1

0

There are real-world multi-key locks made for this purpose. The most common have two separate cores that are internally geared to turn together, which require both keys be present and turned simultaneously.

Other designs have a single key way and require the two different keys be inserted sequentially. Here’s an explanation on using the latter: https://anemo.eu/how-do-dual-key-locks-work This tubular lock requires each key be turned a quarter turn each. Internally, this might be done by boring a groove linking one pin’s hole to span the first quarter turn, ignored by the first key; then boring a different pin’s hole spanning the next quarter turn, which will be ignored by the second key; the rest of the pins would match. The keys would have to be used in order to unlock it, and relocked in reverse order.

Neither of these designs inherently solves the m of n problem where m < n. That can be solved with a standard industrial lock-out hasp with n physical padlocks. Each key holder is then given a unique subset of physical keys to open one share’s worth of padlocks, using a secret sharing scheme. Note that this approach does not scale well in the physical world, as the number of padlocks and keys grows exponentially with n.

John Deters
  • 33,650
  • 3
  • 57
  • 110