Allow me to knock your socks off:
That, you did. Too bad I could not deploy technical means to express as much, as I promptly attempted:
Thus instead, I’ve been trying to work out how best to refactor my code
now to potentially support this feature and similar
later. (Also, I am trying to work out an adequate test system so I can freely add features without risk of burning
Other People’s Money.) Nothing is in the public repo, as of yet; it’s more of a “back to the design phase” thing, and I believe in trying to keep my scratch work in my own bitbucket rather than spreading it to everyone’s. I want to be able to plug in one-at-a-time key generation search, sipa’s keygrinder, trustless client-server “vanity tweak” generation, this (which I’ll call it a trustless pool batch tweak generator), and any other key/tweak generation methods which may arise—without substantial code copypaste.
As for the rest,
I’ll try to be brief (
good luck), since I should code it instead of chatting about it:
Here is how. Each person has a pubkey P_i, they all come up with uniformly random tweaks T_i. They tweak their keys, and send these resulting public keys to the hashing server. They keep the tweak and original pubkey private.
Thus in code terms, clients do secp256k1_ec_pubkey_tweak_mul(ctx, P_i, T_i). (Not looking for handholding here; I just want to confirm my understanding in terms which will compile.)
Question: Can anybody cause problems of any kind by using nonrandom T_i and/or P_i with interesting properties? I think not, but wish to confirm.
The sever takes all the strings and compiles them into a single match expression (which can be matched in log() operations at worst, probably better).
Side note: I’ve been mulling a better regex system.
Something simple and fast, and also secure for use with expressions from untrusted sources. I like sticking with POSIX <regex.h>, because I always try to minimize unnecessary dependencies. But if trying to match expressions from multiple people, it would make sense to use a library which could compile multiple expressions into one match program without hackish text manipulation à la snprintf(... "(%s)|(%s)|(%s)" ...).
This problem is made worse by unpredictable behaviour in identifying submatches with nested parentheses. Discussing backreferences, FreeBSD’s
regex(3)’s BUGS section blames this on vagueness the POSIX standard; and the problem is confirmed by my experience. Reliable identification of top-level submatches would be an absolutely necessity here, for obvious reasons.
Does there exist a secure, efficient library offering multi-expression composite compilation and reliable submatch numbering?
Then the server sums all the tweaked pubkeys and grinds on it comparing the output with the omnibus matcher.
secp256k1_ec_pubkey_combine() over array of all received keys, then secp256k1_ec_grind() with the result as “master” and server-generated random seeds.
Question: If the server’s PRNG is broken (whether through malice or incompetence), does this affect user security? IOW, do users need to trust the server for that? I don’t think so, but I want to be sure.
When it gets a hit it then demands all clients except the one with the match to tell them the private keys for their tweaked keys (this reveals nothing about the original private key, since it's been tweaked). It then sums up the tweak it found and everyone elses private keys and gives that to the lucky user.
I don’t see any _privkey_combine() function. Could the server iteratively loop secp256k1_ec_privkey_tweak_add() over all received private keys, plus the generated tweak?
The lucky user does the final secp256k1_ec_privkey_tweak_mul() on his
original private key (since the result generated by the server is based on his T_i from the initial step).
You could even have the individual users perform their own grinding. So if they all had computers of the same speed, they effectively get an N fold speedup in how fast they find solutions.
So, pure P2P. I will try to remember not to
bolt a DHT onto it unless I have some extreme form of Sybil resistance. <g>
To discourage abuse you could require a new participant grind without submitting their own keys and patterns for a while... There found tweaks prove the work they did, once someone has done enough you can give them a token they can use to submit a pubkey and pattern(s) for matching, if that user fails to reveal, you ban it. They can rejoin ... but they have to do free work to get a new code.
To protect the privacy of users who may wish to generate different vanity addresses for unlinked nyms, this could be handled with a blind signature token system. However, a relatively modest project then grows a significant layer of complexity.
Good behaviour in submitting private keys when asked could be easily tracked anonymously with such a token: Send a private key when asked, receive a sent_private_key token. The problem with using that for tracking work in a P2P system is the same as with exchanging work generally: How to prove that the work was done? I am thinking that in exchange for tokens, users could provide lists of distinct matches they have found for
e.g. the output public key’s Hash160 starting with
n zeroes (for some medium-sized
n). For each submitted POW match, receive a POW token.
Submitting a search expression costs one sent_private_key token, plus a number of POW tokens. Since I am
far from implementing this particular feature, I’ll wave my hands over that number for now—and over the question of whether this could be done without a server, or at least a semi-trusted supernode, who could be trusted to not cheat the token system (but trusted with nothing else).
I haven't previously implemented it because the protocol minutia with tracking and banning and whatnot is a PITA and only the mathematical part is interesting to me.
I enjoy daemonology, and I am limited in the higher maths. So, that works for me. I don’t know how much time I’ll be able to sink into this, when I
should be coding a commercial service (some productive hackery of TLS protocol minutia) I have on the backburner; but it seems I’ve inadvertently stumbled into what could become a very popular utility if done right.
General design note: I would aim for the cleanest feasible separation between the key-handling code and the network exchange of data. I do dislike how Bitcoin marries the wallet to the network node; it’s a smaller issue with well-written code (
thank you gmaxwell for all your refactoring work), but I still prefer process isolation. In addition to memory separation, this also permits application of OS-specific sandboxing features such as capabilities mode, where supported.
Thus, I will write new code with an eye toward eventually running a secrets-handling process with no network access; and that process can use
various methods to exchange non-secret data with a network process which has no access even to the filesystem (let alone any secret keys). The sandbox APIs are simple and easy on FreeBSD and OpenBSD. I would accept well-written patches for Linux. AFAIK, there is no such feature on Windows. I don’t know anything about Mac.
Thanks again for the hardcore tech talk.
This is the forum I’ve said
“I wish I could now experience”! I know that a post is most valuable when it takes me all day to digest it, mull its potential implications, and formulate proper questions in response.
