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

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.

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.

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.

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

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.

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.

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:

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.

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.

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.

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.

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.

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.

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.

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.

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?

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

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  

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.

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.