[Bitcoin-development] ASIC-proof mining

[Bitcoin-development] ASIC-proof mining

[Andy Parkins]

Hello,

I had a thought after reading Mike Hearn's blog about it being impossible to 
have an ASIC-proof proof of work algorithm.

Perhaps I'm being dim, but I thought I'd mention my thought anyway.

It strikes me that he's right that it's impossible for any algorithm to exist 
that can't be implemented in an ASIC.  However, that's only because it's 
trying to pick an algorithm that is CPU bound.  You could protect against ASCI 
mining (or rather, make it irrelevant that it was being used) by making the 
algorithm IO-bound rather than CPU-bound.

For example, what if the proof-of-work hash for a block were no longer just 
"hash of block", which contains the hash of the parent block, but instead were 
hash of 

   [NEW_BLOCK] [ALL_PREVIOUS_BLOCKS] [NEW_BLOCK]

[ALL_PREVIOUS_BLOCKS] is now 20GB (from memory) and growing.  By prefixing and 
suffixing the new block, you have to feed every byte of the blockchain through 
the hashing engine (the prefix prevents you caching the intermediate result).  
Whatever bus you're using to feed your high speed hashing engine, it will 
always be faster than the bus -- hence you're now IO-bound, not CPU-bound, and 
any hashing engine will, effectively, be the same.

I'm making the assumption that SHA-256 is not cacheable from the middle 
outwards, so the whole block-chain _has_ to be transferred for every hash.

Apologies in advance if this is a stupid idea.



Andy
-- 
Dr Andy Parkins
andyparkins@gmail.com

Re: [Bitcoin-development] ASIC-proof mining

[Alan Reiner]

Just a thought on this -- I'm not saying this is a good idea or a bad
idea, because I have spent about zero time thinking about it, but
something did come to mind as I read this.  Reading 20 GB of data for
every hash might be a bit excessive.  And as the blockchain grows, it
will become infeasible to continue.  However, what comes to mind is the
ROMix algorithm defined by Colin Percival, which was the pre-cursor to
scrypt.  Which is actually what Armory uses for key stretching because
it's far simpler than scrypt itself while maintaining the memory-hard
properties (the downside is that it's much less flexible in allowing the
user to trade-off compute time vs memory usage).

ROMix works by taking N sequential hashes and storing the results into a
single N*32 byte lookup table.   So if N is 1,000,000, you are going to
compute 1,000,000 and store the results into 32,000,000 sequential bytes
of RAM.  Then you are going to do 1,000,000 lookup operations on that
table, using the hash of the previous lookup result, to determine the
location of next lookup (within that 32,000,000 bytes).  Assuming a
strong hash function, this means its impossible to know in advance what
needs to be available in RAM to lookup, and it's easiest if you simply
hold all 32,000,000 bytes in RAM.

Something similar could be applied to your idea.  We use the hash of a
prevBlockHash||nonce as the starting point for 1,000,000 lookup
operations.  The output of the previous lookup is used to determine
which block and tx (perhaps which chunk of 32 bytes within that tx) is
used for the next lookup operation.   This means that in order to do the
hashing, you need the entire blockchain available to you, even though
you'll only be using a small fraction of it for each "hash".  This might
achieve what you're describing without actually requiring the full 20 GB
of reading on ever hash.

-Alan



On 07/04/2014 06:27 AM, Andy Parkins wrote:
> Hello,
>
> I had a thought after reading Mike Hearn's blog about it being impossible to 
> have an ASIC-proof proof of work algorithm.
>
> Perhaps I'm being dim, but I thought I'd mention my thought anyway.
>
> It strikes me that he's right that it's impossible for any algorithm to exist 
> that can't be implemented in an ASIC.  However, that's only because it's 
> trying to pick an algorithm that is CPU bound.  You could protect against ASCI 
> mining (or rather, make it irrelevant that it was being used) by making the 
> algorithm IO-bound rather than CPU-bound.
>
> For example, what if the proof-of-work hash for a block were no longer just 
> "hash of block", which contains the hash of the parent block, but instead were 
> hash of 
>
>    [NEW_BLOCK] [ALL_PREVIOUS_BLOCKS] [NEW_BLOCK]
>
> [ALL_PREVIOUS_BLOCKS] is now 20GB (from memory) and growing.  By prefixing and 
> suffixing the new block, you have to feed every byte of the blockchain through 
> the hashing engine (the prefix prevents you caching the intermediate result).  
> Whatever bus you're using to feed your high speed hashing engine, it will 
> always be faster than the bus -- hence you're now IO-bound, not CPU-bound, and 
> any hashing engine will, effectively, be the same.
>
> I'm making the assumption that SHA-256 is not cacheable from the middle 
> outwards, so the whole block-chain _has_ to be transferred for every hash.
>
> Apologies in advance if this is a stupid idea.
>
>
>
> Andy

Re: [Bitcoin-development] ASIC-proof mining

[Eugen Leitl]

On Fri, Jul 04, 2014 at 06:53:47AM -0400, Alan Reiner wrote:

> Something similar could be applied to your idea.  We use the hash of a
> prevBlockHash||nonce as the starting point for 1,000,000 lookup
> operations.  The output of the previous lookup is used to determine
> which block and tx (perhaps which chunk of 32 bytes within that tx) is
> used for the next lookup operation.   This means that in order to do the
> hashing, you need the entire blockchain available to you, even though
> you'll only be using a small fraction of it for each "hash".  This might
> achieve what you're describing without actually requiring the full 20 GB
> of reading on ever hash.

Anything involving lots of unpredictable memory accesses to a large
chunk of fast memory is unASICable. That data vector could be derived
by the same means as an one time pad, and loaded and locked into
memory after boot. If you make it large enough it won't profit from
embedded RAM bandwidth/speedup. The only way to speed up would be clustering,
which doesn't offer economies of scale.

Re: [Bitcoin-development] ASIC-proof mining

[Andy Parkins]

On Friday 04 July 2014 06:53:47 Alan Reiner wrote:

> ROMix works by taking N sequential hashes and storing the results into a
> single N*32 byte lookup table.   So if N is 1,000,000, you are going to
> compute 1,000,000 and store the results into 32,000,000 sequential bytes
> of RAM.  Then you are going to do 1,000,000 lookup operations on that
> table, using the hash of the previous lookup result, to determine the
> location of next lookup (within that 32,000,000 bytes).  Assuming a
> strong hash function, this means its impossible to know in advance what
> needs to be available in RAM to lookup, and it's easiest if you simply
> hold all 32,000,000 bytes in RAM.

My idea wasn't to make hashing memory hungry; it was to make it IO-hungry.  It 
wouldn't be too hard to make an ASIC with 32MB of RAM.  Especially if it 
gained you a 1000x advantage over the other miners.  It seems that sort of 
solution is exactly the one that Mike Hearn was warning against in his blog.

> you'll only be using a small fraction of it for each "hash".  This might
> achieve what you're describing without actually requiring the full 20 GB
> of reading on ever hash.

But we want that read.  Remember the actual hash rate isn't important, what 
matters is how hard it is to reproduce.  If we make it 1000x harder to do one 
hash for everybody, we're still just as secure.  The difficulty adjustment 
algorithm ensures blocks come at 10 minutes, regardless of hash rate.  So we 
can make it harder by picking a harder algorithm -- SCRYPT or BLOWFISH, or 
just by upping the size of the data that needs hashing.  The advantage of 
upping the size of the input is that, unlike an algorithm change, you can't 
build a better ASIC to reduce the size.


Andy

-- 
Dr Andy Parkins
andyparkins@gmail.com

Re: [Bitcoin-development] ASIC-proof mining

[Alan Reiner]

On 07/04/2014 07:15 AM, Andy Parkins wrote:
> On Friday 04 July 2014 06:53:47 Alan Reiner wrote:
>
>> ROMix works by taking N sequential hashes and storing the results into a
>> single N*32 byte lookup table.   So if N is 1,000,000, you are going to
>> compute 1,000,000 and store the results into 32,000,000 sequential bytes
>> of RAM.  Then you are going to do 1,000,000 lookup operations on that
>> table, using the hash of the previous lookup result, to determine the
>> location of next lookup (within that 32,000,000 bytes).  Assuming a
>> strong hash function, this means its impossible to know in advance what
>> needs to be available in RAM to lookup, and it's easiest if you simply
>> hold all 32,000,000 bytes in RAM.
> My idea wasn't to make hashing memory hungry; it was to make it IO-hungry.  It 
> wouldn't be too hard to make an ASIC with 32MB of RAM.  Especially if it 
> gained you a 1000x advantage over the other miners.  It seems that sort of 
> solution is exactly the one that Mike Hearn was warning against in his blog.

I think you misundersood....  using ROMix-like algorithm, each hash
requires a different 32 MB of the blockchain.  Uniformly distributed
throughout the blockchain, and no way to predict which 32 MB until you
have actually executed it.   If the difficulty is high enough, your
miner is likely to end up going through the entire X GB blockchain while
searching for a good hash, but other nodes will only need to do 32 MB
worth of disk accesses to verify your answer (and it will be unknown
which 32 MB until they do the 1,000,000 hash+lookup operations on their
X GB blockchain).

I think that strikes a good compromise of needing access to 100% of the
blockchain, without requiring reading 20 GB to verify a block.

(Replace N=1,000,000, 32 MB and 20 GB with the appropriately calibrated
numbers in the future)

Re: [Bitcoin-development] ASIC-proof mining

[Andy Parkins]

On Friday 04 July 2014 07:22:19 Alan Reiner wrote:

> I think you misundersood....  using ROMix-like algorithm, each hash

I did.  Sorry.

> requires a different 32 MB of the blockchain.  Uniformly distributed
> throughout the blockchain, and no way to predict which 32 MB until you
> have actually executed it.   If the difficulty is high enough, your
> miner is likely to end up going through the entire X GB blockchain while
> searching for a good hash, but other nodes will only need to do 32 MB
> worth of disk accesses to verify your answer (and it will be unknown
> which 32 MB until they do the 1,000,000 hash+lookup operations on their
> X GB blockchain).

Excellent.


Andy

-- 
Dr Andy Parkins
andyparkins@gmail.com

Re: [Bitcoin-development] ASIC-proof mining

[Gregory Maxwell]

On Fri, Jul 4, 2014 at 3:27 AM, Andy Parkins <andyparkins@gmail.com> wrote:
> Hello,
>
> I had a thought after reading Mike Hearn's blog about it being impossible to
> have an ASIC-proof proof of work algorithm.
>
> Perhaps I'm being dim, but I thought I'd mention my thought anyway.

Thanks for sharing. Ideas similar to what you're describing have come
up a number of times before.

I believe the particular formulation you're suggesting is not workable
for a number of reasons.

If I understand what you're proposing correctly, it that it has very
high (nearly symmetrical) verification costs, all the verifiers have
to also hash all of that information to check the result. It is
imperative for the system that the proof of work be cheap to verify,
since every system needs to verify it and have no incentive to skip
verifying it, needs to use it to block DOS attacks, etc.

I believe this design would also completely preclude lite nodes (SPV
nodes, section 8 of https://bitcoin.org/bitcoin.pdf), which are the
most popular Bitcoin wallets. SPV wallets do not need to store the
blockchain, in fact they technically need no storage at all— and are
secure, given some assumptions about the decentralization and honesty
of mining. It would make Bitcoin more or less infeasible to use on
mobile devices and force many people using wallets onto centralized
services providers which they'd have to trust to process their
transactions.

Another longer term side effect of making verification costly is that
it makes it much less reasonable to provide zero knoweldge proofs for
data in Bitcoin— closing off a whole set of useful tools like strongly
private proofs of solvency, and strongly private bitcoin-backed
pseudonymous identities.

I also believe this would also break pruning (section 7 of
bitcoin.pdf): Right now a fully validating node can be created that
uses only on the order of 1GB of disk space, without pruning the
number is 25 GB and the gap is just going to grow over time. The
elimiating of pruning would be a major scalability hit.

A smaller, but potentially still important issue is that the proposed
proof of work function would be expensive to run even once. This may
result in it not being effectively progress free— if a miner would
typically only make a small number of tries before success then it
would make mining like a race where faster miners would have a
super-linear advantage over others instead of statistically rewarding
miners fairly.

There are ways to make what I think you're trying to accomplish work
with fewer tradeoffs that have been suggested before (see
https://en.bitcoin.it/wiki/User:Gmaxwell/alt_ideas "POW which involves
queries against the UTXO set")... the general idea there is that the
candidate block header is used to randomly select one or a few random
entries in the set of spendable coins (UTXO set), which are then
included in the hashing. If the UTXO set is also committed in every
block via a hash tree when the miner finds a solution he can also
extract a compact membership proof that shows the UTXO he included in
his hashing were the right ones.  This way the work can still be
verified by systems that don't have the blockchain (though they may
use 10x more bandwidth— unfortunate on its own and perhaps enough to
still make zero knoweldge proofs less practical), and because the
queries are against the UTXO set instead of the whole blockchain it's
not incompatible with pruning.

Though even with those fixes, I am far from sure that this would be
helpful: It would not preclude specialized high efficiency hardware
for mining (see https://download.wpsoftware.net/bitcoin/asic-faq.pdf
for set of general arguments in this space), and the hardware that
existed may not be actually useful for validation in much the same way
that you cannot use existing mining hardware as a general sha256
accelerator.

This specialized hardware might look more like an massively parallel
flash or dram array with integrated computation (e.g.
http://www.eecg.toronto.edu/~dunc/cram/ )— and these differences may
not all be good: by shifting costs from operating energy to gate-count
it moves the total costs into hardware which is one-time and amortized
over use (generally for modern process, compute bound equipment costs
more in energy than the marginal costs in fabrication after a month or
two of operation), potentially creating an advantage for
earlier/larger participants. Plus a CRAM like design might also have
massive throughput advantages compared to commodity hardware operating
in a bus limited mode its hard to say until millions have been sunk in
trying to optimize it, but even if it does not— one of the arguments
made in asic-faq.pdf is because mining should be, in theory, nearly
perfect competition even the small advantage in costs from eliminating
unneeded peripherals can basically drive everyone without that
advantage out.

As an aside, there is an altcoin "boolberry" that implements something
where 2MB of data is extracted from the blockchain and then mined one.
But because the extraction is not in the inner-loop mining pools just
send it out to miners... and of course it could be uploaded to a
dedicated mining coprocessor (or FPGA, or GPU) if anyone ever got
around to doing the optimizations... it also has most of the other
issues I raised above relative to your proposal. It's still too new to
see what failure modes it suffers the most from first, and the
altcoins that it is mostly competing with suffer from their own ill
advised (_very slow_) POW.

> Apologies in advance if this is a stupid idea.

No need to be sorry— talking about these things is how people learn.
While I don't think this idea is good, and I'm even skeptical about
fixed versions— I promise you many other people were thinking similar
or even less useful things and will find the discussion interesting.

Re: [Bitcoin-development] ASIC-proof mining

[Andy Parkins]

On Friday 04 July 2014 04:37:26 Gregory Maxwell wrote:

[excellent explanation removed for brevity]

> > Apologies in advance if this is a stupid idea.
> 
> No need to be sorry— talking about these things is how people learn.
> While I don't think this idea is good, and I'm even skeptical about
> fixed versions— I promise you many other people were thinking similar
> or even less useful things and will find the discussion interesting.

Thank you for the very thorough and courteous response.  I'm sorry that I 
suggested something that had been thought of before (seems to be the case on 
every great idea I have for Bitcoin) and was not practical; but I'm glad to 
have had your response which was certainly educational for me.



Andy

-- 
Dr Andy Parkins
andyparkins@gmail.com

Re: [Bitcoin-development] ASIC-proof mining

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 921 bytes --]

Yup, no need to apologise. If nothing else the conversations get archived
where other people can use them to get up to speed faster. A lot of these
discussions get spread across forums, lists and IRC so it can be hard to
know what the current state of the art thinking is.

Recall the second prong of my opening argument - if you could beat ASICs,
you'd end up with botnets. I prefer having the chain be dominated by a
single pool for a while than having one with a major botnet presence, given
their history of doing things like mining empty blocks and giving random
people enormous electricity bills.

I think we can make good head way if we just optimise a lot and finish
things off, to be honest. I'm not sure we need an algorithmic silver
bullet. Remember you can always outsource mining by just not having any
hardware at all, CEX style, so trying to prevent outsourcing using clever
hacks seems ultimately doomed.

[-- Attachment #2: Type: text/html, Size: 1054 bytes --]

Re: [Bitcoin-development] ASIC-proof mining

[kjj]

Just some general comments on this topic/discussion.

I suspect that there exist no algorithms which cannot be done better in 
an application-specific device than in a general purpose computer.  And 
if there is such a thing, then it must necessarily perform best on one 
specific platform, making that platform the de facto application 
specific device.

I'm not sure how one would go about proving or disproving that, but it 
seems very likely to be true.

IO-bound is exactly the same as memory bound, for devices that have 
enough memory.  20 GB is already trivial today, and you don't really get 
into ask-the-wife-for-permission money until you cross 128 GB. The 
exception would be if the IO was to an oracle outside of the device's 
control, and artificially limited in throughput.  Such a centralized 
oracle would be contrary to the goals usually stated by people thinking 
about anti-ASIC designs, so there isn't much point.

Keeping the algorithm simple, and ASIC-easy, has one other advantage.  
Just about anyone can sit down and design an ASIC for SHA, for example, 
leading to diversity in the marketplace.  A harder algorithm can still 
be made into an ASIC (or more generally into an ASD), but will require 
more skilled designers, more expensive fabrication, etc.  This actually 
concentrates the ASIC advantage into the hands of fewer people, which 
again, is contrary to the stated goals.

Re: [Bitcoin-development] ASIC-proof mining

[Ron Elliott]

[-- Attachment #1: Type: text/plain, Size: 2213 bytes --]

I feel everyone should re-read that last paragraph as it carries the most
weight IMO.


On Fri, Jul 4, 2014 at 9:50 AM, kjj <bitcoin-devel@jerviss.org> wrote:

> Just some general comments on this topic/discussion.
>
> I suspect that there exist no algorithms which cannot be done better in
> an application-specific device than in a general purpose computer.  And
> if there is such a thing, then it must necessarily perform best on one
> specific platform, making that platform the de facto application
> specific device.
>
> I'm not sure how one would go about proving or disproving that, but it
> seems very likely to be true.
>
> IO-bound is exactly the same as memory bound, for devices that have
> enough memory.  20 GB is already trivial today, and you don't really get
> into ask-the-wife-for-permission money until you cross 128 GB. The
> exception would be if the IO was to an oracle outside of the device's
> control, and artificially limited in throughput.  Such a centralized
> oracle would be contrary to the goals usually stated by people thinking
> about anti-ASIC designs, so there isn't much point.
>
> Keeping the algorithm simple, and ASIC-easy, has one other advantage.
> Just about anyone can sit down and design an ASIC for SHA, for example,
> leading to diversity in the marketplace.  A harder algorithm can still
> be made into an ASIC (or more generally into an ASD), but will require
> more skilled designers, more expensive fabrication, etc.  This actually
> concentrates the ASIC advantage into the hands of fewer people, which
> again, is contrary to the stated goals.
>
>
> ------------------------------------------------------------------------------
> Open source business process management suite built on Java and Eclipse
> Turn processes into business applications with Bonita BPM Community Edition
> Quickly connect people, data, and systems into organized workflows
> Winner of BOSSIE, CODIE, OW2 and Gartner awards
> http://p.sf.net/sfu/Bonitasoft
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>



-- 
- Ron
end of line.

[-- Attachment #2: Type: text/html, Size: 3031 bytes --]

Re: [Bitcoin-development] ASIC-proof mining

[Aaron Voisine]

Agreed. If the POW is most efficient on general purpose CPUs, that
means Intel, AMD and maybe IBM would be the only entities capable of
producing competitive mining equipment.

Aaron


Aaron Voisine
breadwallet.com


On Fri, Jul 4, 2014 at 11:39 AM, Ron Elliott <ronaldbelliott@gmail.com> wrote:
> I feel everyone should re-read that last paragraph as it carries the most
> weight IMO.
>
>
> On Fri, Jul 4, 2014 at 9:50 AM, kjj <bitcoin-devel@jerviss.org> wrote:
>>
>> Just some general comments on this topic/discussion.
>>
>> I suspect that there exist no algorithms which cannot be done better in
>> an application-specific device than in a general purpose computer.  And
>> if there is such a thing, then it must necessarily perform best on one
>> specific platform, making that platform the de facto application
>> specific device.
>>
>> I'm not sure how one would go about proving or disproving that, but it
>> seems very likely to be true.
>>
>> IO-bound is exactly the same as memory bound, for devices that have
>> enough memory.  20 GB is already trivial today, and you don't really get
>> into ask-the-wife-for-permission money until you cross 128 GB. The
>> exception would be if the IO was to an oracle outside of the device's
>> control, and artificially limited in throughput.  Such a centralized
>> oracle would be contrary to the goals usually stated by people thinking
>> about anti-ASIC designs, so there isn't much point.
>>
>> Keeping the algorithm simple, and ASIC-easy, has one other advantage.
>> Just about anyone can sit down and design an ASIC for SHA, for example,
>> leading to diversity in the marketplace.  A harder algorithm can still
>> be made into an ASIC (or more generally into an ASD), but will require
>> more skilled designers, more expensive fabrication, etc.  This actually
>> concentrates the ASIC advantage into the hands of fewer people, which
>> again, is contrary to the stated goals.
>>
>>
>> ------------------------------------------------------------------------------
>> Open source business process management suite built on Java and Eclipse
>> Turn processes into business applications with Bonita BPM Community
>> Edition
>> Quickly connect people, data, and systems into organized workflows
>> Winner of BOSSIE, CODIE, OW2 and Gartner awards
>> http://p.sf.net/sfu/Bonitasoft
>> _______________________________________________
>> Bitcoin-development mailing list
>> Bitcoin-development@lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
>
>
>
> --
> - Ron
> end of line.
>
> ------------------------------------------------------------------------------
> Open source business process management suite built on Java and Eclipse
> Turn processes into business applications with Bonita BPM Community Edition
> Quickly connect people, data, and systems into organized workflows
> Winner of BOSSIE, CODIE, OW2 and Gartner awards
> http://p.sf.net/sfu/Bonitasoft
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

Re: [Bitcoin-development] ASIC-proof mining

[Jorge Timón]

On 7/4/14, kjj <bitcoin-devel@jerviss.org> wrote:
> I suspect that there exist no algorithms which cannot be done better in
> an application-specific device than in a general purpose computer.  And
> if there is such a thing, then it must necessarily perform best on one
> specific platform, making that platform the de facto application
> specific device.
>
> I'm not sure how one would go about proving or disproving that, but it
> seems very likely to be true.

I assumed this was obvious and self-evident for anyone who knows what
a Turing machine is, but judging from the number of smart people
wasting their time on the pursue of the "anti-ASIC" myth (also known
as pow wankery) it seems I was wrong.
Anything you can do with software you can do with hardware and
viceversa (you can even do it with ropes and fire in Minecraft!!)
Does this really need any proof?
I think it's the hard-pow cultists who have to provide a counterexample.

Very often you just need to query-replace "ASIC" with "specialized
hardware" to prove that what they're saying makes no sense.

> Keeping the algorithm simple, and ASIC-easy, has one other advantage.
> Just about anyone can sit down and design an ASIC for SHA, for example,
> leading to diversity in the marketplace.  A harder algorithm can still
> be made into an ASIC (or more generally into an ASD), but will require
> more skilled designers, more expensive fabrication, etc.  This actually
> concentrates the ASIC advantage into the hands of fewer people, which
> again, is contrary to the stated goals.

Yep, I think this is the strongest argument against "hard-pow".
But unfortunately you even find people that want "anti-ASIC without
being anti-GPU", which is funny because GPU just has Nvidia and AMD
and because unlike "anti-ASIC", anti-GPU is actually possible (despite
Litecoin's Scrypt having miserably failed on both accounts).

Interestingly enough, Greg Maxwell told me that the energetc advantage
of memory-hard pow ASICs is even greater than the advantage for SHA
ASICs.

Anyway, I'm working on a branch to encapsulate the proof of work that
should serve people to more easily experiment with alternate proofs on
top of bitcoind's code. I plan to use it for private chains ("proof of
signature" or "proof of script" if you prefer), and although it's not
ready yet, some people may be interested or may want to give some
feedback:

https://github.com/jtimon/bitcoin/tree/proof

I don't know if it will make it into master, but by specializing
ProofOfWork with TestnetProofOfWork we could remove
Params().AllowMinDifficultyBlocks() and its checks.

-- 
Jorge Timón

Re: [Bitcoin-development] ASIC-proof mining

[Luke Dashjr]

On Friday, July 04, 2014 8:21:42 PM Jorge Timón wrote:
> On 7/4/14, kjj <bitcoin-devel@jerviss.org> wrote:
> > I suspect that there exist no algorithms which cannot be done better in
> > an application-specific device than in a general purpose computer.  And
> > if there is such a thing, then it must necessarily perform best on one
> > specific platform, making that platform the de facto application
> > specific device.
> > 
> > I'm not sure how one would go about proving or disproving that, but it
> > seems very likely to be true.
> 
> I assumed this was obvious and self-evident for anyone who knows what
> a Turing machine is, but judging from the number of smart people
> wasting their time on the pursue of the "anti-ASIC" myth (also known
> as pow wankery) it seems I was wrong.
> Anything you can do with software you can do with hardware and
> viceversa (you can even do it with ropes and fire in Minecraft!!)
> Does this really need any proof?
> I think it's the hard-pow cultists who have to provide a counterexample.

Really, if people want to pursue a goal anything like this, they should be 
looking for "ASIC already widely owned" as the property rather than "anti-
ASIC". Thus, a sufficiently memory-hard PoW would really be "RAM is the ASIC". 
Whether it's possible to make this or not, is another question. And then we 
get back to "is is really a desirable property to have people capable of 
mining who have not given any indication of interest?"

Re: [Bitcoin-development] ASIC-proof mining

[Randi Joseph]

Hi All,

This is a bit tangential to the conversation, but since the genesis of 
this conversation is Mike's decentralization blog post, I decided to 
post here.

Perhaps the solution to the mining problem lies in the reward structure 
rather than in the proof of work/asics.

Is it possible instead to allocate a portion of the reward to " a # of 
runner up(s)" even though the runner-up(s) block will be orphaned? For 
example, X% of the block reward goes to Y number of runner-ups based on 
some type of criteria?

This will appear to be a bit like a tax on the winner, but it could 
potentially solve the problem, since a large pool would not want to 
split the pool up to solve multiple blocks.

There are some possible downsides, like probably having to keep those 
orphaned blocks around in the future, etc.

If this is possible, the question that remains then, what would be the 
criteria for the X% payout/allocation?

-Randi

Re: [Bitcoin-development] ASIC-proof mining

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 947 bytes --]

>
> Is it possible instead to allocate a portion of the reward to " a # of
> runner up(s)" even though the runner-up(s) block will be orphaned?
>

There's really no concept of a "runner up" because hashing is progress
free. It's unintuitive and often trips people up. There's no concept that
everyone is 95% of the way to finding a solution and then someone pips you
to the post. It's more like playing the lottery over and over again.
Doesn't matter how many times you did it before, the next time your chances
are the same.

A better concept is of rewarding "near miss" solutions which is what we
already do of course, via pools, which pay you for shares which don't quite
meet the difficulty target but almost do. So the question is how can we
implement pools which have this reward structure (which obviously works
well) without miners simultaneously giving up their right to block creation
either due to technical problems or sheer lazyness.

[-- Attachment #2: Type: text/html, Size: 1255 bytes --]

Re: [Bitcoin-development] ASIC-proof mining

[Randi Joseph]

[-- Attachment #1: Type: text/plain, Size: 1299 bytes --]

Thanks Mike.

Indeed, I am aware of current approach, which is why I was suggesting 
this as an alternative.
I haven't thought about it enough, and perhaps it was too radical a 
rethinking - just wanted to see what the smarter minds thought.

Thanks again.

-Randi

On 7/5/14, 4:43 AM, Mike Hearn wrote:
>
>     Is it possible instead to allocate a portion of the reward to " a # of
>     runner up(s)" even though the runner-up(s) block will be orphaned?
>
>
> There's really no concept of a "runner up" because hashing is progress 
> free. It's unintuitive and often trips people up. There's no concept 
> that everyone is 95% of the way to finding a solution and then someone 
> pips you to the post. It's more like playing the lottery over and over 
> again. Doesn't matter how many times you did it before, the next time 
> your chances are the same.
>
> A better concept is of rewarding "near miss" solutions which is what 
> we already do of course, via pools, which pay you for shares which 
> don't quite meet the difficulty target but almost do. So the question 
> is how can we implement pools which have this reward structure (which 
> obviously works well) without miners simultaneously giving up their 
> right to block creation either due to technical problems or sheer 
> lazyness.


[-- Attachment #2: Type: text/html, Size: 2329 bytes --]

Re: [Bitcoin-development] ASIC-proof mining

[Odinn Cyberguerrilla]

Just as an aside to this lengthy convo, the Cryptonote-based BCN recently
had some interesting updates which made it easier for ordinary computers
(nothing special) to handle it.

I realize that's not Bitcoin, but I thought I'd throw it out there.

> Thanks Mike.
>
> Indeed, I am aware of current approach, which is why I was suggesting
> this as an alternative.
> I haven't thought about it enough, and perhaps it was too radical a
> rethinking - just wanted to see what the smarter minds thought.
>
> Thanks again.
>
> -Randi
>
> On 7/5/14, 4:43 AM, Mike Hearn wrote:
>>
>>     Is it possible instead to allocate a portion of the reward to " a #
>> of
>>     runner up(s)" even though the runner-up(s) block will be orphaned?
>>
>>
>> There's really no concept of a "runner up" because hashing is progress
>> free. It's unintuitive and often trips people up. There's no concept
>> that everyone is 95% of the way to finding a solution and then someone
>> pips you to the post. It's more like playing the lottery over and over
>> again. Doesn't matter how many times you did it before, the next time
>> your chances are the same.
>>
>> A better concept is of rewarding "near miss" solutions which is what
>> we already do of course, via pools, which pay you for shares which
>> don't quite meet the difficulty target but almost do. So the question
>> is how can we implement pools which have this reward structure (which
>> obviously works well) without miners simultaneously giving up their
>> right to block creation either due to technical problems or sheer
>> lazyness.
>
> ------------------------------------------------------------------------------
> Open source business process management suite built on Java and Eclipse
> Turn processes into business applications with Bonita BPM Community
> Edition
> Quickly connect people, data, and systems into organized workflows
> Winner of BOSSIE, CODIE, OW2 and Gartner awards
> http://p.sf.net/sfu/Bonitasoft_______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>