EIP: Reduce ECADD and ECMUL gas costs

[Shadowfiend]

Preamble

---

EIP: <to be assigned>
Title: Reduce ECADD and ECMUL gas costs
Author: Antonio Salazar Cardozo (@shadowfiend) <antonio@keep.network>
Type: Standards Track
Category: Core
Created: 2018-05-17

---

Short Description

Recent changes to the underlying library used by the official Go reference implementation led to significant performance gains for the ECADD and ECMUL precompiled contracts on the alt_bn128 elliptic curve, which should be reflected in reduced gas costs.

Motivation

Recently, the underlying library used by the official Go reference implementation to implement the ECADD (at address 0x06) and ECMUL (at address 0x07) precompiled contracts was shifted to Cloudflare's bn256 library. Based on the initial PR that introduced this change, and corroborated in a later note, the computational cost of ECADD, ECMUL, and pairing checks (excepting the constant) has dropped roughly an order of magnitude across the board.

I am introducing this early EIP to propose dropping the gas costs accordingly.

Specification

Following is a table with the current gas cost and (current) suggested new gas cost:

Contract	Address	Current Gas Cost	Suggested Gas Cost
ECADD	0x06	500[1]	50
ECMUL	0x07	40 000[1]	2 000
Pairing check	0x08	80 000k + 100 000[2]	5 500k + 100 000

[1]- Per EIP-196.
[2]- Per EIP-197.

[shamatar]

@Shadowfiend

Antonio, thank you for opening it. Right now the main show-stopper for practical confidential transactions and ring-signature based votings is a price of MUL operation in G1, that has picked up 20 fold speed-up after changes you’ve mentioned. I’d propose dropping price of ADD from 500 to 50 and the price of MUL operation from 40000 to 2000. Also it's worth including a reduction of paring operation cost too as all those optimizations are closely related.

For the reference of what would be a practical use of such ops I’ll try to give you an estimate of checking a single “Bulletproof” based range proof for 32 bit long integer tomorrow as I’ll release the set of provers, verifiers and mixers.

Sincerely, Alex

[solidblu1992]

I probably don't have the most efficient Bulletproof verification logic, but for a 32-bit proof with a multiplication of a power of 10 and an offset it costs about 4,482,466 gas currently (tx).

[Shadowfiend]

@shamatar an excellent point re: the pairing check, which I've added with a 15-fold drop (except for the constant factor, which seems to be ~the same in the benchmarks). I also took a closer look at ECMUL and you're absolutely right, it's 20-fold, not just 10-fold. Updated accordingly.

[mhluongo]

@solidblu1992 have you published your Bulletproof verification code? We're considering them as an alternative to an accusation-based system

[solidblu1992]

@mhluongo It's public on GitHub as part of my RingCT implementation. My code base is kind of a warzone, but feel free to use anything in it.

[mhluongo]

Eh I've been digging through optimized curve implementations the last couple months, I'm sure it's not that bad @solidblu1992- thanks for the link!

[shamatar]

@Shadowfiend

I've run quick tests, for 64 bits

Single proof for 64 bits gas estimate = 20120556
Aggregated proof of 64 total bits gas estimate = 20265094

Implementation is almost 1 to 1 (hashing was changed to be compatible with Ethereum keccak256() call) compatible with original Bulletproof repo from Stanford and "nothing up my sleeve". So 20-fold decrease makes it completely usable - reduce it to 32 bits and use 3 separate proofs (need at least 1->3 UTXOs mixing for confidentiality), so price will be around 1.5 million per full transaction if full precision is required, or less in case of partial indirect compromise of confidentiality.

Source code is located here. It also has a prover to be run locally using JavaScript.

Sincerely, Alex

[Arachnid]

This looks like it's ready to be a draft EIP. If you agree, please submit it as a PR.

[shamatar]

Shouldn't gas cost per extra bytes also be reduced? As per precompile code base price is a flat fixed price, while extra price per 192 bytes is actually a price per pairing check.

func (c *bn256Pairing) RequiredGas(input []byte) uint64 {
	return params.Bn256PairingBaseGas + uint64(len(input)/192)*params.Bn256PairingPerPointGas
}

[Shadowfiend]

@shamatar isn't that reflected above? The base price remains the same, the per-pairing price is divided by 15, to 5500k + 10000.

[Shadowfiend]

@Arachnid I will do so today, thank you!

[shamatar]

@Shadowfiend

Than you have a small typo in original prices, it should be 80000k + 100000 per pair, while you listed 80000k + 10000 per pair. My mistake, apologies.

Sincerely, Alex

[Shadowfiend]

Yikes! You're completely right, thanks for the catch 🙊

[shamatar]

@Shadowfiend

I’d still suggest lowering a fixed cost from 100000 down to 10000 (if you didn’t make another typing error). Having a large fixed price per call is no point as no expensive operations are done prior to actual pairing computations. So 5500 gas per element + 10000 fixed would be optimal I think.

Sincerely, Alex

[Shadowfiend]

I would be super-interested in that as well; I didn't change the fixed cost because if you look at the linked benchmarks, the “empty data” benchmark sees significantly smaller (~20%) drops. Still perhaps meriting 80 000 instead of 100, but I'm not sure a 10x decrease is justified. That said, I don't see a clear articulation in the EIP-197 regarding the motivation for that constant factor, so I might be missing something.

[shamatar]

@Shadowfiend

I didn't see a motivation for a large fixed cost either, it costs virtually nothing

• check that data.length % 192 == 0
• copy bytes iterating over 192 bytes chunks

Can you add to EIP that sending 0 bytes to it should revert with a corresponding check

if (len(input) == 0 || len(input)%192 > 0) {
		return nil, errBadPairingInput
	}

and set fixed price to zero? Such thing can be elaborated inside of EIP discussion.

Having fixed price is quite unreasonable - I didn't see any context creation operations or something like this (such operations are anyway should only be done once on a startup).

Sincerely, Alex

[solidblu1992]

@shamatar
My comment probably isn't particularly useful for this EIP-1088 discussion, but for your 64-bit bullet proof verification did you mean 2Mgas or 20Mgas? If 20Mgas, there are certainly some optimizations you can make to improve that number (I got it down to 7.9Mgas).

I'd recommend reducing the number of inv() function calls as I've found those to be quite gas intensive. For instance when calling haddamard_inv(publicParameters.hs(), b.ys), you are doing 64 mod inverses when you really only need to be doing one: haddamard(publicParameters.hs(), powers(b.y.inv()).

Again, sorry if this is too far off topic. In any case, I'd be very happy to see the gas costs lowered.

[shamatar]

@solidblu1992

I was mainly porting a prover to abstract curve and JS to be run client side, and make a protocol as itself + tools for key exchange and mixing, but yes, optimizations should be done. By the way, what do you mean under “multiplication by a power of 10 and an offset” in your implementation?

Sincerely, Alex

[solidblu1992]

@shamatar

By the way, what do you mean under “multiplication by a power of 10 and an offset” in your implementation?

So I was leveraging a technique used by Borromean Range Proofs where you can supply a power of 10 and an offset which are publicly known in order to reduce the number of bits required. For example, if I want to commit to 0.051 ETH, that's 5 x (10^16) + (10^15) wei. So, I could do a range proof on 5 for a lesser number of bits (at least 3, but probably more), and tell the contract that I'm multiplying my value by 10^16 and adding an offset of 10^15 (though in practice I rarely use the offset).

The way I do this with bullet proofs is that after the bullet proof is verified, I have the contract modify the commitment and store that one as positive instead: C' = (10^power10)C + (offset)H. Note that if adding a power of 10, the blinding factor is scaled up by that same power of 10: bf' = bf x (10^power10) mod N.

[shamatar]

@solidblu1992

Oh, I see. I've first required a separate "deposit" procedure that normalizes everything to 3 decimals after the point for similar point. Thank you for clarification.

Sincerely, Alex

[shamatar]

Hello @solidblu1992

While it's may be not the most appropriate place to discuss bulletproofs, I've implemented optimizations and fixed a test. Checking a proof by itself is 13 mil of gas, while the rest was coming from loading H[], G[], G and H vectors and points from storage. Out of those 13 mil around 6 are coming from multiExp in inner product proof at the final stage, and another 6 are from range proof pre-check and challenges computation. If you can share some numbers from you and suggestions - would be highly appreciated. Also, may be you have another communication channel?

Sincerely, Alex

[solidblu1992]

@shamatar

Let's open an issue on my GitHub, we can talk there!

[Shadowfiend]

Closing this in favor of the draft EIP @ #1108; apologies for the delay!