data61 / MP-SPDZ

Versatile framework for multi-party computation
Other
953 stars 279 forks source link

Clarification on `sfix` range behavior #1448

Closed mhchia closed 3 months ago

mhchia commented 4 months ago

Based on the documentation Compiler.types.sfix and the discussion in GitHub Issue #512, the range of sfix is [-2**(k-f-1), 2**(k-f-1)).

I've tried the following scenarios:

  1. When sfix is initialized with a value outside the range, a CompilerError: Value out of fixed-point range is raised as expected.
    
    from Compiler.types import sfix

f = 16 k = 31 sfix.set_precision(f, k)

This fails as expected, with the error: Compiler.exceptions.CompilerError: Value out of fixed-point range [-16384, 16384)

too_large_sfix = sfix(2 ** (k - f - 1))


2. When `sfix` is initialized with a value within the range, but the result exceeds the range after operations, no error is raised.
```python
# Example 1:
largest_sfix = sfix(2 ** (k - f - 1) - 1)
# The value is outside the range, but no error occurs. Is this safe?
too_large = largest_sfix + sfix(1)

# Example 2:
# The value is out of the range, but no error occurs. Is this safe?
largest_sfix_computed = sfix(2) ** sfix(k - f - 1)

Is it the intended behavior that no error is raised when sfix contains a value larger than the range after operations? If so, is it still safe to use this out-of-range sfix, or should we implement checks to prevent this overflow from happening?

Thank you!

mkskeller commented 4 months ago

This is indeed the intended behavior. It would not make sense trying to predict the range of operations as even the product of two numbers within the standard range can be outside: 1000*1000. As to whether it's safe depends on the application and the protocol as there are a number of questions:

Lastly, what do you mean by preventing overflow? If the result of an operation is outside the range, there is no way to prevent this as the correct result simply does not fit. The only solution I can think of is to compute a secret correctness bit from range checks akin to the NaN bit in the common floating-point representation. However, even for this you would need to increase the range to the point that it could fit the correct result of possible operations as the check would be incorrect if the result of an operation is outside the range in the first place.

mhchia commented 4 months ago

Thank you for the detailed explanation.

Lastly, what do you mean by preventing overflow?

Ah, I meant detecting whether sfix falls out of the range after an operation.

Just wanted to confirm further: if we know the inputs are within a certain range and we know the computation, is it a standard approach to configure f so that the range will be sufficient? For example, if the computation is x^2 and we expect every input x to be less than 1000, should we set f to something like 10 to make the range [-2^20, 2^20) so that results don't fall out of range?

mkskeller commented 4 months ago

Reducing f does increase the range but it does so at the cost of precision. With f=10, the smallest non-zero value is about 0.001 (1/1024), which might too much depending on the application. I've found that even simple deep learning applications require f=14 and more, but yours might be different. The other way of increasing the range is of course increasing k. MP-SPDZ is well-prepared for k up to 48, but you can further increase by following the instructions when you try higher values.

mhchia commented 4 months ago

Thanks for the answer. We're implementing statistics operations so it should be pretty similar to the case of ML I think. One more question:

MP-SPDZ is well-prepared for k up to 48

I set k to be 48 and it just works with the default bit length of sint modulo prime (-F). If I wanted to set k to be larger, would I need set a larger bit length?

mkskeller commented 4 months ago

The k parameter is independent of -F. If k becomes too large, you will get an error message telling you to recompile the virtual machine, for example after putting MOD = -DRING_SIZE=512 into CONFIG.mine.

mhchia commented 4 months ago

Ah I saw in sfix.set_precision

Generally, 2*k must be at most the integer length for rings and at most m-s-1 for computation modulo an m-bit prime and statistical security s (default 40).

Does this "the integer length for rings" refer to -R? And should we care about this only if we're using a MPC protocol that uses rings instead of fields?

What's the tradeoff if we're using a larger k?

mkskeller commented 4 months ago

Does this "the integer length for rings" refer to -R? And should we care about this only if we're using a MPC protocol that uses rings instead of fields?

Yes in both cases.

What's the tradeoff if we're using a larger k?

What do you mean by trade-off?

mhchia commented 3 months ago

What do you mean by trade-off?

I meant if we're using a larger k, would there be more computation overhead?

Generally, 2*k must be at most the integer length for rings and at most m-s-1 for computation modulo an m-bit prime and statistical security s (default 40).

Sorry, I think I'm a bit confused and wanted to clarify again. According to the description above:

mkskeller commented 3 months ago

What do you mean by trade-off?

I meant if we're using a larger k, would there be more computation overhead?

Yes, that's usually the case even if the computation modulus doesn't change.

Generally, 2*k must be at most the integer length for rings and at most m-s-1 for computation modulo an m-bit prime and statistical security s (default 40).

Sorry, I think I'm a bit confused and wanted to clarify again. According to the description above:

* If I choose a protocol with a field (e.g., MASCOT) with the default bit length of 64 bits and statistical security of 40 bits, should I ensure k is at most m-s-1 (64-40-1=23)? This seems smaller than the default k=31. Did I misunderstand the bit length, or did I use the wrong default bit length?

The default bit length for primes is 128 to accommodate for the default parameters.

* For a protocol with rings and a default bit length of 64 bits, should k be ≤ 64/2 = 32?

Yes, if using division.

mhchia commented 3 months ago

Thank you for the clarification, I appreciate your help. I'll look into it more thoroughly.