Topic: [Crypto] Compact Confidential Transactions for Bitcoin - page 6. (Read 18452 times)

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?



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://bitcointalksearch.org/topic/m.11733325

https://bitcointalksearch.org/topic/m.11735107

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.

Yeah. Footnote removed.


Removed.


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.


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.


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.


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.

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)?

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.

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.

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

I will have a play tomorrow. Thanks.

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.

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?

---

Holy shit

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).

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'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.


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

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;




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



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;

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://bitcointalksearch.org/topic/confidential-transactions-content-privacy-for-bitcoin-transactions-1085273

Nope.


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.

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.

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

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

Request for comment

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