Topic: Multisig, probability to lose coins? (Read 349 times)

Theoretically yes, but the probability that D , E or DE  are lost at the time when ABC occurs is very low , events are independent and if, say DE  has already happened it is more likely that either ADE or BDE/CDE occur than ABCDE. Thus from the practical point of view it can be neglected all other combinations. The same applies to  remaining subsets of the three keys.


Summation would be wrong as the  events of ternaries  loss are independent thus the opposite events are also independent.

Correct, but you are still calculating multiple events multiple times. For each of the five scenarios where you can lose 4 keys, you are calculating each one four times, and the final scenario where you can lose 5 keys is being calculated ten times. Therefore your final value will be wrong.

Your equation is also still multiplying each possibility instead of summing them, which I've already discussed above.

I"m aware of this.

But

If ABC occur the wallet will be locked     independently of  the state of D and E   The same applies  to ABD, BDC and so on. The other combinations probably would be interested from the theoretical point of view but not from the standpoint of the wallet's owner. Thus, I believe, that approach suggested by me, has a practical sense.  

I've already explained above why that equation doesn't work.

If you calculate A*B*C when there are 5 variables, then you aren't just including the situation where you lose those three keys. You are calculating the probability of losing any of the following:
ABC
ABCD
ABCE
ABCDE

If you do the same for ABD, then you are calculating all of the following:
ABD
ABCD
ABDE
ABCDE

You've just calculated ABCD and ABCDE twice. Compound that over your 10 calculations, and you end up calculating the same possibility many times, meaning your final equation is way out.

What you need to calculate is P(A ⋂ B ⋂ C ⋂ D' ⋂ E') for each of your ten possibilities (i.e. A * B * C * Not D * Not E), and then do the same for the five scenarios where you can lose 4 keys, and again for the final scenario where you can lose all 5 keys, and then sum your results.

I  think if the user's interest is in finding the probability of the locking of N-of-M multisig  wallet  then  such formula can be deducted as it should calculate the probability of losing any set of N keys taken from M.

The easiest way to find that probability is to calculate the  probability of opposite event t.e. the probability of not loosing any set of N keys taken from M and then subtract that probabilty   from 1. By using such approach the general formula can be written but I'm still looking for the best notations to write it.

Assuming that all the event of key losing are independent (which is quite reasonable), for the case 3 of 5 it would be

P = 1 - (1-p1*p2*p3)(1-p1*p2*p4)(1-p1*p2*p5)(1-p1*p3*p4)(1-p1*p3*p5)(1-p1*p4*p5)(1-p2*p3*p4)(1-p2*p3*p5)(1-p2*p4*p5)(1-p3*p4*p5)
 
  where p1, p2, p3, p4 and p5 are probabilities  to lose the relevant key

Not really.


Here is an example for a 3-of-5 multi-sig. If you simply calculate P(A ⋂ B ⋂ C), you'll end up calculating this area:



This will give you the chance of losing ABC, with no regard to what is happening with DE.

If you want to extend this to the chance of losing any 3 keys, though, what you actually want to calculate the area P(A ⋂ B ⋂ C ⋂ D' ⋂ E'):



If you don't do this, and just calculate P(A ⋂ B ⋂ C) for each set of three keys, then you will end up with a huge number of overlapping areas which you are counting 2, 3, 4, or even 5 times, instead of just once, and your final answer will be grossly inaccurate.

There is no one formula for any m-of-n. You'll need to create a formula which considers every m or more subset of your n keys, which will very rapidly become a very long equation. So for a 3-of-5, you would need to sum the probabilities of each of the ten ways to lose 3 keys, each of the four ways to lose 4 keys, and the one way to lose all 5 keys.

because i see thatyou guys are talking about multi signature here, i would like to present these slides in addition to the already very good posts/answers, which might give a better understanding of the whole procedure
if desired i can also present more slides about musig2





https://twitter.com/BTCillustrated

Nice, this is exactly what has been used in my calculations, except it has been based not on the probability to losing but the probability of opposite events for all pairs possible. Such approach can be easily extended to any multisig, say 100 of 1000 and result in general formula. By comparison, as I see it, your approach is hard to extend to the general case. (probably I'm wrong in my last assumption  and you will show  us the general formula for N of M)

It depends. There are three things you can work out here.

1.

P(A ⋂ B ⋂ C')
This is the probability of losing only A and B, while not losing C.


2.

P(A ⋂ B ⋂ C)
This is the probability of losing A and B, and also losing C at the same time (i.e. losing all three keys).


3.

P(A ⋂ B)
This is the probability of losing both A and B, regardless of what happens to C.


If you are only interested in the probability of losing A and B, then you would use the third example above, P(A ⋂ B). In this scenario, you don't pay any attention to C at all, and only work out the probability of losing A and B. However, if you are now interested in the probability of losing any two keys, you run in to a problem. Let's calculate the same area for losing keys B and C:


P(B ⋂ C)

You can look at the pictures for P(A ⋂ B) and P(B ⋂ C), you'll see you've now included the middle intersect twice. If you then do the same for P(A ⋂ C), you will include the middle intersect three times, which is obviously wrong.

So you have two solutions to this. My solution above is as follows:
P(A ⋂ B ⋂ C') + P(A ⋂ B' ⋂ C) + P(A' ⋂ B ⋂ C) + P(A ⋂ B ⋂ C)
This solution calculates the first picture above for each combination (i.e. missing out the middle intersect all together), and then adds the middle intersect at the end.

Saint-loup's solution is as follows:
P(A ⋂ B) + P(A ⋂ C) + P(B ⋂ C) - 2P(A ⋂ B ⋂ C)
This solution calculates the third picture above for each combination (and includes the middle intersect three times), and then subtracts the middle intersect twice to get back to the desired one inclusion.

Those two equations are identical, just written in different formats, and it is easy to turn one in to the other as Saint-loup has nicely outlined in this post.

I don't think it's possible because you can also lose B along with C or A along with C and lock your wallet due to these 2 other losses, so how would you represent and count those cases? Probabilities to lose each key are not exactly the same if they are not at the same place or not stored in the same way, so I don't think trying to simplify by using probabilities of losing keys whatever they are would be the most relevant.

Nice illustration.

Well, isn't it enough to lose say A&B and forget about probability to lose C as in this scenario your 2 of 3 keys multisig  wallet will stop to work for you?  I think such scenario has more  practical sense and in this case the red area  on your picture will turn into the single point of intersections  of  three circles.

If the events are independent and don't exclude each other that's how their outcomes intersect. If your keys are in 3 different places, normally they can be lost all together. When you lose the key A you can also lose the key B and/or C at the same time unfortunately so it can be represented like that

It isn't, because you have included the same event multiple times. Just as you can't lose A twice, you can't "not lose A" twice. You either lose it or you don't.

No. As I've already said above:

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

So the probability to not lose all three keys is simply 1 - P(A).P(B).P(C)

Yes that's what we can see if we replace P(X') by 1 - P(X) and make the calculations :

P(A).P(B).P(C') + P(A).P(B').P(C) + P(A').P(B).P(C) + P(A).P(B).P(C) = P(A)P(B)(1-P(C)) + P(A)(1-P(B))P(C) + (1-P(A))P(B)P(C) + P(A)P(B)P(C)
= P(A)P(B) - P(A)P(B)P(C) + P(A)P(C) - P(A)P(B)P(C) + P(B)P(C) - P(A)P(B)P(C) + P(A)P(B)P(C)
= P(A)P(B) + P(A)P(C) + P(B)P(C) - 2P(A)P(B)P(C)

Absolutely correct, but I have multiplied probabilities for not to lose pairs. I can not to lose A&B, A&C and B&C, each event of not loosing is independent. Another words, any of three pairs can not be lost.
Thus the probability to not lose all three is (1-P(A)P(B)) (1-P(A)(C))(1-P(C)P(B))

You multiply within each pair, for example P(A).P(B), as you are considering the probability of losing both Key A and also losing Key B.

You do not then multiply pairs together as you have done, as that doesn't make sense. You aren't considering the possibility of losing the pair A and B, and also losing the pair A and C. How would that even work? You lose all three keys but you lose A twice? You are considering losing pair A and B OR losing A and C, so you add the probabilities of each pair together.

I'm afraid you haven't calculated any real world scenario. You cannot lose A&C when you've already lost A&B. A is already lost. You can't lose it twice.

Well, I have  understood you way of thinking, but I have indeed assumed that three circles (in term of Saint-loup) do not have the common area.  




Because events to lose  pairs are independent thus one needs to multiply probabilities  according to the  probability theory. We add them if they dependent , again according to to the  probability theory.

Well, I think we both have   calculated different cases.

0.098 or 9.8% is the correct answer. Plug those numbers in to an online probability calculator to confirm, such as this one: https://www.calctool.org/math-and-statistics/probability-three-events

Here is your equation:

I'm afraid it simply doesn't make sense.

Why are you multiplying the probabilities together? You are not looking for the probability you lose P₁&P₂ AND P₁&P₃ AND P₂&P₃, but rather you are looking for the probability you lose P₁&P₂ OR P₁&P₃ OR P₂&P₃. And as Saint-loup has pointed out, you are counting the middle intersect three times here, meaning you either have to subtract it twice at the end as they have done in their equation, or you need to modify each equation with respect to not losing the third key as I have done in mine.

Well, easier to say wrong than explain why  

P(1)= 0.1   P(2) = 0.2 and P(3) = 0,3

Your formula  results in 0.098, mine in 0,10646

I'm not sure which of two results is correct.

Please, explain why you think that my approach is wrong.  


Depends on how you will intersect them.

This is correct, and is analogous to the equation I shared above:

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

Your equation works out the three intersects of A ⋂ B, A ⋂ C, and B ⋂ C, and the subtracts the middle intersect of A ⋂ B ⋂ C twice since you have included it three times.
My equation works out the intersects while excluding the middle intersect each time, and then adds the middle intersect back in at the end.

Either way, you will end up with the same result.

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

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₃

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)

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

@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.

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.

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.


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.

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.

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

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.

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?