[Crypto] Compact Confidential Transactions for Bitcoin

[Mixles]

Request for comment

http://voxelsoft.com/dev/cct.html

[mably]

How does it compare to Gregory Maxwell "Confidential Transactions" ?

[andytoshi]

How does it compare to Gregory Maxwell "Confidential Transactions" ?

If it is correct, it accomplishes the same goal with a significant space and verification-time savings.

[mably]

Is an implementation already available somewhere?

Happy to hear that it's ok for inclusion in Bitcoin as stated on page 9 of the whitepaper:

"In addition to standing on its own, Sumcoin can be implemented as a sidechain or integrated into the Monero (or Bitcoin) protocol as a hard fork with a new transaction version."

Would be great to have it also implemented in some Proof-of-stake alt-coins like Peercoin.

[Mixles]

Is an implementation already available somewhere?

Nope.

Would be great to have it also implemented in some Proof-of-stake alt-coins like Peercoin.

Integrating Proof of Stake with the current design would likely require stake disclosure. Confidential Proof of Stake would require more proofs than in the paper.

[DumbFruit]

Just as I'm getting over my migraine from learning about Confidential Transactions at a high level we get another awesome proposal. When I first saw your request for compensation on the CoinJoin thread I thought you were just another crank and/or weirdo (The jury is still out.). I would very much like to see a proof of concept.

Some comparisons between these two new proposals.

CCT transactions are smaller than CT transactions, though it's not as easy as just saying one is X% smaller than the other;

Since the introduction of multi-signature addresses, the average Bitcoin transaction size has risen to about 600 bytes. For a typical two input, two output
transaction, the value hiding enhancement adds two commitments of 33 bytes
each, two smallness proofs of 132 bytes each and two encrypted values of 32
bytes. In net terms, about 400 bytes (66%) are added. While this grows quickly
with the number of outputs, only one commitment (33 bytes) needs to be kept
in each unspent transaction output.

The result is that a proof for a 32-bit value is 2564 bytes, and simultaneously may convey 2048 bytes of message. A 32-bit proof can cover a range of 42.94967296 BTC with 1e-8 precision, or 429.4967296 BTC with 1e-7 precision, and so on.

The required commitments are an order of magnitude smaller than those proposed for Confidential Transactions, hide the whole value rather than only the mantissa, and do not depend on ring signatures.

I thought that CT represented the entire value in the mantissa, so isn't this a distinction without a difference?

CT amounts are expressed using a decimal floating point where the digits are multiplied by a base 10 exponent.  This means that you can prove large amounts with small proofs, so long as they have few significant digits in base 10: e.g., 11.2345 and .0112345 can have the same size proof, even though one number is a thousand times larger.

CT implementation (Well commented.);
https://github.com/ElementsProject/secp256k1-zkp/commit/bd067945ead3b514fba884abd0de95fc4b5db9ae
There is no CCT implementation.

CCT, unlike CT, offers some consideration to miners;

4.2 Coinbase If coinbase subsidy could be both randomised similar to Luckycoin (and earlier version of Dogecoin), and hidden while proved in a narrow range, this could provide extra initial privacy for the miners. This is considered too expensive to implement. The coinbase is instead constrained to be spent into a minimum of 3 outputs. This ensures that a miner’s payee will not be able to determine the exact amounts sent to other payees from the single transaction output. 4.3 Sender and receiver responsibilities Sender and receiver must not disclose the view key, amount and fuzz bits used in each transaction. It is up to the sender of a transaction to guarantee its secrecy by generating good randomness for the fuzz bits of each output. Once the details of a transaction are made public, it is likely that they can not be hidden again.

They both use a zero knowledge proof to ensure that the commitments don't overflow in an homomorphic addition.


Beyond that I'm certainly not qualified to comment so read further at your own risk. One of the neat things about CTT is that the only thing that needs to be stored permanently on the blockchain is the commitment to a value. The value itself is encrypted via Elliptic Curve Cryptography and can eventually be dropped, as it is only needed by the receiver. Allegedly the "proof of smallness" can also be dropped.
CT does not have this same ability to prune because the encrypted value is tied to the commitment. The "range proof", as Greg Maxwell calls them, could likely be dropped in the same way CCT can.
Can CCT be used to encrypt other arbitrary information as well, or is it limited to transaction values?

Cool times in cryptocurrency land.

http://voxelsoft.com/dev/cct.html
https://bitcointalk.org/index.php?topic=1085273.0

[Mixles]

Just as I'm getting over my migraine from learning about Confidential Transactions at a high level we get another awesome proposal. When I first saw your request for compensation on the CoinJoin thread I thought you were just another crank and/or weirdo (The jury is still out.). I would very much like to see a proof of concept.

To be honest, I think the muted response speaks for itself. This stuff turns out to be less important than I thought. Someone will eventually re-implement the same things from the paper (maybe Blockstream or Monero guys?). Multiple independent implementations are a good way to do crypto, because then they can be compared and tested against each other.

I thought that CT represented the entire value in the mantissa, so isn't this a distinction without a difference?

Inputs do not have an exponent.  The exponent is a property of the range proof, not of the values themselves. They work by scaling the basis the proof operates over.

I'm not 100% sure of the CT method, but it sounds like some information about the exponent is exposed to make the proofs shorter (you could keep it secret at a big cost). Maybe not the input magnitude, but the proof exponent range is public, and that selection, can itself give some information away. This is why CT is targeted at smaller 32-bit numbers.

Can CCT be used to encrypt other arbitrary information as well, or is it limited to transaction values?

Yes. There's a DH key exchange, which give a common secret through which you could share as much as you want.

[gmaxwell]

To be honest, I think the muted response speaks for itself. This stuff turns out to be less important than I thought. Someone will eventually re-implement the same things from the paper (maybe Blockstream or Monero guys?). Multiple independent implementations are a good way to do crypto, because then they can be compared and tested against each other.

Oh don't feel let down. It's highly technical and many people don't understand it.   I'm certainly super excited about it, but balancing a bunch of things right now so I haven't had time to give more feedback than I have so far (thanks for so swiftly integrating that!).

When I first explained the concept behind coinjoin it went nowhere, I had to do substantial work to write a plain explanation and simplify it all down, before people paid any attention at all.   When there is an implementation and such you'll see more interest as well.

For whatever it's worth I consider your work important. Between the soundness and efficiency improvements I went from thinking the probability of deployment of CT in bitcoin proper (rather than just in sidechains) was low but non-zero to-- with your scheme-- a view that its even likely eventually. (assuming Bitcoin doesn't get usurped down a privacy unfriendly angle).

[ABISprotocol]

Request for comment

http://voxelsoft.com/dev/cct.html

Holy shit

[SuperClam]

To be honest, I think the muted response speaks for itself. This stuff turns out to be less important than I thought. Someone will eventually re-implement the same things from the paper (maybe Blockstream or Monero guys?). Multiple independent implementations are a good way to do crypto, because then they can be compared and tested against each other.

Oh don't feel let down.
...
For whatever it's worth I consider your work important. Between the soundness and efficiency improvements I went from thinking the probability of deployment of CT in bitcoin proper (rather than just in sidechains) was low but non-zero to-- with your scheme-- a view that its even likely eventually. (assuming Bitcoin doesn't get usurped down a privacy unfriendly angle).

Liberty in the constitutional sense must mean more than freedom from unlawful governmental restraint; it must include privacy as well, if it is to be a repository of freedom. The right to be let alone is indeed the beginning of all freedom.

[coins101]

....   When there is an implementation and such you'll see more interest as well......

What would be the best approach to do an implementation to test (1) it works, (2) it can be pushed, (3) and deployed via sidechain, or some other way?

[gmaxwell]

Unfortunately, Andrew Poelstra was able to break the cryptosystem for this scheme's range-proofs.  The author is working on fixing it, and I'm hopeful for progress there. This may take a bit of time, so if you're looking for something to test right now the CT feature in the Elements/Alpha is the best that is out there  at the moment.

[coins101]

Unfortunately, Andrew Poelstra was able to break the cryptosystem for this scheme's range-proofs.  The author is working on fixing it, and I'm hopeful for progress there. This may take a bit of time, so if you're looking for something to test right now the CT feature in the Elements/Alpha is the best that is out there  at the moment.

I will have a play tomorrow. Thanks.

[mably]

Unfortunately, Andrew Poelstra was able to break the cryptosystem for this scheme's range-proofs.  The author is working on fixing it, and I'm hopeful for progress there. This may take a bit of time, so if you're looking for something to test right now the CT feature in the Elements/Alpha is the best that is out there  at the moment.

Hi @gmaxwell, is Andrew Poelstra analysis publicly available somewhere?  Thanx.

[Mixles]

Unfortunately, Andrew Poelstra was able to break the cryptosystem for this scheme's range-proofs.  The author is working on fixing it, and I'm hopeful for progress there. This may take a bit of time, so if you're looking for something to test right now the CT feature in the Elements/Alpha is the best that is out there  at the moment.

Hi @gmaxwell, is Andrew Poelstra analysis publicly available somewhere?  Thanx.

The problem was with an invalid assumption that two curves of different orders would not be able to generate proof of same negative value, as long as the negative value is in the small range being proved. They clearly can, because "m = r + c*x" allows a negative x to leak into the negative cx and then offset against the positive random r, and the resulting m is then used for both curves.

That assumption is no longer present in the current version of paper (now with:.. diagrams!), but the resulting proofs are not as compact as initially hoped.

[TPTB_need_war]

That assumption is no longer present in the current version of paper

Because proving a number is square (or sum of the squares) of some number(s) proves it is not negative. And proving the committed output x is within a range L <= x <= U is accomplished by proving neither x - L and U - x are negative. Readers may refer to cited reference [38] for the details.

I have some naive (non-expert) concerns about the new constructions.

1.  You wrote, "²To save space, SUM j=0 to outputs(∆j) is revealed as an unsigned integer at the transaction level.". Wouldn't such a sum allow some of the operands to be negative and others to be positive offseting. I presume you reveal the ∆ to prove the sum of the squares isn't negative, but appears that optimization in footnote ² is flawed.

2. There appears to be a typo of an extra superfluous (or missing redundant) parenthesis, "fuzzbits ≈ (curvebits − reservedbits)/2) − valuebits".

3. It appears you avoided factoring fuzzValue into a sum of three squares by inventing a heuristic (to factor into a sum of two squares) to save "50% storage and computation requirements", but at the cost of reducing the security of the value blinding by 1/3 to 1/2 of the bits. Why is this a wise tradeoff? How do you know this heuristic will terminate with less computational cost than factoring?

4. As another consequence of discarding factoring, how do you know that providing one equation of one unknown will not reveal fuzzValue? Does that equation have provably many solutions?

5. Since the security of x2 is lowered by 1/3 bits, how do you know that finding this additional variable thus providing two equations with two unknowns will not catastrophically weaken the security due to some clever algorithm such as for solutions of systems of non-linear equations? Your cited resource [38] pointed out that the prior attempts to be clever to avoid factoring the sum of three (or four) squares lead to a solution that was attackable from both the hardness of the discrete logarithm and the hardness of integer factoring simultaneously, thus required higher bit widths to compensate which ameliorated the efficiency of the algorithm. Isn't the burden of proof on your whitepaper to explain why your cleverness has not introduced analogous vulnerability. I am just really doubting this attempt to avoid factoring to 3 squares. I would naively tend to trust the guy who wrote that cited resource [38] given the breath of knowledge and peer review that apparently went into it.

[TPTB_need_war]

The required commitments are an order of magnitude smaller than those proposed for Confidential Transactions, hide the whole value rather than only the mantissa, and do not depend on ring signatures.

I thought that CT represented the entire value in the mantissa, so isn't this a distinction without a difference?

Inputs do not have an exponent.  The exponent is a property of the range proof, not of the values themselves. They work by scaling the basis the proof operates over.

I'm not 100% sure of the CT method, but it sounds like some information about the exponent is exposed to make the proofs shorter (you could keep it secret at a big cost). Maybe not the input magnitude, but the proof exponent range is public, and that selection, can itself give some information away. This is why CT is targeted at smaller 32-bit numbers.

Between the soundness and efficiency improvements I went from thinking the probability of deployment of CT in bitcoin proper (rather than just in sidechains) was low but non-zero to-- with your scheme-- a view that its even likely eventually.

Am I interpreting this correctly that on the surface analysis Sumcoin (aka CCT) appears to be more sound than Blockstream's CT because in theory it appears to reveal less side channel information. However, in order for Sumcoin (CCT) to do this properly, then it needs to use a sum of three squares NIZKP and thus much of the efficiency gains are lost?

And thus it (and Blockstream's CT) probably wouldn't ever realistically make it into any serious coin (e.g. Bitcoin core chain) that has scaling issues (which is just about everything PoW right now)?

[Mixles]

1.  You wrote, "²To save space, SUM j=0 to outputs(∆j) is revealed as an unsigned integer at the transaction level.". Wouldn't such a sum allow some of the operands to be negative and others to be positive offseting. I presume you reveal the ∆ to prove the sum of the squares isn't negative, but appears that optimization in footnote ² is flawed.

Yeah. Footnote removed.

2. There appears to be a typo of an extra superfluous (or missing redundant) parenthesis, "fuzzbits ≈ (curvebits − reservedbits)/2) − valuebits".

Removed.

3. It appears you avoided factoring fuzzValue into a sum of three squares by inventing a heuristic (to factor into a sum of two squares) to save "50% storage and computation requirements", but at the cost of reducing the security of the value blinding by 1/3 to 1/2 of the bits. Why is this a wise tradeoff?

Finding the actual 3 squares for a specific random integer can get too expensive at these bit levels. Some (maybe all) algorithms require factoring (or similar expense), and it is not convenient for a user to have to factor 252-bit numbers to generate a transaction output (regardless of a coin network's scalability). I will do more background reading to see if there is a better alternative.

Worse than that, even if 3 exact squares are found, one of the three square roots is likely to turn out to be very small (fewer than 32 bits). None of the roots are blinded for the proofs to work; they have to be the actual commitments. Then either the prover has to generate a new random number and run large-integer factoring again (and again...), or the attacker will know that one of the 3 committed values is cheap to break. Then the smallest square might as well be in plaintext and save the 50% overhead anyway. To solve that problem, [38] suggests using a probabilistic ECC system instead of a deterministic one, which doubles the cost of all commitments (though there are probably some new methods to push some of the cost back down), introduces the need for additional explicit equality proofs and other complexities.

How do you know this heuristic will terminate with less computational cost than factoring?

There's a good chance that the first random number will just work.

If not, all the heuristic does is: two square roots, two squares, one difference, one addition and two comparisons. Plain ultra-fast ops to repeat. Nothing like factoring, and much less work than one ECC multiplication.

4. As another consequence of discarding factoring, how do you know that providing one equation of one unknown will not reveal fuzzValue? Does that equation have provably many solutions?

It does have many solutions, as there are many more integers close (up to ∆) to sums of squares than there are integers that are actually sums of squares. There are also many more sums of squares than there are squares. Easy way to think about it is to set ∆=1, and see how sums of squares can work with it (4+9+1=14, 9+16+1=26, 4+16+1=21, 16+25+1=42, 4+25+1=30, ...), and that this is only bounded by the modulus of the system.

A proof of exactly how well [sum_of_two_squares, sum_of_two_squares + n] covers the integers would be good to include in the paper (it might also help to calibrate a better upper limit for ∆), but difficult to come up with.

5. Since the security of x2 is lowered by 1/3 bits, how do you know that finding this additional variable thus providing two equations with two unknowns will not catastrophically weaken the security due to some clever algorithm such as for solutions of systems of non-linear equations? Your cited resource [38] pointed out that the prior attempts to be clever to avoid factoring the sum of three (or four) squares lead to a solution that was attackable from both the hardness of the discrete logarithm and the hardness of integer factoring simultaneously, thus required higher bit widths to compensate which ameliorated the efficiency of the algorithm. Isn't the burden of proof on your whitepaper to explain why your cleverness has not introduced analogous vulnerability. I am just really doubting this attempt to avoid factoring to 3 squares. I would naively tend to trust the guy who wrote that cited resource [38] given the breath of knowledge and peer review that apparently went into it.

The goal in those sources is to provide proof for a very specific integer, they have no choice to opt out of the high level problem. For application in transactions with fuzz blinding, CCT is not constrained in that way, and can simply pick a different random number at the output level. This is actually what is done at low level in many NIZKP of small magnitude. It is done in the NIZKP of source [38] itself, in section 4.22.2, heading "ZK-proof of membership in a much-widened interval." If the random w doesn't work, the algorithm just tries another w until it succeeds. This does not necessarily weaken the system, although as you mentioned, the burden of proof is on the whitepaper. I think solving your point 4 is sufficient.

Also as per my response to point 3, in a deterministic ECC system, using the actual three squares can reveal the smallest one of them.

[TPTB_need_war]

The problem was with an invalid assumption that two curves of different orders would not be able to generate proof of same negative value, as long as the negative value is in the small range being proved. They clearly can, because "m = r + c*x" allows a negative x to leak into the negative cx and then offset against the positive random r, and the resulting m is then used for both curves.

I thought of another strategy (with different tradeoffs) for proving each output value is not negative without relying on proving a square.

Employing an extra proof per output similar to the smallness NIZKP in the first version of your whitepaper (but multiplying by r instead of adding), I believe it can be proven that the sum of the outputs minus the output being proven is some fraction < 1 of the input sum without revealing anything about the magnitude of the inputs and outputs. If this is combined with input mixing, then to the extent that anonymity set can't be unmasked then the relative values can't be traced back to the original coinbase magnitudes.

The advantage is that cryptanalysis break of your proof of square would I assume reveal all the magnitudes and/or allow hidden inflation; whereas my above suggestion appears to afaics have more provable bits of security and doesn't introduce any hardness assumptions other than the discrete logarithm problem (and the probability of guessing correctly the r in the NIZKP?).

Conceptually you have pondered if Blockstream's CT might be exposing some information about the magnitude via the mantissa. My idea would instead expose some information about the relative values but not the magnitudes. Cautiously skeptical (and naive) I assume your proof of square is making some tradeoff that we can't see or perhaps it is just the reduction in the number of bits of blinding security.

My conservative thought is K.I.S.S., but then again I am not a cryptographer. Just sharing a wild idea.

[TPTB_need_war]

Worse than that, even if 3 exact squares are found, one of the three square roots is likely to turn out to be very small (fewer than 32 bits). None of the roots are blinded for the proofs to work; they have to be the actual commitments. Then either the prover has to generate a new random number and run large-integer factoring again (and again...), or the attacker will know that one of the 3 committed values is cheap to break. Then the smallest square might as well be in plaintext and save the 50% overhead anyway. To solve that problem, [38] suggests using a probabilistic ECC system instead of a deterministic one, which doubles the cost of all commitments (though there are probably some new methods to push some of the cost back down), introduces the need for additional explicit equality proofs and other complexities.

But afaics in exchange for that extra complexity, the reduced bits issue is eliminated. Whereas, isn't the weakened commitment E₂ explicit in your protocol?

4. As another consequence of discarding factoring, how do you know that providing one equation of one unknown will not reveal fuzzValue? Does that equation have provably many solutions?

It does have many solutions, as there are many more integers close (up to ∆) to sums of squares than there are integers that are actually sums of squares. There are also many more sums of squares than there are squares. Easy way to think about it is to set ∆=1, and see how sums of squares can work with it (4+9+1=14, 9+16+1=26, 4+16+1=21, 16+25+1=42, 4+25+1=30, ...), and that this is only bounded by the modulus of the system.

A proof of exactly how well [sum_of_two_squares, sum_of_two_squares + n] covers the integers would be good to include in the paper (it might also help to calibrate a better upper limit for ∆), but difficult to come up with.

I think solving your point 4 is sufficient.

But as I said, doesn't ∆ reveal a new simultaneous hardness assumption to the assumption of discrete logarithm hardness, especially in conjunction with the explicit weakened commiment? Whereas, in the sum of 3 squares approach, only the hardness of discrete logarithm is assumed.

Thus it feels very risky to me, but I dunno because I am naive and not a cryptographer. Would it be better to go full 3 squares and when that can't be found, perhaps fall back to my relative values exposed solution?

Edit: also concerned as well that the inflation resistance could also be susceptible to a cryptographic flaw:

https://bitcointalk.org/index.php?topic=68655.msg11733325#msg11733325

https://bitcointalk.org/index.php?topic=68655.msg11735107#msg11735107