-
Notifications
You must be signed in to change notification settings - Fork 1.4k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Slow precompiles for alt_bn128 curve #5492
Comments
That's a great job! Looking forward to further progress. |
Thanks for your work, we are reviewing the code. Any progress will be synced here. |
Very glad to see this work! I have two questions:
|
Based on some research, we can discuss whether increasing the duration of individual transactions to avoid operation execution timeouts can solve this issue. |
@yuekun0707 @CarlChaoCarl
The average time of operations after:
So the gain is 6x - 30x for different ops, whereas BN128Pairing gains even more when more pairs are checked It's really hard for us to give any useful and reasonable opinion on possible timeout values, because
So despite the fact that timeout increase seems to be an easier/faster solution for ZkBob I would say that it should have a lesser priority than optimizations and should be considered as last resort |
@r0wdy1 thanks very much for your information, the statistical data shows great improvement! |
Yes current timeout would be sufficient to execute multiple (15-20) pairings with a reasonable amount of pairs in a single transaction, whereas even a single one used to cause timeout but that off course depends on particular node specs. |
@r0wdy1 Great! Thanks for your replay, I have no more questions~ |
@r0wdy1 Hi, the Tron team have modified the maximum execution time of one transaction to 350ms for the NILE Testnet. https://nile.tronscan.org/#/ |
@yuekun0707 we're currently having minor issues with deploying our contracts on Nile for some reason, doing our best to fix it asap. |
@yuekun0707
AFAIK there's supposed to be some log message for operations that take more than 300 ms. |
@r0wdy1 thanks for your tests, we will check the log then~
|
we will probably have an extended guide for public tests but in the meantime here's our staging environment which is a copy of production app. We also use a simplified CLI-like version of UI which allows to quickly do the same transaction again or make multiple transactions with a single command Using console it's very easy to make multiple transaction, for example here's how to send 10 transaction to yourself :
|
@r0wdy1 |
Hello, @lxcmyf! Yes, it is basically correct. The only differences are that:
We executed approximately 100 transactions and received the following stats:
If we assume that the timeout is set to 350 ms we can estimate that roughly the half of these transacations will be reverted due to the timeout on this (relatively weak) configuration. Testing on the Nile looks promising since we didn't catch any timeout yet. But it will be great to understand how close are we to the timeout to grasp the situation completely. |
@AllFi |
I sent 60 transactions to our contract. It looks like there weren't any timeout situations. Here are the transactions' hashes:
Our transactions are quite expensive in terms of energy. 5000 TRX from the faucet is enough for about 20 txs so it is not very convenient. Is it possible to acquire more TRX for testing on this address: |
@AllFi |
We've sent 300 more tx to Nile , no timeouts so far |
@yuekun0707 @lxcmyf is there any updated plan or estimates for timeout increase ? |
@r0wdy1 |
It's very doubtful that there is an efficient implementation of elliptic curve pairings in pure Java. The only optimization with current implementation that we can do is to break our current contract call (which executes two pairing checks) into two transactions , so that each of them would have a single proof verification. That would require a roughly twice less timeout value There also could be some space for optimization with compilation flags, but I'm not really sure |
@yuekun0707 @lxcmyf |
I'm afraid JVM features and specifically garbage collection make it impossible to reach the same performance levels like native applications. As I said we can try to implement at least mathematical optimizations, but this is not a small effort to put it mildly, and besides from developing there would be required a very thorough review and audit. |
Yes, this will not be a simple task. |
为什么eth不会有这个问题,是不是跑不了zk proof...可以在doc里面给出建议,跑不了zk的智能合约,普通的操作都会超时. |
This issue is not network specific but rather related to implementation. We have modified the original field operation implementation to support Montgomery form in pure Java with approximate gains for pairings around 33% (#5611) |
@r0wdy1 |
超时是不是总是出现在固定的几台机器,是否可以考虑增加节点机器的性能 |
This change was made intentionally small, which is why the gains are somewhat limited. Rewriting BigInt could give some more benefits but it's much more challenging and error prone. |
No, it's related to performance of unoptimized code on recommended node configuration. One could spin up some supercomputer that would chew through even that, but this is of course an unviable option. The only option is to optimize the execution and raise timeout appropriately if required so that transactions are processed but spamming doesn't become to easy at the same time |
@r0wdy1 |
@lxcmyf yes , it's ready now |
主网有计划增加到120ms吗?不然在nile上测试通过了,主网仍然会有问题
|
We cannot confirm at the moment. The relevant PR is currently being evaluated, and any updates will be synchronized in a timely manner. |
既然不确定什么时候主网有变动,能否将nile或者shasta的超时时间改回80ms?不然一直在主网调试合约tron的消耗太高了 |
let success := call(gas, 0x08, 0, add(input, 0x20), len, memPtr, 0x20) java-tron/framework/src/test/java/org/tron/common/runtime/vm/IstanbulTest.java Line 146 in ce0e0c6
function callBn256Pairing(bytes memory input) public returns (bytes32 result) { |
@xiangjie256329 |
不需要了,在shasta可以复现,并且调试了无法解决.等你们主网到120ms,再考虑上这类项目吧 |
@xiangjie256329 |
Please track the latest progress on this issue: #5611 |
Can this technology be used to layer-2 scaling solution ZK Rollups? |
If the underlying algorithm used by ZK rollup adopts the above calculation formula, this optimization may be beneficial to ZK rollup. |
@YuMenGuan @tomatoishealthy |
Get it. |
Intro
Timeout restrictions on Tron have previously prevented the ability to deploy certain zkSNARK-based applications. This issue has been identified in the past and the root problem has not yet been addressed ( #4311).
In this prs, we directly address this issue and propose an implementation that solves it ( zkBob#1,zkBob/zksnark-java-sdk#1 ). By optimizing the bn128 precompiles, zk-based apps and zkSNARKs verification processes become usable on Tron.
It’s important to note that these changes will not only enable the zkBob application on Tron, but also a whole class of applications and protocols based on elliptic curve cryptography and pairings in particular. The possibilities brought by ZKP are not limited to privacy focused protocols, some other examples include zk based auth for AA wallets, light clients, zk based bridges, computational integrity enforcing contracts, and many others.
System information
java-tron version:
java -jar FullNode.jar -v
OS & Version: Linux
Branch: master
Expected behaviour
The
verifyProof
method of a contract for checking pairing over alt_bn128 curve as a part of Groth16 proof system which includes 6 point addition, 5 point multiplication and pairing check itself gives an appropriate result given a valid input.Actual behaviour
A contract fails to return the result due to timeout error because of an unoptimized implementation of the bn128 precompiles (Multiplication , Addition , Pairing)
Steps to reproduce the behaviour
Reproducing on private network
It can be checked on Polygonscan (https://polygonscan.com/address/0xa86c511832ead78d30ad49711874a9f3a1dfb840#readContract) , with the same arguments:
[410187940904267791665857625594021464304867517571189176088693585418403627175,3582932279793408241095145848517164196468279227198151416866003392249976328215,21702782062704102408149255137659156834040101148294719406156063531394617768752,458964024542843322412024634467191796783627388968596258037504,1105154793589499054101509063059520053678357711567632030398761789118900390304]
[17319632901362089667297833381115050472198619632678725143485052131880736564716,20217952180782984327874966839451172866880046964759060634104328470666346490787,14675072293281706791212610449476963932780136199834552157253791069835791205313,11523869594945451880407802780789187832894590986555492595351670286111658956891,3618836117018041122057960110621015024190242066995639123523823804179020820127,17452347979391447598200144953804022165728450595367847105208004839301667143347,10758418988168490454233654079316113438289985487422580576512164625214747833303,16113585132297177719187882899369575704186199591529360947329945124938113973184]
We have created a dedicated repo for this particular purpose: https://github.com/zkBob/tron-local . It contains both a script to deploy contract and to call the
verifyProof
method.FullNode.jar
intobin
folder./scripts/run.sh
./scripts/deploy.sh
TRANSFER_VERIFIER_ADDRESS
in.env
./scripts/verify.sh
returnsclass org.tron.core.vm.program.Program$OutOfTimeException : CPU timeout for 'SWAP1' operation executing
Reproducing on testnet
The same contract is also deployed on Shasta and returns the same error :
https://shasta.tronscan.org/#/contract/TPf7skGEB8h7VPSbd2S1CfxjWSJfPKHpQG/code
Backtrace
The text was updated successfully, but these errors were encountered: