Multisig, probability to lose coins? - page 2.

Saint-loup

legendary

Activity: 2604

Merit: 2353

Quote from: satscraper on September 15, 2023, 01:48:16 AM

Real numbers instance is not a problem at all.
For instance if n=1 P=1 for P₁=1 , while P=0 for P₁=0
If n=2, and say P₁=0.5, P₂=0.7, then P=0.85

Not sure it's really clearer for all people lol.
P= 1 - ∏_i=1..2(1-P_i) = 1 - (1-P₁)(1-P₂) = 1 - (1-0.5)(1-0.7) = 1 - 0.15 = 0.85

Quote from: satscraper on September 15, 2023, 01:48:16 AM

Unfortunately your formula is not valid even for 3keys of a 2 of 3 wallet.

Take P₁ = P₂ = P₃ = 0.9 and you will get P>1 which is impossible.

I will think about N- out -of -M -solution in general case which should include also the calculation of probability to lose the specific set of N from all possible combinations.

You're right bro, actually if you draw 3 circles A, B and C intersected and you take the intersection A ⋂ B, you will also take A ⋂ B ⋂ C into it. So if you take A ⋂ B + B ⋂ C + A ⋂ C you will count 3 times A ⋂ B ⋂ C instead of one time.
So it must be
P_L2K = P₁P₂ + P₂P₃ + P₁P₃ + P₁P₂P₃ - 3P₁P₂P₃ = P₁P₂ + P₂P₃ + P₁P₃ - 2P₁P₂P₃

o_e_l_e_o

legendary

Activity: 2268

Merit: 18748

This is wrong.

If you want to calculate the probability of losing access to a 2-of-3 multi-sig, then you need to work out the sum of the probabilities of losing any two keys and the probability of losing all three keys. The formula you are looking for is as follows:

P(A).P(B).P(C') + P(A).P(B').P(C) + P(A').P(B).P(C) + P(A).P(B).P(C)

This is the probability of losing A and B, plus the probability of losing A and C, plus the probability of losing B and C, plus the probability of losing all three.

The other way to calculate would be to add the probability of losing exactly one key to the probability of losing no keys, and then subtract that from 1:

1 - (P(A ⋂ B' ⋂ C') + P(A' ⋂ B ⋂ C') + P(A' ⋂ B' ⋂ C) + P(∅))

Where P(∅) = 1 - P(A ⋃ B ⋃ C)

Quote from: satscraper on September 15, 2023, 10:04:34 AM

BTW, what does tt /tt code stand for? Never saw it.

Teletype. It's a monospace font which is generally used when referring to small snippets of code, command line arguments, etc.

satscraper

hero member

Activity: 714

Merit: 1298

Quote from: Saint-loup on September 14, 2023, 06:31:41 PM

For example if I have 3keys of a 2 of 3 wallet, what will be the probability of losing at least 2keys?
P_L2K = P₁P₂ + P₂P₃ + P₁P₃ + P₁P₂P₃
But it's not a general formula unfortunately.

@Saint-loup, to get correct formula for P_L2K you should base calculation on the sum of probability to lose any of key pairs and probability not to lose it. That sum is equal to 1

Then, using your notations) P_L2K = 1 - (1-P₁P₂ ) x (1-P₂P₃ ) x (1-P₁P₃ ) If you wanna include three lost keys then P_L2K = 1 - (1-P₁P₂ ) x (1-P₂P₃ ) x (1-P₁P₃ ) x (1- P₁P₂P₃) The same approach is applied to write formula for " at least N keys out of M keys", but I am still looking for the best way to express in general notations the arbitrary commutation of N from M BTW, what does tt /tt code stand for? Never saw it.

o_e_l_e_o

legendary

Activity: 2268

Merit: 18748

Let's call your keys A, B, and C.

Probability of losing A = P(A)
Probability of not losing A = P(A') = 1-P(A)

Probability of losing all three keys = P(A ⋂ B ⋂ C) = P(A).P(B).P(C)

Probability of losing exactly one key = P(A ⋂ B' ⋂ C') + P(A' ⋂ B ⋂ C') + P(A' ⋂ B' ⋂ C) = P(A).P(B').P(C') + P(A').P(B).P(C') + P(A').P(B').P(C)

Probability of losing one or more keys = P(A ⋃ B ⋃ C) = P(A) + P(B) + P(C) - P(A ⋂ B) - P(A ⋂ C) - P(B ⋂ C) + P(A ⋂ B ⋂ C)

Plug in your numbers as desired. If you are looking specifically for the probability of never losing a single key, then do 1 minus the last equation above.

satscraper

hero member

Activity: 714

Merit: 1298

Quote from: Saint-loup on September 14, 2023, 06:31:41 PM

@satscraper It would have been more clear with one example with real numbers but for me you're right, your formula is good.

Real numbers instance is not a problem at all.
For instance if n=1 P=1 for P₁=1 , while P=0 for P₁=0
If n=2, and say P₁=0.5, P₂=0.7, then P=0.85
If n=100 and say P_i =0.9 for each i index then P = 1 - 0.1¹⁰⁰ which is very close to 1

So, you can take any numbers and get the result.

Quote from: Saint-loup on September 14, 2023, 06:31:41 PM

@satscraper It would have been more clear with one example with real numbers but for me you're right, your formula is good.
But do you know one to calculate the probability of losing at least N keys out of M ?
For example if I have 3keys of a 2 of 3 wallet, what will be the probability of losing at least 2keys?
P_L2K = P₁P₂ + P₂P₃ + P₁P₃ + P₁P₂P₃
But it's not a general formula unfortunately.

Unfortunately your formula is not valid even for 3keys of a 2 of 3 wallet.

Take P₁ = P₂ = P₃ = 0.9 and you will get P>1 which is impossible.

I will think about N- out -of -M -solution in general case which should include also the calculation of probability to lose the specific set of N from all possible combinations.

Saint-loup

legendary

Activity: 2604

Merit: 2353

Quote from: hugeblack on September 10, 2023, 07:39:08 AM

If I understand what you mean, in the multi-signature wallet we have a limited number of keys, and let us assume that it is 3 out of 8, so the calculations are as follows:
The total number of N keys is 8
The number required to spend F 3
Losing one of the keys we have
N^ = 8-1=7
F^=3-1=2
Thus, the spending probability becomes p=f^/N^=2/7
The probability of not being able to spend is 1-p
Then you can replace N and F according to the NofM values and thus obtain a general equation.

He's not really talking about the probability of deadlocking a multisig wallet here actually, but more about the probability of losing at least one key (whatever the scheme used by the wallet). If the wallet is a N=M wallet, the wallet will be lost with only one missing key though but I think it's also important to have an idea of the probability of losing at least one key even if it doesn't lock the wallet, in order to take better decisions when we use SLIP39 for example. When we share keys in several locations, the probability of losing them is not identical in each location.

@satscraper It would have been more clear with one example with real numbers but for me you're right, your formula is good.
But do you know one to calculate the probability of losing at least N keys out of M ?
For example if I have 3keys of a 2 of 3 wallet, what will be the probability of losing at least 2keys?
P_L2K = P₁P₂ + P₂P₃ + P₁P₃ + P₁P₂P₃
But it's not a general formula unfortunately.

satscraper

hero member

Activity: 714

Merit: 1298

Quote from: hugeblack on September 10, 2023, 07:39:08 AM

If I understand what you mean, in the multi-signature wallet we have a limited number of keys, and let us assume that it is 3 out of 8, so the calculations are as follows:
The total number of N keys is 8
The number required to spend F 3
Losing one of the keys we have
N^ = 8-1=7
F^=3-1=2
Thus, the spending probability becomes p=f^/N^=2/7
The probability of not being able to spend is 1-p
Then you can replace N and F according to the NofM values and thus obtain a general equation.

Nope, it is not the same. Assume that F=N and set individual probability for each key to lose.

hugeblack

legendary

Activity: 2702

Merit: 4002

If I understand what you mean, in the multi-signature wallet we have a limited number of keys, and let us assume that it is 3 out of 8, so the calculations are as follows:
The total number of N keys is 8
The number required to spend F 3
Losing one of the keys we have
N^ = 8-1=7
F^=3-1=2
Thus, the spending probability becomes p=f^/N^=2/7
The probability of not being able to spend is 1-p
Then you can replace N and F according to the NofM values and thus obtain a general equation.

satscraper

hero member

Activity: 714

Merit: 1298

Let's say one has multisig wallet which requires n valid signatures to sign transactions. What is the probability to loose coins the wallet holds in the case of loosing at least one private key required for signature when each key has its own probability to be lost?

My solution

Let's P_i is the probability of loosing key with the index of i , i= 1.....n

Then the probability of not loosing it is 1-P_i

Allowing independent events for key loosing we get the following expression for the probability that i keys all together will be never lost: ∏_i=1..n(1-P_i)

Then target value is P= 1 - ∏_i=1..n(1-P_i) where ∏ - multiplication operator

Is my calculation correct?

Topic: Multisig, probability to lose coins? - page 2. (Read 349 times)