Implementation of MODPOW opcode

[igormcoelho]

We propose the implementation of a modular exponentiation opcode for NeoVM.
The reason is that some dapp may require implementing RSA cryptography (which is our case on SciChain) and this is also fundamental for other number theory implementations, including zero-knowledge.

Currently, BigIntegers are limited to 32-bytes, but modular exponentiation may require a bit more than this, so one solution is to threat inputs and outputs as bytearrays (currently limited to 1024 bytes).

The initial proposal for MODPOW is to calculate: x = mul*base^{exponent} mod p
Values base, exponent, p and mul could be possibly passed in two options: (i) as an array [base, exponent, p, mul]; (ii) four independent elements taken from stack.
I prefer option (i), and it would be nice to allow mul to be optional and naturally assume value 1.
If exponent is negative, it would be nice to have the calculation of the modular inverse.
All elements would be converted to BigInteger for the calculation (from bytearray), and the final result would be returned as bytearray (thus, not strictly violating BigInteger limits on NeoVM).
On C#, BigInteger ModPow could do the exponentiation and ModularInverse function could do the inverse.

The mul could be eliminated by replacing it by two quadratic exponents with a subtraction and division (as Ethereum did on EIP 198), however that would require us to allow subtraction and division of huge numbers too (over BigInteger limit). We need to see if this mul already solves most general problems involving modular exp applications.

To establish a fair price for the operation it would be nice to have some time experiments and see the actual impact, but it won't be more costly than VERIFY itself.

MODPOW opcode could possibly have opcode 0xb0, although this is a discussion for later.
MODPOW could be acompanied later with another interesting operation which is scalar multiplication for elliptic curve points (possibly opcode 0xb1). This would allow us to implement CHECKSIG, CHECKMULTISIG and VERIFY directly on NeoVM, allowing users to switch cryptographic curves if they desire.

It would be a pleasure to have some voices of the crypto specialists in the community, in order to ensure a nice proposal (we can also create a NEP for this, if necessary).

[erikzhang]

We can prefix the public key so that it is easy to choose a curve or algorithm when executing VERIFY.

[igormcoelho]

What about RSA? We may need to support onchain decryption too. This could also be done by modpow.

[erikzhang]

Does onchain decryption not reveal the private key?

[igormcoelho]

It reveals, but the key is only used in a single step and dropped if this command is activated, so it does not matter being exposed anymore (at this point the users loses his bond if smart contract manages to decrypt hidden info). I agree this looks like an unusual application, but other blockchains are migrating to this model too, allowing users to implement manually their own crypto. In this sense its better to have an opcode like this than one for decryption, por example. I think that curve parameters may be put on storage, and user account could be basically : load curve data, perform point verification.

[igormcoelho]

I will try to devise an alternative without RSA (perhaps ECDH, although this will require point multiplication...), because we need to get this going asap, but community should strongly consider this modpow, perhaps as interop if more acceptable ("Neo.Crypto.ModPow" and "Neo.Crypto.ModInverse")

[jsolman]

Onchain decryption sounds broken to me; couldn’t the message be intercepted and an alternative one relayed to consensus nodes first?

[vncoelho]

I think that the idea is that we really want to decrypt it, @jsolman, no matter who sends the invoke.
The decryptation is just activated after some initial conditions in the SC.

[igormcoelho]

One example for application is the AnonyTree on SciChain. For now, it's beggining as a part of DRandLib, but soon will be moved to SciChain repo: https://github.com/igormcoelho/DRandLib
By having decryption, we could enforce that smart contract would validate information if necessary... since we won't have that, community will need to validate that through a majoritary voting... for us that's possible (not perfect though), but there will be scenarios where only onchain decryption will do the job.

[igormcoelho]

@erikzhang just to exemplify a simple application that uses this (considering ECDSA).
Person A has pubkey pub_A and private key priv_A.
Person B has priv_B and pub_B.
Both will need to secretly define who will pass to next step, without cheating. So both calculate S = priv_A * pub_B = priv_B * pub_A, and use it together with some entropy to decide who will be next. Suppose A wins (and B loses). Using S, a new private key priv_S is derived, and pub_S is used for the next step together with some information from A. However.... B could try to cheat and pretend he won! But in this case, Person A could publish private key priv_A, and the Smart Contract could calculate S and it will know that B is a liar.
In this situation, B would lose its bond, or receive any other punishment, automatically from the smart contract.
However, since we don't have this opcode now, we will need to rely on a community voting to punish people based on public evidence... I think this works for us, because of the nature of the application, but it would be much better to be able to calculate that onchain.

[shargon]

As a syscall it couldn't damage to anyone, so is fine for me.

[vncoelho]

ahueahuehaea, I did not remember about that Milestone.

@shargon, let's do it, I remember that this would proportionate very good applications!

[igormcoelho]

This should be an EXTENSION to neovm...not in blockchain itself.. lets see ;)

[lock9]

@igormcoelho what are next steps? Is this going to be added to this repository?

[erikzhang]

I found that the MODPOW of the built-in BigInteger has only 3 parameters.

https://github.com/dotnet/runtime/blob/a6acafd32d907eecd1359317fb340bced6f92210/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs#L907

[igormcoelho]

I found that the MODPOW of the built-in BigInteger has only 3 parameters.

Indeed the first multiplication can be done separately.. no need to require 4 params.

[erikzhang]

Does it have other scenarios besides on-chain decryption?

[igormcoelho]

Does it have other scenarios besides on-chain decryption?

Not just decryption, which is strange (but useful for commit-reveal schemes), as the most amazing use-case is the ability of a user provide its own cryptography. To fulfill that in a practical manner (not being costly), and to avoid stateless situation during verifications (not depend on storage), I would suggest on Neo project to have some ability to store global constants. Maybe put a very high GAS cost on that (on Put, and very cheap on Get), but we could deploy constants for elliptic curve parameters, and just load them on verification, without breaking stateless invariants (as they will not change).

The interesting thing is that, with constants, we cannot break stateless invariants, because if we try to read them before deploying, verification would fail (so it couldn't be put on blocks or mempool). And after it's on block, any constant it requires must be kept forever (so it will never break any state invariant).

So I propose to have this MODPOW here, together with "Neo.Const.Put" (expensive on GAS) and "Neo.Const.Get" (cheap on GAS), on the Neo core project (see neo-project/neo#2040)