BitCoin uses a tool called “proof of work” that uses hash function as an underly
ID: 3668453 • Letter: B
Question
BitCoin uses a tool called “proof of work” that uses hash function as an underlying tool. Let h : D {0, 1}256 be a keyless hash function, where D is {0, 1}2^64 . Given a challenge string c of length at most 263, a proof of work requires finding a variation of the string of the form c||z of length at most 264, where z is a string itself, so that h(c||z) is a string that starts with exactly twenty 0’s.
Such a string c||z is called a “proof of work” for challenge c. In BitCoin, a miner is required to generate a “proof of work” for a dynamically generated challenge; its purpose is to require the miner to perform certain number of computation steps related to the challenge c. Describe an algorithm that given c, find a proof of work for it in roughly 220 steps in expectation (in each step, the algorithm can evaluate the hash function once).
Hint: Think of the output of the hash function as “randomly distributed”. And to make it simple, you can think of c as sampled once before it is passed to your algorithm, i.e. it does not change once your algorithm receives it.
Explanation / Answer
The key is to use a stream of true randomness - see below for where that comes from! - to simulate the generating of random hashes that a real proof-of-work mining rig would produce. Now, obviously we don't want to "simulate" every actual hash! A "simulation" of proof-of-work at that level of detail would just be proof-of-work! Rather, we want to mimic the statistical properties of a mining rig's stream of hashes, to just the level of detail required to give the same sort of pattern of meeting / not meeting a moving difficulty target, and all the rest of it, that we get with the real thing.
So: first of all, what exactly is my "stream of true randomness"? Chop up time into units considerably shorter than the intended inter-block time, but with no need to go much finer than general network latency. (Seconds will do, I think.) For each second, t, we need a uniform random number between 0 and 1 assigned to it, RAND(t). This sounds as if we need some awful dependency on a fragile central source - some high-powered laser at NASA pouring out quantum noise every second, or something - with all the trust and failure issues that would imply. Fortunately, for simulating mining rigs, we don't need anything like that. All that matters is that, to someone "buying a simulated mining rig" (burning some bitcoins, that is!) at time t, they can't predict the value of RAND(any t' 2 months or more to the future of t). [Where "2 months" means the dead time a burnt coin must wait before it becomes a simulated active mining rig. See introductory motivating section above. It's basically just a generous waiting period to make sure a burnt coin is truly definitely burnt, and won't have any chance of being "unburnt" in a chain reorg, by the time it comes into use in mining.] We do not need fresh statistical independence of RAND(t) w.r.t. all of RAND(t-1), RAND(t-2), RAND(t-3), etc. (And we don't mind if the stream is known a "short" time into the future - e.g. a week or two; at any rate a small portion of the waiting period.)
Such a lesser goal can, I believe, be achieved with just a few tens of bits of true randomness per week. Quality is what matters, not quantity! I suggest tapping into the world's most highly-audited source of low-bit-rate true randomness: lotteries. These (the big reputable ones anyway) are already subject to elaborate inspection of the machinery that tosses the balls around and draws some of them out. And the results are publicised so widely, in so many newspapers, TV channels, websites etc, as to make it impossible for anyone to lie about them.
Roughly weekly, a config-file (lottery-results.dat or whatever) should get "the latest lottery results" appended to it. There is no hurry about this, it doesn't need to be exactly every week, or even the same lottery every time, it just needs several tens of bits of fresh lottery data added roughly weekly. I believe there would be no trouble propagating this to all nodes, by out-of-band means if necessary. The format should be utterly simple and transparent, a 1-line plain text description of the results and the timestamp (t in RAND(t)) from which they are to be paid attention to, onwards. Like this:
(Obviously the meta-level words "for use from... onwards" aren't really needed - I just put them in for clarity.) Each line is added in a leisurely, unhurried fashion, at some time (it doesn't matter when) between the draw and the intended start-paying-attention-to-it date. (Some time between 2013-06-19 and 2013-07-01 00:00:00, in the case of the example last line above.) This gives plenty of time for people to add it themselves, from their favourite news source, and check by out-of-band means that they've added what everybody else has added, right down to spelling and punctuation. (Which in practice probably means copying it from somewhere. The point is, the "somewhere" doesn't need to be trusted - a lie, or an unexpected variation in format or spelling or punctuation, would be called out well within the leisurely timescale.)
RAND(t) is then HASH(config-file [excluding any lines that are "for use from time later than t onwards" of course], plus t itself [in some standard format, e.g. 2013-07-02 23:14:05, or just the Unix numeric time] as a final line). - Or if you like, HASH(HASH(config-file) ++ t), for efficiency. (Where "++" means "append together in some standard fashion".) "HASH()" is your favourite hash function, e.g. SHA256(SHA256()). Thus RAND(t) is a 256-bit integer, which we regard conceptually as a real number between 0 and 1 by putting a binary point in front.
(I'm aware that people on the forums are coming up with randomness protocols for proof-of-stake, proof-of-activity and the like which don't involve external true randomness like lotteries - they just hash the last hundred blocks' hashes together, or something like that. I don't think this is good enough. [For their application or for mine!] Someone producing the latest block, given the previous 99, can privately produce billions of cheap variations on it, by varying the order the transactions are listed etc, until they find, and publish, the one that "games" the randomness in their favour. However, if I'm wrong about this, and hashing the last hundred blocks is in fact fine, then good! We can drop the lottery rigmarole! Anyway, for the rest of this description, I'll simply assume that RAND(t) becomes available for all t, but remains unknown until a week or two before t, and in particular, RAND(2 months or more from now) is "massively unknown" right now - unknown with many tens to hundreds of bits of unknowable future entropy. That's all that matters for turning burnt coins into simulated mining rigs.)
Right then! What do we do with this RAND(t) stream? We simulate the capricious behaviour of a true proof-of-work mining rig! Let us assume that, in the real proof-of-work world, you can buy an h hashes/second mining rig for b=c*h BTC. (c varies with technical progress, BTC price fluctuations, etc; but in the simulated world it can just be left constant.) Or, inverting this, if you spend b BTC, you acquire a mining rig of h=b/c hashes/s power. Now, what does it actually mean for your rig to perform h hashes during 1 second? It means you're producing h uniform random numbers between 0 and 1. (That binary point again!) But you don't really care what they all are individually - how well you did during that 1 second is defined as "what was the lowest hash value you produced during that 1 second?". This is then inspected for whether it beats [is lower than] the network's current target; or, perhaps, whether it beats the lesser [i.e. numerically greater] target of a pooled mining operation. If it's good enough, that precious lowest hash is published to the network (or mining pool), and the others are just thrown away (not published). If it's not good enough, even the [not-so-]precious lowest hash isn't published - and certainly not the others. So, in the simulation, we only need to produce, for each second, a simulated "lowest hash for that 1 second". The "others" don't have to exist at all!
For reproducing (statistically) the pattern of hits and misses w.r.t. targets tough enough to not be achieving several hits within 1 second, and for h>>1, we can take the simulated lowest hash for time t to be (1/h) * HASH(signatures-of-the-act-of-burning-the-b-BTC ++ RAND(t)). [In fact this even works for h<1, despite the rather surreal appearance of "lowest hashes" >1 every so often in that case - i.e. values outside the range that real lowest (or any other!) hashes can ever actually be: it turns out this surreal behaviour is just what's needed to degrade the probability of beating the target by just the right amount. Values >1 in effect represent "I didn't generate any hashes at all during this particular 1-second window".]
Two further subtleties. First of all, it turns out to be desirable to include the block number (chain height @ 1 per block) in the formula - just to keep the owners of simulated mining rigs "on their toes" and not be able to tell a week or so in advance when they'll be lucky. (This encourages them to run a continuous full node. Maybe that's not in fact that important.) So we take simulated-lowest-hash = (1/h) * HASH(signatures-of-the-act-of-burning-the-b-BTC ++ block-number-of-would-be-block ++ RAND(t)). (We should not include finer details of the block, to avoid "gaming" a la the hundred blocks business I mentioned earlier. - Or if I'm wrong about that, then OK, by all means mix in finer details of the block!)
Secondly, it turns out that to keep the burning process going forever, rather than a pulse of initial burning that no-one ever again wants to contribute further burning to, we should simulate one more property of real-world mining rigs: they break down! That is, we should demurrage away the strength of a simulated mining rig. (A plea to the reader: Don't be alarmed by the word "demurrage". This is burnt coins I'm talking about - they should be treated "harshly", in whatever style mimics real-world mining rigs to the required fidelity. Ordinary unburnt coins are not being demurraged! [Unless that's independently desirable as a policy matter, e.g. if it's felt that network strength can only be achieved via more revenue for miners than fees alone will ever provide.]) A real mining rig likely works at full tilt for a few years and then conks out. We could demurrage each burnt coin in that style - it abruptly expires E years after its creation - but I think a smooth exponential demurrage is nicer, i.e. its burnt value after y years is b'=b*exp(-y/E). Thus h = b'/c = (b/c)*exp(-y/E). [And 1/h = c/b' = (c/b)*exp(y/E).]
Taking these two further subtleties into account, we get the following formula:
So there you have it! With this formula, life as a miner is spookily similar to the real proof-of-work case. You "buy a mining rig" - you burn coins, and that hits you in exactly the way sending off money to a chip supplier would have hit you, even though over the whole economy, no real resources have been expended - and you then hope that, by submitting lucky hashes to the network in the form of blocks, you can make more back in fees over time than you spent initially. If you don't keep connected to the network, you won't know what transactions are eligible for including in your next would-be block, and your next lucky hash will run to waste. Meanwhile, other people are "buying mining rigs" (burning coins) too, either freshly or to make up for the "wearing out" of their existing ones; and the network is adjusting its target hash value [reciprocal difficulty] to regulate the rate all this mining effort is producing blocks at, to some preferred average rate. All spookily normal, in other words!
Now, I'm being a little bit disingenuous to say that everything is normal. We need protection against certain things (use of a lucky hash on two or more competing chains; timestamp-falsification abuse) which either do not exist at all under true proof-of-work - the former - or exist but with the consequences and mitigation strategy being different in detail - the latter. I believe I have a way of standing up to the various forms of malice we need to worry about of those kinds. More to follow soon hopefully!
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.