Dave's Data

In the ongoing experiment that is crypto-currencies, several "Proof-of-Work" functions are commonly used as mechanisms to decentralize control of the currency.  These PoW functions, as they are typically referred to, require a participant to prove that they expended (in expectation) a certain amount of computational effort, such as finding a partial collision in a cryptographically strong hash function.  Many have been introduced to counter the gradual ASIC-ificiation of the dominant PoW, partial collisions in SHA256, used in Bitcoin.  I've discussed several in prior posts that try to require random memory accesses in order to favor general-purpose CPUs over specialized devices such as GPUs or ASICs. In this post, I'll take a look at one called Cuckoo Cycle that combines two of my interests:  Cuckoo Hashing and memory-hard PoW functions.  Its author and a few other people asked me to take a look, and it finally seemed like enough people were looking at it to do s

Introduction In the wake of Bitcoin's success, many "alternative" cryptocurrencies, or "alt-coins" have emerged that change various aspects of the coin in an attempt to improve upon Bitcoin.  (We'll ignore the many that have emerged with the goal of simply duplicating it to put money in their creators' pockets). I've been particularly interested in variants that change something with the "proof-of-work" function.  This sits at the heart of Bitcoin's decentralization:  If a node in the Bitcoin network wishes to be the one permitted to sign a block of transactions, and receive payment for doing so, it must prove that it did a certain amount of computational effort.  This mechanism spreads the authority for the transaction history over all of the participants in the protocol in rough proportion to their computational horsepower.  The goal of this mechanism is to ensure that no one entity can control the currency without spending an eno

I've continued to stay interested in alt-currencies, and, recently, a new one caught my eye:   Riecoin .  Named after Riemann, the proof-of-work in this currency is finding dense clusters of primes starting at a number n , where there are six primes "in a row":   n, n+4, n+6, n+10, n+12 , and n+16 .   To solve a block, you do some hashing of the block contents just as in Bitcoin, and use it to generate a "target" number.  The proof-of-work is then to find a prime chain within a certain numerical distance above the target number. I plan on a more technical post about the process of optimizing the search for these (you can see some discussion of it on the Riecoin bitcointalk thread if you really want).  It's quite fun, but at this point, it still boils down to relatively straightforward prime sieving for huge numbers (1200-1300 bits). There's one very important thing to understand about such sequences, though, before going further:  They only appear at