Bitcoin Forum
January 22, 2020, 04:24:57 PM *
News: Latest Bitcoin Core release: 0.19.0.1 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1] 2 3 »  All
  Print  
Author Topic: [BBR] Boolberry Hash-on-blockchain discussion  (Read 6662 times)
crypto_zoidberg
Hero Member
*****
Offline Offline

Activity: 946
Merit: 559



View Profile WWW
April 29, 2014, 02:54:25 AM
Last edit: June 10, 2014, 02:42:58 PM by crypto_zoidberg
 #1

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.  Huh

Since cn_slow_hash created 2MB scratchpad, it's have to cover all this data, that's why they use 220 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:

Quote
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.

1579710297
Hero Member
*
Offline Offline

Posts: 1579710297

View Profile Personal Message (Offline)

Ignore
1579710297
Reply with quote  #2

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

Posts: 1579710297

View Profile Personal Message (Offline)

Ignore
1579710297
Reply with quote  #2

1579710297
Report to moderator
1579710297
Hero Member
*
Offline Offline

Posts: 1579710297

View Profile Personal Message (Offline)

Ignore
1579710297
Reply with quote  #2

1579710297
Report to moderator
1579710297
Hero Member
*
Offline Offline

Posts: 1579710297

View Profile Personal Message (Offline)

Ignore
1579710297
Reply with quote  #2

1579710297
Report to moderator
digicoin
Legendary
*
Offline Offline

Activity: 1106
Merit: 1000



View Profile
April 29, 2014, 03:10:26 AM
 #2

Adam Back raises a concern on the possibility to run a SPV client on CryptoNote blockchain. He does not find a way yet. Running a full node is not an option to mobile clients like iPad or Android client. Do you have any improvement on this issue?
digicoin
Legendary
*
Offline Offline

Activity: 1106
Merit: 1000



View Profile
April 29, 2014, 03:16:40 AM
 #3

Does keccak in use mean that the coin can be mined using GPU?
crypto_zoidberg
Hero Member
*****
Offline Offline

Activity: 946
Merit: 559



View Profile WWW
April 29, 2014, 04:13:26 AM
 #4

Adam Back raises a concern on the possibility to run a SPV client on CryptoNote blockchain. He does not find a way yet. Running a full node is not an option to mobile clients like iPad or Android client. Do you have any improvement on this issue?
If you don't want to mine on ipad or on android you do nod need to have a node on it - Cryptonote wallet is designed as separate process and can be connected theoretically to any daemon. (or to few daemons to be sure)

crypto_zoidberg
Hero Member
*****
Offline Offline

Activity: 946
Merit: 559



View Profile WWW
April 29, 2014, 04:14:52 AM
 #5

Does keccak in use mean that the coin can be mined using GPU?
Don't think so. Keccak is only a part of hash function.

axo
Full Member
***
Offline Offline

Activity: 131
Merit: 100


View Profile
April 29, 2014, 06:07:07 AM
 #6

Using the blockchain is a good idea to prevent gpu mining in the long term (when it cannot fit in the gpu memory) because the slow transfer speed from host memory to gpu memory.
I'm not sure it could be a problem for realizing an ASIC. In the pipeline there is a step that picks up relative small amount of data from big set of data and fills the relative small pipeline memory (actually 130k is not small but in the future it could be). This is a bottleneck but not so big as for GPUs.
The problem with ASIC is not only the bigger calculation power than cpu, but the better energy efficiency. The problem with ASIC remain if it is possible to realize an ASIC not faster than a cpu but that requires thousands times lesser energy.

An idea: what about using the selector hash to vary the instructions sequence of second hash? In that case the ASIC pipeline becomes inefficient and similar to cpu.
digicoin
Legendary
*
Offline Offline

Activity: 1106
Merit: 1000



View Profile
April 29, 2014, 06:29:58 AM
 #7

Adam Back raises a concern on the possibility to run a SPV client on CryptoNote blockchain. He does not find a way yet. Running a full node is not an option to mobile clients like iPad or Android client. Do you have any improvement on this issue?
If you don't want to mine on ipad or on android you do nod need to have a node on it - Cryptonote wallet is designed as separate process and can be connected theoretically to any daemon. (or to few daemons to be sure)

However, the wallet needs to operate on the whole blockchain if I understand correctly. Downloading and sync-ing the full blockchain is not easy on a mobile device
kalisto
Sr. Member
****
Offline Offline

Activity: 245
Merit: 250


View Profile
April 29, 2014, 11:55:50 AM
 #8

However, the wallet needs to operate on the whole blockchain if I understand correctly. Downloading and sync-ing the full blockchain is not easy on a mobile device

It needs the whole blockchain but it doesn't care if this is a remote blockchain like a bitcoinj implementation.
BitRock
Full Member
***
Offline Offline

Activity: 137
Merit: 100


View Profile
April 29, 2014, 04:11:40 PM
 #9

CPU coins are heaven of botnet. Does Blockchain-based hash or cryptoNote against botnet?
tromp
Hero Member
*****
Offline Offline

Activity: 627
Merit: 551


View Profile
April 29, 2014, 05:54:13 PM
 #10

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.

Shortcomings
1. H1, as well as final hash (keccak) have to be very fast, otherwise memory consuming accent will be slight. If H1 is slow than possible to implement some specific hardware working similar to Instruction pipeline
2. Despite the first, H1 have to have modern cpu instructions set - 64-bits numbers multiplication, AES/SSE instructions to make ASIC engineers bloody mad.

Wellcome to comment.

If you want to strengthen the ASIC resistance of CryptoNight and avoid the slowness of verification,
why not use an a-symmetric memory-bound proof-of-work like Momentum or my Cuckoo Cycle?
koop4u
Sr. Member
****
Offline Offline

Activity: 308
Merit: 250



View Profile
April 29, 2014, 06:03:09 PM
 #11


+1

tacotime
Legendary
*
Offline Offline

Activity: 1484
Merit: 1004



View Profile
April 29, 2014, 06:11:28 PM
 #12

This doesn't really prevent botnets... you can just torrent the blockchain and distribute it amongst all peers in the botnet.  Worse, it totally breaks any chance of having SPV clients in the future.

Code:
XMR: 44GBHzv6ZyQdJkjqZje6KLZ3xSyN1hBSFAnLP6EAqJtCRVzMzZmeXTC2AHKDS9aEDTRKmo6a6o9r9j86pYfhCWDkKjbtcns
crypto_zoidberg
Hero Member
*****
Offline Offline

Activity: 946
Merit: 559



View Profile WWW
April 29, 2014, 10:41:48 PM
 #13

Using the blockchain is a good idea to prevent gpu mining in the long term (when it cannot fit in the gpu memory) because the slow transfer speed from host memory to gpu memory.
I'm not sure it could be a problem for realizing an ASIC. In the pipeline there is a step that picks up relative small amount of data from big set of data and fills the relative small pipeline memory (actually 130k is not small but in the future it could be). This is a bottleneck but not so big as for GPUs.
The problem with ASIC is not only the bigger calculation power than cpu, but the better energy efficiency. The problem with ASIC remain if it is possible to realize an ASIC not faster than a cpu but that requires thousands times lesser energy.

An idea: what about using the selector hash to vary the instructions sequence of second hash? In that case the ASIC pipeline becomes inefficient and similar to cpu.
mmm...do you mean some kind of polymorphic hash?...

crypto_zoidberg
Hero Member
*****
Offline Offline

Activity: 946
Merit: 559



View Profile WWW
April 29, 2014, 10:55:47 PM
 #14

However, the wallet needs to operate on the whole blockchain if I understand correctly. Downloading and sync-ing the full blockchain is not easy on a mobile device
Not really. When you creates a new wallet you don't need to read all blockchain that have been before, obviously there are can't be a transactions to this address you just created. (and wallet keys file actually keeps creation timestamp inside). You only need a chain of block hashes, that can be fetched very fast(Wallet data file keeps hashes chain to be able detect and handle splits in daemon). So it can be easily implemented in mobile device. Even for bytecoin huge blockchain the hashes in new just created and synchronized wallet takes about 18MB, and it can be reduced without big effort.

tacotime
Legendary
*
Offline Offline

Activity: 1484
Merit: 1004



View Profile
April 29, 2014, 10:59:38 PM
 #15

However, the wallet needs to operate on the whole blockchain if I understand correctly. Downloading and sync-ing the full blockchain is not easy on a mobile device
Not really. When you creates a new wallet you don't need to read all blockchain that have been before, obviously there are can't be a transactions to this address you just created. (and wallet keys file actually keeps creation timestamp inside). You only need a chain of block hashes, that can be fetched very fast(Wallet data file keeps hashes chain to be able detect and handle splits in daemon). So it can be easily implemented in mobile device. Even for bytecoin huge blockchain the hashes in new just created and synchronized wallet takes about 18MB, and it can be reduced without big effort.

Ah... I guess if you only use header data it's not much of an issue for an SPV client, but then I'm not sure if this affords additional security to the hash function.

Code:
XMR: 44GBHzv6ZyQdJkjqZje6KLZ3xSyN1hBSFAnLP6EAqJtCRVzMzZmeXTC2AHKDS9aEDTRKmo6a6o9r9j86pYfhCWDkKjbtcns
crypto_zoidberg
Hero Member
*****
Offline Offline

Activity: 946
Merit: 559



View Profile WWW
April 29, 2014, 11:05:13 PM
 #16

CPU coins are heaven of botnet. Does Blockchain-based hash or cryptoNote against botnet?

WE ARE AGAINST ANY KIND OF CRIMINAL.

Probably in future, when blockchain will not fit in a memory of a typical workstation with 4GB RAM it may became not effective to mine with botnets. But not sure about this.
Anyway, it can be said for any ASIC-resistent project, isn't it?  

crypto_zoidberg
Hero Member
*****
Offline Offline

Activity: 946
Merit: 559



View Profile WWW
April 29, 2014, 11:18:37 PM
 #17

If you want to strengthen the ASIC resistance of CryptoNight and avoid the slowness of verification,
why not use an a-symmetric memory-bound proof-of-work like Momentum or my Cuckoo Cycle?
Thank you for suggestion, will look at this. How long it do one check in microseconds?

crypto_zoidberg
Hero Member
*****
Offline Offline

Activity: 946
Merit: 559



View Profile WWW
April 29, 2014, 11:23:10 PM
 #18

This doesn't really prevent botnets... you can just torrent the blockchain and distribute it amongst all peers in the botnet.  Worse, it totally breaks any chance of having SPV clients in the future.
Not agree about SPV clients. I've posted before in this thread: https://bitcointalk.org/index.php?topic=588421.msg6464526#msg6464526

smooth
Legendary
*
Offline Offline

Activity: 2366
Merit: 1142



View Profile
April 29, 2014, 11:38:58 PM
 #19

CPU coins are heaven of botnet. Does Blockchain-based hash or cryptoNote against botnet?

Botnets mining (which is stupid for them) is a good thing longer term. Not something to be worried about. This is obvious to anyone who thinks through the economic and game theory aspects of it.

tromp
Hero Member
*****
Offline Offline

Activity: 627
Merit: 551


View Profile
April 29, 2014, 11:45:56 PM
 #20

If you want to strengthen the ASIC resistance of CryptoNight and avoid the slowness of verification,
why not use an a-symmetric memory-bound proof-of-work like Momentum or my Cuckoo Cycle?
Thank you for suggestion, will look at this. How long it do one check in microseconds?

42x2 siphashes and 2 sha256 hashes can't take more than a few microsecs...
Pages: [1] 2 3 »  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!