Bitcoin Forum
April 19, 2014, 10:08:34 PM *
News: Due to the OpenSSL heartbleed bug, changing your forum password is recommended.
 
   Home   Help Search Donate Login Register  
Pages: 1 2 [3] 4  All
  Print  
Author Topic: defending ahead the p2p nature of bitcoin - blending hashcash & scrypt  (Read 6248 times)
mmeijeri
Sr. Member
****
Online Online

Activity: 336

Martijn Meijering


View Profile

Ignore
May 23, 2013, 09:03:38 PM
 #41

@Adam:

Would it be possible to use some well-known NP-complete problem (take your pick) for proof of work? Say we hash the transactions, the hash of the previous block etc and derive a random graph for which we solve the travelling saleman problem? The difficulty would be translated to the size of the random graph. Wouldn't this push decision power all the way back to CPUs and the individuals owning them?

Bitcoin may be doomed without Ripple or something like it.
1397945314
Hero Member
*
Offline Offline

Posts: 1397945314

View Profile Personal Message (Offline)

Ignore
1397945314
Reply with quote  #2

1397945314
Report to moderator
1397945314
Hero Member
*
Offline Offline

Posts: 1397945314

View Profile Personal Message (Offline)

Ignore
1397945314
Reply with quote  #2

1397945314
Report to moderator
Buy a Blade, Get a 5-Chip Free!
Start Mining with GAWMiners.com
24/7 Live Phone & Tech Support
Free Hosting & Electricity for 1 Year!

Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1397945314
Hero Member
*
Offline Offline

Posts: 1397945314

View Profile Personal Message (Offline)

Ignore
1397945314
Reply with quote  #2

1397945314
Report to moderator
1397945314
Hero Member
*
Offline Offline

Posts: 1397945314

View Profile Personal Message (Offline)

Ignore
1397945314
Reply with quote  #2

1397945314
Report to moderator
1397945314
Hero Member
*
Offline Offline

Posts: 1397945314

View Profile Personal Message (Offline)

Ignore
1397945314
Reply with quote  #2

1397945314
Report to moderator
1397945314
Hero Member
*
Offline Offline

Posts: 1397945314

View Profile Personal Message (Offline)

Ignore
1397945314
Reply with quote  #2

1397945314
Report to moderator
gglon
Jr. Member
*
Offline Offline

Activity: 59


View Profile

Ignore
May 23, 2013, 11:40:34 PM
 #42

Solution to TSP is not easily verifiable - you need to do all the work yourself to verify answer.
mmeijeri
Sr. Member
****
Online Online

Activity: 336

Martijn Meijering


View Profile

Ignore
May 24, 2013, 07:23:26 AM
 #43

You only have to do a polynomial amount of work to verify the answer, with difficulty N being adjustable.

Bitcoin may be doomed without Ripple or something like it.
mmeijeri
Sr. Member
****
Online Online

Activity: 336

Martijn Meijering


View Profile

Ignore
May 24, 2013, 07:35:12 AM
 #44

Maybe the boolean satisfiability problem would be a better choice though.

Bitcoin may be doomed without Ripple or something like it.
malditonuke
Full Member
***
Offline Offline

Activity: 145


View Profile

Ignore
May 24, 2013, 07:38:41 AM
 #45


I am anti-fork as bad for mindshare, confidence and dilutive of bitcoin and crypto currency value aggregate.


Awwww man  Cry

Seriously though, with all due respect (and with admittance of my conflict of interest here) - alt-coins (or rather, truly innovative alt-coins as opposed to one-two tweak clones) are useful.

They prevent monoculture.

If anything, we need more altcoins pursuing different niches (I feel that there are market niches which BTC, contrary to popular belief, fills imperfectly, allowing for an alt to take that niche without affecting mainstream btc adoption - but that's a long and boring story)

1. Alt-coins
2. Crypto-currency exchange
3. Currency basket

A user can hold bitcoin, litecoin and whatever-coin using any ratio that they deem fit.
mmeijeri
Sr. Member
****
Online Online

Activity: 336

Martijn Meijering


View Profile

Ignore
May 24, 2013, 07:55:42 AM
 #46

Come to think of it, boolean satisfiability isn't such a good choice after all. Hmm. Maybe NP-complete isn't such a good criterion.

Bitcoin may be doomed without Ripple or something like it.
adam3us
Full Member
***
expert
Offline Offline

Activity: 238


in bitcoin we trust


View Profile WWW

Ignore
May 24, 2013, 08:47:37 PM
 #47

Come to think of it, boolean satisfiability isn't such a good choice after all. Hmm. Maybe NP-complete isn't such a good criterion.

I think one could make a mining function which was fairly hard to gain an advantage with using ASICs.  But I do think you have to target GPUs because a GPU is basically a better CPU.  The CPU has a lot of resources dedicated to optimizing the single thread execution speed (eg super scalarity, out-of-order execution etc).  Alternatively GPUs dont have that.  A 7970 has basically a 2048 RISC cores.  So I think you want to optimize for the characteristics of the GPU.  Memory line size, cache architecture, instruction set.  Make all of those things work hard, and dynamically, but in proportion to the resources the GPU has.  eg some integer instructions, some FP instructions, some memory.

Then a would be ASIC miner has to make a better GPU.  AMD is putting quite a lot of resources into that.

Also I think we could have automatically balanced algorithm mining, including mining parameters.  So the idea is anyone can introduce a new algorithm or new set of algorithm parameters.  Presumably with some public review process so that there is no trapdoor known only to the introducer.  Then each algorithm has a floating separate difficulty set by the network.  The difficulty inflation is set so that the algorithm which appears last susceptible empirically to inflation is he inflation target.  Other algorithms have their difficulty adjusted so that their inflation matches the minimum inflation algorithm.  So eg if SHA256 hashcash mining has a big batch of new fast ASICs come online, to the extent that difficulty gets much harder quickly, the difficulty is increased faster yet so that the proportion of coins producible with SHA256 mining falls and the other mining functions rise.

Adam

hashcash, committed transactions, homomorphic values, blind kdf; researching decentralization, scalability and fungibility/anonymity
mmeijeri
Sr. Member
****
Online Online

Activity: 336

Martijn Meijering


View Profile

Ignore
May 29, 2013, 07:41:27 PM
 #48

Just found this interesting video of the Bitcoin conference:

Dan Kaminsky Predicts The End Of The Current Proof-Of-Work Function

Bitcoin may be doomed without Ripple or something like it.
mmeijeri
Sr. Member
****
Online Online

Activity: 336

Martijn Meijering


View Profile

Ignore
May 29, 2013, 07:44:30 PM
 #49

I think one could make a mining function which was fairly hard to gain an advantage with using ASICs.  But I do think you have to target GPUs because a GPU is basically a better CPU.

GPUs wouldn't necessarily bad, because they are consumer hardware with a primary purpose other than mining, and therefore impossible to suppress. But it would be nice if CPUs were still competitive, because the hardcore gamer community too is a very unrepresentative cross-section of society. But because there are so many CPUs, they might collectively still wield considerable influence even if there is a factor of ten performance difference.

Bitcoin may be doomed without Ripple or something like it.
Shevek
Sr. Member
****
Offline Offline

Activity: 252



View Profile

Ignore
May 29, 2013, 09:02:05 PM
 #50

Just found this interesting video of the Bitcoin conference:

Dan Kaminsky Predicts The End Of The Current Proof-Of-Work Function

Actual ASIC-miners will not allow this change. And the have more votes (=hashpower) than anybody.

It's enough for them to reject the blocks with new PoW algorithm.

Proposals for improving bitcoin are like asses: everybody has one
1SheveKuPHpzpLqSvPSavik9wnC51voBa
adam3us
Full Member
***
expert
Offline Offline

Activity: 238


in bitcoin we trust


View Profile WWW

Ignore
May 29, 2013, 09:22:14 PM
 #51

Just found this interesting video of the Bitcoin conference:

Dan Kaminsky Predicts The End Of The Current Proof-Of-Work Function

Actual ASIC-miners will not allow this change. And the have more votes (=hashpower) than anybody.

It's enough for them to reject the blocks with new PoW algorithm.

I am not sure the ASICs actually have any protocol choice power.  If bitcoin main developer branch for some reason decided to phase in a new mining algorithm, the choice is actually the users.  If the users agree, they will keep on the main branch and accept the algorithm phase in.  If they dont someone forks the code, and the users migrate over to a new fork.

If there was a code fork like that where both forks accepted the existing coins created up to the fork date as valid, that might be kind of strange sort of like an alt-coin that accepts bticoins up to a hard-fork point in time.

Adam

hashcash, committed transactions, homomorphic values, blind kdf; researching decentralization, scalability and fungibility/anonymity
kodo
Jr. Member
*
Offline Offline

Activity: 42



View Profile

Ignore
May 29, 2013, 10:12:44 PM
 #52

Wow very interesting stuff in this thread, thanks!

Just A Guy Interested In Bitcoins
adam3us
Full Member
***
expert
Offline Offline

Activity: 238


in bitcoin we trust


View Profile WWW

Ignore
May 30, 2013, 09:05:50 AM
 #53

I think one could make a mining function which was fairly hard to gain an advantage with using ASICs.  But I do think you have to target GPUs because a GPU is basically a better CPU.

GPUs wouldn't necessarily bad, because they are consumer hardware with a primary purpose other than mining, and therefore impossible to suppress. But it would be nice if CPUs were still competitive, because the hardcore gamer community too is a very unrepresentative cross-section of society. But because there are so many CPUs, they might collectively still wield considerable influence even if there is a factor of ten performance difference.

I can see the attraction of CPUs however if you optimized for the CPU to the detriment of the GPU, that leaks possible advantages to ASICs over GPUs.  I think about all you can say that a CPU has is faster single core performance (irrelevant for mining: more compute bandwidth is more important than per core speed).  And main memory readable over a narrow bus (DDR3 64-bit vs DDR5 over 384-bit).  GDDR5 in an AMD 7970 is quad-pumped at 1500MT with 384-bit data bus where as DDR3 is dual-pumped a 1333MT or 1600MT etc similar speed.  So if you are reading random chunks in CPU friendly 64-bit chunks the GPU ram is still 2x speed (quad vs dual pump) even though its 6x bus-width advantage is wasted for random access.  However i7s have two memory channels so they match the GPU for 64-bit reads.  Some CPUs eg 3930k have quad channels so they can do 2x that and beat a GPU.  i7 3930k rated at 51.2GB/sec memory, regular i7 at 25.6GB/sec bandwidth, amd 7970 rated at 288GB/sec but in terms of ability to read 64-bit chunks the 7970 would do 6x less = 48GB/sec.

However the peak figures are in sequential read, DDR3 and GDDR5 are both slower with random reads.  And thrashing RAM with reads for data intentionally too big to fit in L3 is going to bog your computer down for normal use.

Adam

hashcash, committed transactions, homomorphic values, blind kdf; researching decentralization, scalability and fungibility/anonymity
adam3us
Full Member
***
expert
Offline Offline

Activity: 238


in bitcoin we trust


View Profile WWW

Ignore
May 30, 2013, 09:56:33 AM
 #54

I can see the attraction of CPUs however if you optimized for the CPU to the detriment of the GPU, that leaks possible advantages to ASICs over GPUs.  I think about all you can say that a CPU has is faster single core performance (irrelevant for mining: more compute bandwidth is more important than per core speed).  And main memory readable over a narrow bus (DDR3 64-bit vs DDR5 over 384-bit).

Another thing CPU cores have going for them over GPU is they are independent.  AMD GPU cores are in SIMD groups, eg 7970 has 2048 cores, but groups of 16 of them have to execute the same instruction each clock on different data, that means if you force them to do dynamic work, there are only really 128 cores that can do independent dynamic work.  And the cores are about 32x slower than a CPU core.  So then a four core CPU matches a GPU for dynamic workloads.

However again that is not a good ASIC-hard direction because the SIMD nature of AMD GPUs is overcomeable eg http://www.adapteva.com with a MIMD (ie no SIMD restrictions) 28nm 64 core risc CPU and plans for 1024 even 4096 risc cores per chip.  And they are low energy too.

Adam

hashcash, committed transactions, homomorphic values, blind kdf; researching decentralization, scalability and fungibility/anonymity
mmeijeri
Sr. Member
****
Online Online

Activity: 336

Martijn Meijering


View Profile

Ignore
June 14, 2013, 01:16:20 PM
 #55

In addition to using memory-hard hashing algorithms, would it be useful to investigate choosing a hashing function that requires the hashing core to be of similar complexity as a typical CPU execution unit? I'm thinking of something that uses multiplication, division and modular reduction relative to some large prime number, and elliptic curve group operations rather than the typical rotate, xor and addition modulo 2^n operations. If necessary we could always xor the result with an ordinary SHA256 hash.

Bitcoin may be doomed without Ripple or something like it.
bluemeanie1
Full Member
***
Online Online

Activity: 168


http://ALTCHAIN.ORG


View Profile WWW

Ignore
June 15, 2013, 01:06:46 AM
 #56


 the solution is to remove mining altogether:  https://docs.google.com/file/d/0BwUFHE6KYsM0ZkxLVmFwbXQ3ck0/edit?usp=sharing

PRESENTING... ALTCHAIN.ORG   
mmeijeri
Sr. Member
****
Online Online

Activity: 336

Martijn Meijering


View Profile

Ignore
June 15, 2013, 08:36:58 PM
 #57

However again that is not a good ASIC-hard direction because the SIMD nature of AMD GPUs is overcomeable eg http://www.adapteva.com with a MIMD (ie no SIMD restrictions) 28nm 64 core risc CPU and plans for 1024 even 4096 risc cores per chip.  And they are low energy too.

On the up side, they are still general purpose hardware. It might be good to have a set of algorithms, so that each class of PoW hardware has at least one it excels at.

Bitcoin may be doomed without Ripple or something like it.
Wolf0
Sr. Member
****
Offline Offline

Activity: 448


View Profile

Ignore
June 17, 2013, 07:08:49 AM
 #58

I agree with this. Mining power is already being concentrated into fewer and fewer hands, and I do believe it will get worse as time goes on. Perhaps scrypt with different parameters should be used, though, to make it more memory hard?

BTC.sx - For an easy way to trade Bitcoin, using Bitcoin.
Buy cheap GPUs with GPU Coin
Win a video card! - Drawing/Contest
oatmo
Member
**
Offline Offline

Activity: 104


View Profile

Ignore
June 17, 2013, 10:22:35 PM
 #59

Very interesting thread.

My background is 20 years of designing CPUs/ASICs/GPUs.

A few comments here:

1) There is no computational problem that you can't design custom ASIC hardware to do faster than a GPU. The extent faster is a function of the types of operations used. If you use multiply and divide, the advantage will be less. Using AND/OR/XOR logical functions makes the advantage more. ASICs will always kill the CPU in control, because general purpose code runs tons of instructions for control flow, these all make a few small gates in HW. The more complicated the decisions, in general custom HW will have a bigger advantage.

2) The way to limit ASICs is to have huge memory requirements. This essentially limits all the options at the memory controller. GPUs kill on these APPs because they are optimized around 2 things (1) massive memory bandwidth, and (2) massive numbers of threads. Basically the GPU wants to run 10000 threads at once, and assumes that every memory access is going to miss and go to memory. They are optimized around using all the parallel HW in the GPU. The one thing they suck at is memory latency, so they hide that with large numbers of threads. scrypt is essentially a large memory algorithm, which makes it difficult for ASICs. You can build large memories onto ASICs, but the cost will be probilitively large unless you can run millions of units.

Thinking out load here, the only way that I think you could design an algorithm where it wouldn't be preferred to use GPUs or ASICs, you would need something which has a lot of decisions, large memory, and chaining in the algorithm (scrypt has all these things, but some sort of chaining nonce-nonce, which is really against how the crypto currencies work).

I think a full ASIC implementation will have a unit cost which is much higher than the SHA algorithm in bitcoin, but would still produce an order of magnitude performance improvement over CPUs, but I'm not sure how much better than GPUs. In the end, if it's profitable to do so, people will design custom HW for these tasks. Right now, it doesn't look likely at litecoin's current price, but everything could change. I think if something happened to the bitcoin viability (like corporations coopting it or something like that), then people will switch to litecoin, and then it will be much more profitable.

Oatmo
mmeijeri
Sr. Member
****
Online Online

Activity: 336

Martijn Meijering


View Profile

Ignore
June 17, 2013, 10:26:05 PM
 #60

It's not necessary to prevent ASICs from doing the PoW faster than CPUs / GPUs, just to make sure they don't have more power than the huge installed based of computers bought for other purposes.

Bitcoin may be doomed without Ripple or something like it.
Pages: 1 2 [3] 4  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!