New host function for bn254 G1 MSM

[jayz22]

In https://github.com/orgs/stellar/discussions/1772#discussioncomment-14489791 we added three host functions for bn254 in protocol 25.

These functions provides sufficient curve support (in parity with Ethereum). However in some use cases, the contract cost is still much higher than the current Soroban's cpu limit (100M instructions). Here we propose a few more host functions that can enable greater performance improvements. The targeted use case is Noir's Ultrahonk verifier contract (and the underneath lib), for which we will base our analysis on.

G1 MSM - in Ultrahonk msm operation takes up a big portion of cpu cost in proof verification.
As a rough estimate using bls12-381 G1 calibrated budget numbers:

• 70 G1 add and multiply — 172M
• G1 msm with length 70 — 55M
  So more than 3x cpu saving by switching to an msm host function. The main cost saving comes from less internal conversions (converting from Montgomery form).

Fr arithmetic - i.e. modulo {add, sub, mul, exp, inv}. UltraHonk verification contains Fiat-Shamir, sumcheck and other routines which perform heavy guest side arithmetic on Fr (a 32-bytes-scalar modulo bn254 curve subgroup order).
Without these, contracts will need to implement them, or import external libs (e.g. arkworks), which is more expensive and bloats code side. Ethereum supports native modulo arithmetic operations (ADDMOD and MULMOD as opcodes; modexp as a precompile).

Here is an ultrahonk verifier contract prototype with the above host functions (env), the contract performance has been significantly improved.

                           Old            New
contract size (bytes):     129522     —>  15385
cpu insn:                  557793594  —>  112533176

cc @yugocabrio @Savio-Sou

[tupui]

Since we are struggling to get Ultrahonk to respect the budget, that sounds like a great idea.

There is also the idea to have Ultrahonk directly added as a host function if this is the target. In the end if we really want to target ZK applications it could make sense and be a security guarantee to have this available as a function vs making a cross contract call. Because even if that does reduces the cost to just move that function, running a proof is still very expensive and limits what can be done around the proof in a single invocation. Moving to a full host function could open more use cases.

[jayz22]

Thank you for the suggestion @tupui. I'm definitely no expert in proof systems but the main goal is to provide enough building blocks to support a wide range of them. Ultrahonk is the current main choice in Aztec but even in their roadmap there were several variants in the past (stemming from Plonk which is one of the best known one).

Specifically for Ultrahonk verifier, the prototype has shown the majority cost coming from just a few crypto operations (g1 add/mul, g2-check-point-in-subgroup, pairing accounts for 98M/105M cpu instructions). So I think it's fairly clear supporting a native g1-msm should be necessary, since the other ones are already in host functions (and only called 1-2 times per verification).

We definitely still want a fully vetted implementation of the verifier itself, whether it's in a contract or in the host.

[tomerweller]

Should we just go ahead and implement the rest of the bn254 functions outlined here? https://github.com/orgs/stellar/discussions/1772#discussioncomment-14481047

Waiting for a hard requirement on individual operations seems fairly inefficient.

We want to appeal to projects building ZK systems so having rich set of operations that make ZK doable and cheaper on Stellar is a big plus. If the cost of implementation is reasonable and they use the same dependency anyway then I think we should go for it.

[jayz22]

@tomerweller I've updated the top discussion with the full set of host functions, and their improvement results.

I think we should add those, they are straightforward (requires no new host side libraries), and result in significant improvements, and some of them are natively supported in Ethereum already (modexp, ADDMOD, MULMOD).