Elgamal encryption cycle blowup in Miden vm

[nlok5923]

Hey Team!

At RizeLabs we have been designing the encryption architecture for Aze Poker which we are building on top of Polygon Miden. We are implementing barnett smart protocol for fair gameplay by enabling every player to fairly participate in maintaining privacy of the Poker Cards.

In barnett smart protocol the encryption function is defined as

M: Is the point on curve (in case of miden ecgFp5 curve) (We are maintaing a public one to one mapping f(C) -> M where C is plaintext card and M is point on curve)
r: Is the masking factor private to player
G: Generator point (generate point of ecgFp5 in case of Miden VM)
H: aggregated public key

The encryption requires mainly

• Two scalar multiplication
• One addition

Further, the protocol defines an operation remasking (to remask the card before shuffling) to make sure player can't maintain mapping of cards and deduce the original order

The remasking function is defined as

The remasking function requires

• Two scalar multiplication
• Two addition

As, per the game design we are planning to implement procedures encrypt_and_shuffle and remask_and_shuffle in player accounts. To enable players to encrypt/remask and shuffle the cards.

But since the deck contains a total of 52 cards and encrypting/remasking cards would require a total atleast 104 scalar multiplication and atleast 104 additions. Which should be done at each player.

This much amount of computation on user device could affect the UX quite a bit.

Is there any possibility of having some sort precompiles in miden vm so that we can limit the cycle count and make these as native vm operations ?

More details around encryption design is available here

Barnet smart protocol (Mental poker)

• https://geometry.xyz/notebook/mental-poker-in-the-age-of-snarks-part-1
• https://geometry.xyz/notebook/mental-poker-in-the-age-of-snarks-part-2

cc @Dominik1999 @gubloon

[Dominik1999]

Thanks @nlok5923 !

For more context: On a M3 Pro (18gb RAM) calling the gen_mul procedure 26 times in a single note script (this many times we need at least for 13 cards) is taking around 30 seconds to create + consume + state syncing. Considering the fact that this process would occur four times at each player account it would take around 2 minutes which might be feasible for the POC.

However, this is definitively worse UX than player online poker on PokerStars.

Potential alternative: Encrypting outside the VM

An alternative approach could be not to encrypt or decrypt inside the VM. In theory, this can happen outside the VM.

Shuffling:

1. The game account sends a note with 52 cards unencrypted to Alice. The cards are inputs to the note.
2. Alice reads the note inputs and encrypts them outside the VM
3. In a transaction, she
   • injects the array of encrypted cards via NoteArgs
   • shuffles the encrypted array
   • creates a new note to Bob with the encrypted and shuffled array of cards as inputs
4. Bob reads the note inputs and encrypts them outside the VM
5. ...

Dealing:

1. The game account sends Alice two cards of the encrypted deck as note inputs
2. Alice decrypts her cards locally (either inside the VM or outside)

Betting:

1. There is no encryption needed during the betting phase

Revealing:

1. Every player when folding, will send the cards back to the Game Account. There can be a sanity check inside the VM, that at the end there is a full deck.

Potential Attack Vector:

• Alice could sneak in any card twice or she could use a malformatted deck (for a PoC we could have stronger trust assumptions)
• ...

Potential alternative: Using precompiles / chiptles

We could try to speed up el gamal or any other scheme by building a specialized chiplet for the Miden VM. https://0xpolygonmiden.github.io/miden-vm/design/chiplets/main.html .

This might take longer than the 4 weeks we have, but if you wanna give it a try.

[Al-Kindi-0]

An alternative to solve the problem with expensive encryption is to work with a mock encryption scheme. The ElGamal scheme requires a cyclic group (usually of prime order in order to avoid some attacks). What we can do is use the multiplicative sub-group of the field as our cyclic group. This way all operations become just an exponentiation or a multiplication in our base field.
Here is a rough implementation of the idea.
The main thing that is still not clear to me is related to the shuffle argument and how it is implemented in the above.