Verifying Modular exponentiation operation in etherum

Question

I have Alice who should do some cryptographic operations off-chain. Then a smart contact has to verify equality by performing Modular exponentiation operation. I attached an image of the off-chain and on-chain operations. Is there any library that can verify the last equality in the image. I tried to write the math here, but writing math equations is not allowed.

alberto · Answer 1 · 2019-06-07T14:15:40.540

From the answer of @Julien Marchand it's possible to create the function viewing the attributes of the precompiled contract:

https://github.com/ethereum/go-ethereum/blob/master/core/vm/contracts.go#L226

Address: 0x05 https://github.com/ethereum/go-ethereum/blob/master/core/vm/contracts.go#L56

The verify function is untested but maybe could help.

pragma solidity ^0.5.8;

contract ModularCheck {

    // Untested code
    function verify(uint256 _D, uint256 _C, uint256 _c, uint256 _h, uint256 _z, uint256 _g, uint256 _l, uint256 _modulus) public returns (bool){
        uint256 exp1 = modExp(_C, _c, _modulus);
        uint256 exp2 = modExp(_h, _z, _modulus);
        uint256 exp3 = modExp(_g, _l, _modulus);

        if(_D == mulmod(mulmod(exp1,exp2, _modulus),exp3, _modulus)) return true;

    }

    function modExp(uint256 _b, uint256 _e, uint256 _m) public returns (uint256 result) {
        assembly {
            // Free memory pointer
            let pointer := mload(0x40)

            // Define length of base, exponent and modulus. 0x20 == 32 bytes
            mstore(pointer, 0x20)
            mstore(add(pointer, 0x20), 0x20)
            mstore(add(pointer, 0x40), 0x20)

            // Define variables base, exponent and modulus
            mstore(add(pointer, 0x60), _b)
            mstore(add(pointer, 0x80), _e)
            mstore(add(pointer, 0xa0), _m)

            // Store the result
            let value := mload(0xc0)

            // Call the precompiled contract 0x05 = bigModExp
            if iszero(call(not(0), 0x05, 0, pointer, 0xc0, value, 0x20)) {
                revert(0, 0)
            }

            result := mload(value)
        }
    }
}

@albeerto, can I test this code on remix. or should I have account on etherum blockchain to call the contract at 0x05 — Heba Mohsen, Jun 07 '19 at 20:41
But remix has the precompiled contract 0x05 ? in other words, on the current time, I do not have access to the real etherum blockchain so can I test it locally on remix — Heba Mohsen, Jun 07 '19 at 21:46
Yes, it has, you only need to copy the code and paste on remix. If you prefer, copy only the function modExp() to your contract. — alberto, Jun 07 '19 at 22:02
Could you please suggest how can I create values to test your answer. In other words, How to generate values for D,C,c,l,z to test your contract. — Heba Mohsen, Jun 10 '19 at 05:56
These values are generated offchain (as you say, and I don't know how to generate them), thus the verify function is untested. I only wrote the verify function to show how to use modExp() for your particular case. modExp() function can be tested passing the base, exponent and modulus as attributes of the function. — alberto, Jun 10 '19 at 07:35

score 3 · Accepted Answer · answered Jun 07 '19 at 11:35

Modular exponentiation can be computed on Ethereum using a precompile, which is included in all client implementations since the Byzantium fork (cf EIP-198) at address 0x05. Precompiles can be called from a Solidity smart-contract using assembly code.

I couldn't find a proper smart-contract calling the modular exponentiation precompile but as an example, calling the ecmul (at address 0x07) can be done using the following code:

  function ecmul(uint256 x, uint256 y, uint256 scalar) public constant returns(uint256[2] p) {
    // With a public key (x, y), this computes p = scalar * (x, y).
    uint256[3] memory input;
    input[0] = bx;
    input[1] = by;
    input[2] = scalar;
    assembly {
      // call ecmul precompile
      if iszero(call(not(0), 0x07, 0, input, 0x60, p, 0x40)) {
        revert(0, 0)
      }
    }
  }

I want to test the code in practice, what should I do? – Heba Mohsen Jun 07 '19 at 20:45 — Heba Mohsen, Jun 07 '19 at 20:45

Verifying Modular exponentiation operation in etherum

2 Answers2

Linked