Quote from: adam3us on October 08, 2013, 09:25:10 PM

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

and the verification compute c=s+H(s,i,a,m) and check as before a=?h^r*h0^-c.

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

Quote from: adam3us on October 08, 2013, 10:40:40 PM

[...] the ASIC hashcash backwards compatible variant is actually more convenient because you can test the work separately from the signature.

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

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!

Quote from: adam3us on October 08, 2013, 10:40:40 PM

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.

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