blind-hashcash, potential bitcoin applications using blind brands certs/ecash

[adam3us]

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

[1715454293]

1715454293

[1715454293]

1715454293

[1715454293]

1715454293

[adam3us]

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:

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.

(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

[adam3us]

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

[...] 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!

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

[adam3us]

A blind-schnorr signature actually hides the hash and message from the issuer

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.

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.

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

[marcus_of_augustus]

Interesting direction ...

[adam3us]

We may need a different form of proof of work where the work is blindable / offloadable.

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

[adam3us]

signed-hashcash variant with an indistinguishable short-cut [...] based on RSA:

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.

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

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

[socrates1024]

I can't figure out what you're saying you have in mind for the application of this. This is an alternate proof-of-work puzzle? What's the benefit of using this puzzle?

[adam3us]

I can't figure out what you're saying you have in mind for the application of this. This is an alternate proof-of-work puzzle? What's the benefit of using this puzzle?

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

[adam3us]

[RSA based offloadable blindable function]

public params:

n= RSA modulus (prime factors 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 (broadcast r to miners)

work:

s=r^e mod n (expensive because e is big and carm(n)  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})

[...]Presumably can construct a signature out of this somehow.

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:

the proof-of-work to be amenable for distributed mining has to have [...] no progress, [...] no large precomputation optimization and it has to be non-interactive

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

[fellowtraveler]

watching