Suggestion => reduce big operands gas penalty

[CryptoPascal31]

Since a couple of days, I'm playing with ZK proofs.

A lot of ZKsnarks circuits use the MiMC hash: https://eprint.iacr.org/2016/492.pdf
which is simple and ZK circuits friendly.
As an example, Tornado Cash uses this algorithm a lot to build its Merkle tree.

On EVM, there are some relatively efficient ASM implementations:
https://github.com/iden3/circomlibjs/blob/main/src/mimcsponge_gencontract.js

I tried to implement myself with Pact and this is very straightforward. Just a dozen of lines of Code and voila !!
https://github.com/CryptoPascal31/pact-mimc/blob/main/pact/contracts/mimc.pact

The core of the algorithm is made of modular 256 bits/256 bits multiplications and additions.

BUT: It appears that the gas usage is too high => 27k for a single hash !

I've done benchmarks using (env-gaslog). And it appears that roughly 90% of the gas is spent by the operands size penalty. GIntegerOpCost

When I look at the code:

pact/src/Pact/Gas/Table.hs

Line 345 in e8f5899

intCost :: Integer -> Gas

I see that there is an arbitrary threshold of 10^30 (roughly 100 bits) for "cheap" operations. And after that the gas is charged quadratically (9 for a 256bits operand). => And thus a 256 bits x 256 bits multiplication costs 21 gas: 3 + 2 x 9

On the EVM side, since this is the native size, 256 bits operation can be made for free.

---

As a conclusion:

• It looks like the 10^30 limit has been defined arbitrarily
• I know that touching gas is very sensitive, but on a modern 64 bits computer with gigs of RAM, 256 bits operations shouldn't be a big issue.
• The EVM handles 256 operations for free.
• Unleash some artificial limits when working with ZK profs.

=> I suggest increasing the operand penalty threshold to 2 ^ 256, and maybe correcting the quadratic gas calculations accordingly.

[emilypi]

This is an interesting idea. We could certainly come up with a gas cost for our integers that's aware of what native operations we care to support without penalty, but I'd want to hear from @jmcardon @jwiegley on this one. Your assessment of the way we calculate the threshold seems correct, though, I doubt it was arbitrary.

[CryptoPascal31]

My point of view:
Since Kadena is becoming a ZK capable blockchain, Pact should be able to do 256 bits arithmetic without restriction for most "integers only" operations:

• Comparison operators (< ), (= ), ...
• Bitwise operators (& ), (xor ), ...
• Additions: (+ ), (- )
• Modulo
• Multiplication
• Exponentiation (for the first operand)
• Shifting (for the first operand)

Not sure about division and about "bastards" operators like (exp ) or (ln ) (that shouldn't accept integers anyway)

This is very important to benefit from all the research, and development effort made around EVM the last couple of years.

[jwiegley]

Hi @CryptoPascal31, I'm not sure about making the operations free just yet (we have always charged something as a factor of integer size), but I do agree that if ZK operations are going to become common on chain, we should change the threshold in this case to not penalize them.

Ideally the measure should be this:

• Measure the wall-clock time it takes to perform a hash, in nanoseconds.
• Divide this by 2,500.
• This should approximate the gas cost on an "average" machine (say, an Intel box from 2018, like my computer).

I can easily setup a test with your MiMC algorithm to determine how out of line we are, but your assessment sounds reasonable to me.

[CryptoPascal31]

My computer is a little bit old compared as "a middle range 2018 computer".

It's an intel i5 from 2011. According to some benchmarks I found, it may be something like 20% slower than your "reference".

I did many tests, to compare execution time and Gas. It was very interesting. Feel free to comments and criticize. I'm happy to discuss the subject further, or to answer to questions if something is not clear. I attach the the code if you want to reproduce my tests.

All of my tests are done by running 300 hashes in a row:

(env-gasmodel "table")
(env-gaslimit 10000000000000000)
(env-gas 0)

(let ((func (lambda (x) (feistel-hash 53 {'L:0, 'R:0}))))
  (map (func) (enumerate 1 300))
)

(let ((total-gas (env-gas)))
  (print (format "Total Gas: {}\nGas per Hash: {}" [total-gas (/ total-gas 300)]))
) 

---

Test 1

---

I try to do a "calibration", by removing all the math from my code. I've just kept the plumbery:
fold, function calls, binds, objects creation.

Roughly per hash:

• 1100 non-native function calls
• 220 binds (2 variables)
• 220 objects creation (2 variables)

Total execution time: 4.3s
Time per hash: 14.3 ms
Gas per hash: 1,991
Average time per gas: 7182 ns

7128 ns is much more than you expected. 2 possibilities:

• My computer is a little bit too slow.
• Some Pact operations (function calls and/or binds and/or objects creation) are under-priced.

---

Test 2

---

I reintroduce the maths operations in my code, but in degraded mode. I force all calculations to use only 8 bits integers < 255.

Roughly per hash:

• 660 multiplications
• 660 additions
• 880 modulo
• 1100 non-native function calls
• 220 bind
• 220 object creations

Total execution time: 7.2s
Time per hash: 24.0 ms
Gas per hash: 5,511
Average time per gas: 4355 ns

Differential calculation (Test 2 - Test 1)

Try to isolate the cost of the math only without the plumbery.

Time per hash: 9.7 ms
Gas per hash: 3,520
Average time per gas: 2755 ns => As expected.

Looks like the price of the math operation (+), (*), and (mod) have in average the fair price.

---

Test 3

---

I restore back my code to the original, using the 256 bits constants. And thus the calculations are done now with big integers.

Roughly per hash:

• 660 (256x256) multiplications
• 220 (256+8) additions
• 440 (256+256) additions
• 880 (512/256) modulos
• 1100 non-native function calls
• 220 bind
• 220 object creations

Total execution time: 8.4s
Time per hash: 28.0 ms
Gas per hash: 27,147
Average time per gas: 1031 ns

Differential calculation (Test 3 - Test 2)
Try to measure the impact of big integers

Time per hash: 4 ms
Gas per hash: 21,636
Average time per gas: 184 ns => (Pact is a thief !!! ... I want a gas refund)

The impact of using 256 bits integers instead of 8 bits integer is relatively small in terms of time, but huge in terms of gas.

I did some others test trying to isolate the cost of a single operations. And they confirm my conclusions.

• Some basic functions (functions calls, bind, object creations) seems under-priced, relatively to basic math.
• Math operations are relatively cheap in terms of time. I feel like most of the time is taken by Pact/Haskell code, instead of the operation itself (btw maybe you should reconsider the price of 3 gas for (*), relatively to (+) and (mod).
• The expensive penalty for 256 bits operands price does not make sense (x19 for (+) and x6 for (*)), for only +40% execution time.

pact-zk-hashes_gitthub_issue.tar.gz

[jwiegley]

Excellent analysis, @CryptoPascal31, you've given us some good fodder for analysis.

[CryptoPascal31]

Fixed by: #1272

The gas usage for my hash computation has been divided by 5.
This is still 3 roughly times worse than the EVM reference implementation. But it does perfectly fits my needs.
And obviously I don't expect that an high level implementation in Pact would compete with an assembly implementation running on the EVM.