Topic: [BBR] Boolberry Hash-on-blockchain discussion (Read 6869 times)

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://bitcointalksearch.org/topic/bbr-boolberry-privacy-and-security-guaranteed-since-2014-577267

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:


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.

Have you got a chance to optimize the miner?

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  

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

EDIT: div cycle count on Sandy Bridge depends on divisor, bigger divisors take more time (latency: 30-94 cycles). As a comparison, L2 cache minimum latency is 11 cycles.

The block chain is tiny right? Probably all in near cache

now when mining in testnet, currency::get_blob_longhash takes 75% of CPU time, and 75% of CPU time in that function is spent in doing div instructions due to size() and operator[], not quite memory-hard

I feel that i need to have more clear description.
Each block's entry in scratchpad is not depends of number of transactions included in it.
It is fixed to about 320 bytes and use prev_id, merkle root, onetime coinbase  key, and hashed coinbase outs (usually 8 ).

Now lets imagine - just for a short time - this currency will be really successful. The blockchain of bitcoin grows faster thean linear in time, it does make sense to assume a slow exponential growth for a successful altcoin too.


Now lets just assume you hit a 40 G blockchain in 3 years. Are you sure there are enough nodes left with 64 GB Ram? What about the distribution of this kind of workstations?

Compare memory read/written per second by the hash to memmove() speed. What do you get?

Does each round of keccak read from different areas of scratchpad?

Memorycoin failed on the 2 first point (I don't know about the last). It was AES-NI instruction only, if you didn't have a recent CPU, you were very slow or it didn't work.
It was supposed to rely on RAM amount to counter bot farming but it didn't.
I think it is a great to be memory dependent.

What do you think about a minimum memory amount to mine ?

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.

1. Wide CPU instruction set
2. Memory-oriented algo
3. Small work time.

We are looking for a way to be memory hard (at mining) on the one hand, on the other to use wider cpu instruction set (if possible). In our opinion it make sense in ASIC protection. Please correct me if i wrong.

Is it possible to extend daemond to return full list of block header hashes instead of the full blockchain? What is the security implications of this approach? E.x: a malicious/compromised node can response with purposefully modified hash list?

I believe that this coin can take CryptoNote as its core technology but it must separate itself from Bytecoin to make room for improvement. At least for the middle term.