Bitcoin Forum

I have been researching this for a few months on and off, because it seems like an interesting construct in its own right, a different aspect of payment privacy (eg from a user perspective or for auditable but commercially sensitive information if we expect commercial entities to use smart-contracts) but also that other than its obvious direct use it may enable the realization of some features that we have not thought of yet, or perhaps improve the efficiency of zerocoin like ideas (I dont see how yet, but it seems related).

The starting point is it is known in the literature that you can do additively homomorphic encryption, and there are also zero-knowldge proofs of less than.  (Proving E(a)+E(b)=E(a+b) is not enough you also have to prove that the attacker did not add n to his balance during the process as the addition is modulo n, the order of the group, not normal arithmetic.)  Its more efficient to do less than a power of 2, but arbitrary values are possible by composition (all values are buildable from power of 2 ranges after all).

Both of these (homomorphic add and ZK less than proofs) are based on established conservative crypto assumptions, however the generic ZKP of less than is big (number of digital signature sized proofs proportional to log(v) where v=log2(n/vmax)+1 = log2(n)-log2(vmax)+1, so in bitcoin log2(n) = 256, and vmax depends on the encoding, but there are 21million BTC < 2^51 satoshis.  And potentially also slow as it involves verifying v signatures.

Originally I was thinking that will work out to be embarrasingly slow and big (something like zerocoin) so I held of discussing if and until i could find a practical efficient method.  There is also an efficient approximate less than ZKP by Berry Schoenmakers (that he never bothered to write in a paper, natch).  However that seemed to me to be more non-standard assumption based on choosing non standard p & q for the Schnorr group and to also not work over elliptic curves and so not ECDSA (only Schnorr, of which DSA is a variant).

However finally I think I saw the missing step that the way bitcoin uses and validates coin values you only need to prove the two most significant bits of each coin is 0, and use an encoding which sets vmax<2^254 (ie increase bitcoin precision from 51 to 254 bits, less significant extra bits beyond the < 2^51 satoshis are the private key.  That gives encoding for 203 bits of security which is greater than the security of ECDSA over P256 which offers security of 128 bits.

And so there is then finally a non-embarrassing efficiency way to do it with EC-Schnorr signatures at the cost of only 2 ECS sigs (same cost and size as ECDSA) per input and output where #input < 4 and #output <4.  For #input>3 you nee to also show eg ZKPoK{(a+b+c,d):a+b+c<2^254,d<2^254} and same if #output>3.  So 2k+2log3(k) signatures for k inputs or outputs.  (3 because 2^254*3<n but 2^254*4>n.)

Btw there are good reasons to use ECS over ECDSA IMO its still conservative and simpler and anyway DSA is based on it.  Because its simpler (no *k^-1 step) its more flexible and easily supports multiparty (n of n) and even threshold signatures (k of n) which allows multisig in the space of one ECS signature (and without even disclosing the existance of k of n nor how big k or n is even), there are some arguments that ECS is more secure than ECDSA in its assumptions about hash properties.  To do multiparty with ECDSA is a research topic, even multiparty DSA is ridiculously complex and depends on the security of a homomorphic encryption instance big enough to hold temporary results involving powers of q eg the paillier cryptosystem with big keys, and threshold DSA on the even more complex Damgard-Jurik extended Paillier scheme.  The flexibility of ECS makes it more flexible for many things, eg the zero knowledge selective disclosure and blinding certification features of Brands certificates based on the representation problem (which is a kind of generalization of Pederson commitments, which is itself a generalization of schnorr).  There are a huge number of things you can do with Brands certificates towards smart contracts that preserve the privacy of the attributes of a person relying on smart contract by using ZK proofs of boolean formulae etc.  

Also for the cost of an extra signature per value you can even have unconditional value privacy.  (Ie a hypothetical all powerful entity able to perform discrete log with minimal effort still cannot tell how much money  you paid).  This is because like OTP all possible values are equally possible, eg with a pederson commitment two base points G, H then xG+yH there are n possible solutions for all possible values of x and y (where x is a secret key and y is a value you prove things about).  The powerful adversary can just solve and find all the possibilities but your public  recorded ZKPs do not show which x value you knew, nor which y was the value you transferred.

Will post more crypto level details and perhaps an openSSL based implementation presently.

Adam

How do validating nodes sum input and output values to determine a fee? This is the only part that doesn't seem clear to me. Doesn't the network need to know sum(outputs) - sum(inputs)?

So if you assume the existence of a ZK proof of knowledge of x (with syntax x_i is the i'th bit of x starting from 0 for the LSB) then ZKPoK{(x):x_i=0} then we can check two most significant bits are 0 with ZKPoK{(x):x_255=0 and x_254=0} by using it twice.

This proof will work on values in some group, we use EC instance of schnorr group (like DSA, same keys, parameters, but simpler signature; DSA is a Schnorr signature variant that offers no advantages over the original AFAIK and many disadvantages that I mentioned in OP).  So we will call the value x where the top two bits must be 0 x_255 = x_254 = 0, and x_{253...x202} are the value in satoshis (same as existing precision) and the remaining values of x_{201..x0} are the private key.

xG will be public and is also the coin public key (slightly different from an existing bitcoin address public key).  Now people can verify that encrypted input values (A,B) add up to encrypted output values (X,C) and fee f, where X is encrypted spend, C is encrypted change and f is fee because A=aG, and A+B=X+C+fG because aG+bG=xG+cG+fG.  This enforces that a+b mod n = x+c+f mod n.  The sender must include ZKPoK{(a,b):a_255 = a_254 = 0}.  The sender must also encrypt x and send it to the recipient so that he can prove information about it when he in turn spends it.  f is public because anyone must be able to collect it and attach it to their address via a mining event.

When the recipient spends xG he will have to similarly prove that x_255 = x_254 = 0.

The reason we need two bits is because n is not a power of two.  Say for simplicity we say n = 250.  Now imagine a=3, b=1, but we have to watch out for fraud by adding n because a+b+n = 254, a+b+n mod n = 4, and x=127,c=126,f=1 so checking only the top bit one could forge value by n as a+b+n = x+c+f mod n   3+1 = 127+126+1 mod 250.  The attacker has increased his value by 250 (minus 1 fee) without using any values with msb != 0.  If we prove top two bits are 0 then we can prevent this attack for up to 3 inputs.  (Because 3*64<250; but not 4 input because 4*64>250).  So for greater than 3 inputs we also prove each intermediate calculation in a 3-ary expression tree also has two msbits=0.  eg where Z(x) is short hand for ZKPoK{(x):x_255=0 and x_254=0}, Z(a),Z(b),Z(c),Z(a+b+c),Z(d),Z(e),Z(f),Z(d+e+f),Z(g),Z(h),Z(i),Z(g+h+i),Z((a+b+c)+(d+e+f)+(g+h+i)) so as mentioned i OP there must be k+log3(k) pair of proofs for k inputs (pair because there is one for x_255=0 and one for x_254).

Finally notice that proving knowledge is a kind of signature so in principle you could pay to another persons existing balance, with their approval, rather than transfer control of a value to a new address.  ie say that your recipient already has a balance y and you want to add x to it for them, you disclose x to them (by encrypting it for their public key say) and then they can add it and therefore you can replace coin addresses by existing balances to save on signatures and keys.

eg ZKPoK[Y]{(a,b,x,y,c),f:a+b=x+c+f and Z(a) and Z(b) and Z(y)}, E(x)

where [Y] indicates an auxiliary signature of some information combined with the PoK.  So the sender is binding his spend of X to say it can be added to existing balance Y (where the sender does not know y). 

Now the block validation will allow the recipient to replace his balance with Y'=Y+X=(x+y)G.  As the sender encrypts the value x for the recipient he can now make onwards transfers.

Taint mixing is also possible (though not that cheaply at scale) by spending dust to some number of other users as a kind of ring-transfer.  (A ring-signature is a scheme where you can implicate without their permission other signers as possible originators of a signature where the originator wants to hide their identity among possible authors).  So thats a bit like coinjoin but you dont need the active collaboration of the other users.  If the E(values) are offchain (eg direct to the recipient) the recipient may or may not even be able to use the extra value, if he doesnt know the dust value (he can reject it by referring only to his previous balance, but that does not disprove that he could still have it in reserve - its hard to prove a negative.)  We could alternatively attach it to the chain (at some size cost) maybe even encrypted with proof that the recipient could decrypt it.  (It is easy to prove xG=xH where H=yG, y unknown to the prover, so EC Egamal could do a provably decryptable value, in which case the software can incorporate the coin and block the owner from using earlier versions).

(dust is a value as now that is considered small, but because x_{202..0} is random by the sender and not computable without DL ability it has to be communicated to the recipient in order to be of value to them).

With mining the original coin is of known value 25 bitcoins (and no dust), however the recipient can still spend it securely without people working out his current balance by elimination by keeping dust as change (which he may never spend as it is has truly negligible fractional nano satoshi values.)

Adam

Unlike currently you would have to communicate fee explicitly and have it validate as the inputs summing to the output.  (It is shown in my second post where f is communicated while inputs a,b and outputs x (spend) and c (change) are in encrypted form and yet it can be audited that A+B=X+C+fG.

Adam

How do you intend to do a proof that the upper two bits are zero?

I don't think anyone knows how to do an efficient ZK proof for things like less-than, or bit extraction, or mod x. There are generic ZK schemes like Pinocchio and TinyRAM but they're expensive. What do you have in mind?

Aye, aye I'm getting there give me a chance :)

The existing ZKP of less than use proof of a bit being 0 or 1 as a building block (thats why they are inefficient, they do that dozens of times depending on the ranges).  ie to prove x <= 5 = 101b modulo for illustration n=257 (9bit prime) they prove x=000000101b the prove first that x<100b by proving the top 6 bits are 0, and then the prove that xG-4G=01b <= 1 by proving the top 8 bits of xG-4G are 0.

Adam

I believe there is a description/footnote/reference from chapter 3 of Brands PhD thesis/MIT press book "rethinking public key infrastructures", which is available for free download.  Its a component of ZK range proofs or ZK less than.

http://www.credentica.com/the_mit_pressbook.html

I'll write it up presently otherwise.  (Going to be AFK for a bit).

Adam

Uh oh I think I made a mistake in reference to the t parameter - its the precision of the range, not the number of most significant bits.  Thats not as nice, but still perhaps just about practical.  (I was incorrectly thinking by changing the value range to 0..2^254-1 and using the step-wise addition cant wraparound argument made in this thread, I had it cracked and I would make the proof smaller, but its actually worse and the wrong direction).

I was thinking of the algorithm due to Berry Schoenmakers (reference is unpublished) but Brands describes on p129 of chapter 3.

To adapt for that it's back to what I had in mind previously that I was not that happy about the efficiency of.   Crap.  

Now that I explained the thing prematurely (before its actually nicely efficient it turns out) here's the explanation of where it got to in the previous version.

Choose value x with encrypted value X=xG+yH (or X=g^x*h^y in non EC syntax) and then proof as described in Brands p129 writeup of Schoenmakers with reference to OR proof more easily comprehensible from .   However I temporarily thought t was 2, which would've been sweet.  So the only remaining flexibility with that algorithm is to minimize bitcoin precision its still currently say 40 bits with bitcoin price up to $500 and precision down to 1c US.  A bit close to the limit if the price rises.  Bitcoin actually uses 51 bits (1c precision up to $1m per coin).  Anyway you need to run that proof which involves 40 or 51 subproofs each including one schnorr proof (2x ECDSA sized at least because of the need to prove x_i = 0 or x_i = 1 by the generic OR construct of creating one real ZKP with fairly chose challenge c (eg c=H(params)) and then two forged/simulated ZKP with forged c1 and c2 transcripts where c = c_1+c_2 mod n).  I cant see that working out at under 14kB to 18kB, probably a lot worse.

[EDIT the general OR simulation argument should be one forged (c_1 calculated backwards from the simulated protocol run), then c = H(params) and finally c_2 chosen so that c = c_1+c_2 mod n and a real ZKP using c_2).]

There was also another unpublished idea by Schoenmaker I mentioned that is more direct but doesnt work in EC and with non-standard p, q choice.  There's also an idea to use number other than 2 in the \alpha = \sum \alpha_i 2^i mod q line by someone.  Lipmaa also has a clever idea involving a generic argument about subset sum "additive combinatorics and discrete logarithm base range protocols" but the advantage over Camenisch previous result is not game changing for our purposes.  There were dozens more; maybe I'll post a fuller list of papers later on.

Adam

There's a section in this bibliography about ZK range proofs, but I'm not familiar with any of them. Maybe there's something useful in here.
http://www.cs.ut.ee/~lipmaa/crypto/link/zeroknowledge/pok.php

Wait a moment.

Wasn't homomorphic encryption a theoretical academic thing that has not been proved to even exist (or be possible to perform) yet ?

Correct me if I am wrong here, please.

You are wrong. But you're asking in the wrong place— go see the nice article on wikipedia.

I did see the article on wikipedia, and it says that full homomorphic encryption is a scientists' wet dream and it has never been achieved.

Well technically it was achieved by Gentry and a few related improvements on that, however those schemes are extremely far from practical.  Ie megabyte keys, bajillion machine cycles per encrypted operation etc.  Still it was a nice result that proves it is actually possible which was uncertain in the 30+ years since it was posed as a question by Rivest et al.  They even somewhat recently have a library so one could download it and try out how expensive it is.

Anyway for homomorphically encrypted coin values you dont need fully homomorphic (ie you dont need both additively homomorphic & multiplicatively homomorphic, additive only is enough).  In fact thats even easy and there are several additively homomorphic encryption systems like elgamal and paillier.  The hard part is efficiently preventing the user adding n the order of the group to their balance for massive scale fraud.

Adam

So for practical usage it has not yet been really achieved. That's what i wanted to say.

Anyway, it would be extremely cool to have homomorphic encryption as it would enable ultimate blockchain compression (there was a topic here claiming that).

An update on this, actual numbers for the size and its a bit better than thought.  This is from the above Brands reference, algorithm due to Schoenmakers.  Lets call bitcoins precision m=51.  x is a secret value and p commitment to the coins value (like pederson commitment) p = g^v*h^x.  g and h are bases such that the discrete log of h wrt g is unknown (log_g( h ) = y aka g^y = h , y is unknown).  I use exponentiation notation because I prefer it but the same works in EC.

v=bitcoin value, bits of v are v0 ... v50 (ie so that v=sum 0..50(2^i*v_i) with v0 is the LSB.

Choose m=51 random values in Zn (where n is the order of the group) call x0, ..., x50, and set x=sum 0..50(2^i*x_i) mod n.  Primary commitment is y=g^v*h^x.

Now do m=51 auxiliary commitments i=0..50 calculate h_i = g^v_i*h^x_i.

Prove for each auxiliary commitment that v_i = 0 or 1 as follows.  If v_i = 0 compute v_i=0 proof and forge v_i=1 proof, in such a way that you can only forge sub-proof, if v_i = 1 compute v_i=1 proof and forge v_i=0 proof.

If v_i=0:

prove v_i=0: k=random, a=h^k,c=H(a,h_i), c'=random,r=k+c'*x_i mod n.
forge v_i=1: r'=random, c"=c-c',a'=h^r'*(h_i/g)^-c",

else if v_i=1:

forge v_i=0: c'=random,r=random,a=h^r*h_i^-c',c=H(a,h_i)
prove v_i=1: k=random,a'=h^k,c"=c-c',r'=k'+c"x_i

sub-proof message is: (h_i,a,c',r,a',r") 6x 32 byte values.

sub-proof verification is the same for v_i = 0 or v_i = 1 (as the verifier must not be able to tell the value of v_i).

check a=?h^r*h_i^-c' and a'=?h^r'*(h_i/g)^-c"

Finally the verifier also checks y =? prod 0..50 h_i^(2^i) mod n.

This works because x=sum 2^i*x_i and v=sum 2^i*v_i.

So adding up!  Each value is 32 bytes (for 256-bit values/compressed points and 128-bits of security margin) where m is the mantissa in bits we have presuming for now g, and h are shared parameters.  We have h, plus m times (h_i,a,c',r,a',r") so that is 1+6m=307*32=9824 bytes.  The other values c=H(a,h_i), c"=c-c are computed.

However I spent the weekend on size optimization:

1. note either r'=random (v_i = 0 case) or r=random (v_i = 1 case) and both are public values, so instead of choosing them randomly we can reuse r'=r (v_i=0 case) or r'=r (v_i=1 case). We cant use a seed and KDF to create r' or r respectively because that would reveal whether v_i = 0 or 1.  So then we get 1+5m=8192 bytes.  

2. same argument for c' being random and public, in this case we can use a public seed of all non-dependent values, so then we have 1+4m=6560bytes.

3. we can send H(a) and H(a') instead (H truncated to 128-bits according to Schnorr though Brands cautions that one must be careful with this depending on the complexity of the formula proven, so some more things have to be checked) and modify the sub-proof verification step to check H(a)=?H(h^r*h_i^-c') and H(a')=?H(h^r*(h_i/g)^-c").  So then 1+3m=4928bytes

4. instead of H(a) from 3 send a (cant do both H(a) and H(a') as we need a) we can compute the public key h_i from the extended schnorr signature/representation proof (analogous to the way you can compute the public key from a DSA signature).  As we're verifying h^r=?a*h_i^-c', we can rearrange and compute h_i=(a*h^-r)^{c'^-1}.  We need to verify h_i values but we can do that with one hash h'=H(p,h_0,...,h_50).  So then we have 1.5+2.5m=4128bytes (or 2+3m=4960 bytes with out optimization 3).


Recap at this point the proof message is { a,H(a'),r } or {a,a',r} the other 3 values are r' (copied from r or vice-versa), h is computed from sub proof (v_i=0 proof/forgery) verification relation, and cross checked with sub proof 2 (v_i=1 proof/forgery) verification relation.  c is computed as H(a,h_i) and c' is from the KDF seeded with the non dependent values.


There is one more promising optimization which might take it to 3+2m, I need to verify for feasibility of dependencies.


Also note one could reduce m eg to 24 bits, and include an exponent e also so that bitcoin value is m^(2^e).  24 bits is enough precision for 1c precision for up to $1.6m.  The exponent can be public (and signed as an auxiliary message to the proof).  Some ambiguity about the range of the value can be achieved by using a unencrypted mantissa offset o=random(-4,4) and from the original mantissa instead encoding: m'=m*2, e'=e+o so the coin value is the same m'^(2^e')==m^(2^e).

The exponent itself could even be homomorphically encrypted and proven in a range and compared for equality using an equality proof proving the e1 and e2 values are the same, or differ by the unencrypted offset q1=g^e1*h^z1 and q2=g^e2*h^z2.  To compare offset do a range proof on e1 and e2 as above, and the encrypted range could be eg o/3 (in multiples of 8 bits) and the remaining bits from the public offset.  To verify the offset you'd prove q1 has same e value as q2/g^o.  As we only need to cover 25 bits, a 3-bit range proof for the exponent is enough which is quite small.  recalling (2+3m)*32=352bytes.

You could probably set m=20 and e=31/8=4 for 2+3m+2+3e=2432 bytes.


Finally some interesting implications arising: you can add coins without owning them (owning them is knowing the private keys xi.)  You can pay someone by adding your coin to their coin and broadcasting (or sending privately) the private key encrypted with their public key.  Anyone can verify publicly that the coin adds up.  You cant oveflow mod n to attacks because there are by definition less than 21mil BTC.  You can randomize a coin by adding a 0-value like g^0*h^x.  How you add is multiply the coins together (or point addition in EC terminology).  The new private key is the addition of the old private key and the new one.  No one not involved can tell if that was a 0-valued red-herring or 1c payment or $100.  The network itself could pre-emptively add the coin without the recipient doing anything and compact them if the encryption is also a proof.  (ie I try to add a new value v to your coin g^v*h^x, which comes with a range proof proving v is positive  and doesnt wrap  mod n and to do that I encrypt with your public encryption key pk (which was signed by the person who sent you the input) the key x and I also prove that the person with the private key corresponding to pk can decrypt to the same value as x (that anyone can verify) proving equality of discrete log.  If you had to you could probably reuse the coin public key for encryption (like sharing a schnorr signature public key and an elgamal public key, need to be careful but there is some analysis).

For inputs, you only need to refer to the outputs (and prove knowledge of the private key) without having to do a new range proof, because by definition all bitcoins in existence cant wrap if added up.  You do need fresh range-proofs when you split a coin (to spend part of it).  You can split the private key too (x = x1+x2).

To create a coin receiving address you just produce a zero-valued coin and prove knowledge of discrete log wrt h (because g^0*h^x = h^x).  Then people can send you coins without being able to spend them.

For mining you prove knowledge of representation g^25*h^x which is efficient (no range proof because 25 is public).  Then you split the coin with range proofs when you spend (or when the mining pool divides up the reward to the pool workers).

You maybe no longer need an address (hash of public key) that signs, because the coin private key is a signature key, but you do need an encryption public key.

A type of taint mitigation is  spending to some statistical number of addresses a 0 or low value spend together with your real spend.

I really need to implement the crypto as a library or stand-alone demo program and double check somethings are not confused but this appears quite practical.

The bloat caused may not be so much because there is some privacy gain that may reduce incentive to have multiple addresses or use mixes.

Adam

OK I guess I was thinking about it wrong last night, dependencies dont matter as a' is public so its simple: compute a' from the second verification relation (analogous to computing public key, but this time we know the public key h_i from computing the first verification relation).  Second verification relation a'=?h^r*(h_i/g)^-c".  Now send a new value t=H(a_0',...,a_50').  So thats 3+2m which is 1+(3+20*2+3+3*2)*32=1665 bytes for the m=20,e=3,and a one byte signed offset.  Or 3+2m is 3+51*2=3360byte for full precision e=0, or perhaps 3+(3+30*2)*32 = 2016 byte with a clear text 21-bit exponent, or even (3+27*2)*32=1824byte. 

Coins with different public exponents can still be publicly audited (just raise the smaller coin to power 2^abs(e1-e2) which is multiply by 2^abs(e1-e2) in EC form). The exponent wont really need to move except over the multi-year time-frame as bitcoins get smaller.  27 bits is lots of precision giving a decimal precision of 8 digits eg 1c on $1mil or $1 on $100mil etc.  Just about plausible though maybe forcing mix of different precision coins reducing privacy could be 20bits and cleartext exponent at (4+20*2)*32 = 1408bytes.

I think 27-bits is a nice precision balance without using the complexity of the encrypted exponent so I'll focus on clear text exponent and 27-bit precision, though the encrypted exponent is a valid optimization at implementation level.

Encrypted value coins (of both mantissa only or mantissa and encrypted exponent form) are encrypted UTXO compactable after spends which is bitcoins UTXO compaction model.

Clear text fees are still validatable: just publish f=fee and then include g^f*h^0=g^f with the other validation.  Clear text value payments are similarly validatable: just publish v and compute g^v*h^x.  They take the space of one ECS (EC-Schnorr) signature, same as DSA, no range proof required.  What you sign is proof of knowledge of discrete log of h^x.

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.

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

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

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

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

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.

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.

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.

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

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

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

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

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.

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?

http://www.e-allmoney.com/inflation/images/zimbabwe_inflation.jpeg

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

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.

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

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 ?

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

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

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