Two approaches to secret sharing: math vs. blockchain

The other day I rediscovered the cryptographic protocol called Shamir’s Secret Sharing, and it reminded me of something I meant to blog about two years ago.

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.

Readers of Michael Crichton novels, or 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.
“Two-out-of-two” dual-key mechanisms are state-of-the-art in safety deposit boxes
(although physical security is a very different game from cryptographic security),
and trapped-key interlocks
also bear some passing similarity.

Anyway, in cryptography, we can solve our “two-out-of-three” keying problem like this.

## Shamir’s Secret Sharing

We need a cryptographic analogue for our bank’s “gold.” Let’s say that we’re trying
to secure the secret word that would allow us to log in to our online vault.
We want to secure that secret word so that no single unscrupulous director can find it out,
but any pair of directors working together *can* find it out.
(Of course once the vault is open, both directors in the pair will know the secret word,
and be able to use it any time they want, even unilaterally. So our analogy isn’t so great.
But let’s run with it.)

First, we hire a trustworthy locksmith. The locksmith chooses a random polynomial
with two terms \(f(x) = a_{1}x + a_0\), where \(a_0\) is actually our secret.
This polynomial is defined in some finite field GF(*p*).
The locksmith issues to each director a key in the form of an ordered triple —
\((1, f(1), p)\), \((2, f(2), p)\), and \((3, f(3), p)\).

For example, suppose the secret word is `fish`

. Our trustworthy locksmith encodes
that in hex as `0x66697368`

. He picks a prime bigger than it; let’s say
`0x01'6098b2cd`

. He picks a random polynomial in GF(`0x01'6098b2cd`

); let’s say

```
f(x) = 0x1'48270199 * x + 0x66697368
```

He issues the following keys:
`(1, 0x4df7c234, 0x16098b2cd)`

, `(2, 0x35861100, 0x16098b2cd)`

, `(3, 0x1d145fcc, 0x16098b2cd)`

.

For comparison, if the secret word had been `gold`

, our trustworthy locksmith
would have encoded that in hex as `0x676f6c64`

, might have picked the random
polynomial `f(x) = 0x1'47a4051b * x + 0x676f6c64`

, and might have issued keys
`(1, 0x4e7abeb2, 0x16098b2cd)`

, `(2, 0x35861100, 0x16098b2cd)`

, `(3, 0x1c91634e, 0x16098b2cd)`

.

Then we shoot the locksmith. Now nobody knows the secret word; the only place it’s recorded is as the Y-intercept of the locksmith’s polynomial, which nobody knows.

Any director alone cannot reconstruct the polynomial. For example, director 2
cannot reconstruct the polynomial knowing only his personal key `(2, 0x35861100, 0x16098b2cd)`

.
However, if two directors get together and share their keys, they can reconstruct
the polynomial. For example, the first two directors can solve for \(a_1\) like
this:

```
a1 = (0x35861100 - 0x4df7c234) % 0x16098b2cd
```

And knowing \(a_1\), they can each compute the secret word like this:

```
a0 = (0x35861100 - (2 * a1)) % 0x16098b2cd = 0x66697368
a0 = (0x4df7c234 - (1 * a1)) % 0x16098b2cd = 0x66697368
```

(As they now have all the information the original locksmith had, they can now also compute each other’s keys, and the key of the third director.)

Let’s see another way of tackling the same problem, using a different set of tools.

## The blockchain analogue

I learned about this next bit via Andreas M. Antonopoulos’s book
*Mastering Bitcoin* (2014),
which is freely available in translation and/or in source-code form,
or available for real money on Amazon.
Chapter 7 discusses
multisignature scripts.

Thanks also to Greg Walker’s “learn me a bitcoin.”

Unlike raw math, Bitcoin is designed to mimic real assets in many ways. So our Bitcoin analogue
of “gold” is not going to be a secret word like `fish`

; it’s going to be some actual
quantity of bitcoin. We want to secure that bitcoin so that no single unscrupulous director
can transfer it to a different address, but any pair of directors working together
*can* transfer it to a different address.

The first thing we do is, every director creates their own ECDSA keypair, consisting of a public key and a private key. All the directors reveal their public keys. Let’s say that the directors’ public keys are these 65-byte vectors:

```
04cf291c54e736d412adcf2287bf8bb2cae680b79996e8f6aab8f98648e0419df8
943ead0e62b5044b533b073b1bc6f2af8ba93ca23e3d9738376824711ef2ad59
04c38de5add314f1e9d896265e9f436b8e260470f095a04fe66419bff2d24c2ff8
ecad15a23edbb95db2486f45e41c3bbe331a96c3385f7cc3784d763ced8a1fa7
04c9ee0cb11ec2cb7ac54a13b07818417822f191d4f789395df0a0ab80eb5d8884
99a89e6b557ed7aa091fee4889b2bb9c6205512b02362490f129ba105f776c74
```

Now we create an “unlocking script” in Bitcoin Script,
a stack-based language that’s part of the Bitcoin protocol. Script is a stack-based language
where its stack doesn’t store *numbers* (like Befunge) or
*numbers and/or references* (like the JVM),
but rather *arbitrary-length byte vectors*. (Actually, the length of a byte vector maxes out
at 520 bytes as of this writing.)
Our unlocking script looks like this:

```
OP_2
<push director 1's public key>
<push director 2's public key>
<push director 3's public key>
OP_3
OP_CHECKMULTISIG
```

Confusingly, Script doesn’t have any particular mnemonic notation for “push a byte vector.”
You can push a vector of up to 117 bytes by just placing the vector right into the Script code,
as a Pascal-style string. So hex `02 03 04`

means “push the byte vector `0304`

,” and hex
`01 02`

means “push `02`

.” Since that’s so frequently done, Script also provides
a dedicated opcode with a visible mnemonic: hex `52`

means “push 2,” and is known by the mnemonic `OP_2`

.
Other opcodes have nothing to do with pushing; for example, hex `93`

means “pop the top two vectors
and add them,”
and hex `AE`

means “check signatures for validity in an interesting way to be described later.”

So our unlocking script looks like this, in hex, with linebreaks added for readability. By the way, Simin Chen’s Bitcoin IDE can disassemble scripts like these.

```
52
41 04cf291c54e736d412adcf2287bf8bb2cae680b79996e8f6aab8f98648e0419df8
943ead0e62b5044b533b073b1bc6f2af8ba93ca23e3d9738376824711ef2ad59
41 04c38de5add314f1e9d896265e9f436b8e260470f095a04fe66419bff2d24c2ff8
ecad15a23edbb95db2486f45e41c3bbe331a96c3385f7cc3784d763ced8a1fa7
41 04c9ee0cb11ec2cb7ac54a13b07818417822f191d4f789395df0a0ab80eb5d8884
99a89e6b557ed7aa091fee4889b2bb9c6205512b02362490f129ba105f776c74
53AE
```

We then create a Bitcoin transaction “locking up” our quantity of bitcoin, by indicating through
the *locking* script that the output of that transaction is spendable (or “redeemable”) only
by someone who presents a copy of our unlocking script, identified by hash, along with the proper
data inputs to make it return `1`

when evaluated by a Bitcoin Script interpreter.

Any director alone cannot spend the UTXO we thus “locked up.” However, if two directors together want to spend it, they do the following:

Create a new transaction. Agree on the rules for who can spend the output of this
*new* transaction, and encode them in a locking script which again becomes part of the
new transaction. Hash this new transaction (using double SHA-256, if I understand correctly).
The first director signs a copy of the hash using his private key.
The second director signs a copy of the hash using *his* private key.
Use these hashes to create a “redeem script” that looks like this:

```
OP_0
<push director 1's cryptographic signature of this transaction>
<push director 2's cryptographic signature of this transaction>
```

Send the directors’ transaction out to the world. If all goes well, some miner somewhere will pick it up and incorporate it into a block in the blockchain. Other miners will not necessarily trust this block; they’ll want to verify that it’s valid, meaning that it consists of all valid transactions. To verify that the directors’ transaction was valid, a miner will concatenate its redeem script with its unlocking script:

```
OP_0
<push director 1's cryptographic signature of this transaction>
<push director 2's cryptographic signature of this transaction>
OP_2
<push director 1's public key>
<push director 2's public key>
<push director 3's public key>
OP_3
OP_CHECKMULTISIG
```

And then it’ll interpret the script — which means push eight byte-vectors onto the stack and then
execute `OP_CHECKMULTISIG`

. When the Script interpreter sees this opcode, it pops the top `3`

from the stack,
and based on that pops three public keys. Then it pops `2`

from the stack, and based on that pops two signatures
(and a trailing `0`

, for historical reasons). Finally, it validates the signatures: it checks to see if
director 2’s signature is `SIGN(hash_of_transaction)`

according to director 3’s public key. Nope! It goes on
to the next public key. Is director 2’s signature valid according to director 2’s public key? Yep! It goes
on to the next public key *and* the next signature. Is director 1’s signature valid according to director
1’s public key? Also yep! Having validated all of the signatures it popped, it has succeeded; so it pushes `1`

back onto the stack. Finally, having reached the end of the script, the interpreter stops and checks the top
value on the stack. It’s `1`

(truthy), so the transaction is considered valid (by every miner who bothers to
examine it).

Now you see how one unscrupulous director, acting alone, cannot steal the gold. He could construct a new transaction with the “redeem script”

```
OP_0
<push director 1's cryptographic signature of this transaction>
```

or even

```
OP_0
<push director 1's cryptographic signature of this transaction>
<push director 1's cryptographic signature of this transaction>
```

but neither of these inputs, when combined with the true “unlocking script,” would result in a truthy value on the interpreter’s stack at the end of the script. The unscrupulous director could try presenting a different unlocking script altogether, for example

```
51
41 04cf291c54e736d412adcf2287bf8bb2cae680b79996e8f6aab8f98648e0419df8
943ead0e62b5044b533b073b1bc6f2af8ba93ca23e3d9738376824711ef2ad59
41 04c38de5add314f1e9d896265e9f436b8e260470f095a04fe66419bff2d24c2ff8
ecad15a23edbb95db2486f45e41c3bbe331a96c3385f7cc3784d763ced8a1fa7
41 04c9ee0cb11ec2cb7ac54a13b07818417822f191d4f789395df0a0ab80eb5d8884
99a89e6b557ed7aa091fee4889b2bb9c6205512b02362490f129ba105f776c74
53AE
```

or even

```
51
```

but those unlocking scripts don’t have the same hash as the true unlocking script chosen by the directors, whose hash is incorporated into the directors’ original transaction that locked up the funds. Therefore again no miner will consider the unscrupulous director’s new transaction to be valid.

## Conclusion

The mind-bending thing about the Bitcoin approach is that it completely sidesteps all the math that makes Shamir’s scheme work. We don’t have to look for some mathematical primitive that can split up a secret into parts. We just build the “2-of-3 keys required” protocol directly into the Bitcoin Script interpreter, as a primitive operation!

And then we leave our money out in plain sight, guarded only by a sign that says “Everyone please take note: Nobody shall be considered to have taken any of this money unless they were accompanied by at least two of the bank’s directors.”

How can this be secure? Couldn’t anyone “get at” the funds, if they’re sitting right there, guarded
only by convention? Well, yes — but what’s the use of “getting at” money
if nobody in the world agrees that you have gotten it? In fact (and this is Bitcoin’s core insight),
if nobody *agrees* that you have the money, then in a very real sense you haven’t got it at all.