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#msg3277431at 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