Multisig, probability to lose coins?

[o_e_l_e_o]

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?

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.

[satscraper]

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?

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


3.

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

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)

[cygan]

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

[o_e_l_e_o]

Such approach can be easily extended to any multisig, say 100 of 1000 and result in general formula.

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.

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)

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.

[satscraper]

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.

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

[o_e_l_e_o]

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.

[satscraper]

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

[o_e_l_e_o]

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.

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.

[satscraper]

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.

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.

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.

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

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