Optimizations [migrated from ethereum repo]

[solidblu1992]

Was #7

[shamatar]

Hello @solidblu1992

By the way, why do you use ring signatures at the first place? It’s anyway seen who has signed an original transaction (eg msg.sender), so I’ve seen it the following way: 1) User publishes his global master public key 2) Sender has an output and wishes to send to that user 3) He chooses a random 251 bit index and derives a child public key of the recipient 4) He performs a ECDH on his current output’s public (private) key and newly derived public key. 5) Sends a confidential transaction to the user by sending an output to the same newly derived key and encrypting value and the blinding factor by AES based on on ECDH ephemeral key 6) Recipient monitors every payment by knowing index and derived public key, so he tries to generate a matching private key, and accepts a transaction if succeeds.

Would you explain me why you want separate spending and viewing keys?

Sincerely, Alex

[solidblu1992]

@shamatar

If the real sender publishes their own transaction to the contract, you are correct. However, I have a bounty system built in so that a transaction can be generated by a sender off-chain and given to a third party using a layer 2 solution (not yet built/specified but it would probably be Whisper). By publishing the original sender's transaction, that 3rd party can redeem a bounty (currently in Ether, but thinking of migrating it to DAI).

I use separate spending and viewing keys for the same reason that Monero does. There are some cases (accounting/auditing purposes) in which a person would want to de-anonymize themselves and they can do so by publishing their private view key. In your case they can't do that because you would be exposing the whole private key thus making any UTXOs spendable.

[shamatar]

@solidblu1992

Yeah, I was designing for anonymity and no audit :) Definitely should work on it, just in case!

Regarding actual sender - I was hoping of “account abstraction” features, when the contract itself would pay a cost, but it’s very long-term. What is possible is to have the third output for fee (confidential too) to the relayer public key, so its a clear incentive. What do you think?

[solidblu1992]

Yeah, that makes sense. In essence mine has flexibility in mind.

After depositing ETH, converting them into tokens, there is really only one transaction type in my contract: Send(). Send allows some unknown vector of confidential UTXOs to be spent, creating an arbitrary number of new confidential UTXOs PLUS an optional amount of transparent ETH (redemption). In order to convert tokens to ETH, a Send Tx must include a non-zero value of redemption ETH and can either specify an ETH address or leave it blank. My thinking here is that:

1. By specifying an ETH address and a non-zero redemption value, the sender wants to withdraw some of their own tokens for ETH. There isn't much effort to preserve the sender's anonymity in this case since ETH by default doesn't have a good way of doing that. The sender's remaining amount is hidden, because each withdraw must specify at least one confidential UTXO (even if it is a commitment to zero tokens). Ideally the token would have implicit value by being pegged 1:1 with ETH, and no one would really call Send() this way. But, this function is needed, otherwise the token is not redeemable for ETH, meaning its value is not pegged to ETH.
2. By leaving the ETH address blank and redemption value at zero, the Send Tx will deal only in token UTXOs. If a confidential bounty is desired, the sender and 3rd party would negotiate it off-chain prior to generating the transaction. This bounty UTXO would be indistinguishable from the other UTXOs. And, again, the 3rd party
3. By leaving the ETH address blank with a non-zero redemption value, Send() functions the same as number 2 but with a transparent ETH bounty redeemable by anyone. Whichever msg.sender successfully publishes the transaction will be rewarded with the redemption value in ETH. This is how I do bounties currently.

Personally, I'm not a huge fan of using account abstraction in this use case, since it seems to me like it would be easy to publish a bunch of invalid transactions and drain the contract of gas. There's probably a way around that. But, it still seems to require some sort of sender deposit or bounty, and in my case it seems even more difficult to preserve privacy since I don't want to reveal which UTXO was actually spent.

[shamatar]

Good point, redemption value is nice for a bounty and partial with withdrawal. I think the same is applicable for tokens (erc20), it a relaying party is market averse. The idea of open output is cool even without convidentiality, this way we can decouple private key on BN256 from one on Secp256k1 for someone who wants.

Should we also agree on proof serialization standard and usage of multiplier or “on deposit” conversion? May be a ERC is not necessary, but some open standard mixer interface would be useful.

In account abstractions the contract “pays” for execution every few lines of code, so if the transaction reverts early the miner will unlikely include it into the block as he loses profit. Although full account abstraction like this one has drawbacks, you should not be able to drain the contract that easy :)

[solidblu1992]

Should we also agree on proof serialization standard and usage of multiplier or “on deposit” conversion? May be a ERC is not necessary, but some open standard mixer interface would be useful.

Yeah, that would be good. Currently my standard for Bullet proofs is:

• p.length - [uint256] - number of individual proofs

Then for each proof:

• V[p].length*2 - uint256 - number of output commitments times 2 (indicating total array length)
• L[p].length*2 - uint256 - number of L points times 2 (indicating total array length)
• R[p].length*2 - uint256 - number of R points times 2 (indicating total array length)
• V[p] - uint256[] - serialized output commitments, expanded x coordinate then y coordinate
• A[p].x - uint256 - expanded x coordinate of A[p]
• A[p].y - uint256 - expanded y coordinate of A[p]
• S[p].x - uint256 - expanded x coordinate of S[p]
• S[p].y - uint256 - expanded y coordinate of S[p]
• T1[p].x - uint256 - expanded x coordinate of T1[p]
• T1[p].y - uint256 - expanded y coordinate of T1[p]
• T2[p].x - uint256 - expanded x coordinate of T2[p]
• T2[p].y - uint256 - expanded y coordinate of T2[p]
• taux[p] - uint256
• mu[p] - uint256
• L[p] - uint256[] - serialized L points, expanded x coordinate then y coordinate
• R[p] - uint256[] - serialized R points, expanded x coordinate then y coordinate
• a[p] - uint256
• b[p] - uint256
• t[p] - uint256
• N[p] - uint256 - number of bits that each V[p] commitment conceals

Then after all proofs:

• offset - uint256[] - a transparent offset to be added to each V[p][x] commitment individually
• power10 - uint256[] - a transparent power of 10 to mulitply each V[p][x] commitment individually

Preemptively, I realize that:

1. The lengths of the V[p], L[p], R[p] arrays as well as the value of N[p] could be smashed together into one uint256 integer in order to save proof size.
2. The offsets and power10 arrays don't really belong where they are and feel "hacked in".

Edit: Not sure why I forgot A, S, T1, T2, etc.

[darioAnongba]

Hi!

I tried merging @shamatar's JS Bulletproof creation and @solidblu1992's smart contracts since @shamatar's proof verification on-chain does not work as it costs too much gas for some reason and @solidblu1992's does not have a way to create proofs in JavaScript so his implementation cannot be used in a web or mobile apps. Being able to merge both would actually result in an usable implementation of Confidential transactions.

Sadly, it doesn't work on this specific line in BulletproofVerifiy.sol:

v.Y2 = ecMath.MultiExp(bp[0].V, v.vpz, 0, 0);

The code reverts as this requirement fails in ECMath.sol:

require(P.length == 2*s.length);

where bp[0].V = P and v.vpz = s here.

I'm pretty sure that I serialize the parameters correctly following @solidblu1992's guideline. The code to test this can be found on this repo. Checking the file test/bulletproofs.js.

Any ideas? Would be nice to actually have a working prototype instead of just PoCs for Confidential transactions.

[solidblu1992]

@darioAnongba

I think this may at least be my fault in part. I recently updated my Bullet Proof structure to combine V.length, L.length, R.length, and N into one uint256.

When was the last time you pulled my contracts?

[solidblu1992]

My revised standard for Bullet proofs is:

-p.length - [uint256] - number of individual proofs

Then for each proof:

• [R[p].length, L[p].length, V[p].length, N[p]] - combined uint256 to express 4 x uint64 values. All values are big-endian and the bracketed format matches how the test vectors are written in hex:
  1. N[p] - bits 0-63 - number of bits that each V[p] commitment conceals
  2. V[p].length*2 - bits 64-127 - number of output commitments times 2 (indicating total array length)
  3. L[p].length*2 - bits 128-191 - number of L points times 2 (indicating total array length)
  4. R[p].length*2 - bits 192-255 - number of R points times 2 (indicating total array length)
• V[p] - uint256[] - serialized output commitments, expanded x coordinate then y coordinate
• A[p].x - uint256 - expanded x coordinate of A[p]
• A[p].y - uint256 - expanded y coordinate of A[p]
• S[p].x - uint256 - expanded x coordinate of S[p]
• S[p].y - uint256 - expanded y coordinate of S[p]
• T1[p].x - uint256 - expanded x coordinate of T1[p]
• T1[p].y - uint256 - expanded y coordinate of T1[p]
• T2[p].x - uint256 - expanded x coordinate of T2[p]
• T2[p].y - uint256 - expanded y coordinate of T2[p]
• taux[p] - uint256
• mu[p] - uint256
• L[p] - uint256[] - serialized L points, expanded x coordinate then y coordinate
• R[p] - uint256[] - serialized R points, expanded x coordinate then y coordinate
• a[p] - uint256
• b[p] - uint256
• t[p] - uint256

Then after all proofs:

offset - uint256[] - a transparent offset to be added to each V[p][x] commitment individually power10 - uint256[] - a transparent power of 10 to mulitply each V[p][x] commitment individually

[darioAnongba]

Hi @solidblu1992,

I already took the concatenation into account when creating the proof. I also checked that the Bulletproof Structure (Data) was created correctly.

Something I noticed is that in your Python scripts L[p].length 2 = R[p].length 2 = a = hex(10) when creating a proof with 4 commitments, and N = 8. In @shamatar's implementation, L and R size is 8. Couldn't figure out why though.

Cheers, Dario

[solidblu1992]

0xa seems correct. L.length = R.length = log(M)+log(N)=2+3=5. Twice that is 10

Could you supply your serialized vector?

Or, could you tell me what length of V and vpz is being fed into MultiExp?

[darioAnongba]

Here is the vector serialized. This time with 2 commitments (V.length = 4 on-chain) and N = 8 bits.

[ 1,
  <BN: 6000000000000000600000000000000040000000000000008>,
  <BN: 1fa9ad881904f9517c1b15f06824372e6179721519df9d2781e74e0e37b5f8f3>,
  <BN: 20a12a05b370c1bbfaa83d632742c5636d9b38a6a6325dc6906927fea9d5bf84>,
  <BN: 599dae99ddf9135da87304444d84cbc59e7b22072f126bfaf73cb7b5c8b9614>,
  <BN: 20ef504bb33d62cfd4a2fae081c4650050d181038e3cc5ac800788dcec8826fe>,
  <BN: 6f3014bfe18eca992488466588a363c2eed227e4443d3d8d01f15088a586b65>,
  <BN: f4677738270f6683fceef68e9e5dc920b20d3531258b9a23d6493970bb391c2>,
  <BN: 1bc2cae6a7f61dd5bedd9847a182a835c1af4f06d7cf2f12a411945d9412220c>,
  <BN: 13bd9835efd62661cb5ad986742d35b5d3e2f28d718a2e0df551f4f31805b82c>,
  <BN: 26680ad3ba3d081c71265dbb9c15642924fa1abc4266f796c8e89bc7f607f7e3>,
  <BN: 3a7669dcd3d74431ef036bdd959df8f76a78a5a559d9792ba7c7bb13278b64b>,
  <BN: 27635e4f7afec88f44e107e050bed012f12c150b044bac6af64b0f118184b02e>,
  <BN: 1a3fdbddb25d07a26c76fb9e840f54d1b8f9680e69022b6a0f6de0462f1c6bf7>,
  <BN: 2d43e03adb06282c83e486de8e5f3dcfb680dff5060d8461eba6a10897237ba2>,
  <BN: 124f8129f754606dff1976bd000d8fdaabc89c442f502834af2acaa0505af084>,
  <BN: b596b5b87073ec0a7081459f44506066c92a70aacdaca21c3bcd89f3c50e8f6>,
  <BN: 2d8af322a670f53425b82b77c7518405225737e5eaa8ebd81ac978d0a0671943>,
  <BN: e5aa89f51dd84ac56fec2b91cace42ed6be754bf4c8451e1e505f9fbd67b196>,
  <BN: 2dadc4e224ef111ed5aca5931ab0e55f47927ef559b82d0b4484c450027da7c1>,
  <BN: 3d7d6d7b63dcd2df63709a9ea9dd93dba23a5f780c37f31e96dd9c00f03da5>,
  <BN: 38e212bbdc44f8a8a5da2a73fc80153935cbab2202e3441d6f0d3e2197aa3fd>,
  <BN: bec4ba6a82c966ce9778531b856f742fdc82ebbe299076046be7a65902c70ae>,
  <BN: 1028c4e662ec79491fd77f2c9f46aa9fbdcef88dfebe65e561a121d907c80ea9>,
  <BN: 98c2af7a7a430d192acc0c44949b46a6d5be873ee859894c197eda6c840fb00>,
  <BN: e75ecc62e2a732f4b90f11354091483b4e252efefd322261da77940b6b35f1b>,
  <BN: 22d28ea3644aca4e6da5013db932be0a15227c7801f34b2a2ae0039a3f0feec6>,
  <BN: 2688b4d05fad4d2fa065b32aa1df518dc8dc632c1b232c51124d04de7508ea4e>,
  <BN: 133904527fa1693d77c7c103c7f95c927be0185e9a9981cc7cc19f54d3646ca3>,
  <BN: 2c67e2e35465304c2798eb3a8a6f97d648888f03943761d1bed7d366b353ba04>,
  <BN: 1b8682e734975ee5f9107545c1df973d85eb58789422ce09130c05ae6fbd9c3e> ]

When testing on-chain I have V.length = 4 and v.vpz.length = 1. So that's why it fails but I don't know how to fix it.

[solidblu1992]

So in this case, v.vpz seems to be the wrong length. v.vpz is created by vPow(v.z, v.M). Which tells me that v.M is evaluating to 1 instead of 2.

[solidblu1992]

Dario. I figured it out. For N=8 and M=2 (V.length=4), the lengths of L and R need to be 8 not 6 (4 points long, not 3). This is an extension of the discrepancy you found earlier. I think the problem is with the generation logic, but I could be biased...

[darioAnongba]

If this is true, then this may interest @shamatar, as I'm using his code to generate proofs. Seems that the proof generation has some bug.

[solidblu1992]

Either that or he has some optimization that I'm not aware of.

[shamatar]

Oh, a good discussion is here.

I'm finally more or less free from Plasma development and can post my proposal and clarifications (and yes, confidential transactions will be a part of my Plasma when (and if) BN256 operations will become cheaper :) )

Let's put the following notations:

M - number of bits for unsigned integer representation
N - use integer, usually used for for numbering here
numProofs - number of proofs in consideration
Base10Multiplier - clear text base 10 multiplier for transaction parameters
inN (in0, in1, ...) - an input to confidential transaction
outN - an output
commitment = v*G + r*H - an input or an output
v - value for the transaction
r - blinding factor
sigGenerator - generator for UTXO signatures
G, H - generators for commitment
G[N], H[N] - public parameters for Bulletproofs

For technical perspective - all numbers are uint256 if not stated otherwise. For hashing numbers are ALWAYS padded left with zeros to 32 bytes (necessary for consistent hashing in smart contracts).

There are various range proofs possible with Bulletproofs. One proof takes 5 scalar values in F_p and 2 x ( log2(M) + log2(numProofs)) + 4 in G.

1) Normal range proof, numProofs = 1. All M bits belong to one unsigned integer, verification requires roughly 4*M scalar multiplications in naive verification that I use for the reasons explained below. 2) Aggregated proof, numProofs > 1. M bits are divided evenly by numProofs, so a size of two 16 bit proofs is the same as the size of one 32 bit proof. Verification is roughly as expensive as one 32 bit proof.

Now about batch verification - one can simultaneously check two equations of the form

g ^ x == 1 && g ^ y == 1

as

g ^ (a*x + y) == 1

iff one has access to the "good" (cryptographically strong) random number generator to sample "a". This is the optimization @solidblu1992 uses, but I don't, so my verification is twice more expensive usually. This optimization is valuable for both single and multiple proof verifications. Please refer to 6.2 of original Bulletproofs article for info.

After all this into we can get to the important parts 1) Should we use a batch verification? Using a previous block hash is "OK" since proof can not be generated with the classical attack on all Ethereum random generators - make another contract to generate something before the calling external function. But my personal opinion is that without much better source of entropy we can not use this optimization. We can try to create some "challenge and response" procedure using external oracles, but there is no mechanism to take any penalty from the user for malformed proof, as all addresses will be "stealth". 2) Usage of Base10Multiplier (and additive shifts too) - this is indirect compromise of confidentiality. Much cleaner solution would be to allow users to deposit their "assets" to the smart contract and normalize all the assets to 3 decimals. If we exposure such parameter on "per output" (so, per proof) basis most of the time there will be one-two outputs with the large multiplier and another few with a small one 3) Aggregated proofs or separate proofs - tough decision. If one can not win here is verification price or proof size without batch verification optimization, than they are the same in term of verification price and almost the same in term of proof size. Using separate proofs can be even cheaper since we have to read much larger number of public parameters G[N], H[N] from the storage (linear scaling) and than keep them in memory (quadratic scaling!). I'd bet for separate proofs for now at least. 4) Allow users proofs of different size or only one fixed size M - it's also indirect compromise of confidentiality. If the proofs is "short" that it most likely an integer number like 1, 2, 3, or even 0 (it's especially compromising if one can also check Base10Multiplier). The whole idea of Pedersen commitments if perfect statistical hiding, so I'd bet to make same size proof mandatory for each output of the transaction.

I'd like to hear your ideas @solidblu1992 , @darioAnongba . After we agree on questions 1-4 the draft of confidential transactions mixer will be straightforward. I'd like to invite @swasilyev to this conversation, he is another author of our JS library.

Sincerely, Alex

[shamatar]

@darioAnongba

Regarding my code for proof generation - please make sure that you can first generate a single (non-aggregate) proof and perform a verification. In JS library it's called just "RangeProof" (aggregated = MultiRangeProof). Also, did you check that our base generators (G[N], H[N] and G, H) match between my implementation and @solidblu1992 ?

Sincerely, Alex

[darioAnongba]

Hi, Sorry I just came back from vacation.

I'm the least experienced in cryptography so my opinion is not very meaningful but here it is.

I think that we all try to solve a different problem. Personally, I'm only interested in hiding the amounts of transactions with bulletproofs and not the sender or recipient, so I use their standard ethereum addresses and not "stealth addresses".

1. I am not sufficiently aware of the consequences but reducing gas cost is one of the mos important factors so I'm for using batch verification.
2. I also think that using a multiplier is not a good idea.
3. You say that separate proofs are cheaper but I didn't notice a difference when verifying a single proof vs a multirangeproof (almost same cost for both) using your implementation.
4. I'm for using a fixed M for all proofs.

Sincerely, Dario

[solidblu1992]

Dario / Alex,

I'm going to be taking a break from RingCT for the summer. Feel free to continue discussing here if you wish. Just wanted you to be aware of my absence.

Best regards,

Andrew