Bitcoin Forum

Request for comment

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

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.

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.

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.

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://bitcointalk.org/index.php?topic=1085273.0

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.

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

Holy shit

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?

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.

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.

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.

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

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.

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.

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://bitcointalk.org/index.php?topic=68655.msg11733325#msg11733325

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

Can you elaborate further? I don't see how m = r*c*x would be secure.


E1 and E2 bit strengths are both well defined, and are both stronger than 128 bits on a 768 bit curve (i.e. not weak).


Of course, there is a reduction in cryptanalysis complexity given by the attacker knowing that F1 and F2 are squares, and knowing an encryption of their sum. This is already baked into the bit security reduction from 188 fuzzbits to 64 E2 bits, and why the scheme is hungry for a large curve.

CCT does not rely on additional assumptions as included by [38]'s reference [25] (Boudot "Efficient Proofs that a Committed Number Lies in an Interval") Appendix A or B. It's also a sum. There is no product for an attacker to factor.

Probably I am incorrect, because I don't have much experience in this field, but why is it insecure if the verifier doesn't know r then how can verifier know x?

I envisioned two proofs, one for m = r*c*(sum of inputs) and n = r*c*(sum of outputs - output proving non-negative), i.e. same U and V used in both proofs. If n/m <= 1, then the output is non-negative (because also the sum of outputs * G = sum of inputs * G).

Afaics, all that is revealed is the ratio of the values, not the magnitudes. But I did it only quickly in my head, so maybe I screwed up. I am very rusty haven't been doing higher-level maths since decades.



You are asserting only the bit security has been weakened and thus can be compensated with a larger curve. I am thinking the attacker also knows a relationship between the sum (fuzzedValue) and a revealed constant (∆) that is not baked into the bit security reduction, specifically the point #4 that you admitted defines a set (probably smaller than Z_n) with attributes that are either not well understood or not yet explained.

Eve would multiply by multiplicative inverse of public c to find product z = r*x modN. Factor it. Maybe use some other equations too.


Yes, the set is smaller. That's why the bit security is lower.

∆ is a random number near any sum of squares. There are provably many more sums of squares than there are squares. There are as many possible squares as bits in x₂ allow. There are therefore many more possible fuzzedValue solutions for a single ∆ than iterations in brute forcing all the bits in E2=x₂*G.

Knowing exactly how many more possible fuzzedValue solutions for a single ∆ doesn't change that. Having the mathematical beauty explained Gauss-style over Z_n would be a nice-to-have for sake of pure mathematics, but I don't see it as necessary.

Edit: Curiously, if I used the third square for ∆ instead of a random number, I would also be concerned of some other relationship between that and the other two squares.

Afaik, the only purpose of c is so the prover doesn't cheat, so it is okay if it drops out for the verifier. I don't see how factoring can reduce the set of possibilities. There is no constraint on z other than r which the verifier doesn't know. The set of possibilities appears to be the bit security of r?


∆ has less entropy than fuzzbits because some of those degrees-of-freedom are constrained (discarded) by the smallness requirement on ∆, thus I don't see how you concluded that the lowerbound of the entropy is only that imparted to x₂. The relationship appears to me to be more complex.


The distinction afaics is that then you don't reveal it and the entropy is not knowingly constrained to less bits. That is why I thinking of the 3 squares when the sender can find a suitable set, and fall back to one of the other ideas if not. But any way I am not really qualified to do this and I am probably wasting your time.

x*r is discovered, which is much easier to factor to get [x, r, ...] as factors than doing ECDL. You're then relying on, as you put it earlier, a different hardness assumption.


Yes. The entropy in ∆ is specifically fuzzbits/2 bits. ∆ comes directly from the difference between a uniformly random number and a randomly selected sum of two squares (which are much more common than squares).


Qualification and pieces of paper are irrelevant. I don't have any certificates of cryptographic achievement myself. You challenge me to think about the assumptions, and that is a useful part of review.

Why isn't that also the case for m = r + c * x? Verifier knows c thus the possibilities for x are entirely determined by the possible values for r.

Isn't it still just a brute force search of the entropy in r?


The fuzz and the sum of squares are not independently random. And then there is the added constraint that all those ∆ > 2^fuzzbits/2 are discarded. I thus speculate that the lower bound of entropy is potentially much less than you calculated.

Because c*x is not modulo N, but some N-r, so you can't get the multiplicative inverse without the secret r, for which you need ECDL.


As I have proved in my earlier post, there are many more possible solutions for each ∆ than there are possible sums of squares. You cannot imply anything from ∆, which is a random number. If I picked ∆+1, ∆+2 or ∆+3, I could still pick with that, the same sum of squares with each, or any one of more than 2^fuzzbits/2 other sums of squares.

As uniform random numbers are picked and then their roots are taken, the distribution of the roots won't be uniform of course, while the distribution of the squares is. That's how squaring works. Fortunately, the roots will still be big enough to satisfy the bit security requirement.

I think that your square-roots have too few bits.

In your current scheme x1 has 126 bits.  Then x2^2 < 2*x1, hence x2 has only 64 bits. Since you publish x2*G, the baby-step giant-step algorithm would only have 32 bits complexity. It is even worse, since you know that the highest 32 bits of fuzzvalue are probably 0.  So x2 is almost trivially breakable.  Even x1 can be broken with ~50 bit complexity if one has a good guess what the value is.

So I think you should make the square roots at least about 250 bits, so that using baby-step giant-step is hard enough.  This means that you need more than 512 bit ECC.  Also don't use the scheme where x2 has only has half the bits of x1.

If you have multiple outputs you could distribute the squares over the outputs.  You could use a single square root x_i for each output, such that the first 64 bit of x_i^2 equal the satoshi amount.  Choose the lower bits of x_i at random except for the last one.  Then publish the square-roots and the difference Δ = sum inputs - sum x_i^2.  

BTW, how much information would leak if Δ = fuzzvalue - floor(sqrt(fuzzvalue))^2 is known (if there is only one output and the simple scheme is used)?  To avoid leaking the magnitude of x, one could make sure that Δ is not the smallest remainder but equally distributed with (fuzzbits+64)/2 bits.

I don't know what is this M you refer to. The only mod I say was 2^t on c only.


I can see that is true if finding the squares by any possible algorithm, but afaics the algorithm you have suggested restricts the sums of squares to specific values with the entropy of x2. Yet this entropy of x2 is further constrained because only some of those will satisfy the requirement that ∆ < 2^fuzzbits/2.

Updated paper to 768 bit curve for now, which brings square roots up to x1@220 and x2@190.

Baby-step giant-step algorithm is memory intensive. Eve would be spending 2^(190/2)=2^95 on storage and also a lot of CPU for 768-bit ECC, just to see a single root (not even the full single output).


x2 doesn't get that low generally, it retains about 87% as many bits as x1. Note, I am not rooting x1 to get x2, I am rooting |x1^2 - fuzzvalue|.


In your approach you have basically removed sum of squares and settled on a single square per output and Δ per txn?

I was also thinking of a less dramatic optimisation with a dominant x1 that is reused for each output (based on log mean), then only require additional x2 and Δ per output.


The bit lengths of everything will be revealed. I don't see a way to have Δ both evenly distributed and complete the exact output sum with a square x_i. If you mean to only publish one Δ for the whole transaction, then each output would be constrained to only ever spend square amounts. I guess you mean using multiple outputs to send the amount to save revealing a Δ per output?

I think I may understand what you were referring to. In your NIZKP it is necessary that it not be easy to guess an r that is negative such that x > b and c * b < m < T. (And why did you remove "3.6 Optional repeated application of smallness proof" from the new version of the paper?)

However that requirement (on inability to remove the crucial c from the Fiat-Shamir transform) appears to be unnecessary in my idea. I think this can be shown by noting that a NIZKP is not even required to construct my suggestion. The relative weights of the outputs can instead be explicitly stated by expressing each output as a multiple of some base magnitude commitment (mag * G), which proves each output is not negative (unless the input is but can't be due to transitivity).

It is still required to construct your NIZKP of smallness from the first iteration of the Sumcoin (CCT) paper, and better yet afaics this can then be done for the entire sum of the outputs instead of for each output separately.

What am I missing? Afaics my suggestion is much more efficient and secure.

I paradigm-shifted away from the intractable (security assurance and indeterminism of the) sum-of-squares approach(es) by thinking more holistically about the anonymity and the risk of enabling inflatacoin.

Didn't I just break your smallness proof? The attacker can always use a negative r then adjust the value of x accordingly. But the x * G has to match the value of the inputs (assuming non-negativity of outputs is assured), thus the attacker has to make a search for match.

I see why you dropped that section, because in the NI (non-interactive) context the hacker can search for R proofs which succeed, so the security is not improved. The only way to increase the security of (both blinding and smallness of) x is to increase the size of the curve.

Afaics, there needs to be some sum-of-squares NIZKP on r which should be much easier (deterministic) and more secure than attempting to constrain a sum-of-squares to fuzzedValue x. Probably should use the 3 squares approach of [38] which is entirely blinded.

Edit: ah thus the sum-of-squares smallness proof fails for the same reason recursively forever. Thus Sumcoin is broken and can't be fixed, i.e. [38] "ZK-proof of membership in a much-widened interval." only applies in the non-interactive context.

I think I see the solution and it avoids all zero-knowledge proofs. It is my former (unpublished because invalid) ridiculous simplification combined with my new idea.

Take my idea that the outputs are expressed as multiples of some base magnitude commitment for the transaction (not global for all transactions).

Then employ two curves to express the equality of the sum of the commitments of inputs and outputs.

So then in a simplified way of visualizing:

5 mod 5 = 15 mod 5 + 0 mod 5

5 mod 7 = 15 mod 7 + 4 mod 7

Before my recent idea to expose relative weights of the outputs, then the attacker could hide the unmatched excess (0 and 4) in the second output and only spending the matched inflation (15), but now he can't because the relative weights  (15 / 0 != 15 / 4) have to be consistent across both curves, even though the public base magnitude commitment isn't (the private base magnitude is consistent).

TADA :)

Unless I've missed something obvious (which is likely!), this radically simplifies, increases security, and increases efficiency.

Breaking this appears to be related to factoring the discrete logarithm?

Ah maybe we can fix this, c_i = Hash(U_i|V_i|c_i-1) mod 2^t where c_o = 0 or probably requires instead c_i = Hash(c_i-1) mod 2^t where c_o = U_i|V_i ∀ i. Set the required number of iterations of i high enough to be sure the attacker couldn't have guessed a negative r_i match on every iteration, no matter how many times he tries. The proofs get huge and the computational load explodes. This only has a chance to be viable if the chance of success on any try for r_i is greater if r_i is positive than if it is negative.

So the CCT which also hides relative weights of the outputs perhaps can be rescued, but with huge proofs.

Now we need to compare with Blockstream's CT.

Nope. This is a long time peer-reviewed proof, r cannot leak into x because of the equations the verifier checks. Please check literature for this.


Such interactive proofs can be converted to non-interactive. Then the hash limits the prover. If you can see some specific technicality that I've missed in the conversion, please let me know.


This is about soundness, which with t=128 in CCT is already high enough, so repeated application is not required.

Please spend more time to verify your work, as it takes me some time to get through the messages.


We don't want to reveal which output got most of the coins. That's kind of a big deal around here. Long term network analysis would reveal everything.

Fine, 440 fuzzbits + 64 bit brings x1 to 252 bit, which is what I had in mind.


But you choose x1 to be the square root rounded down.  Since x1^2 and (x1+1)^2 are only 2x1+1 away, this means x2^2 < 2x1+1.  Hence x2 is very small.


As I interpret it now, the fuzzvalue is really the value (as a very high precision number, 504 bits).  Only the first 64 bit are visible in the user interface and the lowest bits are chosen at random.  Rounding errors (in the range of a satoshi) could be displayed as part of the fee in the user interface.

True, every output must be a square in my scheme, but the square numbers are not that far apart.  Δ has worst case 253 bits. In the 440+64 bit scheme the rounding error due to choosing a square is only 10^-55 satoshi.  The added 440 bit fuzz value (which is needed for securing privacy) brings in much more rounding errors.

In this scheme, you can add Δ to the high-precision fee and you can randomize the lowest 256 bits of the fee before computing the outputs (the fee must be public anyway).  This way you don't reveal Δ at all.

I should add that it is not true that x1 has 220 random bits.  This is because x1 is the square-root of fuzzvalue rounded down:

Assuming you know that fuzzvalue is exactly 10 million bitcoins, i.e. it is a 440+50 bit number with the first 50 bits known. Then x1 = sqrt(fuzzvalue) is a 245 bit number with the first 50(!) bits known.  So x1 has "only" 195 random bits.  This is the worst case, though.

Essentially every known bit of the transaction value except leading zeros remove half a bit of the 220 random bits.  My scheme has the same problem.  I don't see it as a big problem since 195 bits should be secure against baby-step giant-step.

I assume the randint in the x1 line is just a typo.

Check the precision.  x1 should be 864566219253763970902429276239497915, and x2 should be 841252670382898896.

I assume python does now use full big integer precision since a float (0.5) is used.

Update: math.sqrt doesn't work, either.  Any python guru knows a way to compute square roots of a 500 bit number?

Yeah the python lied, verified your number in sage. x₂ is small, which makes the single square scheme more appealing.

With big curves the satoshi error is small. Paper revised to use single-square method. Will think further about 440+64.

I've added an Acknowledgements section, let me know if you're ok to be credited.

1. I think I found a problem in the zero-knowledge proof of F=x^2*G for a small x.  You need to include E,F in the hash.

Attack:

• Choose some small x_1, set E = x_1 G. 
• Choose r_1 in [0,T], random r_2,  compute U=r_1 G, V = r_2 E.
• Compute m = r_1 + Hash(U||V) * x_1.  Repeat from beginning until m in right interval
• Compute x_2 = (m - r_2) / Hash(U||V) (modular division),  F=x_2 E.
• Publish E,F,U,V,m as proof of small square.

Now E,F,U,V,m should be accepted by the verifier but F = x_1 x_2 G is not a square.

The problem is that currently the proof does not commit E and F.  Thus F can be changed after the hash is computed to fit the equation.  A simple c=Hash(E||F||U||V)  mod 2^t should fix this.


2. You can reduce the proof size by including the Hash c and omitting U,V.  U,V can be computed from mG - cE, mE - cF.  The verifier checks that hashing these values yields c.

3. As further optimization, r could contain 380 bits (47 bytes) additional information for the receiver.  If you know the transaction amount you can decode the message and vice versa(!), so one has to be careful with the encryption scheme.  I'm not sure about the security implications.  The ZK proof requires that r is randomly chosen, so the encrypted message must be indistinguishable from random bits.

What is the error in my math  ???

x = 2b
r = -b
m = -b + 2cb
cb <= 2cb - b <= (2^t)b - 1

c <= (2^t) - 1
2(2^t)b - 3b = (2^t)b - 1 + (2^t)b - (3b - 1)
(2^t)b <= 3b - 1
t <= 1

c = 0
2b - b <= (2^t)b - 1
b <= (2^t)b - 1
t >= 1, b >= 1


If prover can try over and over again, he can find an r, c, and x > b that solve the equation per the math above. By recursing the hash, you can require the prover to find those matching metrics over several proofs, where the guess was made once for all proofs. This can decrease the probability of guessing.



High enough for what? Does t=128 for the NIZKP exceed the security provided by the curve for the discrete logarithm?

Hey I am verifying my work. If I've missed something, then point it out. If you don't want me to try, then just say it.


Did you find any other flaw in my idea? If not, then I will be very pleased because my idea does not require any NIZKP and thus doesn't incur the cryptographic issues thereof, e.g. doesn't require huge curves. Need to evaluate the tradeoffs. Does my idea have unconditional security against inflation? Note my idea still employs your clever fuzzbits.

I've already stated upthread that when combined with mixing (e.g. Cryptonote ring sigs), then the output which got most of the coins will be obscured by the downstream mixing. But more importantly, I posited that due to mixing it won't be possible to trace back to coinbase, then the magnitude of the transfer will be unknown. Receiving 99% of a dust transaction isn't that informational. It is also possible to split a supermajority output into multiple minority outputs (which in either case says nothing about whether the outputs are large or small if mixing has been correctly employed). However, I have now contemplated that even though the output commitments to the ring of a Cryptonote mix would obscure the uncommitted magnitudes from the public, the uncommitted magnitude would be known to every member of the ring unless it was reasonable to have multiple realistic magnitudes that mapped to the same committed value? This is a crucial question and I am not knowledgeable enough about the ECC math to answer it. Can you or someone clarify? If the commitment value can not represent a multitude of realistic uncommitted magnitudes, then Cryptonote mixing would reveal the values in my design but not in yours which doesn't reveal relative weights of the outputs.

Hiding values without mixing is insufficient anonymity, because coins would still be traceable which leads to spender identity analysis such as when change outputs are merged (as inputs) into a transaction.

I'd like to see an improvement to the two weakness of Cryptonote wherein the output values (or the derivative transactions) must be equal when mixing senders in a ring for a transaction input and the rings must be mandatory for each member in the ring (otherwise combinatorial analysis can unmask the rings in some scenarios...which afaik sadly is currently unimplemented in any Cryptonote coin). The former is inefficient and complicates wallets because when paying in for example non-powers-of-10 values with Monero, the transaction ends up being multiple transactions of powers-of-10.

So assuming the answer to my crucial question above is positive, homomorphic encryption of value (my or your design) would at least hide magnitudes of transactions so that mixing would not need to be used on every transaction and when mixing is used, there will be multitude of values that can mixed in any ring. Even if the answer is negative, employing homomorphic encryption of value with multiple inputs each a Cryptonote ring, could allow the sender to mix with unequal commitments for as long as every permutation of possibilities provided the same sum. However this latter strategy would violate the need to make rings mandatory for each member in the ring, yet permutations might overlap much less frequently so this might be an alternative strategy to mandatory mixing.

Homomorphic encryption of value could be used to obscure the values even when mixes are not employed. However if the values are revealed by upstream mixing then my idea wouldn't obscure anything (unless the mandatory rings are abandoned) thus I await the answer to my crucial question.

The proof only shows that |x| < T (for |x|> T it succeeds with probability < 2^-t).  The number T is (2^t)b, t = 128 in the paper.

So for your slightly too large x it is easy to guess an r such that m is in [c*b, T].  However for |x| > T, every possible "c" needs a different choice of r for c*b < r+c*x < T to hold.  If you know c, you can compute a matching r, but this is impossible because the hash c depends on U = r*G.

Ah yes. I was thrown off by the statement that "prover also knows that x < b". The other statement that x ∈ [0,T] is inconsistent with the prior statement so apparently my logic filter chose one of the two. Symbols are important in math. I suggest not reusing a symbol that has two meanings. For clarity, I think that there needs to be a distinction between the uncommitted value of x claimed to recipient of the transaction and the committed value of x in the sum. But I am still confused I guess, because if the recipient is given a value for x that is greater than b, they wouldn't accept it. So something is illogical here or I am still missing something ? Edit: oh because the spender can spend to himself then spend that to other recipients with x < b in the output given the recipient. Thus the statement "prover also knows that x < b" is misleading. I suggest instead, "prover also knows that x < T, and x < b only if revealed to party other than prover, i.e. when not spending to self".

What is your reaction to rest of my prior post?

1. Wow. Fixed.

2. Amazing. Do you have any literature I could refer to for this trick?

3. Cool.

Wow. Thanks! This should squeeze the proof right down.

There is no reuse for different applications, x is the same x. The committed x is called E.

(x < b AND x ∈ [-T, T]) is true, because b < T


I pay Jack. I don't want Jack to know how much change I received. If ratios are revealed, Jack might know. Same if I pay employees Jack and Jill, they shouldn't find this out. A thorough network analysis will reveal the general flow of value in the system. You can rely on mixing to obfuscate this, I guess, but some people will prefer to just hide the values.

You cannot repeat with the same r, since allowing two c's for the same r would reveal x by a simple linear equation.  But if the prover can choose a different random r in each repetition and he knows which c he gets (since in the non-interactive case it is deterministic) building the second proof is not more difficult than building the first one.


No, the 380 bit security of the elliptic curve much exceeds the 128 bit security of t=128.  Mixles didn't choose the order of the curve so high to get more security, but to prevent wrap-arounds.  128 bit security is the same as the 256 bit bitcoin curve provides.

Moreover, the discrete logarithm can only attack zero knowledge.   If you can compute the discrete logarithm, the verifier can compute x from E and F and thus see the spent amount.  But it doesn't help the Prover to fake a proof (E,F,U,V,m) that shows that x is a "small" number and E=xG, F=xE.

To compute a fake proof, the prover can try to brute force the "r" values (hidden in U/V) or the "x" values (hidden in E/F) until he find one combination that fits, or try to attack the hash function to find r,x with Hash(x*G||x*x*G||r*G||r*x*G) = floor(-r / x).  Assuming that the hash function is secure, brute force is the only viable way.  This needs 2^t iterations on average unless log F is really a square of a small number. 

It depends on how one interprets the the < operator. If one interprets < as creating a set of integers, then your Venn diagram is correct, but if one interprets < as making a statement about a requirement on x, then your logic is incorrect. So to prevent misinterpretation, I suggest you make it unambiguous. One could argue that you could only mean the former interpretation due to the inconsistency otherwise, yet I still think you can clarify to prevent confusion.

Please also see my prior post, because I had edited it while you were writing. I explained the confusion that can arise.

Edit: you added this:


I mean differentiating between uncommitted value x when it is revealed to a recipient and not revealed.



There are numerous solutions to this issue.

Presumably the reason you don't want Jack to know is because you don't want him to know you have great wealth.  So break up your wealth into small portions employing a hierarchal deterministic wallet.

If you don't want Jack to be able to trace that value in the change to the next transaction, then mix the change output.


Not if mixing is employed.

Can you address my specific question about mixing because it also applies to how much your design can improve Cryptonote mixing?

How do you know that if one can break the discrete logarithm in such a way to establish a mathematical relationship between r with U,V and x with E,F, that one can't accelerate the search of the 2^t space?

I believe it to be sufficiently clear, and changing it would make it less clear.


I am not sure what the question is, because there is a lot of noisy verbiage. Have you not answered your own question? Cryptonote requires equal denominations, otherwise you can tell them apart. Your design makes it possible to tell them apart by their relative value. CCT is orthogonal to mixing, and as it says in the paper, can be used with CoinJoin or Cryptonote. Section 5.1: "Of course, the enhancement does not preclude a user from using additional address hiding protocols such as mixing, though the linkability of both the view key and the spend key must be considered. A hidden satoshi will mix as well as a hidden coin..." Of course, as the values are hidden, then you can't tell them apart.

Because the 2^t space is the result of a hash function, and you can't control what the bits of the hash will be. If you could do that, you would also be able to mine Bitcoin ultra fast.

More accurate is, "prover also knows x < T which is constrained to x < b by the sum of the inputs".

Proving x < T, implicitly proves x < b because the inputs were constrained transitive to the coinbase values. If not for revealing the coinbase value, you could not constrain b < 2^(fuzzbits+valuebits).

I disagree if you claim what you have now is more clear than the above wording. You are expecting the reader to make the above deduction. The reader has a different level of holistic insight than you who has been thinking about this specific design for a long time.



I challenge you to rewrite what I wrote on that issue and remove what you claim is "noise".


Afaics, Cryptonote if combined with homomorphic encryption would be spending commitments not denominations.

One of my questions was is it possible to have multiple denominations that have the same commitment value?


Your design does too. The relative value has nothing to do with it. Only equal commitments can be mixed[1].

[1] That is unless my other idea for mixing unequal commitments was employed where the sum of the inputs would need to be the same for every permutation of the commitments in the rings of all the inputs.


And that is wrong. If mixes are mixing equal denominations then it breaks your hiding of value, because to mix would mean to reveal value. That is why my question is so crucial.

And they are also not orthogonal because hiding value alone is not sufficient for preventing untraceability.

Ah yes, I see that now. Assuming the hash is truly random, no relationship can be established between those and the value c. Note however real world hash functions are not perfectly random, so I don't think it is quite accurate to claim 2^t, yet it is true to claim that cracking the discrete logarithm could only be combined with any attacks on the hash which reduce the entropy of the hash to less than 2^t. Attacks on hash functions have different qualities, such as preimage attacks, second preimage attacks, etc..

I am going to this level of detail because it is important to assess the risk of counterfeited value which would steal value from all holders of the coin via debasement, which afaik is a MAJOR concern (and potentially an obstacle) to putting value hiding in any serious coin.

Please at your leisure (no rush) kindly remove Anonymint from the Acknowledgements. Thank you for the kind gesture.

Please refer to CryptoNote whitepaper Section 4.5, https://www.cryptonote.org/whitepaper.pdf

"With a ring signature Bob can effectively hide every input among somebody else's; all possible spenders will be equiprobable, even the previous owner (Alice) has no more information than any observer. When signing his transaction Bob specifies n foreign outputs with the same amount as his output, mixing all of them without the participation of other users."

When values are hidden, the spenders are just as equiprobable, as when the denominations are equal.


Why would you purposely weaken the hiding system by only mixing equal denominations?

Isn't 128-bits deemed to be too low for hash functions? Afaik, 256-bit hash functions have only 128-bits of security against finding a collision due to the Birthday attack. Since afaics we are concerned with collisions in this application, I think the actual security is 2^(t/2) not 2^t and that is if the hash function is perfectly random.

The current Bitcoin block has 72 bits set to zero in the hash. It would require 2^56 times the current Bitcoin hash power to find a particular 128 bits of sha256 that you need to forge the proof in 10 minutes. Strong enough I think.

Please think your questions through before asking them - this is a thread about CCT, not Crypto 101 or CryptoNote. Some trivial questions are better directed to google, or a book on the subject.

How do you hide the value when all the commitments to the mix are the same and the other n equiprobable spenders also know the the value of their output commitment?

That is why I asked you is it possible to have different values map to the same commitment? I assume yes. The follow on question is can we find the set of values of that map to the same commitment?

I was challenging this claim:


Thus the actual security is perhaps 2^64 (but I am not sure if a collision attack can help the prover, probably not). But due to other potential weaknesses in real world hash functions, I am wondering if 128-bits is enough margin.

Hey I am playing devil's advocate because any risk of counterfeiting is too catastrophic. And I am trying to assess any difference in that risk to the idea I proposed.

Nope, it is 2^128. Once again, you cannot predict every bit in the hash, and there are 128 of them.

If you can find a weakness in the first 128 bits of real world sha256, please direct some of your insta-mined Bitcoins to my donation address. Alternatively, consult google or a book to find out why that is hard.

When those hashed commitments are spent as inputs to a CCT transaction then the unequal commitments are revealed. So you can not use hashed unequal commitments in a Cryptonote ring without unmasking who the sender is when those commitments are revealed as inputs later on.

Afaik we can't assume every possible unknown attack would be uniformly distributed over the bits of a hash function.

I am wondering how books can make me omniscient about what is not yet discovered  ::)

Ok, so your question should actually be "Since CN requires the hashes of commitments to be the same, and CCT requires the hashes of commitments to be different, are the two compatible?"

Asking that could have saved me a few hours. This is the first time I've been able to figure out what the question actually was (assuming it is that).

Ok, off the top of my head, this might be possible with something like chameleon hash functions, and/or different proofs, but may be very tricky to solve.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.3262

You appear to be confused. (or I am)

My assumption is that in Bitcoin 101 any hash is the hash of the public key that will be used to do the ECDSA.

The value is not hashed. The values have to be known to the public and are associated to the hashed public keys.

As for Cryptonote, I assume the public keys can not be hashed, because you'd have no way to compose the ring signature if you can't access the public keys (but that is beside the point that the associated values are not hashed in any case).

Seems you are entirely missing my point, which is that n foreign outputs in a ring sig will all have the same (commitment) value. And thus all those n know the actual value committed, which thus potentially breaks the value hiding of homomorphic encryption. I am asking (for the 3rd time), is it possible to have multiple uncommitted values that result in the same commitment value?

Signing any transaction involves hashing the transaction outputs including the value, then signing the hash.


Seems like we're talking different languages. I would suggest using formulas instead, but a better idea is to postpone this discussion until the rest of CCT is figured out and I get some weeks to study ring sigs.

You want to generate multiple uncommitted values that result in the same committed value. This is not possible with a deterministic point commitment, and impractical with a probabilistic system (off the top of my head). The reason you needed this property, however, is for the commitment hash to be the same for all commitments so that signatures can be done. I suggested instead that the commitments can remain different, so long as their [chameleon or other proof] hash is the same for the purpose of signing.

Given how catastrophic breaking the smallness is for ALL holders of the the entire coin (suspicion of can cause a selloff for the entire coin in some scenarios, e.g. when is a pegged BTC side chain), I think it is wiser to use 256-bits of hash security. Some systems even recommend 512-bit hashes now. So I guess you'd need a larger curve yet again. You may disagree, but I am thinking this is the way some people will view it.

I am not selling a product, and math careth not what people (including me) think.

You are welcome to implement CCT with t=256 bits, and curves of 1024 bits.

Please get a book on hash functions and information theory. Claude Shannon's papers, Turing, etc. Break the first 128 bits of sha256 and mine huge amounts of Bitcoins.

I don't know how many hints to give you. Even if you're right, it is just an arbitrary constant that can be changed by any implementation, and the hash function can be changed. Move on.

Afaics, that is irrelevant. Afaik the output values are not hidden by the transaction hash because they are separably spendable. The hash is the way to compress what is public into a fewer number of bits that can be referenced. The outputs to a mix are public and must be the same with Cryptonote if the anonymity is to be achieved.


I don't see how anything about hashes helps in any way, because afaics the commitments have to be revealed publicly when they are spent as inputs into a CCT transaction. So when the other n spend their outputs then all the obscurity attempted by hashes would be unmasked.

So if it is unrealistic to have multiple uncommitted values correspond to the same commitment value, then for Cryptonote the only way is to mix equal commitments, but in your design that doesn't entirely unmask values because before and after spending in and out of a Cryptonote mix, one could create a CCT transaction spent to self to hide how much of the revealed value was in each output and input respectively. Since the values are hidden, for a CoinJoin mix where each input value is split into two or more outputs then no one knows whose input corresponds to whose outputs so unequal commitments could be employed.

So if it is unrealistic to have multiple uncommitted values correspond to the same commitment value, my idea for a homomorphic value hiding design would not work because the magnitudes would not be hidden across mixes.

I need to do some thinking about what hiding values really adds to Cryptonote mixing that can't also be achieved by spending to self a large balance and spending the change output to others to obscure that one holds a large amount of wealth? Because hiding values does risk undiscovered counterfeiting if a cryptographic breakage is secretly discovered.

WTF  ???

This was a discussion that started with pondering why you removed a section that was in the prior version of your whitepaper. Then after that was clarified, the discussion proceeded where johoe explained that the inflation resistance security is 2^t. Then I pointed out that t = 128-bit might be too aggressive. Johoe has pointed out that your 64-bit assumption for the square root was too weak and subject to a known form of attack (which was after me sharing with you my thoughts about the entropy being too low and you dismissing me and later on dissing me), so you raised the size of the curve in the paper. I accepted that you may not feel warranted to raise the size of the 128-bit hash dependency in the default implementation in your paper, but I just wanted to note some reasons that 256-bit hashes have been become more prominently employed in critical situations.

Then you slander me in every other (or third) post with snide insinuations about needing to get an education, about writing noise. Social skills are apparently not your greatest asset.

Btw, I bet I've done a lot more reading about hash functions than you have. For example, do you know what a Merkle–Damgård construction is? Do you know what a wide pipe design means? Etc, etc, etc.

Edit: also you equate two cases which are not at all similar. One only needs to break CCT's inflation resistance once, to create nearly infinite coins. Whereas any break of SHA256 to mine coins would need to do it over and over again at a very fast rate. That mistake in evaluating security risk indicates that maybe you are the one who needs to read some more books.

P.S. I did recently start to read up on ECC.  I did this when I was wondering why we couldn't just detect the sign of the value in the commitment. I learned about the structure of the curves and how it is mirrored across the x-axis and thus -P = (x,-y). And I learned that every abelian group has an inverse element such that the group operator (e.g. +) can be applied to the inverse element (instead of the concept of subtraction being distinct from adding a negative number). So I realized that a cyclical group wraps onto itself and thus positive and negative values can occupy the same points unlike the number line of for example integers which extend to infinity from both directions from the abelian group origin 0 (zero).

Edit#2: your work has been broken 2 times in 2 weeks, so I don't think you should be talking down to anyone, especially not one who is sincerely trying to help and understand. Thanks.

Not talking down to you. Merely telling you 3 times, with increasing assertiveness, that this one particular line of inquiry is a dead end (reasons both explained and in literature), as you have asked me to tell you.


As I said, it is a well known security parameter that is good enough, and can be changed by any implementation. It can also be upgraded in-flight along with the curve size. The hash function can be changed to a different function. It is clearly not broken and not worth 10 forum posts. The noise generated by such posts can bury johoe's contributions, each of which are very succinct and very significant. An example for both of us.



There are 16060000 10-minute blocks in 100 years. So you need to dedicate the current Bitcoin network hashing power for 100 years to reduce that to 2^32, during which the hash length (or function family) will probably be upgraded (mitigating your attempt and losing you many years of Bitcoin block rewards), and quantum computers will be all the rage. Just switching the hash function nesting (e.g. sha(sha(sha(E|F|U|V)))%128) every couple of years (maybe even automatically based on the hash of some recent block checkpoint) is sufficient to prevent the attack, without changing the bit length. This is probably a better way to discourage practical attack, rather than to have a single unmoving target sit there for 100 years.

Please move on to the other ideas, as I will not be spending any more time on this, nor on making things personal.

It's not a collision attack between two hashes.  There is only one hash involved here and it has to fit its own input.  If the hash function is a random oracle it is possible to prove that 2^t calls to the hash oracle are necessary on average to produce a fake proof.  Of course, true hash functions are not random oracles, but they come very close.  I think there is more trust in current hash functions than, say, in ECC (simply because hash functions have been longer around than ECC).  Also current hash functions cannot be broken by quantum computers as far as I know.

I understand that you want to play devil's advocate and I agree that the impact is much larger than in the crypto used in the Bitcoin main chain.  If you can fake a single signature in bitcoin, you can just access one output, but if you can fake a proof of being a small positive number, you can drain the whole side-chain.  If CCT would be implemented in the main chain, you can even mint as much money as you want and it would be undetectable unless you spend too much.

My personal opinion is that the security t=128 is good enough for now but it may change in a few decades if the cost per computation continues to decrease exponentially at the same rate it has done so far.

The input and output values are not the same, as there will be transaction fees and some randomness in the sub-satoshi area of the fuzzvalue.   The sub-satoshi area alone should provide about 200 bits of random difference between input and output which is secure against logarithm.  So I think in the worst case it should still be secure against an outside analyzer.  It could be that some participants of the transaction gain more information, since they also have to exchange the exact fee spent by the outputs of any partially build transaction.  But I think it could be similarly solved as the problem of adding inputs and outputs without knowing who added which input and which output.

Quantum computing apparently enables Grover's algorithm which afaik effectively reduces to 2^(t/2). This is one reason to prefer 256-bit hashes, although practical quantum computers would be probably be at least 10 - 15 years from now.

My concern is that when analyzing the security of hash functions, there are subtle degradations such as distinguishers, near-collision attacks, boomerang attacks, etc.. I do not think we can fathom all the ways such potential attacks may interact with the other invariants, in a such a way that reduces the entropy. I think it is fool's folly to assume otherwise and advocate such aggressive tolerances. It runs counter to my sensibilities as an engineer to underdesign for failure tolerance. Perhaps I have missed some mathematical insight which invalidates my concern but generally it is more difficult to prove something can't exist than it is to argue about what is known to exist. If so, please feel free to point it out. Mea culpa in advance.


Seems you continue to miss the point I made, which is that any breakage for Bitcoin's use of a hash function, would need to be replicated a multitude of times (without detection) in order to do widespread damage. Whereas, with homomorphic value hiding, your design's employment of a hash function only needs to be broken once to destroy the entire coin (unless that breakage can be detected and corrected). Edit: if you argued that the difference in brute force computation for breaking the hash function once or 1024 times is only 2^10, I would retort that the breakage might be opportunistic on a particular input structure that only occurs once per year. My point is we can't just pull strong assumptions out of our ass.

You know it all though, so when you say a line of inquiry has no merit, then you are always correct:

Here and in your other post earlier, you seem to misunderstand that I was asking and asserting certain ideas based around my idea for a different design that employed two sums on two different elliptic curves with revealed weights, but that idea hinged on being able to use ring signatures to mix who is the source of each input with the additional requirement that it would need to be possible to have a multitude of different values map to the same commitment value. When Mixles confirmed that the last requirement was implausible, I abandoned that idea.

It is understandable that you would lose track of what I referring to, because I compacted (multiplexed) orthogonal thought processes into my posts and it can be difficult enough to follow through writing the non-intertwined thoughts of another person. I wasn't going to mention this on your prior illustration of this misunderstanding, but then on your second invocation, I decided to add this explanation of the confusion I had introduced.

I have since abandoned homomorphic value hiding entirely. I now believe it doesn't add anything that can't be accomplished with careful management of Cryptonote ring sigs. And it adds the catastrophic risk of undetected inflation (no matter how implausible the risk) and destroys tracking of aggregate statistics on the economy such as velocity of money. That is my marketing opinion, which is orthogonal to the technical work (which is I think is interesting), so please continue without me. Thanks for allowing me to investigate and get my questions answered.

None of these attacks apply to a single hash, which is what we have.

A priest could simply ask God to adjust the hash, but you are correct, that is not something that I can disprove.


I have specifically addressed this very point in multiple ways. Why limit to 2^10? Making the hash structure different does not need to be linear at all. The structure can be arbitrarily different like a tree structure: hash(reverse_x | hash(hash(x) | hash(reverse_x))) for another 2^128. Take the last 128 bits of an un-knowable-in-advance block hash, and construct a completely different Merkle tree every month.

This is unnecessary, of course, because a single 128 bit hash is sound enough and can be upgraded in flight for when quantum computers come into their own. Further unnecessary because any implementation can change the number to 256 or 512; if they need more, or are plain superstitious.


As you know, Bitcoin doesn't show the real velocity of money, because holders can just shift coins between their own wallets. There are a bunch of attempts at trying to differentiate between the uses, like days destroyed, but they are hugely inaccurate and subject to gaming as well. A more reliable indication of activity comes from market price of fees, which are expensive to manipulate, and are public in both CT and CCT.

Thanks for your technical analysis and marketing opinion.

Yes, I didn't think of Grover's algorithm.  However when practical quantum computers arrive, the scheme is not useful anymore.  Breaking DLP on 768 bit curves should be much easier than Grover's algorithm, which still needs 768 bit curve multiplications in this setting.


What you need to break is hash128(f(c,x1,x2,m)) = c,  where hash128 is whatever hash function is chosen for the scheme and f is a complicated injective function involving 768 bit ECC multiplications (which needs hundreds of thousands of 64-bit operations) and which uses different kinds of operations than the hash function.  Changing a bit in the input of f should change several 100 bits in the output of f.  It is similar to but more complicated than a fixed-point attack.  Does this kind of attack to hash128 have a special name? 

The function f(c,x1,x2,m) is x1*G|x2*x1*G|(m-c*x1)*G|(m-c*x2)*x1*G in case you wonder, where x1,x2 are 768bit numbers, m is 380 bit and c 128bit.  It is not injective only if x1=x2<T, in which case the proof is not fake.

Anyway, for t=256, the scheme can be easily adapted: use 1024 bit elliptic curves.  For every output, the sender needs to provide E,F (2*129 bytes), m (64 bytes), c (32 bytes) and as usual an output script (~26 bytes).  So in total 380 bytes.   That is 33 % more than the 284 bytes needed for t=128 but it is still reasonably small.

Did I forget anything in the size estimation?  The values U,V can be computed from c. The value x can be computed by the receiver from the ZK proof if value r is chosen using a secure deterministic random number generator seeded with a shared secret between sender and receiver.  The value Delta would be included in the fee.  The fee is another 64 byte value that needs to be included in every transaction (but only once even if there are many outputs).  The size of the inputs does not change.

x is smaller than r, so might as well share x (32 bytes) as the secret between sender and receiver. Less implementation hassle and space for some different encrypted short message in r.

I have E (97) F (97) m (48) c (16) enc(x) (32) for 290 bytes on 768 bit curve.

My thought is that if transaction fees were a significant fixed percentage, then transaction volume would more accurately reflect commerce. Edit: I guess that is your point to weighting transaction value by fee.

My other thought is that revealing fees when they are a fixed percentage in the system, breaks value hiding.

My other thought is afaik CCT has no means of enforcing a fixed percentage system wide.

Edit: note fixed percentage transaction fees are not competitive (if they are significant and what is the point if they aren't significant) against a system where transaction fees are set according to costs. So my thoughts might be irrelevant, except for unresolvable complications where such costs are not symmetric between who creates a transaction and who pays for the cost of hosting the transaction such as in Bitcoin where the entire system pays the centralization costs of spam if the block size if unlimited.

I'm reasonably confident that the paper as written on July 3 works. I'm a bit unsure about the perf characteristics (specifically can we find a 768-bit curve for which arithmetic can be implemented efficiently? gmaxwell is thinking a little bit about this) and exact security parameters (though they look good at first glance).

I think it's worth writing a "proper" academic security proof, with a reduction to discrete log and/or security of the proof-of-two-discrete-logs.

I'm sorry your thread was so badly derailed as to be basically unreadable. When we get to a point where I can be more sure of the paper's correctness I guess you should start a new one.

I've been toying around with a 384 bit quadratic extension field curve that supports a four dimensional endomorphism (GLV-GLS).  The use of the quadratic extension avoids much of the bad scaling, but I'm not to a point where I can benchmark anything yet.

Very interesting stuff, I will keep my eyes on both threads (this one and also the original Confidential Transactions). 

I have had a little bit of time, so I can present an up-to-date apples-to-oranges comparison results from my most recent CCT test:

Criteria	BlockstreamCT	DenisCCT	Improvement
value bits hidden	32	64	100%
blockchain space	2.55kB	0.30kB	850%
verifications per sec	1300	800	-38%

CCT was tested using OpenSSL (normalised by factor 1.82 from Q9550 to i7-4770R) whereas the published CT result was using libsecp256k1, which is a much faster curve-specific library (20x faster than OpenSSL).

I believe with a faster library and picking a convenient curve, CCT can reach performance parity. Curve extensions, and/or using the point halving multiplication algorithm could yield further performance gains.

Thinking of replacing U and V in the hash with their sum W = U + V = r*G + r*E then c=HASH(E||F||W).

Then the verification can be done in a single multiply-add step as m*G + (m-c)*E - c*F, instead of the current two steps.

384 bits perfectly fit into 243 trits, is there an advantage of using balanced trinary numeral system (https://en.wikipedia.org/wiki/Balanced_ternary) instead of binary?

Without this optimization, I'm up to 800 verifications per second now (implemented efficient inversions).

With this optimization, I'm up to 1400 verifications per second, which would make CCT faster than CT (even before we get into curve extensions).

Can anyone suggest an attack on the optimization, or maybe suggest a proof of its validity?

This is sortof what is done for the scalars in Joint Sparse Form multiplication, see "Low-Weight Binary Representations for Pairs of Integers" http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.440

I don't know how it can be applied to curve representation. Do you have an idea?

Well, I'm asking because I'm not completely familiar with this stuff. I noticed that representation of numbers in balanced trinary form does give some advantage (e.g. https://www.cdc.informatik.tu-darmstadt.de/~dahmen/papers/DOT05b.pdf), also balanced trinary is the only numeral system where multiplication is as simple as in binary, and addition is even simpler (carry propagation happens less often). Even more, balanced trinary doesn't require a special "bit" to represent the sign of a number, i.e. naturally stores the sign inside its digits. All this should speedup math beyond inherent advantage of trinary being closer to 2.718 than binary, this is why I asked the question.

Ah yes, I've seen this. It is also about scalar representation, it is an improvement on Joint Sparse Form with a speed up of 10%.

The reason I'm not doing stuff like this is basically the effort:improvement ratio. It would take months/years to get this 10% improvement (probably I would write a new crypto library, and still it would not be mature nor well reviewed), whereas by improving the protocol (or usage of OpenSSL) I could still get a 60% improvement in days. I don't implement GLV-GLS for the same reason. Avoiding premature optimization. There could be a special curve that is fast enough to multiply by some other method.

The optimization doesn't work.

For E=a*G, F = (-a-2)*E,  F is a negative number but it can be "proved" with the new protocol:

  W = U + V = r*G + r*E,  c=HASH(E||F||W)
  m = r - c*a

satisfy m*G + (m-c)*E - c*F = W

That was quick, thanks! I can see it now.

Denis, on quick glance this appears to be superior to the current Distribute algorithm that appears in Appendix A of your paper:

http://math.stackexchange.com/questions/1276206/method-of-generating-random-numbers-that-sum-to-100-is-this-truly-random

I want to compute the probabilities of restarting the protocol in step 4 of the section 3.52 proof of small magnitude (http://voxelsoft.com/dev/cct.pdf#page=7) of Compact Confidential Transactions. I will be more verbose to attempt to make this comprehensible to those who didn't complete relevant courses in Calculus and Probability Theory. Please check my math below. Tangentially, am I correct that step 4 in the white paper is currently missing a required stipulation that the protocol must also be restarted if c = 0?

Joint Probability of Sum

In consideration of the relevant value r + c * x̄ (where x is renamed x̄ so isn't confused with x-axis below) from step 3 (of the proof of magnitude within a much larger interval T), then in general the probability that any sum (e.g. x + y) is greater (or separately less) than some chosen value k, can be modeled by the area above (or respectively below) the line x + y = k within the rectangle containing the range of tuples (x, y) and relative to the total area of said rectangle. For example, if the possible values of x and y are between 0 and 1, then the probability of x + y ≥ 1 (i.e. k = 1), is given by the area above the line y = 1 - x bounded by the unit square[1] divided by the area of the said square as shown below:

http://i.stack.imgur.com/AwCou.png (http://math.stackexchange.com/questions/285362/choosing-two-random-numbers-in-0-1-what-is-the-probability-that-sum-of-them)

The area above the line y = 1 - x contained within the unit-square can be computed by integrating (https://www.youtube.com/watch?v=1FICxdXswIs) over the difference (distance) between (https://www.youtube.com/watch?v=fZ9iHFHMdsQ) the square's top line y = 1 and the lower line y = 1 - x over the interval where the line intersects and is within the said square from x = 0 to x = 1:

area = ∫¹₀ 1 - (1 - x) dx = x²/2 |¹₀ = 1²/2 - 0²/2 = ½

Since the total area of the unit square is 1 * 1 = 1, then P(X + Y ≥ 1) = ½ / 1 = ½.

Note this can also be computed as double integral directly computing the area between the unit-square as the upper curve and the line y = 1 - x as the lower curve:

∫¹₀∫¹_1-x dy dx = ∫¹₀ (y |¹_1-x) dx = ∫¹₀ 1 - (1 - x) dx.

---

Note n00bs may skip this paragraph. The above is a 2D simplification that only applies where x and y are independent and uniformly distributed (https://en.wikipedia.org/wiki/Uniform_distribution_(continuous)) variables, which applies in our case. Given x and y are independent but not uniformly distributed, then (even though it doesn't apply in our case but stated to so as to be thorough) the joint probability distribution function (https://en.wikipedia.org/wiki/Probability_density_function) (pdf) of x and y must be plotted along the z-axis to compute the 3D volume above the 3D plane x + y = k (which requires a double integral to compute, as we will see when we consider the joint probability of sums and products). The joint pdf is the convolution of the independent pdfs[1] as intuitively depicted below for the uniform distribution case. In the animation below visualize 1 + 1 = 2 (as the two distributions first touch) has a probability of ~0 and ½ + ½ = 1 has the maximum probability (because the pdfs of x and y are maximally overlapped).

https://upload.wikimedia.org/wikipedia/commons/6/6a/Convolution_of_box_signal_with_itself2.gif (https://en.wikipedia.org/w/index.php?title=Convolution&oldid=690216758#Visual_explanation)

---

Joint Probability of Product

In general the probability that any product (e.g. x * y) is greater (or separately less) than some chosen value k, can be modeled by the area above (or respectively below) the hyperbola x * y = k within the rectangle containing the range of tuples (x, y) and relative to the total area of said rectangle. For example, if the possible values of x and y are between 0 and 2, then the probability of x * y ≥ 1 (i.e. k =1), is given by the area above the hyperbola y = 1 / x bounded by the two-unit square[2] divided by the area of the said square as shown below (note only the hyperbola is draw below and the two-unit square is not shown so just draw it in your mind). Note that in this example a unit-square (as opposed to a two-unit square) would contain none of the area above the hyperbola, because mean of the product of two (independently, uniformly distributed) numbers is half the mean of the product, e.g. 16 (mean of 8) = 16 * 1 (means of 8 * ½) = 8 * 2 (means of 4 * 1) = 4 * 4 (means of 2 * 2) with mean of 8 for [0, 16], 4 for [0, 8], 2 for [0,4], and 1 for [0,2]:

https://upload.wikimedia.org/wikipedia/commons/1/13/Hyperbola_construction_-_parallelogram_method.gif (https://en.wikipedia.org/w/index.php?title=Hyperbola&oldid=689732565#Geometrical_constructions)

The area above the hyperbola y = 1 / x contained within the two-unit square can be computed by integrating over the difference (distance) between the square's top line y = 2 and the lower hyperbola y = 1 / x over the interval where the hyperbola intersects and is within the said square from x = ½ to x = 2:

area = ∫²_½ 2 - 1/x dx = 2 * x - ln(|x|) |²_½ = 4 - ln(2) - (1 - ln(½)) = 3 - 2 * ln(2) = 1.6137

Since the total area of the two-unit square is 2 * 2 = 4, then P(X * Y ≥ 1) = 1.6137 / 4 = 0.40343.

Note this can also be computed as double integral directly computing the area between the two-unit-square as the upper curve and the hyperbola y = 1 / x as the lower curve:

∫²_½∫²_1/x dy dx = ∫²_½ (y |²_1/x) dx = ∫²_½ 2 - 1/x dx.

Joint Probability of Sum and Product

(Again assuming the simplification of independent and uniformly distributed variables x, y, and z, then ) In general the probability that any sum and product (e.g. z + x * y) is greater (or separately less) than some chosen value k, can be modeled by the 3D volume above (or respectively below) the 3D hyperbolic paraboloid z + x * y = k within the 3D cuboid (i.e. cube without requirement for equal area sides) containing the range of triples (x, y, z) and relative to the total volume of said cuboid. A third axis z is required to model the joint probability of (two) combined 2D joint (sum and product) probabilities.

Afaik, generally the closed form of computing the volume under a 3D curve constrained by another 3D curve is complex because the definite integral needs the definite bounds of the intersection of the two curves on each axis, which can require for example rebasing the equation to a suitable coordinate system such as the use polar coordinates in Example 2 of [3].

The 3D hyperbolic paraboloid is a saddle shape[4] where cross-sectional hyperbola x * y = k - z (where z is constant for the cross-section) drifts lower moving away from the origin as shown below. Note the equations for hyperbola and hyperbolic paraboloid at Wikipedia and else where contain x² and y² terms and mine above do not, this is because those equations have the center axis aligned with an axis of the coordinate system as depicted below:

http://www.math.ubc.ca/~cwsei/math200/graphics/hyperbolic_paraboloid_1.gifhttp://www.math.ubc.ca/~cwsei/math200/graphics/hyperbolic_paraboloid_2.gif (http://www.math.ubc.ca/~cwsei/math200/graphics/hyperbolic_paraboloid.html)

So visualizing the above rotated to as the hyperbola was depicted for Joint Product of Sum for z = 0 cross-section for 3D hyperbolic paraboloid and considering the relevant r + c * x̄ from the white paper, then a cuboid defined by the 3D segment [(0,0,0), (b, 2^t, T)], I attempt to write the correct integral to compute volume above the hyperbolic paraboloid and contained within 4 faces of the cuboid:

volume = ∫^k₀∫^(k-z)/2t_b∫^2t_(k-z)/x dy dx dz = ∫^k₀∫^(k-z)/2t_b 2^t - (k-z)/x dx dz = ∫^k₀ (2^t * x - (k-z) * ln(|x|) |^(k-z)/2t_b) dz.

volume = ∫^k₀ (k-z)(1 - ln(|(k-z)/2^t|)) - 2^t * b + (k-z) * ln(|b|) dz

volume = 1/4 (-z (b 2^t+2+3 z)-k²+2 (k-z)² log(2^-t (k-z))+6 k z)+log(b) (k z-z²/2)+constant |^k₀ (as integrated by Wolfram Alpha)

Even if the above is correct so far (which I am not so confident of[5]), it assumes k < T and it doesn't subtract the volume above the hyperbolic paraboloid that is under the bottom two faces of the cuboid. So the correct probability would be smaller.

For the moment, I have expended my available time to further this.

Can anyone help finish this and compute some sample probabilities for the originally stated goal at the top of this post?

[1] http://math.stackexchange.com/questions/285362/choosing-two-random-numbers-in-0-1-what-is-the-probability-that-sum-of-them

[2] http://math.stackexchange.com/questions/1292294/find-the-probability-of-the-product-of-two-random-variables

[3] http://mathinsight.org/double_integral_volume

[4] http://www.math.ubc.ca/~cwsei/math200/graphics/hyperbolic_paraboloid.html

[5] http://math.stackexchange.com/questions/581440/finding-the-volume-of-a-region-below-a-plane-and-above-a-paraboloid-triple-inte

1. As per responses within the link, at first glance, this does not achieve uniform distribution, and therefore is not a good choice to replace Distribute.

2. Following the sum-of-squares approach, Distribute algorithm has become a minor (and optional) part, as it is now only used by the miners. I kept it in as it looks pretty, could easily be useful for related applications (and took some effort to test and typeset neatly...), so would be a shame to leave out.

3. The Distribute algorithm, if used, already runs in a trivial time compared to the elliptic curve operations.

Sounds like a useful thing to calculate.


The probability of this happening is 1 in 2^128, or about as likely as breaking 128-bit security. The impact is that the single output would be revealed, as then m=r. You're right in that the protocol, technically, should restart in this unlikely case.

I believe I have more need to calculate this in my version of Compact Confidential Transactions, because I eliminate the use of squaring to prove x ∈[0,T]. Thus the probability of restarting the protocol is greater in my version of your design. Afaics in my design, there is a trade-off between that probability and performance of verification. This also ties into proving that values are not dust, which afaics will become critical for anti-DDoS (against bot nets) when implementing micro-transactions (noting that Lightning Networks can't do end-to-end principled anonymity), which I will explain in a new thread I will create today (https://bitcointalk.org/index.php?topic=1249015.msg12969405#msg12969405) in this Development & Technical Discussion forum (as the issue pertains to Bitcoin). This will become more clear once I have published my design. I am rushing to get to the point where I can publish.

Note I may have errors in my thinking because no one has checked my work, I haven't implemented my design yet, I am not a mathematician (took mathematics courses in college but 30 years ago and haven't employed higher maths much hence until recently autodidact on crypto), my mind is scattered all over on many aspects of holistic design for a crypto-currency, and I am still some what "foggy brain" from my ongoing battle with (undiagnosed specificity of) autoimmune disease.

---

Afaics the comments under Thomas Andrew's answer argue that it does achieve a more uniform distribution than just subtracting iteratively starting from 100 in a deterministic number of steps, because it doesn't favor the first value having a 50% chance of being greater than 50. Your Distribute is sorting random values and adding differences, so perhaps yours is equivalently or more uniformly distributed, but since it is iterative in a non-deterministic number of steps, I think it may be slower than what Thomas Andrew proposed?

Perhaps the only way to get a perfectly uniform distribution is to select uniformly distributed random values until they sum as required, but this would be computationally prohibitive. Further analysis would be to examine how the non-uniformity in the algorithm employed impacts the security and/or the probability of restarting the protocol in step 4 (and any other impacts).


Please consider to not remove because my version of your design eliminates the use of sum-of-squares (so the huge 801-bit ECC curve isn't needed and other impacts), and I cite your paper rather than repeat everything from your paper.


I hadn't thought of that. Nevertheless I think it is useful to have two algorithms to compare, so with further analysis perhaps someone can determine which has better uniformity of distribution if so.


Agreed and inserted into your comment that t is a configurable parameter.

Someone at UCL suggested a couple of ways to achieve smaller curves with sum-of-squares (maybe this would improve your idea too). I am very tired after a busy week (devcon1), will be trying out the approaches next week.


I have found that peer review has been very useful to move the work forward. There are many things that I have thought of previously, but discarded too quickly (or assumed too hastily), and it is helpful when people point them out. Happy to have a critical look at your method in public or in private.

Someone at UCL has pointed out the assumption of unknown factorisation for the modulo group, that underlies the CFT proof. This means that CFT proof is not (automatically under ECDL assumption) secure in EC, as the curve order is possible to calculate and factor.

CCT is dead. Long live CCT.

I have re-based the proof of smallness on Warren's work (Cryptography meets voting), which seems not to rely on the assumption. Unfortunately, the new construction takes twice as much space and runtime (for now):

Criteria	BlockstreamCT	DenisCCT	Improvement
value bits hidden	32	64	100%
blockchain space	2.55kB	0.71kB	359%
verifications per sec	1300	400	-69%

Paper has been updated.

Does this apply because of the two base points G and E introduced when you switched to the proof-of-square?

In other words, does the original proof-of-smallness (that did not employ H, the decomposed hash of G) have this assumption if E is not employed (i.e.  before you added proof-of-square to your white paper)? I think not (because the assumption of factorization is between G and E correct?). I ask because my version of your paper does not use a proof-of-square.


By space, you mean the size of the proofs (because of the extra parameters introduced with H) but not an increase in the bit width of the ECC curves employed.

Also afair the proof-of-square had increased the space considerably too. So if my design is correct (and perhaps it isn't since it seems quite implausible so many mathematicians would have failed to see the simple method I used so they must have dismissed my line of thought as insecure!), it should get back to efficiency of your original design, except not entirely on performance, because in my design there is still extra computational overhead to substitute for the proof-of-square.

No. It's because the original CFT widened interval proof depends on an unfactorable number (or as Boudot and Cao put it, "n is a large composite number whose factorisation is unknown [to the prover]").


Yes, the transaction payload.


My intuition says there's high probability of a mistake there.

If you have the time and inclination, I would sure love to read a more elaborated (slightly more towards layman comprehension) explanation of what is subject to factorization and not related to the inability to find the multiple between two points given by ECLP:

https://www.certicom.com/index.php/52-the-elliptic-curve-discrete-logarithm-problem

Where I have seen the decomposition from a Hash function as the base point for breaking the factorability between commitment sets such as in Shen-Noether's design for CT+ CN (where knowing the commitment point of H relative to G, would enable one to cheat). It seems factorability applies when there are two commitment base points involved. I am not readily seeing where such factorability can be employed by the prover to break the original proof in a large interval because afaics there was already a hash function for the Fiat-Shamir in between any such factorizations? When -T > x > T, then the prover's guess has to be exactly 1 of the 2^t possibilities. How does factoring help avoid the security provided by the hash function?

In short, it appears you can either employ a Hash on the relative base points or on the values committed to the base points. Afaics, your original proof in a large interval did the latter and thus was already immune to factorization of the committed values. Now you've changed it to do hashing on both. What am I missing?

good

So would I.

Cao kept the unknown factorisation assumption even after reducing to a single base in modular DLP, so it has nothing to do with multiple base point commitment (Fujisaki-Okamoto):
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=2B21218DC3B721C6834211C3DFEE544D?doi=10.1.1.79.5740&rep=rep1&type=pdf

Apparently, "if the order of the group is known, the [widened-interval] protocol becomes easy to break". It will take some time for me to figure out whether this is true or not (or maybe only applies to non-prime curves and some types of commitments). I don't know the specific attack.


Possibly. Will take some time to figure out.

I wish I fully understood this. Its seems important so maybe I will devote some time to learn.

From section 4 (http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=2B21218DC3B721C6834211C3DFEE544D?doi=10.1.1.79.5740&rep=rep1&type=pdf#page=6):


A residue class in this context would be a functional relationship between the commited values D and the commitment values g^D mod n w.r.t. to modulus n such that Alice (as an adversary) would know all values for D which produce the same commitment value g^D mod n. Thus when −2^t+lb > x > 2^t+lb, Alice would not be limited to only one value for α which fulfills the proof. Thus the probability of Alice cheating would not be limited to 1/_2^t+lb[/sub]. The hash C = H(W) is secure only under the assumption that Alice can't factor the curve order so that D is just an integer to Alice and not a member of a residue class which Alice knows.

For ECC, the "n" is the order of the curve, i.e. the finite number of elements in the field which is the "modulus" where xG wraps around and repeats values that are obtained for other values of x.

Thus the simple solution to this problem is to make the curve order prime so that it can't be factored and thus a residual class can't be found (in the computationally conditional not information-theoretic security (https://en.wikipedia.org/wiki/Information-theoretic_security#Unconditional_security) model) . In [7] two distinct finite fields were employed because it was constructed in the setting where one of the prime factors of the modulus was known (thus the modulus could be theoretically factored), but in our case only the curve order is known, so we merely have to make it prime to make it (theoretically assuming the proof of it being prime is sound) unfactorable.

Or you do what you proposed which is hash the mathematical relationship of the commitment values (not just hash the integer relationship, thus why two hashes are required) so that no such residue class can be found, but this makes your algorithm 50% slower. My way of thinking about this is that the committed values are a distinct field (https://en.wikipedia.org/wiki/Field_(mathematics)) from the commitment values, thus the hash C = H(W) applies to the field of real numbers (stated as "integer" by Cao) and does not apply to the abelian group field of the commitment values.

Note that Berstein's curves have odd prime orders:

http://ed25519.cr.yp.to/eddsa-20150704.pdf

So problem solved and efficiency maintained.

Again I am not a mathematician and my training in this area of algebraic geometry is non-existent, so please do peer review of my statements.

For n00bs, remember it is the factorability of the RSA modulus (because it is composed of two prime factors) which makes it vulnerable (but this may not be the only vulnerability (https://www.schneier.com/blog/archives/2013/11/elliptic_curve.html#c2205767)) and why it needs exponentially larger keys (http://arstechnica.com/security/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/2/) than ECDSA (or Berstein's EdDSA):

http://arstechnica.com/security/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/
https://bithin.wordpress.com/2012/02/22/simple-explanation-for-elliptic-curve-cryptography-ecc/
https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Example

There is something else.

Knowing the prime curve order n, the Prover can cheat widened-interval protocols (CFT and Warren) by setting x=(n-1)/2, thereby committing to the multiplicative inverse of -2 mod n. Thereafter she can use -c/2 as c*x. The Verifier is fooled because E is indeed the encryption of "divide by -2" and does produce something small when multiplied by an even challenge. This would work for other positive and negative multiplicative inverses too, with the appropriate challenges.

My initial thought is that we can require the proof on two curves of co-prime order. Paper updated to illustrate (section 3.5.2). While small numbers would produce the same exponentiations on both curves, multiplicative inverse of one curve will not work on the other. I actually started off with two co-prime curves in June more directly, but that particular approach could not prevent negative numbers.

I am offering a prize pool of 10 Bitcoin (about 3,600 USD at time of writing) for any breaks, cryptanalysis, security proofs, analysis or improvements relating directly to the CCT protocol.

Some ideas in no particular order:
1) what is the most optimal attack on E, as it is known to be a square root?
2) other ways for prover to cheat
3) other ways for verifier to gain information
4) ways to make calculation go faster, and/or reduce curve size
5) out of the box thinking

Target for attack is section 3.5.2 on page 7
http://voxelsoft.com/dev/cct.pdf

Deadline for entry by posting to this thread, or PM/BM/email to me, is 20th of January UTC (but earlier is better). I have set a fixed date, and no escrow, to avoid creating an unclaimable (https://bitcointalk.org/index.php?topic=279249.msg2983911#msg2983911) fund. Awards to be made at my discretion. By default, the coins would be distributed to people who have made significant contributions previously. List of awards will be paid and publicly posted here by end of January.

If you're not into crypto, please pass on the message to a cryptanalyst who might be interested.

If you wish to contribute to the prize, my address is in the signature and QR code is in the whitepaper.

I think your update won't prevent this scenario:

Prover sets x = -1/2 or another small fraction, E=x*G, F=x*E, I=x*H,  where -1/2 is computed modulo the prime order of the respective curve, i.e. I = (m-1)/2 * H.  Then if c is divisible by 2, c*x is a small number and m = r+c*x is in range.  The verifier would still accept the proof.

I think a better way to fix this is to require c to be a prime, instead of adding I, H and the second curve.  This puts a bit more burden on the prover, as it has to restart if c is not prime.  This extra burden is no problem for your scenario, right? The verifier would just have one additional step that checks that c is prime (e.g., using some probabilistic primality test, or requiring that the prover provides a  primality certificate).  I haven't completely checked this yet but I think it should work.   If the verifier succeeds, it means that |c*x| is <= 2^t * T (or the prover had a very lucky guess of c).  Moreover, since c is prime, this means that x < 2^t*T or x is a multiple of 1/c (which means that the prover guessed c).

This sounds excellent! Putting burden on Prover is the right way to go. In typical usage this seems to require a few, to a few hundred, restarts of the protocol. Probably need a couple more bits in c. Probabilistic primality test should be ultra fast and good enough (128 miller rabin steps are much faster than EC multiplication, gives 4**-128 ability to cheat), and a mis-verifying miner would get overpowered. Paper updated. Will think it through further.

Someone has emailed me, demonstrating that a prime c still allows cheating. With odd c, prover can use (c-1) to cancel an x in r. I've rebased the paper on Warren's version of the interval proof again (will test against these attacks when I get some spare time).

Can you give more details? Does the prover need to know c before choosing x? This would not be possible, since the prover needs to commit for x and c is the hash of the commitment.

I have tested the following, and it verifies. The prover is free to move multiples of x between r and cx, to increment/decrement c (for the purpose of calculating m), so we can't rely directly on the prime property of c.


My new version based on Warren is also broken (I just tested x=(n-1)/2 and it verified).

So... I can try prime c in Warren and then it's back to the drawing board.

I'm missing the unit of measure here (and in the paper). I guess it is seconds?

Yes, "per sec" means seconds.


Edit: another attempt didn't work

If the problem is that prover is free to choose any x and r, including a multiplicative inverse, then the solution is to restrict that choice. There seems to be no good way to do that without initial trusted set-up.

Quick paper update, we have 4 cases to consider with (2) and (4) being interesting options.

1) Trusted, unknown group order:
Trusted party generates p*q factors
Use Paillier or additive ElGammal cryptosystem.

2) Trusted, known group order (elliptic curves):
Trusted party generates r in the correct range, and hands out batches of r to participants on request.
We can then use the super-efficient CFT proof on a large curve.
It is compact (0.4KB) for private blockchains, but is not suitable for Bitcoin.

3) Trustless, unknown group order:
Generate a UFO (UnFactorable Object) like ZeroCash.
Use Paillier or additive ElGammal cryptosystem.

4) Trustless, known group order (elliptic curves):
I have managed to make BCDG proof more compact (2.5KB) than the original paper.
As it can deal with 64 bit numbers, it is still more compact than CT, and is suitable for Bitcoin.

Thanks to everyone who helped to further my comprehension of the topic.

Awards have been sent:
elaine and andrew on behalf of IC3 (1C3rocKSh6sPPibn2jbMFBzcdvfGZySY6t): 6BTC
johoe in this thread (1K4b1MKUJ4mnsR4MMHBkL3Q55XP9YFZVjL): 2BTC
jonathan from UCL: 2BTC

Sorry this took a couple of days longer than expected. I haven't been able to sync a full node despite much effort, as bitcoind doesn't cope with the bitflips in my RAM.

Does RingCT (https://github.com/ShenNoether/RingCT) fit into any of those categories?

I'm guessing 3 or 4 might apply, but my parser fails at "group order."   :P

My comment: that's a wonderfully written paper, really well done.

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.

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.