Precompile: 0x05 modexp

[ChihChengLiang]

No description provided.

[ChihChengLiang]

Scroll has an on going implementation

scroll-tech/zkevm-circuits#520

[adria0]

It seems that Scroll MODEXP precompile is not exactly the same than Ethereum Mainnet.
https://docs.scroll.io/en/technology/chain/differences/#precompiled-contracts

[lispc]

yes..

It seems that Scroll MODEXP precompile is not exactly the same than Ethereum Mainnet. https://docs.scroll.io/en/technology/chain/differences/#precompiled-contracts

yes.. may not suitable for a type1 zkevm

[adria0]

yes..

It seems that Scroll MODEXP precompile is not exactly the same than Ethereum Mainnet. https://docs.scroll.io/en/technology/chain/differences/#precompiled-contracts

yes.. may not suitable for a type1 zkevm

Any plan, for the moment, to release a Type-1 MODEXP @lispc ?

[lispc]

yes..

It seems that Scroll MODEXP precompile is not exactly the same than Ethereum Mainnet. https://docs.scroll.io/en/technology/chain/differences/#precompiled-contracts

yes.. may not suitable for a type1 zkevm

Any plan, for the moment, to release a Type-1 MODEXP @lispc ?

Maybe not within a foreseeable future. We collected usage of modexp from mainnet, and found most (maybe all..) of them are U256 input. Supporting only u256 is simpler, so we chose to support only u256.

[adria0]

@ed255 @ChihChengLiang some notes about this:

It seems that we need to implement variable-length arithmetics, because the bigint lengths are not fixed. So, if building EXP was complex, let's do mainly looping with MULADD and MULMOD with variable length of base exponent and modulus is not trivial at all.

Let's say that this could be done in common Halo2 frontend, in the sake of building new halo2 reusable chips, that could be ok, but I see that nobody is going to use this chips because serious crypto is done with fixed length not variable-length-everything, so I do not expect to be reusable at all.

Also this is not a very used precompile, and exists for verifying RSA ( that typically is 2048/4096) signatures, that is more in the "corporate" world that in the crypto space.

So, a loooot of work for a barely-used and probably non-reusable circuit. Anyway, there's the precompile and needs to be implemented.

I checked some implementations:

Scroll: only supports up to 256 bits, and does not plan to support the full precompile. Unsure if we can reuse it for variable-length.
Polygon: also only supports up to 256 bits.
zkSync: just is not implemented. But looking for more implementations I found that zkSync is following a strategy to implement precompiles using the EVM, so exists an implementation written in YUL there

So this gives some different strategies that we can follow (at least):

1. Implement, as usual, as a halo2 circuit with the usual rust frontend
2. Use EVM code installed in the precompile address (note that we can use this also for blake2f and RIPEMD-160
3. Implement as a HALO2 circuit, but try to find how to write a frontend to handle it with less drama (something like powdr?)