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

Edit: I might not have this right.

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.

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?

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.

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.

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?

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

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.

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.

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.

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.

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?

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?

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. 

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.

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.

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?

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.

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.

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.