Aside from the asymmetric blind proof of work, BIP 38 could be tweaked to avoid this issue.  (Though this approach is not securely sever offloadable).

http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg02948.html


Adam

The risk with brain-wallets (eg BIP 038 with no EC multiply, or even with EC multiply if the manufacturer is not that trustworthy) where the ECSA private key is computed from password is that the passwords can be ground and if successful the funds can be stolen.  So clearly its desirable to use key-stretching for brain-wallets and  this is already done with Scrypt or PBKDF2.  However a limitation with key stretching is it incurs computational load on the client, which maybe a smart-phone or single desktop class machine.  eg 16384 scrypt iterations are suggested in BIP 038, chosen to be fast enough to tolerate in javascript.

So it would be desirable to have a secure server offloadable KDF, which means a kind of blindable deterministic proof-of-work.  I described one such proof-of-work in this post (relating to blind-hashcash a different but in hind-sight related topic, where you in addition need a transferable publicly auditable proof of work):

An RSA based blindable (secure) work offload function:

So if we call that can be use as a blind deterministic password-based proof of work: we could set message = password, or H(password), blind by random factor g^b, and have the server compute blind-pbkdf( password ) for us with some large w that we cant afford to do on our smart-phone or laptop because itd be too slow.

The above work function is basically a blinded version of Rivest et al's time-lock puzzle (the time-lock puzzle desires non-parallelizabiiity as the idea is to intentionally encrypt something for the future, where you cant speed it up by using multiple cores.) 

The fact that it is non-parallelizable is actually a disadvantage for a blind KDF, it means the speed up is limited to the fastest single-core offload server.   Another simple parallelizable time-lock is proposed in the time-lock paper which is simply to symmetrically encrypt and discard say 40 of the key-bits (this is also the model used by Juels & Brainard for their client-puzzles proof of work which is somewhat hashcash-like but has no public auditability).  However that is not blindable as its not an algebraic form.

But it is easy to make an intentionally parallelizable instance by say 128 server cores (16x 8 core servers, or an even more impressive core count GPU server farm), use a smaller e value to take eg 10 minutes on a 1Ghz GPU core (whatever your transaction delay tolerance is), then stretch the password using eg PBKDF2 and 1 iterations, null salt, into 128-values worth of pseudo-random output call those m1..m128.  ie (m1||..||m128)=PBDF2(1,"",password).  Now create 128 cryptographically random (non-deterministic RNG) challenges b1...b128, the ECDSA key is x=m1^e+...+m128^e mod n, which is fast to compute when you know d (before deleting p, q, and d).  Each offload message is r_i = g^b_i*m1 mod n, and the respective unblind u_i=y^b_i mod n.  and the key is k = s1/u1+...+s128/u128 mod n.

Unfortunately the user does need to retain g, y & n (or publish them in a hard to censor location, and keep the hash c=H(g,y,n) as a public fingerprint, or embed that in their coin on the block chain, because if the user relied on the offload server to provide g,y,n the server could provide a g,n where g has a small sub-group, allowing the search-space of blinding factor to be greatly reduced.  The few remaining candidate password hashes could then be run through the KDF with the real n.

The user can even create a pre-signed message transferring ownership from key Q1=x1*G to new key Q2=x2*G, with bigger work parameters on x2, that it requests the server operator, or trusted party to release when the available compute farm sizes increase and compute becomes cheaper.  If locktime worked properly, you could even broadcast that transaction with a locktime 1 year into the future, and rely on the bitcoin network to automatically update your security margin over time.

So a user protecting a $10,000 brain-wallet bitcoin investment might say use $10 worth of GPU time (at amazon prices of $2.10 per 400core tesla GPU hour thats 100,000 fermi core seconds or 714 fermi card seconds.  According to the bitcoin wiki mining comparison an S2070 is 4 tesla cores, and does 750MH so say 187.5MH/tesla second is about 37-bits in entropy compared to PBKDF2 rounds.  If you have a 40-bit entropy password that takes you from at risk of being GPU brain-wallet mined ($80 worth of grinding) to implausibly uneconomical  border line not feasible with any resources for the mid-term.  Of course there are faster (AMD not Nvidia) and cheaper ways to grind than amazon.  Eg bitcoin mining pool payout probably charges a lot less.  Maybe it would be something for CPU & GPU miners to do as an alternative to vanity address mining or  primecoin/litecoin mining.


So in summary you in a javascript client, or puny cell processor can create an arbitrarily hard to undo KDF with no practical CPU cost at setup time.  You can offload it securely later to a server, and you are not relying on the server to be around - the information is public (on the blockchain) the "server" is replaceable and stateless, and could even be a bitcoin core feature (pay CPU/GPU miners and other users small fees to help you decrypt your brainwallet).  This is parallelizable so it should be easy to add 40-bits of key-stretching or more that would be really expensive even on a high end PC with top of the line graphics card, to do that from a smart phone.

Probably some more things that could be done eg combine with secret sharing so you can detect and eliminate defective work answers, or perhaps find a way to also have signed proof of work that somehow is easily verifiable without introducing a password verification crib.

Adam

Not that simple to make a signature from that blind offload function, but I think I have a variant that does it, a working blind proof-of-work signature (blind implies privacy preserving offloadable).  

(Though its still broken for mining uses for reasons explained below.)

n=RSA modulus (prime factors deleted at setup)
g=shared generator
e=2^2^w-1 a very big odd number
y=g^e mod n (generated cheaply at setup, or computable one-off cost afterwards)

blind:

m=message
b=random odd blinding factor
r=g^b*g^h(m)  (broadcast r to miners)

work:

s=r^((e-1)/2) mod n (expensive because e is big and carm(n) is unknown)

unblind:

u=(y/g)^(b/2) (unblinding factor)
c = s/u = g^{(e-1)/2*h(m)} (as u=g^{b*(e-1)/2})

verify:

c^2*g^h(m) =? y^h(m)

however this still fails multiple criteria for mining:


so this blind proof-of-work signature is still broken for proof-of-work uses because there is a precomputation that can be used by user (or equivalently a user in cooperation with a miner if he forgoes the privacy from blinding)).  The miner cant use the short-cut when the user blinds the work.

precompute:

p=g^{(e-1)}/2

short-cut using precompute:

c = p^h(m)

(also it has progress in its computation).

Adam

OK so here's the evolution, from the other thread on homomorphic encrypted values

https://bitcointalk.org/index.php?topic=305791.msg3277431#msg3277431


which seem to work and be a more space efficient than I was expecting (1-2KB per value depending on value precision), with that you could take an input with homomorphic encrypted value, spend it to three outputs two of which also have encrypted values (and one clear text fee for the miner) and prove to the miner in zero-knowledge that the transfer is authorized by the holder of the input value 's private key, and that the inputs add up to the outputs.  So the miner has validated the spend but doesnt know the values.  So thats value privacy.

But there is still normal linking of which inputs are linked with which outputs.

For comparison if we could use a signature by a trusted party for validation (as say in a central server ecash system), people use blind signatures to break the link.  So Chaum coins work that way, you probably know but for others Chaum blind signature is very simple:

RSA key: e, d, n=PQ
x=random
s=x||h(x)  (coin serial number with some verifiable structure)

user blind:

b=random
p=b^e*s mod n (send proto-coin to bank)

bank signs (normal RSA sig):

r=p^d mod n (return to user)

user unblind and get (blind signed coin):

c = r/b = s^d  (as r/b=p^d/b=(b^e*s)^d/b=b^{ed}*s^d/b=b*s^d/b=s^d)

so then a user deposit a coin and get a new coin out which is unlinkable, the bank keeps a double spend db of coin serial numbers s and refuses to accept them twice.

so bitcoin distributes the double spend database and uses a proof-of-work with certain required properties instead of a signature.  But if we had a blind proof-of-work, which would be the distributed analog of a blind-signature, we could add the blind-signature style unlinkability to a distributed ecash system like bitcoin.

The important property would be that the proof survived the unblinding step.   It would be immediately apparent to the recipient of c=s^d that someone put a lot of work into this, however they nor the miner who did it would be able to tell which mining event it was, because its blind.
(Earlier in thread I posted a few proof-of-work signatures, that are signatures that support blinding, but the user has to do the work which is backwards and seemingly fairly useless).

Even if we had a Chaum style signature (blind RSA signature) with a proof of work we could make an efficient zerocoin like system (where there is only one coin denomination).  Chaum cant handle multiple denominations because the server doesnt know what it signed.

But there are several more advanced forms of blind signatures which allow the user to prove attributes of the protocoin (coin before signing) in zeroknowledge to the server, eg the value of the coin.  Brands can do that with an extended and blind Schnorr signature like mechanism called a restrictive blind signature or private key certificate.  Brands credentials are pretty counter-intuitive but basically say we have a coin that has an attribute being its value v and this attribute is encoded in some way into a coin public key h.  Now Brands you can do:

h=encode(attribs,x)  (public key with attributes encoded & private key x)
b=random blinding factor

h'=blind(h,b)
p=zkprove(attribs,h')
s=sign(h')
c=unblind(s,b)
sig-verify(c,h,attribs) =? valid

so h is a public key that has some private attributes and a private key x.

you blind h to form h' (eg multiply it or raise it to a random power by blinding factor b you keep)

you create a proof p that still proves the attributes that are in the now blind form of the public key to the server.

The server verifies the proof that the coin contains value v eg deducts that from the users account balance (the user is not anonymous at this point).  The server does an unblindable signature, and sends it to the user.

User unblinds the signature to get a signed but unlinkable coin c which is a signature of h the public key which encodes the attributes.  Because the signature c of the public key h is not blind anymore no one can tell who's coin it was, even the recipient if you spend the coin, nor the recipient and the bank server in collusion.

Brands calls this a restrictive blind signature because the server can see the attributes throgh the blinding (via the zero-knowledge proof) and choose whether it likes the attributes and if the user has enough balance etc before signing, compared to a simple blind signature like chaum where the server does not have any information about the signed value.

There are a few papers that describe the Brands protocols I have links to here:

http://cypherspace.org/credlib/


So anyway any form of blind proof-of-work could be quite interesting as even the simplest form (Chaum, RSA) would be enough to match zerocoin.  Unfortunately the proof-of-work to be amenable for distributed mining has to have a number of specific properties that of the proofs of work only hashcash has (I consider litecoins mining also as hashcash its just using scrypt(1) as the hash function instead of sha256^2).  It has to have no progress, so that its like a random event like a coin toss, no large precomputation optimization and it has to be non-interactive as there is no server to interact with.  So even that seems challenging.

To do attributes proven in zero-knowledge to the miners with restrictive blinding likely a lot harder.

Adam

Here's a pair of offloadable blindable functions:

First RSA based

public params:

[EDITED to relabel x as e, as its more like a large RSA public e exponent]

n=pq (primes p & q deleted at setup)
g=shared generator
e=2^(2^w)-1 ie a big, big number
y=g^e mod n (generated cheaply at setup, or computable one-off cost afterwards)

blind:

m=message
b=random blinding factor
r=g^b*m (broacast r to miners)

work:

s=r^e mod n (expensive because e is big and carm(n)=(p-1)(q-1)/2 is unknown)

unblind:

u=y^b (unblinding factor)
m^e = s/u (as s/y^b=r^e/g^{be}=g^{be}*m^e/g^{be})

Not bad other than the trap-door of n that you cant disprove knowledge of without a trusted person at setup.  Its also non parallelizable, and deterministic cost, so its not a good distributed mining function.  But the cost factor w can be increased fairly arbitrarily without n being bigger than 3072 bits.  Presumably can construct a signature out of this somehow.


square root (4.1 from Dwork & Naor) is also blindable:

public:

prime p (of size relating to w)

blind:

m=message
b=random blinding factor
r=b^2*m (broacast r to miners)

work:

s=sqrt(r)

unblind:

m=s/b (as sqrt(r)=sqrt(b^2*m)=b*sqrt(m))

There are signature schemes based on square root (assuming RSA groups) but that could work over prime field, if the scheme doesnt need a trap-door, just use a very large prime so that its a big amount of work to compute the square root.  Unfortunately that makes big prime fields as you cant increase the work factor without increasing p.  (And using repeated square root wont work much because there are also n-th root algorithms).

Square root doesnt have to be determinstic and the tonelli-shanks square root algorithm even has
some randomness (better for distributed mining) however there are there are slower algorithms which do not and there is a precomputation on Tonelli shanks if you have to find multiple square roots.  To make the precomputation too large you have to increase s where p=2^s*q+1 but before it gets to be a useful size another algorithm becomes better Cipolla which has some small randomness but more of the work is deterministic.  The verification cost and RAM usage also increases as the prime size increases, and the difference between cost and verification is not as stark, ie it starts to get quite expensive to verify even for interesting work factors.

Adam

This is another unpublished signed-hashcash variant with an indistinguishable short-cut I came up with recently based on RSA (n here is the RSA modulus):

setup: c=random, s=salt, i=counter, t=random mod 2^k, a=c^t mod n, m=message
repeat find i such that t =? h( s, i, a, m ) mod 2^k
verify: a == c^t mod n and t = h( s, i, a, m ) mod 2^k
shortcut: s=salt, v=random, i=plausible random, t = h( s, i, a, m ) mod 2^k, c=v^(1/t) mod n

works because knowing p, q you can efficiently compute arbitrary t-th roots.


It has feature parity with Dwork & Naor's (section 4.2 of paper) Fiat-Shamir signature forgery based proof of work (if you want RSA trapdoor for some reason).  But its faster, smaller, and simpler, also supports trap door based on RSA.

They could have supported delegation because Fiat-Shamir is an identity based signature scheme, which they dont seem to mention in their use cases, that this approach doesnt.  However then you cant revoke so thats probably why they avoided it.  Also users who do the work can forge identities anyway in their scheme, though they cannot if they have delegated authority.

[EDIT: also not blindable/offloadable because the work is in the exposed hash, but RSA has a simpler form of blinding so its a start.]

Adam

The other important thing I forgot to say is because the issuer doesnt see the hash its more that user can prove they have a forged issuer signature that the user spent a lot of work creating (its the user that does the work not the issuer).  And the user no longer needs to do the blinding and unblinding steps from 1. blinding the message, 2. having the server signing, and then 3. unblinding, he can just forge a weak signature himself at 2, an then there is no need to blind because you never showed it to anyway before.  This rather analogous to the way bitcoin freshly mined coins are fully anonymous, as you dont really need to bind a proof of work to a forged signature to prove work.


So I think I am demoting/renaming the above scheme to be called signed-hashcash as while its true that you could blind, then do the forged signature, and then unblind (so it is a blindable signature) thats a waste of time as you're doing the blinding and unblinding all yourself the context of the user forging the signature!

We may need a different form of proof of work where the work is blindable / offloadable.  Ie the user can blind a message, publish it so that miners can work on forging a blind-signature on it, and then have the users unblind it in such a way that the proof-of-work survives but in an unlinkable form.

Adam

There is a slip in that writeup, it is missing one parameter, the public key h0 (with unknown discrete log) that must go in the hash, it should be: H(s,i,a,h0,m).


It should be noted that the hashcash backwards compatible version (unlike the non-backwards compatible version) is clearly distinguishable as a forgery, because in a real signature (with knowledge of the discrete log x of h0 where h0=h^x mod n) using the short-cut of knowledge of the discrete log the hash output mod 2^w would be unlikely to be 0, as c=s+H(s,i,a,h0,m) would be computed in a forward direction using knowledge of the discrete log x (of h0 wrt base h) with no iteration, and a and s computed as k=random, a=h^k, r=k+cx.

Its easy to avoid forgery distinguisability, just use the not hashcash mining format compatible first form where c=random, r=random, a=h^r*h0^-c, and c=H(s,i,a,h0,m) mod 2^w (ie where the hash output is random but chosen first, and the only way to avoid work is to know the discrete log of h0. 

But the fact that the backwards compatible form is distinguishable as a forgery, when h0 is chosen to prove no one knows the discrete log, doesnt matter, because any signatures are forgeries by definition!


While true, this does not directly work out so well, as probably intuition should show anyway - how can miners create a forged signature based on a shortened hash with a target output (0 or committed random in the two alternative forms), and then have someone unblind that work and still verify the proof of work.  Hash outputs are non algebraic operations, not amenable to blinding/unblinding.  Here's why:

A blind-schnorr signature actually hides the hash and message from the issuer, more details eg in Brands http://cypherspace.org/credlib/brands-technical.pdf (middle page 17), the certificate signature after unblinding looks like (using convention as Brands that variable with ' like c' are unblinded versions and c are the corresponding blinded version of the same variable)

c' = H(h0, g^c'*h0^r')


So Brands actually takes it one step further and the value that is (blindly) signed is users public key h0.  The issuer never sees h0 during issuing protocol.

But what the issuer sees (if this were not forged) figure 7, page 18 of above Brands paper is obsecured c=c'-a2 for random blinding factor a2, and the issuer sends a blind signature r computed using its private key and c, and the user can unblind that as:

r'=(r+a3)/a1 mod n

using two more random blinding factors a1 and a3.  Now anyone can verify that the certificate signature is valid, it requires knowledge of the discrete log x1 of h1=g1^x1 to compute, which only the issuer knows (h1 is the issuer private key), and yet the neither verifier nor even the verifier and issuer in collusion can link the blind issue value c and blind response r to the unblinded values c' and r'.

h0 is the users public key and the user can then demonstrate certified attributes.  (As part of the issuing protocol the user can also optionally disclose some attributes).

(Much detail elided thats the bit that matters for this argument).  Now what about blind-hashcash - well if you forge the signature you dont need to talk to the issuer, and in fact the issuer doesnt exist.  So you dont need to blind nor unblind.  Consequently you are left with a moderately hard to forge signature only, which seems more like a curiosity than a useful addition to basic hashcash, because while it successfully binds a hashcash proof-of-work to a blindable-signature there is no need to blind or unblind as the user creates his own (forged) certificate.

There does remain some interesting new flexibility in the signature, but it does not seem to admit any new features - eg homomorphic value was already possible with hashcash without binding it to a blindable-signature.

ps dont mind me, it helps to clarify thinking to explain things as if to others I am doing the open source analog of crypto, most people who publish papers do this on a white board and keep it closed until they reach publishable conclusions.  So you are seeing the steps, and failed or interesting but not-useful intermediate steps. 

Adam

(edited slightly)

Its an interesting side effect that the ASIC hashcash backwards compatible variant is actually more convenient because you can test the work separately from the signature.

Just check H(s,i,a,m) mod 2^w == 0 as now.  Then optionally you can check the signature could be useful its much simpler to check the hash, and for some aspects of validation the hash alone would be enough.


(Step c=s+H(s,i,a,m) mod 2^w is equivalent to check 0=?H(s,i,a,m) then c=s).

So far this is a blindable signature, I need to write up (and check) how the Brands blind schnorr signature fits together with blindable-hashcash.

Adam

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

I had been musing on and off for a while now there ought to be a way to create and use to some useful effect in the bitcoin context a blind proof-of-work.  And that homomorphic value might open the way to some interesting not-forseen features.  This might be it.  With reference to this other thread on homomorphic values:

https://bitcointalk.org/index.php?topic=305791.msg3277431#msg3277431

at the end I quote an email to Chris Odom where I observe that the pederson commitments that are used for homomorphic values are actually the same encoding as the representation problem of an unblinded brands credential ecash.  So that leads to the question well can we use a blind form of hashcash instead of hashcash mining in bitcoin so that we use can somehow validate coin without seeing its spend history.

The morphcoin proofs are using Schnorr /EC Schnorr (ECS) also, so the proof of value & range proofs etc are all compatible with Brands blinding.selective disclosure and other proofs.  (Only his coins are signed).

However you might think, but how can you unblind a hash.  You could maybe include a random value in an additional hidden field like g^v*f^r*h^x and the miners challenge is to find a collision involving f, and then you could blind, still prove the coin contains v and adds up, and the right f value, have the miner do its work, the unblind.  That could work however then your coin is associated with a specific mined block reducing the anonymity set.

So ideally you need to have the work itself be unblindable hence blind-hashcash.  Turns out you can do that: it has to be signed, and there is no signing entity.  However the trick is as with the outline idea of one of Dwork & Naor's 1992 proof-of-work (4.2)  (see http://hashcash.org/papers/ ) model of constructing a signature forgery as the work.  In our case because we want no central trapdoor (unlike the RSA modulus in zerocoin and Dwork's use of Fiat-Fiege identity scheme).  So we just create a public key that we can prove no one knows.  eg hash2curve digits of pi (or in non EC public key is hash of seed of digits of pi or such things).  Now we cant compute the EC discrete log (prime field discrete log) and everyone can be convinced that no one knows it.  RSA based is bad for trap doors, discrete log-based good.

Recall a normal Schnorr signature is x is private key, signature is pair (a,r):

k=random, a=h^k, h0=h^x, r=k+cx

and the verification relation is to check: h^r=?a*h0^c
or equivalently a=?h^r*h0^-c.

Now for a forgery we dont know x but never the less we want those verification relations to work.

Here's how blind-hashcash works:

s=random salt, r=random, c=random mod 2^w
compute a=h^r*h0^-c
find i such that c=?H(s,i,a,m) mod 2^n

w is the work factor in bits, i is iterator a string to randomly increase, s is a salt so miner's dont accidentally or intentionally (as DoS) do the same work, a is the initial witness a, h0 is the public key.  m is the message that is signed, in bitcoin thats the coinbase.

The explanation is that we normally need to compute c=H(a,m) so we fix that up after the fact by doing the now shortened hash and using finding s,i such that c is still the same as the random value we guessed up front.

You can use this blind-hashcash protocol with your choice of hash: double SHA256 as H for bitcoin, or similarly with scrypt with iterator 1.  (Litecoin itself is using hashcash also, its just the hash function is replaced with scrypt(1)).

This is nicer than Dwork & Naor's weakened signature forgery based proof of work because the work core does not use big number operations.  (Well you could try to frustrate ASICs with such operations but thats what ppcoin is about, as a basic function you want simplicity).  Also unlike Dwork & Naor function has a trap-door that cant be removed.  Its also faster to verify, more compact, supports blind signatures.  We could allow a trap-door if desired by publishing a public key with an actual private key, or a threshold-held private key so k of n authorities need to collaborate to produce a proof-of-work with a short-cut.  However a short-cut in bitcoin means undo transactions, mint coins, killing the network (difficulty rockets to infinity unless real signatures and doesnt come down) etc.  Also its safer to use a separate signature for short-cuts so that it can be revoked, and detected, and ignored by users who dont trust the authority.  We wont be doing any of that for bitcoin, only mentioned for feature improvement of Dwork & Naor who focused on a central authority model, I tend to focus on eliminating such things!

You notice the core work function is slightly incompatible maybe enough to break existing double SHA256 hashcash ASICs.  We can fix that if desired by doing:

r=random, s=random
compute a=h^r*h0^-s
find i such that 0=?H(s,i,a,m) mod 2^n

on verification compute c=s+H(s,i,a,m)

Now the core work function of blind-hashcash is standard hashcash work function and so can reuse existing asm, C, GPU, FPGA and ASICs for normal hashcash with double SHA-256 or scrypt(1) as hash function.


Then back to bitcoin applications now we can do blind-hashcash (a blind forged signature for an unknown discrete log public key that incorporates a proof-of-work), we can maybe find a way to use that in place of the certificate authority/ecash bank in brands.  If we can do that we can get the advantage of blind ecash privacy with the lack of central authority and distributed mining that bitcoin has.

So if it can be made to work (some questions to check) we would optionally use a homomorphic value input (or a clear input though amounts tend to link if uncommon), blind it, the miners can validate the encrypted amounts add up, even though the coin is blinded (have to check that range-proofs work on blind representation).   Then the miners can make a forged blind signature that looks like they know the discrete log but in reality the forgery is created because we are using a malleable short hash (where you get to try lots of times).

We need to encode in an extra attribute of the coin a block counter j.  So then we'd have a blind-coin with and blinding factor b:

h0 = (g1^j*g^v*h^x)^b

that then can be blinded and disclose to the miners j, v still prove to the verifier you know x (and b).

The main tricky things to work out are the interactiveness as we can have no issuer interaction as there is no issuer, just a distributed forged signature.  Some of the brands mechanisms are resonsive to a server chosen initial witness.  There are some lower round variants but as I recall they were RSA.  Unless the forgery aspect can take care of it - ie e dont need an initial witness, only a self-chosen forged one.  Not sure about that.  And also server knowledge of discrete log of bases g1,g wrt g0 that cant work at least directly in a distributed environmnt.

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

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

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

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

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

A third order thing that could be constructed if the second order boot strap of a synthetic USD traded with BTC worked, and a liquid market in auditable block-chain settled BTC <->synthetic USD could emerge to have auditable decentralized price-discovery of the exchange rate would be to create an alt-coin or coloured coin on the same chain, call that mined virtual USD that references the p2p validatable synthetic USD BTC exchange rate to dynamically control a mining function with the exchange rate as input with the objective of mathematically pegging the alt difficulty to keep the price stable. Of course people would be interested for mining to manipulate the price but arbitrage should ensure that would be a losing proposition.

Adam

For straight odds bet there's a more efficient protocol with no disconnect nor extortion attacks here:

https://bitcointalk.org/index.php?topic=277048.msg3220019#msg3220019

maybe the same trick can be applied to the binary option with reference to an external price feed.

I think partly its that not many people tried to figure out how to write smart-contracts with bitcoin script, though I would think these are exactly the kinds of things Satoshi designed it for (as a smart-contract implementation with knowledge of what smart-contracts are).  So if you buy into the argument that we can with a bit of work find reasonably efficient contracts for the necessary options - I am still more interested in critique of the financial option/market assumptions.

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

ie once you had a bootstrapped exchange market in BTC with synthetic USD (itself constructed from  BTC denominated synthetic USD futures) the only thing you lose if someone shuts off the conventional exchange is the possibility to do arbitrage between the BTC<->synthetic USD market and the BTC<->USD market?

ie the external cash in and cash out would be missing other than bitcoin OTC, but people with synthetic USD positions (still fairly closely tracking USD modulo missed arbitrage price synchronization) would be able to create new positions and liquidate existing positions and spend BTC and synthetic USD.

Adam