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.