BitShares Forum

Main => General Discussion => Topic started by: bytemaster on June 30, 2015, 02:23:50 pm

Title: $500 BitUSD Bounty - ECC Blinded Signatures
Post by: bytemaster on June 30, 2015, 02:23:50 pm
I am looking for the following algorithm to be made available in fc using libsecp256k if possible:

I remember Oleg Andreev working on an ECC blind signatures scheme.
http://blog.oleganza.com/post/77474860538/blind-signatures

It seems he has a working implementation based on obj-c.
https://github.com/oleganza/CoreBitcoin/blob/master/CoreBitcoin/BTCBlindSignature.h

Proposed/Expected API

Code: [Select]
fc::ecc::extended_private_key  bob;
fc::ecc::extended_private_key  alice;
fc::ecc::extended_public_key   bob_pub = bob.extended_public_key();

// a public key that only bob has the ability to generate blinded signatures for
fc::ecc::public_key    pub_key = fc::ecc::blind_public_key(  alice, bob_pub, i );

fc::sha256  digest;

int i = 0;

fc::ecc::blinded_hash          blind_digest =  fc::ecc::blind_hash( alice, bob_pub, digest, i );
fc::ecc::blind_signature       blind_sig      =  fc::ecc::blind_sign( bob, blind_digest, i );
fc::ecc::compact_signature unblind_sig  =  fc::ecc::unblind_signature( alice, bob_pub, blind_sig, i );
 
FC_ASSERT( fc::ecc::public_key( digest, unblind_sig ) == pub_key )


Title: Re: $1000 BitUSD Bounty - ECC Blinded Signatures
Post by: bytemaster on June 30, 2015, 02:35:51 pm
I am looking for ways to combine this technique with stealth addresses and confidential transactions to enable perfectly private transactions with 2-factor authentication:

It would be ideal if a blind_public_key between alice_priv and bob_pub could be derived by SAM with only a one time key and Alice's Extended public key, and Bob's Extended Public key.

Title: Re: $1000 BitUSD Bounty - ECC Blinded Signatures
Post by: arhag on June 30, 2015, 07:17:22 pm
I read the paper and it seems like if Bob does blind_sign on two different blind_digests but with the same index i, he will reveal p and q which thus reveals his parent private key due to the nature of the CKD. So Bob would need to make sure that he never signs with the same index i twice.

Also, this method seems somewhat unfortunate because there doesn't seem to be a way to prove to the public that the only signer of that public key is some specific account. I'm not sure how this plays into what you plan with privacy, but it seems this particular blind signature scheme would not be very useful for a private voting system for example.
Title: Re: $1000 BitUSD Bounty - ECC Blinded Signatures
Post by: bytemaster on June 30, 2015, 07:51:23 pm
This approach allows ME to have someone else sign SOMETHING without them being able to prove they were the one who signed it which could be useful for multi-sig / two-factor on confidential transactions.

I now have a ONE TIME PUBLIC KEY that I know has been signed by SOMEONE  but that SOMEONE cannot use knowledge of the ONE TIME PUBLIC KEY to link back to ME.   

Any way that we could modify this to allow the signer to know that they had the private key for ONE_TIME_PUBLIC_KEY but not give them enough information to tie it back to ME?
Title: Re: $1000 BitUSD Bounty - ECC Blinded Signatures
Post by: arhag on June 30, 2015, 08:27:19 pm
This approach allows ME to have someone else sign SOMETHING without them being able to prove they were the one who signed it which could be useful for multi-sig / two-factor on confidential transactions.

Ah, got it. The tricky thing is that the only person who is able to derive this one-time public key is the one who can generate a, b, c, d, P, and Q (Alice in the example). But I would think for private multisig to be useful the sender of the funds needs to be able to independently specify the public key that is allowed to withdraw the funds using only public information about the receiver. So that means unsolicited funds could not be sent to Alice with this kind of blinded withdraw condition. It would require Alice to provide the sender with the one-time public key that Alice generates in order for the sender to send Alice the funds.

As an aside, for this to be really useful, it would be nice it the scheme could be augmented into a blinded threshold signature scheme (to generalize from a blinded 2-of-2 multisig to a blinded M-of-N multisig). In fact, I would be concerned with being dependent on another party to be able to access my funds. But at least that part can be solved through a convention of everyone using a 1-of-2 multisig where the 2 keys are different one-time public keys: one between ME and the regular blinded signer, and one between ME and my cold storage key acting as the blinded signer.
Title: Re: $1000 BitUSD Bounty - ECC Blinded Signatures
Post by: bytemaster on June 30, 2015, 08:45:31 pm
This approach allows ME to have someone else sign SOMETHING without them being able to prove they were the one who signed it which could be useful for multi-sig / two-factor on confidential transactions.

Ah, got it. The tricky thing is that the only person who is able to derive this one-time public key is the one who can generate a, b, c, d, P, and Q (Alice in the example). But I would think for private multisig to be useful the sender of the funds needs to be able to independently specify the public key that is allowed to withdraw the funds using only public information about the receiver. So that means unsolicited funds could not be sent to Alice with this kind of blinded withdraw condition. It would require Alice to provide the sender with the one-time public key that Alice generates in order for the sender to send Alice the funds.

As an aside, for this to be really useful, it would be nice it the scheme could be augmented into a blinded threshold signature scheme (to generalize from a blinded 2-of-2 multisig to a blinded M-of-N multisig). In fact, I would be concerned with being dependent on another party to be able to access my funds. But at least that part can be solved through a convention of everyone using a 1-of-2 multisig where the 2 keys are different one-time public keys: one between ME and the regular blinded signer, and one between ME and my cold storage key acting as the blinded signer.

Worst case you have to sweep all funds you receive from "single-signature" to "multi-signature" leaving them vulnerable for a short period of time to your single private key being hacked. 
Title: Re: $500 BitUSD Bounty - ECC Blinded Signatures
Post by: arhag on June 30, 2015, 10:42:28 pm
Here is my attempt at modifying the protocol to fix the unsolicited sending problem. I am not sure if this change doesn't break the security (Yes it does! See Edit2) or privacy guarantees of the original protocol. I highly appreciate review of this modified protocol.

There are three parties involved: Alice, Bob, and Carol. Bob is designated as Alice's blinded signer publicly in her account metadata. Carol wants to send funds to Alice without needing any private data from Alice. Carol knows she is sending the funds to Alice, so there is no point in blinding Alice's withdraw signature from Carol. The protocol however needs to guarantee that Carol does not have enough information to get Bob to sign a digest that allows Carol to reclaim the sent funds. Bob only needs to verify that a particular user requesting him to generate a blinded signature is a customer (and verify their identity through whatever means is appropriate to provide the multisig protection) before signing with the appropriate keys meant only for that customer. No one other than Alice or Carol (this includes Bob) should be able to associate the sent balance to Alice at any time in this process including after Alice withdraws the balance using the unblinded signature.

Alice's extended public key is Ka (and corresponding private key is ka). Bob's extended public key is Kb (and corresponding private key is kb which is specific to Alice.

Carol generates a one-time private key o (corresponding public key is O). She generates shared secret s from the x-coordinate of o * Ka (which can also be derived by Alice using O * ka). The modified shared secret s' = H (s || "modified"). The index i = H(s' || "index1"), a second index j = H(s' || "index2"), and the values v1 = H(s' || "value1") and v2 = H(s' || "value2"). Comparing to the paper, v1 == a-1c-1 and v2 == d. Carol also uses index i to derive the child public keys P (represents the same P as the one in the paper) and Q', where P = ND(Kb, 2*i + 0) and Q' = ND(Kb, 2*i + 1). She also uses index j to derive the child public key B' = ND(Ka, j). Comparing to the paper, Q' = a-1Q and B' = a-1bG.

Carol then calculates kG = v1P (from the paper, kG == a-1c-1P), and r which is defined to be the x-coordinate of kG. From the paper, T (the public key in the withdraw condition) is given by T = r-1(a-1bG + a-1Q + a-1c-1dP). We can rewrite this as T = r-1(B' + Q' + v1v2P), which Carol is able to compute.

When Alice receives the funds she can verify that Carol followed the correct procedure. She is able to generate all the same values (including r) starting from the shared secret s. When Alice finally wants to withdraw the funds in another transaction she is going to need the values for a, b, c, and d. Through the index j she is able to calculate the private key for B', which is equivalent to a-1b from the paper (call that value v3). By selecting a random value for a, Alice can then calculate the remaining values: b = av3, c = a-1(v1)-1, and d = v2. This then allows Alice to generate the blinded digest of digest h: h2 = ah + b. However, Alice cannot only send h2 and i to Bob, she must also send a to Bob. As far as I am able to tell, this should not reveal any new information to Bob (would really appreciate a check on this). Also with knowledge of a, even if Bob is colluding with Carol, they cannot withdraw the funds because they are unable to derive b (Not true! See Edit2). However, if Bob and Carol are colluding, Carol can share j with Bob which along with a and h2 allows Bob to associate h2 (and thus Alice's identity) to the digest h (and thus to the balance that Carol sent Alice). But if Bob and Carol are colluding anyway, Carol could just simply tell Bob this information as she was the one who sent the funds to Alice in the first place.

Bob now takes h2, i and a provided by Alice and computes p-1 (where P == p-1G) and q' (where Q' == q'G == a-1Q == a-1qp-1G). Then he computers q = apq'. Finally, Bob computes s1 = ph2 + q, sends s1 back to Alice.

Alice can then use s1 to compute s2 = cs1 + d. The unblinded signature on digest h is then (r, s2) which is signed using a key corresponding to public key T. This signature allows Alice to withdraw her funds.

Edit: Require Bob's extended public key to be a hardened child specific to Alice or else Alice could determine Bob's master private key by getting him to blinded sign the same hash but with different indices. Even if the private keys for P and Q' were uncorrelated, the master private key could have still been computed by getting him to blind sign the same hash four times but with different indices. This also removes the requirement for Bob to track indices for which he has signed before.

Edit2: Major flaw found with the above. If Bob and Carol are colluding, they can determine ka after Alice signs the transaction that withdraw funds sent by Carol. s2 = c*p*a*h + c*p*a*(ka + j) + c*p*a*q' + d.  Carol knows a*c, d, and j. Bob knows p and q'. Together they know y1 and y2 where s2 = y1*(h + ka) + y2. After Alice publishes the transaction to the network to withdraw the funds, she also necessarily publishes h and s2, and so at that point Bob and Carol can simply solve for Alice's private key ka. :( Back to the drawing board I guess.
Title: Re: $1000 BitUSD Bounty - ECC Blinded Signatures
Post by: arhag on July 01, 2015, 01:51:46 am
By the way, I don't think the scheme discussed in this thread is what is typically known as "blinded signatures" in the literature. Here you are requiring that no one other than the person who blinds the digest and unblinds the signature to be able to associate the public key corresponding to the signature to the blinding signer. But in typical blinded signatures (useful in eCash and voting) that requirement isn't necessary and in fact not desirable. In those situation we would want everyone to be able to know the authority that signed the digest; we just don't want anyone (including the authority) other than the blinder/unblinder to know the association between the digest/signature and the identity of blinder/unblinder. I believe that cryptographic procedure will also be desirable to include in the future (as far as I am aware, it will be needed for voting since the alternative of ring signatures leads to large transaction sizes), so it makes it especially confusing to use the same name for the scheme described in this thread.


Any way that we could modify this to allow the signer to know that they had the private key for ONE_TIME_PUBLIC_KEY but not give them enough information to tie it back to ME?

What would be the purpose of that? If the signer knows they can sign for a particular ONE_TIME_PUBLIC_KEY then they must know that the balance is meant for one of their customers. But if they cannot know which specific customer it is for (because we don't want to leak that information), then what would they possibly do with this knowledge?
Title: Re: $500 BitUSD Bounty - ECC Blinded Signatures
Post by: karnal on July 01, 2015, 08:52:30 am
Glad to see this is being discussed, even if technically it is a bit over my head. +5%
Title: Re: $500 BitUSD Bounty - ECC Blinded Signatures
Post by: Ander on July 01, 2015, 09:35:52 pm
Glad to see this is being discussed, even if technically it is a bit over my head. +5%
Arhag's post was more than just 'a bit' over my head.

:D
Title: Re: $500 BitUSD Bounty - ECC Blinded Signatures
Post by: arhag on July 03, 2015, 03:56:00 am
Is anyone actually working on this bounty? Here are my thoughts on how this bounty should be restructured.

I think wrapping the crypto primitives from secp256k1-zkp in a nice friendly C++ interface that we can use to intuitively do crypto math (adding/multiplying 256-bit numbers modulo order of the curve, adding curve points together, and multiplying a 256-bit scalar with a curve point, etc.) is a project of its own that could act as a prerequisite to this blinded signature project. It should also implement or wrap HMAC-SHA512 as that is needed for BIP32, which as far as I am aware libsecp256k1 does not implement but OpenSSL might. (By the way, why do we bother with a choice in the fc library between an OpenSSL implementation for the ECC math versus the libsecp256k1 one? At this point can't we just commit to the libsecp256k1 one? The secp256k1-zkp dependency is needed anyway for the Confidential Transaction stuff, right? It's also a bit frustrating seeing the public_key and private_key implementations depend on OpenSSL's bignum while libsecp256k1 apparently implements its own bignum stuff in order to do the ECC math.)

Then after that, those crypto primitives could be used to build extended_private_key and extended_public_key which can be used for proper BIP32 hierarchical deterministic wallets (honestly I was surprised to find out that wasn't already implemented in BitShares).

Then finally, the crypto primitives and extended_private_key/extended_public_key classes can all be used to implement Oleg's algorithm in a pretty straightforward and easy way. In fact at that point I would be interested in implementing my own modified version just to see how it works.

So I see this bounty broken down into those three separate projects. I think it would make this task more accessible for people. And in my opinion, the first one should be worth more than the second, and the second worth more than the third.
Title: Re: $500 BitUSD Bounty - ECC Blinded Signatures
Post by: bytemaster on July 03, 2015, 04:52:21 am
Now that fc defaults to libsecp256k we might as well embrace it and clean up the wrapping of it.
I am also in favor of using libsec256k bignum support where possible.   

We had extended public/private keys but they were in bitshares not fc.   I would like to keep fc "application neutral" and general purpose.

Generally speaking I don't have the money to improve something that isn't broken, but I will award major BROWNIE.PTS for anyone who wants to take on these tasks. 
Title: Re: $500 BitUSD Bounty - ECC Blinded Signatures
Post by: arhag on July 03, 2015, 05:07:38 am
We had extended public/private keys but they were in bitshares not fc.   I would like to keep fc "application neutral" and general purpose.

Oh no wonder I couldn't find it. It isn't in the Graphene toolkit first of all. And while it is in the old BitShares codebase, it isn't in fc like you said. Are you guys planning on adding hierarchical deterministic wallet support into Graphene?

Well if you don't want to put that in fc, then either there is a weird dependency issue if you want this blinded signature algorithm in fc OR the interface of the algorithm needs to change to not depend on extended private/public keys OR the blinded signature algorithm should just be put into the Graphene toolkit and not fc (but if you go that route I would argue you should strip all ECC out of fc).
Title: Re: $500 BitUSD Bounty - ECC Blinded Signatures
Post by: pc on July 03, 2015, 08:35:10 pm
Is anyone actually working on this bounty?

I am, but at a very low pace.
Title: Re: $500 BitUSD Bounty - ECC Blinded Signatures
Post by: arhag on July 03, 2015, 09:29:57 pm
Is anyone actually working on this bounty?

I am, but at a very low pace.

Glad to hear someone is working on it.  :)
Title: Re: $500 BitUSD Bounty - ECC Blinded Signatures
Post by: pc on July 19, 2015, 09:29:24 pm
Got a working version - https://github.com/cryptonomex/fc/pull/46

Notes:
* The call interface is slightly different from the suggestion in the OP.
* The generated signatures will fail the public_key::is_canonical test in slightly more than 50% of the cases. Callers must check and retry with the next i. IMO is_canonical is much more restrictive than required.
* libsecp256k1 does not export all required primitives, so I had to fall back on openssl in some cases.
Title: Re: $500 BitUSD Bounty - ECC Blinded Signatures
Post by: xeroc on July 20, 2015, 07:02:02 am
Got a working version - https://github.com/cryptonomex/fc/pull/46

Notes:
* The call interface is slightly different from the suggestion in the OP.
* The generated signatures will fail the public_key::is_canonical test in slightly more than 50% of the cases. Callers must check and retry with the next i. IMO is_canonical is much more restrictive than required.
* libsecp256k1 does not export all required primitives, so I had to fall back on openssl in some cases.
it's great to have you on board!!
Title: Re: $500 BitUSD Bounty - ECC Blinded Signatures
Post by: cass on July 20, 2015, 11:44:58 am
Got a working version - https://github.com/cryptonomex/fc/pull/46

Notes:
* The call interface is slightly different from the suggestion in the OP.
* The generated signatures will fail the public_key::is_canonical test in slightly more than 50% of the cases. Callers must check and retry with the next i. IMO is_canonical is much more restrictive than required.
* libsecp256k1 does not export all required primitives, so I had to fall back on openssl in some cases.
it's great to have you on board!!

 +5% good work @pc
Title: Re: $500 BitUSD Bounty - ECC Blinded Signatures
Post by: bytemaster on July 20, 2015, 01:33:13 pm
Nice work PC!
Title: Re: $500 BitUSD Bounty - ECC Blinded Signatures
Post by: alt on July 20, 2015, 02:15:15 pm
Got a working version - https://github.com/cryptonomex/fc/pull/46

Notes:
* The call interface is slightly different from the suggestion in the OP.
* The generated signatures will fail the public_key::is_canonical test in slightly more than 50% of the cases. Callers must check and retry with the next i. IMO is_canonical is much more restrictive than required.
* libsecp256k1 does not export all required primitives, so I had to fall back on openssl in some cases.
it's great to have you on board!!

 +5% good work @pc
+5%
Title: Re: $500 BitUSD Bounty - ECC Blinded Signatures
Post by: arhag on July 29, 2015, 03:54:02 am
There is a potential flaw with this algorithm. At the moment that the user stores their balance on the blockchain with a particular blind public key T, they are also forced to commit to a particular nonce k = (c*p*a)-1. The final signature s(h) on any given hash h is s(h) = (c*p*a)*h + (c*p*b + c*q + d) = y1*h + y2, where y1 and y2 are values that neither the user nor the blind signer alone know but are nevertheless fixed given a fixed blind public key T. If the user wants to spend the balance, they craft a transaction with digest h1, go through the blind signature process and generate the signature s1 = s(h1) which they include with the signed transaction they broadcast to the network. So far no problem.

But what happens if for whatever reason that signed transaction is not included in the blockchain before the transaction expires? The user is then forced to craft a new transaction with a new expiration time, and thus necessarily a new digest h2, go through the blind signature process again and generate the signature s2 = s(h2) which they include with the new signed transaction they broadcast to the network. This is where we have a problem. Anyone with access to those two signed transactions can then calculate k through k = (s1 - s2)-1 * (h1 - h2), and with k known they can then calculate r = x-coordinate of the point (k*G), and x = r-1*(s1*k - h1)). The value x is the private key of the public key T (i.e. T = x*G). With x known, an attacker can then craft another transaction spending that balance to their own account and try to get that transaction into the blockchain before the user's second transaction. This is quite easy to do if many of the witnesses are colluding in the attack OR if the attacker controls all the nodes that the user's client happens to be connected to.

One quick fix to this problem is to not require withdraw operations signed by blinded signatures to be indistinguishable from regular signatures. We could decouple the blinded signature from the signature that signs the transaction (this is something that might be a problem for this algorithm on the Bitcoin network, but fortunately we have the flexibility to modify our blockchain protocol). The withdraw condition of the balance would no longer be that it requires the transaction to be signed by public key T. Instead it would require that the transaction include a special operation whose validity is determined by public key T and that the transaction be signed by public key Y, where Y = z*G and z is a hardened child private key determined using index Hash(T) (it is important for it to be hardened so that the public cannot check if this balance is associated with the user's account). This special operation would include a signature embedded inside of it and for the operation to be valid it would require the signature be a valid signature on the digest Hash(Y) using public key T.

So the way this would work is that when the user is storing the balance on the blockchain, their client first goes through the regular procedure to calculate T and then it would use Hash(T) to calculate z and thus Y. It would then create, sign, and broadcast the transaction that initially stores the balance on the blockchain using the values of the address of T and the address of Y in the transaction.

Later when the user wants to spend that balance, the user's client would again generate Y = z*G , go through the blind signature process using the digest Hash(Y), and keep the resulting unblinded signature s in memory (if necessary, say the client crashes and s is lost, the user can repeat the process, meaning re-authenticate with the blind signer, and recalculate s). The user can then generate as many transactions as they want (with unique nonces each time of course) by including the special operation (which contains s) in the transaction and signing it with private key z. Once the transaction is confirmed in the blockchain, the user's client can then delete s from memory.

It is important to understand that from the time that the user receives s and keeps it in memory until the time that the balance has been fully spent on the blockchain, the user is no longer protected with two-factor authentication. If their client gets compromised in that time in such a way that an attacker can get access to the client's memory, the attacker will be able to spend that balance without needing to authenticate to the blind signer at all. Fortunately, it is more difficult to compromise the memory of the client rather than just the user's private key and the window of attack opportunity should normally be very short. Alternatively, the attacker can also compromise the user within the attack window if they know the user's private key AND are able to get access to plain-text communication between user and blind signer such that they can grab (p*a*Hash(Y) + p*b + q) while it is in transit over the network from blinded signer to user (I am of course assuming the attacker with the user's private key is not in collusion with the blind signer, since in that case it is trivial to compromise the balance). For this reason, it is important that the session between the user's client and the blind signer be encrypted (i.e. use TLS), so that the attacker really does need to compromise the client's memory to succeed in the attack.
Title: Re: $500 BitUSD Bounty - ECC Blinded Signatures
Post by: arhag on July 29, 2015, 08:54:24 am
Okay, this is my second attempt at coming up with a blinded signature algorithm that (attempts to) solve what I consider two problems with Oleg Andreev's algorithm. The first is the fact that the nonce is determined at the time the public key is determined (which I discussed in my previous post). The second is the unsolicited fund problem (which means that the balance remains unprotected by two-factor authentication from the time the sender sends it until the time the receiver moves it into a new balance that is protected by the public key derived from the blinded signature algorithm).

I believe I have come up with a solution (although for all I know it might be flawed like my first attempt (https://bitsharestalk.org/index.php/topic,17315.msg220498.html#msg220498) which allowed colluding attackers to gain access to the user's private key) that solves both of those problems while generating a standard Schnorr signature (https://en.wikipedia.org/wiki/Schnorr_signature). I had to give up on ECDSA since I'm not sure if it is even possible to do a blinded signature algorithm that satisfies these two requirements. Schnorr signatures have a lot of advantages over ECDSA anyway, like making threshold signatures really easy.

Again I assume there are three parties: Alice, Bob and Carol. Carol is sending unsolicited funds to Alice and Bob is Alice's designated blind signer. This time Bob does not need to have a public key specific to each of his customers. (Not true. See edit.) I believe the protocol I lay out below allows Bob to protect his private key even though it is being used to service all customers (meaning his customers cannot trick him to generate and return values that allow them to recover his private key... I hope). Bob's blind-signing private key is b and his published blind-signing public key is B = b*G. Alice's blind-receiving private key is a and her published blind-receiving public key is A. (Note I use blind-signing and blind-receiving rather than just active as an added security precaution. If I am wrong and there is a way to determine Alice's or Bob's private key, at least the damage is contained only to balances designated for blind signing rather than everything. This of course assumes that the blind-signing/blind-receiving private keys are determined through hardened child derivation from the corresponding active private keys, rather than normal child derivation.)

When Carol wants to send funds to Alice all she needs is the share secret z derived from Diffie-Hellman key exchange, Alice's blind-receiving public key A (which is published in her account metadata), and the blind-signing public key B of Alice's blind signer (Carol looks up in Alice's account metadata that Alice's blind signer is Bob, and then looks up in Bob's account metadata that his blind-signing public key is B). Carol then computes f = HMAC256(z, SHA256("blind")), and then the public key T = A + B + f*G. She sends the funds to a balance that can be withdrawn using a Schnorr signature corresponding to public key T (the full public key T is included rather than the address since Schnorr signatures do not allow recovering the public key from the signature) and also includes in the transaction the one-time public key that Alice needs to derive the shared secret z. When Alice receives the transaction, she can compute the shared secret z, then f, and then T, and verify that the transaction is valid before accepting it as payment for goods and services.

Later, when Alice wants to actually withdraw the funds, she creates a withdraw transaction which has digest h. She then connects to Bob with a secure connection, authenticates herself to Bob, and then they go through the following procedure (all operations are modulo the group order):
Then (s, e) is the Schnorr signature on digest h with public key T. The blockchain can verify the signature is valid by verifying that SHA256(h || (s*G + e*T)) == e.

Bob only has access to r, P, w, and y. Since v is a pseudo-random number that Bob does not know, he cannot relate w to e. If Bob suspects a particular spent balance belongs to Alice, he can compute F1 = s*G + e*T - P - (w+e)*(B + r*G) which should be u*G if it is in fact Alice's balance. He can also compute F2 = s*G - y*G + e*A - e*r*G which should be u*G - e*f*G. Therefore, even though Bob cannot know the pseudo-random number u, if e-1*(F1 - F2) ==  f*G, then Bob can know the balance does in fact belong to Alice. However, Bob also does not know f because he does not know the shared secret z. While Carol does know the shared secret z, if Bob and Carol were colluding, she could just trivially tell Bob that the balance does in fact belong to Alice. I don't believe there is any way for Bob alone to link the balance to Alice by following this protocol.

The remaining questions are: if Bob and Carol colluding together can generate a valid Schnorr signature on an arbitrary digest or even discover Alice's private key a; and, if Alice can trick Bob into revealing his private key b. While I don't have any proof that these two things are impossible, I haven't yet been able to figure out a way that it could be done. Of course, a review of the protocol is highly appreciated.

Edit: Once again a flaw. Though I still think users cannot trick Bob into revealing his key with the above protocol, it is still broken because users sharing the same blind signer essentially are not protected by two-factor authentication with respect to each other. Eve can legitimately authenticate with Bob and get him to blind sign a digest that allows her to steal Alice's balances if she also knows Alice's private keys. The whole point of this is to provide two-factor authentication so the above protocol is broken if they use a universal public key B (and Bob uses the corresponding universal private key b). Instead B should be specific to each customer where its private key b is for example determined using hardened child private key derivation with SHA256(A) as the index. Alice could have Bob generate that public key for her once and then she would post it on her public metadata. Unsolicited transactions would still work fine. I will have to update the details of this protocol more formally to reflect these changes, but I have other changes planned with this protocol such as:
So I will eventually post an upgraded version of the protocol some time later with all of those changes included.
Title: Re: $500 BitUSD Bounty - ECC Blinded Signatures
Post by: xeroc on August 13, 2015, 01:32:35 pm
Is there an update as to how blinded transactions are actually implemented now?
Title: Re: $500 BitUSD Bounty - ECC Blinded Signatures
Post by: roadscape on August 14, 2015, 07:52:43 pm
Thanks @arhag for looking out for potential flaws!

Is there an update as to how blinded transactions are actually implemented now?

+5%.. I hope this feature will be disabled on the main chain until we are sufficiently confident about it (even if it means it won't be available on Day 1)