Post
Topic
Board Development & Technical Discussion
Merits 64 from 1 user
Topic OP
bitcoins with homomorphic value (validatable but encrypted)
by
adam3us
on 01/10/2013, 14:19:53 UTC
⭐ Merited by ETFbitcoin (64)
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*3n.)

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