Topic: bitcoins with homomorphic value (validatable but encrypted) (Read 19890 times)

I am not sure.  One thing you could say is if amounts are encrypted maybe you dont so much need lots of addresses.  However I think encrypted amounts isnt quite enough, you probably need like to hide who is paying as well as hide the amount before that becomes convincing enough to say you only need one address.  Then it could save some UTXO space as you only need one unspent address per user for privacy.

Adam

Yes, I'm here. And some of the arguments I read these days made me change my mind. So yesterday I began finishing the preliminary paper I started long ago..

Could someone explain in simple terms why that would compress the blockchain?
I see how it could hide amounts and identity, but the only effect I see on the blockchain would be to make it larger.

I must be missing something obvious. 

Already done. So you can't be remembered as such, because somebody already did it (or will do it soon) ! Do you get the logic ?

CoinSwap. CoinJoin. CoinControl. ZeroCoin. BlockChain info's CoinJoin implementation.

Hello ? Sergio ? You there ?

I think it's the first time I see a possible Bitcoin upgrade / replacement that makes me say "Holy shit...".

I absolutely want more!
Time to learn more math...  

Let me get this straight - allowing people to use their money how they wish is ethically and morally questionable, but forcing entire populations to pay for their own oppression is perfectly fine?

https://twitter.com/3min3nt_mfn/status/405327147205545984

http://benswann.com/cops-spray-womans-vagina-with-mace-to-punish-her-after-drug-arrest/

http://www.huffingtonpost.com/2013/11/26/nsa-porn-muslims_n_4346128.html

http://www.cracked.com/blog/5-recent-trends-that-make-it-hard-to-trust-police/

https://www.aclu.org/blog/criminal-law-reform/easy-money-civil-asset-forfeiture-abuse-police

http://thefreethoughtproject.com/revealed-why-do-cops-shoot-your-dog/

http://www.upworthy.com/something-sickening-is-happening-to-some-of-our-schoolchildren-and-you-probably-have-no-idea?g=2

There is nothing moral or ethical about giving more capabilities to the most violent and destructive mafias to ever walk the face of the Earth.

Gold itself is a truly anonymous untraceable coin.

What is better for the economy, gold? Or a version of gold that the government can track and control and freeze and confiscate at will, from any place on the earth?

When gold was the primary money, did it fill the earth with terrorists, drug dealers, and child pornographers?



Bow before your false god if you wish, but it has murdered hundreds of millions in the last century alone.

Agree, but the protocol must support those levels of anonymity.

I didn't say it was the holygrail. It has advantages over the other protocols (uses old more proven crypto) and some disadvantages.
The greater disadvantage is that it was not widely reviewed.

But ethic was not the only reason, the other reason is that I don't like writing proofs of any crypto I do.


Ok. I'll reconsider.
 
The levels of online poker gambling addiction are far lower than the levels of real-word casino addictions. Also the software I developing has all kinds of controls against problem gambling (but of course, you can recompile it and remove all those checks, since it will be open sourced).

Best regards,
 Sergio.

I don't have the best idea. No one can claim to have the best idea. But I'm unsure if I'd like to be remembered as the guy that facilitated global crime.


If you're religious, then it's true.

But still I want a paper with numbers that proves that the economic benefits of a truly anonymous untraceable coin outweigh the problems it may bring.
Or a paper that proposes a system where governments may have a trapdoor to allow them get trace of all transactions over 1 M USD but no trace of transactions of lower value. ... ohhh.. I've may have came up with an idea to do just that.

Ouch .... but it crossed my mind also.

So Sergio are you ever going to publish? Have you looked at the arguments regarding fungibility? If you truly have an idea that is possibly the best money humanity can have, the enormous economic benefits alone far outweigh any moral quandaries provide by a few errant users of the money (who, after all, have to answer to their God and their peers ultimately for their actions whatever the medium is that they choose to perpetrate them with).

I think eg if you read the original zercoin paper and I said similar things on bitcointalk that anonymity is the ideal building block.  What you can build with it is many permutations of desired and useful privacy levels.  It doesnt have to be full payee & payer anonymous just because the building block supports that.  And there are many reasons in the real world that you dont get that privacy in practice.  IP logging, IP geolocation, physical shipping address, knowledge of you by the person you are paying/receiving from, privacy mistakes etc.



Kind of odd if you are sitting on the holygrail crypto and not publishing for some kind of ethical considerations?  Really?  Technology is neutral and this technology can add many useful permutations of privacy to bitcoin.  I'd sure publish it immediately if I had figured it out and feel I did a good thing for society.

Maybe you want also to read this post by Greg Maxwell explaining why privacy is important for society and commerce.

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

I think you get that also because as I understood it you explored anonymity because of your interest in card gaming to prevent collusion being used to cheat.

ps Personally I think gambling has far more ethical worries than users being able to transact privately with something approaching the analogous already existing levels of privacy in other systems.  For some people gambling becomes a near ruining addiction.

Adam

I hope your understanding of cryptography is better than your understanding of morality.

Actually since CoinControl, CoinSwap, CoinJoin and even ZeroCoin are already coming i think that your invention is not so of a big deal anymore.

However obviously everybody would surely welcome yet another way(tm) to anonymize their wealth.

EDIT:
What I meant to say was that releasing it today would not mean much because we soon will have other means of gaining complete financial privacy.

All these problems, like hiding the transfer amount , and anonymization, etc were solved (*) by my Appecoin protocol.
Appecoin proofs are relatively small, and fast to verify.

The fact that I didn't publish it (for a year) is that I still have moral doubts of enabling a completely anonymous payment system. Somebody has to proof that the benefit of such system outweigh the costs of its illegal use.

I hope Adam you're sure that you solved that dilemma when you finally build your own protocol.

(*) This is not completely true, since my paper has received little peer review, it might contain mistakes.

This could be the next revolution.

The blockchain could become 1000x smaller making it possible to run full nodes in low-power devices. I mean, that would be something.

That idea was blind-hashcash

https://bitcointalk.org/index.php?topic=308009.new#new

which I found a nice simple and efficient design for, that is backwards compatible even with the exiting hashcash with SHA256 or hashcash wth scrypt(1) CPU/GPU software and FPGA/ASIC hardware.

The zerocoin killer status has some questions yet, but its interesting that you can make a distributed signature with no private key via the miners, and that you could blind something to be signed, and have the user unblind it.  Signatures are more malleable because they are based on algebra where as hash functions and symmetric ciphers are bit-level operations in their own right.

Adam

Interesting thread! I don't know enough to contribute, but i will continue reading.

For off-chain purposes it is interesting to note that the morphcoins (hidden homomorphic value coins) have a representation problem format and so are compatible with brands credentials.

Brands credentials http://www.cypherspace.org/credlib/ has the links to the Brands book, some technical papers, an implementation in C/openSSL.

For an off-chain issuing server like open transactions (paste from email to Chris Odom):

In the context of an issuing server, you could use Brands credentials which
are related to what I did (homomorphic value is using some techniques from
Schoenmakers, Pederson, Brands).

But if you use Brands credentials as a blind ecash system you can put a
cleartext or hidden value in an attribute and prove things add up too, but
with the more complex added feature of server blind signatures from the
issuer.  As there is a reissue sub-protocol where you can exchange a hidden
value coin for a fresh unlinkable (freshly blinded) hidden value coin with
the bank, you dont even need to do homomorphic values.

Maybe there are some other things you would like to prove at the transaction
server level without reference to the issuer.  (Eg if there is a motivation
for the issuer to be relatively offline).  A Brands ecash coin once it is
unblinded is the same format as the homomorphic value, so I think you could
do homomorphic tallies on the transaction servers, and the users could audit
the information and validate it against transaction logs and other servers
to make sure the balance matches the issued amount at all stages yet without
being able to observe commercially sensitive smart contract amounts.

I think I have a bit of implementation work ahead, convert credlib to use
EC, add homomorphic value range-proof etc.

And that led to a new idea... the topic of a new thread, which might offer finally an outright zerocoin killer.  Feature parity and more CPU & space efficient and no trapdoor.

Adam

Lets call the homomorphic coin for short morphcoin (and not homocoin;)  Or ringcoin from the additional implication of the below extended protocol.

One more proof which allows a ringcoin (ring signature analog of Greg Maxwell's coinjoin) is to create a ring input R=g^v'*h^x' and change C' and then prove that with respect to someone else's coin where it can be publicly audited that C=R*C' (ie the coin adds up) and C' is the change left for the original owner.  The proof you need to make that an acceptable proposition for the original owner (subtracting random amounts from his coin!) is that either R=g^(v'=0)*h^x' OR  RP(C') and RP(R) such that C=R*C') where RP is the range proof construction from parent post.  

That proves either you have a coin with 0 value (so its safe to subtract it without someone else's permission or cooperation from their coin) OR that you know the coin private key, so you can subtract whatever you want because you're its owner.  The way the subtraction is proven not to underflow, is you split the coin into two or more outputs range proofs that add up to the original coin, proving you are the owner.  The coin private keys for C is x, for R is x' and C' is x" and x' is random and x"=x-x' mod n, so final validation is simply EC addition of the split proceeds (which could be spent to other person and change address eg.)

The OR construction is standard and the same technique as in parent post to allow to prove v_i=0 or v_i=1 (namely you intentionally allow a maximum of one forgery, by adding one degree of freedom to the choice of the challenge).

Now a ringcoin is like coinjoin, but more powerful because you dont need the cooperation of the other coins!  That makes sense because you are provably not removing any value from them (as you dont know their private keys).   The additional cost for the "v'=0 OR "clause should be small, about 3 or 4 values (96-128bytes) on top of the two range-proof encrypted values.

[EDIT: sorry about that its more like 2x ie 2*(2+3+2m) 5.6kB approximately for the ring coin because you need enough degrees of freedom to forge any 2 of the 3 statements v'=0 or v_i=0 or
v_i=1, so you need m independent proofs of knowledge involving R=g^v'*h^x'.]

You could in theory mix coinjoin multiple cooperative inputs with ringcoin appropriated inputs in one combined spend however it is only plausible to the extent that an adversary would find it plausible that one person controlled both private keys.

Or I suppose you could state that differently that you could combine coinjoin and ringcoin to mix real inputs, real outputs, and additional ring-inputs (0-value inputs for people not in the coinjoin set) all for the same cost of <1+r+o range proofs.  Where i is the number of real inputs, r the number of ring inputs and o is the number of outputs (including change and fees).  Its a bit artificial as it will be thereby obvious the ring inputs are fake (as they are combined into a single multi-ownership proof unless they are used in limited numbers so that its plausible there is one owner for the multiple ring inputs) and the coinjoin inputs are real.  So to do it properly you would need to prove separately < i+r+o range proofs.

You can also do coinjoin more efficiently on morphcoin (homomorphic values), which is not so much to do with the homomorphic encrypted values as that multi-sig is compact on schnorr signtures because it supports after-the fact multisig on the addition of the coin private keys.  So coinjoin only (no ringcoin) would cost 1+o range proofs in space, though each input i would have a private message as they built up the single combined rangeproof for their i respective inputs being a combined proof of C1+...+Ci.

Generically n of n multisig (with one owner or a single owner with pre-split private key) is compact with schnorr.  Shnorr is a better sig than DSA, NSA reduced its flexibility when they tweaked it to avoid Prof Schnorr's patent.

Schnorr also supports efficient threshold signatures (k of n multisig) so you can also do k of n multisig in the space of one signature on the validation side.

Again to summarize:

Ringcoin is like coinjoin except you the spender choose who to mix your inputs with, and you take 0 from each input, but because the value is homorphically encrypted no one but you can tell that, and you dont need to mix other people's outputs.

Ringcoin seems likely to outperform zerocoin in anonymity, certainly in performance (coins can have flexible value unlike zerocoin which is one denomination, or dilutes the anonymity set if you have multiple denominations and 2 output coins are 10x smaller and much CPU cheaper to create and verify).  You can mix with 10 ringcoin inputs per 40kB zerocoin proof, and you dont have the competing anonymity-set issues from having to balance number of denominations (for efficiency of payments eg $1000 coins = 1000x $1 coin payment) against anonymity set (introduce $1, $10, $100, $1000 coins and now you can infer possible sources from handling of coins of required value and so reduces the anonymity-set).  Unlike zerocoin there is no unwanted trapdoor (the n=p*q issue where p, q is a global trap door allowing coin forgery that you cant prove you destroyed).

It seems plausible that you might be able to combine ringcoin with zerocoin because coincidentally they also use pederson commitments though in a different group (subgroup prime field orer q, not EC prime-field order n.)  I haven't tried to look at that but if turns out to be possible it might solve their anonymity set/denomination number trade-off issue.

Taken together the two factors (single ZC denomination and CPU/storage cost) it seems likely ringcoin could provide better anonymity set size, CPU performance, storage and bandwidth and solid security margin (256-bit EC throughout) in most if not all plausible use-cases.

[EDIT: I should clarify that this ringcoin/zerocoin claim is efficiency/practical biased not theory based: with the argument that inefficiency reduces the anonymity set as people wont use it as heavily in its proposed plugin to bitcoin model where zerecoin mixing is optional and explicit on the part of users.  Your anonymity set in that zerocoin deployment is only as large as the number of ZC users between when you put your coins in and when you took them out.  So really it serves as a distributed intentional mix in that deployment model.

A hypothetical all zerocoin alt-coin could have full system anonymity set which is appealing an categorically stronger claim,  however the single denomination or anonymity set reductions for multi denomination still impair the theoretical anonymity in practice.  And the zerocoins are CPU an bandwidth expensive.]

Adam

Actually Gentry and his colleagues didn't stop after 2009. There have been big advances in the efficiency of FHE since then. Also people are exploring hardware acceleration for it. I'm talking very vaguely because I sort of scan read some of the papers and let the general gist digest in my mind, but the maths is extremely advanced and I'm not actually a mathematician.

If you're interested in such topics, the best place to follow crypto research is here:

http://eprint.iacr.org/eprint-bin/search.pl?last=31&title=1

It's a rolling archive of crypto research, updated every few days. For example, here's a recent paper on the speed of FHE when combined with FPGAs:

   http://eprint.iacr.org/2013/624.pdf

They get a 26x speedup for integer based FHE, which is itself orders of magnitude better than Gentry's lattice based scheme.

However I don't think it will be interesting for Bitcoin any time soon. It's important not to underestimate the incredible value Bitcoin derives from using simple, totally ordinary cryptographic constructs that any first-year CS student can understand.