Closed CryptoPascal31 closed 1 year ago
emilypi
commented
1 year ago 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
commented
1 year ago 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:
(< ), (= ), ...(& ), (xor ), ...(+ ), (- )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
commented
1 year ago 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:
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
commented
1 year ago 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:
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:
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:
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:
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.
jwiegley
commented
1 year ago Excellent analysis, @CryptoPascal31, you've given us some good fodder for analysis.
CryptoPascal31
commented
1 year ago Fixed by: https://github.com/kadena-io/pact/pull/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.
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. GIntegerOpCostWhen I look at the code: https://github.com/kadena-io/pact/blob/e8f5899b2512ccd7e05b4523b20cbc6f8286f736/src/Pact/Gas/Table.hs#L345 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:
=> I suggest increasing the operand penalty threshold to 2 ^ 256, and maybe correcting the quadratic gas calculations accordingly.