Erroneous Multiplication Results

[lumip]

In my application it sometimes happens that the results of multiplication of arithmetic shares are wrong i.e., not the result of the multiplication of the input values but some apparently uniform random value.

I've now written a small test program which runs 2000 rounds and performs 1000 independent multiplications per round (using Reset to reset the party before each round and ExecCircuit after putting the 1000 multiplication gates) and outputting how many of these rounds produced correct results. Averaged over 7 executions of this program the mean ratio of bad runs (those with wrong results) is 13.99 % (0.1399 with a standard deviation of 0.0168). Also, either all the multiplications in a round give bad results or none does. (I didn't obtain more results because I ran into problems described in #110 (albeit with a much higher rate of segfaults and not so much stalling).

I suspect something going wrong during triple generation in the setup phase. This happens with the MT_OT triple generation strategy. (I was unable to try with the other two, MT_PAILLIER causes the program to crash and MT_DGK just freezes for me).

I'm a bit confused about this, especially since it doesn't seem to be a common issue or at least was not reported so far..

Edit: Running some more tests playing around with the number of multiplications per round I found more interesting behavior. As opposed to what I stated in the above, it is not the case that either none or all multiplications fail; there's a certain point after which failures can occur which seems to depend on the number of multiplications (or gates in general?) in the circuit. From my observations so far, either no failures occur or all multiplication after that threshold are wrong. Interestingly, that is always either a power of two or a sum of powers of two. The following tables gives my results for certain numbers:

number of multiplications	first multiplication which may fail (but when it does, all following do, too)		frequency	number of rounds run in total (so far)
1000	0		0.1399	14000
4000	2048	2^11	0.139	1000
4097	2048 or 4096	2^11 or 2^12
5000	4096	2^12	0.137	1000
6000	4096	2^12
7000	6144	2^12 + 2^11	0.155	600
8000	6144	2^12 + 2^11	0.114	1200
10000	8096	2^13	0.116	1600
20000	18432	2^14 + 2^11	0.13	1200
400000	399360	2^18 + 2^17 + 2^12 + 2^11

Note that every multiplication gate in my test program also has 2 related input gates and 1 output gate, which might quadruple the total number of gates (depending on whether input and output gates are counted as proper gates or not).

Edit: I ran the tests a bit more often for some of the multiplication amounts above and provided the frequency of the issue occuring as well as the number of rounds executed in total to obtain this frequency to the table above

[lenerd]

Thanks for the detailed report! Can you share the test program(s) you have written? That might help us to resolve the problem.

It looks like there is something wrong with the generation of multiplication triples. It might be connected with the apparently random failures of test cases in OTExtension.

[lumip]

I uploaded the code of my test program. Currently the number of rounds and multiplications per round is adapted by changing the constants and recompiling, which I'll admit is not the nicest way to go about things.. I've also had the whole thing run some more times for the number of multiplications mentioned above to get some idea about the frequency of occurence and added that information in the table above

[lumip]

Is there maybe any idea as to what the problem might be and when it might be fixed?

I have currently implemented a workaround that add a sequence of dummy multiplications with known results to the circuit (with higher multiplicative depth than "production circuit" to ensure that at least one of those dummy multiplications will be the last, checking whether the result is correct and restarting the session if not. However, combined with the stalling issue #110, this is also not really a workable solution as it means that the likelihood to experience a deadlock during a setup phase is increased which turns out to be really annoying...