[BBR] Boolberry Hash-on-blockchain discussion

[otila]

You have smoke for write algo hash or I did not understand ?

Talking to me?
I don't understand you 

[BitRock]

seems this miner stuff is obfuscated on purpose, dev is probably running 10x faster miner himself..
but I have two days to make a faster version  

Code:

#0  std::vector<crypto::hash, std::allocator<crypto::hash> >::operator[] (this=0x7f837d3fb950, __n=12302) at /usr/include/c++/4.9.0/bits/stl_vector.h:780
#1  0x0000000000c4e75c in currency::miner::<lambda(uint64_t)>::operator()(uint64_t) const (__closure=0x7f837d3fb4e0, index=9325784170990468272)
    at /c/boolberry/src/currency_core/miner.cpp:365
#2  0x0000000000c4f912 in currency::<lambda(uint64_t (&)[25], uint64_t (&)[24])>::operator()(crypto::state_t_m &, crypto::mixin_t &) const (__closure=0x7f837d3fb200, st=..., 
    mix=...) at /c/boolberry/src/currency_core/currency_format_utils.h:189
#3  0x0000000000c4fdab in crypto::wild_keccak<crypto::mul_f, currency::get_blob_longhash(const blobdata&, crypto::hash&, uint64_t, callback_t) [with callback_t = currency::miner::worker_thread()::<lambda(uint64_t)>; currency::blobdata = std::basic_string<char>; uint64_t = long unsigned int]::<lambda(uint64_t (&)[25], uint64_t (&)[24])> >(const uint8_t *, size_t, uint8_t *, size_t, currency::<lambda(uint64_t (&)[25], uint64_t (&)[24])>) (
    in=0x7f837d3fb540 "\366+\307\351\330\b3pQ\264\067\061ǭVjf1\034s \237\224\233\327\016\226-\332xko", inlen=33, 
    md=0x7f837d3fb540 "\366+\307\351\330\b3pQ\264\067\061ǭVjf1\034s \237\224\233\327\016\226-\332xko", mdlen=32, cb=...) at /c/boolberry/src/crypto/wild_keccak.h:134
#4  0x0000000000c4fb09 in crypto::wild_keccak_dbl<crypto::mul_f, currency::get_blob_longhash(const blobdata&, crypto::hash&, uint64_t, callback_t) [with callback_t = currency::miner::worker_thread()::<lambda(uint64_t)>; currency::blobdata = std::basic_string<char>; uint64_t = long unsigned int]::<lambda(uint64_t (&)[25], uint64_t (&)[24])> >(const uint8_t *, size_t, uint8_t *, size_t, currency::<lambda(uint64_t (&)[25], uint64_t (&)[24])>) (
    in=0x7f8381dba098 "\001-\261FVm\345O\330\061\021\237\257\210\200\204\364=\374\243\031.\023\254\350\233O\372\373\262\032~łz$i", inlen=76, 
    md=0x7f837d3fb540 "\366+\307\351\330\b3pQ\264\067\061ǭVjf1\034s \237\224\233\327\016\226-\332xko", mdlen=32, cb=...) at /c/boolberry/src/crypto/wild_keccak.h:151
#5  0x0000000000c4fa8d in currency::get_blob_longhash<currency::miner::worker_thread()::<lambda(uint64_t)> >(const currency::blobdata &, crypto::hash &, uint64_t, currency::miner::<lambda(uint64_t)>) (
    bd="\001-\261FVm\345O\330\061\021\237\257\210\200\204\364=\374\243\031.\023\254\350\233O\372\373\262\032~łz$i\000\216\353қ\005QJ\034k0\023pq\024y\\\356\031\343\376\376\342\366\250{\340\327\363\344RSn\002c\f\277\236\001", res=..., height=2056, accessor=...) at /c/boolberry/src/currency_core/currency_format_utils.h:179
#6  0x0000000000c4ec65 in currency::miner::worker_thread (this=0x7fff82e7fdd8) at /c/boolberry/src/currency_core/miner.cpp:366

Have you got a chance to optimize the miner?

[otila]

Have you got a chance to optimize the miner?

Not much to do, since PoW still uses % operation (and gcc generates four div instructions in that function because there's also some array indexing), and I didn't figure out the C++ code with splattered-around lambda functions, callbacks and recursive macros.  And then summer came in Finland and I have been out more 
Hash rate could be two times faster if I figure out what the code does and can do with less div operations.  (I have been programming in C for 20 years, maybe I should learn more C++..)

However, I replaced the keccak function with a faster one, but it does not help much, because much of the CPU time is spent in  div operations.

[doldgigger]

Let's open hash-function discussion friends.
Just want to uncover our approach and show differences with CryptoNote that we use in our project announced here: https://bitcointalk.org/index.php?topic=577267.0

First of all I want to say that CryptoNote hash function (so called cn_slow_hash) is actually a very strong protected from ASIC's with different CPU instructions set as well as memory consuming algo. cn_slow_hash works hard on 2MB scratchpad and most of this scratchpad are fits in CPU cache.

For now it is difficult imagine that will be possible to make some specific hardware which will be more effective than CPU and will coast less than CPU. But world changes so fast, nobody knows what will happen in near future. We've all seen how rapid technological breakthroughs capable of performing the computer industry.  

Since cn_slow_hash created 2MB scratchpad, it's have to cover all this data, that's why they use 2²⁰ iterations, and side-effect from this pretty slow work (about 500ms on normal laptop, twice faster on normal pc with suitable cpu cache). It may slow down synchronisation process at downloading blockchain (that is not a big problem) and theoretically it may be possible to attack network - connect and send a random block to make peer calculate slow_hash for useless fake block.

So, putting all together, we want to have:
1. Wide CPU instruction set
2. Memory-oriented algo
3. Small work time.

Realizing it, we've  tried to take a step to the side.

Idea of using blockchain data as scratchpad resulted in this hash function:



Actually this is a keccak hybrid, which use external scratchpad. After each keccack round, psudo-randomly addressed[state vector used as addresses] data is taken from scratchpad and xored with state.
Calculating each block PoW usualy hits about 1100 randomly addressed reading of blocks by 32 bytes.

I used "performance_tests" with different scratchpad size to find out memory hardness:

Warm up: 2161 ms
test_wild_keccak<400> - OK:
  loop count:    100000
  elapsed:       3020 ms
  time per call: 0 ms/call

Warm up: 2158 ms
test_wild_keccak<40000> - OK:
  loop count:    100000
  elapsed:       3060 ms
  time per call: 0 ms/call

Warm up: 2168 ms
test_wild_keccak<4000000> - OK:
  loop count:    100000
  elapsed:       3484 ms
  time per call: 0 ms/call

Warm up: 2156 ms
test_wild_keccak<40000000> - OK:
  loop count:    100000
  elapsed:       8119 ms
  time per call: 0 ms/call

Warm up: 2150 ms
test_wild_keccak<100000000> - OK:
  loop count:    100000
  elapsed:       8574 ms
  time per call: 0 ms/call

As you can see, working on small amount of memory 100000 hash operations takes 3020 ms, meanwhile work on 100Mb scratchpad with the same operations count takes 8574 ms.
Such difference(caused by the cache memory overflow) points to real memory hardness we guess.

Wellcome to comment.

Do you have some cryptography-based rationale on the "wild keccak" approach?

[funnyman21]

Are there any other coins that have copied this hash function yet?