rusty_share_trick.md

Rusty's Revocation Secret Threshold Trick

Rusty describes how given x shares, one can distribute different subsets of those shares to n participants such that any quorum of at least t participants would have the complete set, but no quorum of t-1 or fewer participants would.

In this exercise, we try to standardize how to determine the necessary number of shares x for any t/n threshold scenario, and how to distribute subsets of those shares in a manner that will ensure these constraints.

For the specific use case of threshold channel revocation, the assumption is that for a set of shares {A, B, C}, the actual secret that participants meeting the threshold requirement would need to be able to calculate is simply the XOR of all components, i. e. S = A xor B xor C. However, the share distribution mechanism is agnostic to the exact manner in which knowledge of the full set of shares may translate to specific applications.

Something I would like to explicitly point out:

• A participant may have multiple shares, though all users will have the same number of shares ("shares per user")
• Multiple participants may have the same share, though the number of participants with a given share will be equivalent across all shares ("users per share")

Trivial Scenarios

Let's think through some trivial scenarios that are either 1/n or n/n, where the share distribution is rather obvious.

1/2

One of two users needs to come together to calculate the secret.

Participant	Shares
Alice	A
Bob	A

Secret: A

Total shares	1
Shares per user	1
Users per share	2

2/2

Two of two users need to come together to calculate the secret.

Participant	Shares
Alice	A
Bob	B

Secret: A xor B

Total shares	2
Shares per user	1
Users per share	1

1/3

One of three users needs to come together to calculate the secret.

Participant	Shares
Alice	A
Bob	A
Charlie	A

Secret: A

Total shares	1
Shares per user	1
Users per share	3

3/3

Three of three users need to come together to calculate the secret.

Participant	Shares
Alice	A
Bob	B
Charlie	C

Secret: A xor B xor C

Total shares	3
Shares per user	1
Users per share	1

Summary

We can immediately see that for any 1/n, there is only one share, and all participants have it, meaning any individual participant comprises the full quorum.

On the other hand, for any n/n, we observe that each user simply has their own unique share, so the set can only be complete with a quorum of all users.

Nontrivial Scenarios

2/3

Two of three users need to come together to calculate the secret.

Participant	Shares
Alice	A B
Bob	B C
Charlie	A C

Secret: A xor B xor C

Total shares	3
Shares per user	2
Users per share	2

2/4

Two of four users need to come together to calculate the secret.

Participant	Shares
Alice	A B C
Bob	A B D
Charlie	A C D
Dylan	B C D

Secret: A xor B xor C xor D

Share	Users
A	Alice, Bob, Charlie
B	Alice, Bob, Dylan
C	Alice, Charlie, Dylan
D	Bob, Charlie, Dylan

Total shares	4
Shares per user	3
Users per share	3

3/4

Three of four users need to come together to calculate the secret.

Participant	Shares
Alice	A B C
Bob	A D E
Charlie	B D F
Dylan	C E F

Secret: A xor B xor C xor D xor E xor F

Share	Users
A	Alice, Bob
B	Alice, Charlie
C	Alice, Dylan
D	Bob, Charlie
E	Bob, Dylan
F	Charlie, Dylan

Total shares	6
Shares per user	3
Users per share	2

Tabulation

Scenario	Total shares	Shares per user	Users per share
1/2	1	1	2
2/2	2	1	1
1/3	1	1	3
2/3	3	2	2
3/3	3	1	1
1/4	1	1	4
2/4	4	3	3
3/4	6	3	2
4/4	4	1	1

Observations:

Users per share	$n - t + 1$
Total shares	${n \choose \text{{<}Users per share{>}}} = {n \choose n - t + 1}$
Shares per user	${n - 1 \choose t - 1}$

Experiment

3/5

$$\text{Total shares} = {n \choose n - t + 1} = {5 \choose 5 - 3 + 1} = {5 \choose 3} = 10$$ $$\text{Shares per user} = {n - 1 \choose t - 1} = {5 - 1 \choose 3 - 1} = {4 \choose 2} = 6$$ $$\text{Users per share} = n - t + 1 = 5 - 3 + 1 = 3$$

So to summarize the result of our calculation:

Total shares	10
Shares per user	6
Users per share	3

A critical thing to point out is that there are exactly 10 ways of combining 3 users per share out of a total of 5 participants, which is the number of shares that we have. In fact, the reason the number of total shares is ${n \choose n - t + 1}$ is because it's actually ${n \choose \text{{<}users per share{>}}}$, and $\text{{<}users per share{>}} = n - t + 1$.

On the other hand, the number of combinations of 6 shares per user out of 10 is 210, which is drastically more than the number of participants. For that reason, finding correct subset distributions is easier based on the users per share than vice versa, so we'll go through each of the 10 shares and iterate over the 10 possible combinations of the 5 users in sets of 3.

Share	Users
A	Alice, Bob, Charlie
B	Alice, Bob, Dylan
C	Alice, Bob, Emily
D	Alice, Charlie, Dylan
E	Alice, Charlie, Emily
F	Alice, Dylan, Emily
G	Bob, Charlie, Dylan
H	Bob, Charlie, Emily
I	Bob, Dylan, Emily
J	Charlie, Dylan, Emily

Let's construct a dim(<shares> X <participants>)-matrix to map the share-participant-pairings:

Share	Alice	Bob	Charlie	Dylan	Emily
A	X	X	X
B	X	X		X
C	X	X			X
D	X		X	X
E	X		X		X
F	X			X	X
G		X	X	X
H		X	X		X
I		X		X	X
J			X	X	X

Based on this output, we now transpose from the shares to the users.

Participant	Shares
Alice	A B C D E F
Bob	A B C G H I
Charlie	A D E G H J
Dylan	B D F G I J
Emily	C E F H I J

The secret is S = A xor B xor C xor D xor E xor F xor G xor H xor I xor J. Any set of 3 participants should have sufficient information to calculate it, whereas no combination of 2 or fewer participants should.

Another trick for easy iteration would be thinking of the user allocation as a 5-digit binary number where exactly 3 bits must be 1, and going through all combinations between 00111 and 11100 where that is true. The bit index may indicate the participant, and that they would have that particular share if the bit is set.

Script

Ugly script to generate the share distribution: https://gist.github.com/arik-so/f23c710c42da0fe5d06a528c49fb1e58