Optimizations

[shamatar]

Hello @solidblu1992

Would you help me to optimize my version of bulletproofs and mixer? I've shredded almost 2.5 mil gas by only reading public parameters from the storage once and another 1 million by improving modular inversion (trick of big mod exp a^-1 = a^(p-2) mod p is actually more expensive than naive algo in my case). Right now my pure cost for 64bit (aggregated or not, not much difference) proof verification is roughly 13 million gas. Would you have a look? I'm going to fork your code and profile it to see where we have large discrepancies in gas costs.

My repo is here

Sincerely, Alex

[solidblu1992]

Alex,

I took a quick look and nothing in particular jumped out immediately. I would continue to compare your implementation to mine and see if you find any opportunities to reduce gas.

Out of curiosity, how much gas does it take for your implementation to fetch the G and H points? I remember mine was super high until I left the points in the storage of ecMath and then pulled them into memory only of BulletproofVerify (with ecMath.GetGiHi(v.maxMN)). I'd be lying if I said I knew for sure why this was cheaper, and I'm not even sure if your implementation is that different.

Just food for thought. If I think of anything else, I'll let you know!

[shamatar]

Reading 64 points (so 128 uint256) by pulling them from storage costed me 2 mil gas for some reason. I didn’t check of unpacking can save me something, but still single SLOAD should be 500 gas per slot, so I’d expect something like 70k gas. I’ll investigate it later this evening and will report my findings.

Sincerely, Alex

[shamatar]

@solidblu1992

This is the most stupid bug ever, I've generated an array of point G[] and H[], but instead of just reading them and passing to the function I was actually calling a function that did hash a string like "G0" to point on elliptic curve. Now getting a set of G[] is only 83195 gas, but still full proof check for 64 bits is roughly 13 million gas, I'll investigate further.

Sincerely, Alex

[shamatar]

By the way, are you using a trick with single multi-exponentiation as described in 6.2 in here? Than 2 times the discrepancy between my and your gas prices is logical.

Sincerely, Alex

[solidblu1992]

Alex,

That could very well be the case. I was using Monero's MultiBulletproof implementation as a reference, so they probably used that trick. Also, I think it was so good that it didn't even make sense to use a SingleBulletproof.

[darioAnongba]

Hi you two,

I happened to read your conversation and I checked shamatar repo. I noticed something that was quite different between your two implementations and I couldn't figure out what were the implications @solidblu1992 , @shamatar.

In @shamatar's code, you create Multiple generator points G, G1, G2, etc. by simply hashing strings like "G", "G1", "G2", and projecting them to curve. Same to create H, H1, H2, etc. Whereas @solidblu1992 follows Andrew Poelstra's guidelines of hashing G1 and then incrementing it until finding a suitable H. It was a Stack Overflow's answer here.
I believe that for bulletproofs @solidblu1992 uses the previous generated point to generate the current and so on (not sure).

Why go through all the trouble @solidblu1992 does if @shamatar's way of doing it is also valid? Am I missing something?

[shamatar]

Hello @darioAnongba

I think you are a little confused, there is no substantial difference.

First you have some string like “G0” and get 32 bytes X coordinate candidate for a point. Than you check this candidate by trying to find Y for it by using the curve equation. If you don’t hit a point - you increment X and try again. We may have a difference in seed strings (I’ve used one from Stanford implementation, they use “G0”, “G1”, ....) but hashing a string to point should be the same in principle.

Sincerely, Alex

[darioAnongba]

Thanks for your quick answer!

So if I understand correctly, you must have the same logic in your solidity smart contract than in your scripts (JS, Python, etc) for the system to work? For example, @solidblu1992's implementation would obviously not be compatible with your JS code because you don't have the same Gs and Hs.

I mean, if I create a range proof with your JS implementation and then try to verify it on-chain with @solidblu1992's implementation.

Shouldn't this need some sort of agreement so that all applications could share a common alt_bn_128 contract or library?

[shamatar]

Hello @darioAnongba

In principle yes, we can more or less agree or merge some code. I’ve structurred the contract to take arbitrary external public parameters (base points), and can have the same in JS prover. We have substantial difference in verification procedure and proof serialization (in technical terms, but not in validity), but should be able to use each-others public parameters.

Sincerely, Alex

[darioAnongba]

@shamatar, @solidblu1992

I see, so your implementation is pretty generic, that's nice!

I personally think that given the huge demand for confidential transactions by the Ethereum community, you two should create an "official" Open source project to share your JS library, EC Math, Bulletproof verifier and other contracts (if that was your intent, since your 2 repos are public). So that you two can create the "standard". Maybe one day see an ERCX for confidential tokens.

But that's for you two to decide, I would gladly help though since I'm pretty interested in this for my Master's thesis.

Sincerely,
Dario

[shamatar]

@darioAnongba

I’d appreciate if me and @solidblu1992 can agree on some fundamental points and than make a standard. Our largest discrepancy is usage of quasi-random number for verification and a secret address logic, as well as storage of auxiliary information like key derivation index. You can check my repo too, there is my vision of a mixer there.

Sincerely, Alex

[solidblu1992]

@shamatar

Honestly, I'm not too attached to the way I chose the generator points. The only reason I did it by hashing each successive point is because that's how Monero did it.

For "quasi-random number for verification", do you mean generating parameters like y, z, x, and x_ip using Fiat-Shamir? If so, I'd be happy to follow lock step with what you do there. I know I took a lazy approach when hashing the V commitment array first then adding the hash in A and S to get y.

The above point reminded me of something. Do you have the ability to batch verify multiple bullet proofs? This section of my BulletproofVerify.sol could use some standardization and collaboration.

        //Pick *random* weight, not sure if this works...
        //Probably need a better source of randomness
        if (bp.length > 1) {
            v.weight = uint256(keccak256(blockhash(p), gasleft(), v.weight)) % NCurve;
        }

[solidblu1992]

@shamatar

Also ideally, I would like to integrate some of Vitalik's comments as well. Particularly the one quoted below. Maybe it would be better to just be a different version of the token due to most of the security being offloaded onto verifies, but in order to go mainstream and drastically reduce network load it may need to be done. Though, EIP-1108 and EIP-1109 would certainly help as well.

2. Consider reducing gas costs with cryptoeconomics. That is, don't verify the RingCT signatures by default, and instead just save the hash of the signatures on chain, and if unchallenged let them finalize after N blocks. During that phase, anyone can challenge by re-supplying the signature, and then the contract checks the signature against the hash and attempts to verify the signature; if verification fails, then the challenger gets a bounty and the includer is penalized.

[shamatar]

Hello @solidblu1992

Regarding signature verification - I’ll describe you my optimization for it tomorrow, have few good points there. For batch verification - by using a “random number” you can effectively verify two equations like g^x == 1 and g^y==1 by verifying g^(a*x + y) == 1, so with high probability g^x == 1 and g^y==1 holds. It saves you half of exponentiations compared to my “naive” prover that follows Stanford implementation. Using a random number like blockhash is fine I think, as there is no guarantee on block inclusion time, but large players (miners) can potentially have capabilities to exploit it.

Sincerely, Alex

[shamatar]

Also you can have “batches” in a form of aggregated proof, but to do so you need enough public parameters (points). Or you can add all those coefficients in exponents (which I’ve described above) and verify such full linear combination, that is also batching. Unfortunately I don’t think you should allow aggregation and than verification in such form, as some third party will have an obligation to call a contract to verify a full set at once.

Sincerely, Alex

[solidblu1992]

I split off the RingCT token from my "ethereum" repo. We can continue this in issue #1 above.