Issue with recombine function at mpyc/thresha.py

[mvievaz]

Executing my program I found an error on mpyc/thresha.py:

Traceback (most recent call last):
  File "uvloop/cbhandles.pyx", line 63, in uvloop.loop.Handle._run
  File "/.local/lib/python3.10/site-packages/mpyc/asyncoro.py", line 451, in <lambda>
    task.add_done_callback(lambda t: _reconcile(decl, t))
  File "/.local/lib/python3.10/site-packages/mpyc/asyncoro.py", line 375, in _reconcile
    givn = task.result()
  File "/.local/lib/python3.10/site-packages/mpyc/asyncoro.py", line 304, in _wrap_in_coro
    return await awaitable
  File "/.local/lib/python3.10/site-packages/mpyc/asyncoro.py", line 292, in __await__
    val = self.coro.send(None)
  File "l/.local/lib/python3.10/site-packages/mpyc/runtime.py", line 568, in output
    y = recombine(field, points)
  File "/.local/lib/python3.10/site-packages/mpyc/thresha.py", line 104, in recombine
    s = share_i[h]
IndexError: list index out of range

To reproduce this error we have to execute the following code:

from mpyc.runtime import mpc

bits= 64

async def integer_div(a, b):

    sec_int = mpc.SecInt(bits)
    ret = sec_int(0)
    while await mpc.output(mpc.ge(a, b)):
        ret = ret + sec_int(1)
        a = a - b

    return ret

async def mod_inverse(b, m):

    original_m = m
    sec_int = mpc.SecInt(bits)
    sec_int_one = sec_int(1)
    x0, x1 = sec_int(0), sec_int(1)
    if await mpc.output(mpc.eq(m,sec_int_one)):
        return 0
    while await mpc.output(mpc.ge(b,sec_int(2))):
        q = await integer_div(b, m)
        b2 = m
        m = mpc.mod(b, m)
        b =  b2
        x0, x1 = x1 - q * x0, x0
    if await mpc.output(mpc.lt(x1,sec_int(0))):
        x1 = x1 + original_m
    return x1

async def main():

    await mpc.start()
    sec_int = mpc.SecInt(bits)
    print("TESTING INVERSE-MOD")
    # Example of inverse mod with 3 and 7 (sol = 5)
    b = sec_int(3)
    m = sec_int(7)
    sol = await mod_inverse(b,m)
    print(await mpc.output(sol))
    await mpc.shutdown()

if __name__ == "__main__":
    mpc.run(main())

We are testing this code with 3 players on local. This are the output for each player (We tested various times and we get the same errors on different players. Not always the same error for the same player)

PLAYER 0 (HANGED)

python3 HEMPC/test.py -M3 -I0 
2024-07-17 08:57:16,773 Start MPyC runtime v0.10
2024-07-17 08:57:18,588 All 3 parties connected.
TESTING INVERSE-MOD
2024-07-17 08:57:18,704 Exception in callback UVTransport._call_connection_lost
handle: <Handle UVTransport._call_connection_lost>
Traceback (most recent call last):
  File "uvloop/cbhandles.pyx", line 69, in uvloop.loop.Handle._run
  File "uvloop/handles/basetransport.pyx", line 169, in uvloop.loop.UVBaseTransport._call_connection_lost
  File "/.local/lib/python3.10/site-packages/mpyc/asyncoro.py", line 125, in connection_lost
    self.runtime.unset_protocol(self.peer_pid)
  File "/.local/lib/python3.10/site-packages/mpyc/runtime.py", line 4181, in unset_protocol
    self.parties[self.pid].protocol.set_result(None)
asyncio.exceptions.InvalidStateError: invalid state

PLAYER 1

python3 HEMPC/test.py -M3 -I1 
2024-07-17 08:57:14,758 Start MPyC runtime v0.10
2024-07-17 08:57:18,588 All 3 parties connected.
TESTING INVERSE-MOD
2024-07-17 08:57:18,644 Unhandled error in exception handler
context: {'message': 'Exception in callback <function mpc_coro.<locals>.typed_asyncoro.<locals>.<lambda> at 0x77052d181000>', 'exception': IndexError('list index out of range'), 'handle': <Handle mpc_coro.<locals>.typed_asyncoro.<locals>.<lambda>>}
Traceback (most recent call last):
  File "uvloop/cbhandles.pyx", line 63, in uvloop.loop.Handle._run
  File "/.local/lib/python3.10/site-packages/mpyc/asyncoro.py", line 451, in <lambda>
    task.add_done_callback(lambda t: _reconcile(decl, t))
  File "/.local/lib/python3.10/site-packages/mpyc/asyncoro.py", line 375, in _reconcile
    givn = task.result()
  File "/.local/lib/python3.10/site-packages/mpyc/asyncoro.py", line 304, in _wrap_in_coro
    return await awaitable
  File "l/.local/lib/python3.10/site-packages/mpyc/asyncoro.py", line 292, in __await__
    val = self.coro.send(None)
  File "/.local/lib/python3.10/site-packages/mpyc/runtime.py", line 568, in output
    y = recombine(field, points)
  File "/.local/lib/python3.10/site-packages/mpyc/thresha.py", line 104, in recombine
    s = share_i[h]
IndexError: list index out of range

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "uvloop/loop.pyx", line 2415, in uvloop.loop.Loop.call_exception_handler
  File "/.local/lib/python3.10/site-packages/mpyc/asyncoro.py", line 461, in exception_handler
    task = context['handle']._args[0]
AttributeError: 'uvloop.loop.Handle' object has no attribute '_args'
Traceback (most recent call last):
  File "/test.py", line 46, in <module>
    mpc.run(main())
  File "/lib/python3.10/site-packages/mpyc/runtime.py", line 200, in run
    return self._loop.run_until_complete(f)
  File "uvloop/loop.pyx", line 1515, in uvloop.loop.Loop.run_until_complete
RuntimeError: Event loop stopped before Future completed.

PLAYER 2

python3 HEMPC/test.py -M3 -I2 
2024-07-17 08:57:18,581 Start MPyC runtime v0.10
2024-07-17 08:57:18,588 All 3 parties connected.
TESTING INVERSE-MOD
2024-07-17 08:57:18,644 Unhandled error in exception handler
context: {'message': 'Exception in callback <function mpc_coro.<locals>.typed_asyncoro.<locals>.<lambda> at 0x7b9f927541f0>', 'exception': IndexError('list index out of range'), 'handle': <Handle mpc_coro.<locals>.typed_asyncoro.<locals>.<lambda>>}
Traceback (most recent call last):
  File "uvloop/cbhandles.pyx", line 63, in uvloop.loop.Handle._run
  File "/.local/lib/python3.10/site-packages/mpyc/asyncoro.py", line 451, in <lambda>
    task.add_done_callback(lambda t: _reconcile(decl, t))
  File "/.local/lib/python3.10/site-packages/mpyc/asyncoro.py", line 375, in _reconcile
    givn = task.result()
  File "/.local/lib/python3.10/site-packages/mpyc/asyncoro.py", line 304, in _wrap_in_coro
    return await awaitable
  File "/.local/lib/python3.10/site-packages/mpyc/asyncoro.py", line 292, in __await__
    val = self.coro.send(None)
  File "/.local/lib/python3.10/site-packages/mpyc/runtime.py", line 568, in output
    y = recombine(field, points)
  File "/.local/lib/python3.10/site-packages/mpyc/thresha.py", line 104, in recombine
    s = share_i[h]
IndexError: list index out of range

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "uvloop/loop.pyx", line 2415, in uvloop.loop.Loop.call_exception_handler
  File "/.local/lib/python3.10/site-packages/mpyc/asyncoro.py", line 461, in exception_handler
    task = context['handle']._args[0]
AttributeError: 'uvloop.loop.Handle' object has no attribute '_args'
Traceback (most recent call last):
  File "/test.py", line 46, in <module>
    mpc.run(main())
  File "/.local/lib/python3.10/site-packages/mpyc/runtime.py", line 200, in run
    return self._loop.run_until_complete(f)
  File "uvloop/loop.pyx", line 1515, in uvloop.loop.Loop.run_until_complete
RuntimeError: Event loop stopped before Future completed.

We tested with 2 players and it work, but the errors appears when we started to use more than 2 players.

I hope this issue can help to improve the repo and we can find a solution for this problem. Thanks for your work at MPyC :)

[lschoe]

Hi, yes, the problem is that you use mpc.mod(b, m) where m is not a public value. The function mpc.mod() calls mpc._mod() and there this constraint applies.

This constraint will be lifted in the near future say. The raw material to handle the general case of a secret-shared m is already present in MPyC as we need it to work with secure (secret-shared) class groups.

So, if you add this line mpyc.secgroups import _divmod at the top of your program, then you can replace the call to mpc.mod()by:

        _, m = _divmod(b, m)

Note that _divmod() gives you the secure integer division with remainder that you are aiming for with your program. Actually, because your program reveals the outcomes of intermediate tests as in while await mpc.output(mpc.ge(a, b)), it is not secure (not privacy-preserving). The solution underlying _ divmod() avoids revealing any intermediate values.

[mvievaz]

Hi, thanks for your help!

We tested and it work perfectly. We close the issue .Thanks for your note too ;)

The code is attached in case someone needs it in the future:

from mpyc.runtime import mpc
from mpyc.secgroups import _divmod

bits= 64

async def mod_inverse(b, m):

    original_m = m
    sec_int = mpc.SecInt(bits)
    sec_int_one = sec_int(1)
    x0, x1 = sec_int(0), sec_int(1)
    if await mpc.output(mpc.eq(m,sec_int_one)):
        return 0
    while await mpc.output(mpc.ge(b,sec_int(2))):
        b2 = m
        q, m = _divmod(b, m)
        b =  b2
        x0, x1 = x1 - q * x0, x0
    if await mpc.output(mpc.lt(x1,sec_int(0))):
        x1 = x1 + original_m
    return x1

async def main():

    await mpc.start()
    sec_int = mpc.SecInt(bits)
    print("TESTING INVERSE-MOD")
    # Example of inverse mod with 3 and 7 (sol = 5)
    b = sec_int(3)
    m = sec_int(7)
    sol = await mod_inverse(b,m)
    print(await mpc.output(sol))
    await mpc.shutdown()

if __name__ == "__main__":
    mpc.run(main())