Bitcoin Forum
September 20, 2019, 09:17:01 PM *
News: If you like a topic and you see an orange "bump" link, click it. More info.
 
   Home   Help Search Login Register More  
Pages: [1] 2 »  All
  Print  
Author Topic: I found a way to implement real asic-resistant POW algorithm  (Read 649 times)
lichuan
Newbie
*
Offline Offline

Activity: 126
Merit: 0


View Profile
June 01, 2018, 03:46:00 AM
Last edit: June 01, 2018, 06:55:20 AM by lichuan
 #1

Hi, everyone
    As we know, the mining process is like this:
Code:
while(hash_value > target)
{
    nonce = new_nonce()
    hash_value = sha256d(utc + version + pre_block_hash + nonce + miner_pubkey + merkle_root + something else)
}
   the ASIC's advantage over GPU or CPU is that ASIC can run sha256d more times under the same time condition, so in the loop, we can combine sha256 with a lot of memory access to resist ASIC, because ASIC is good at sha256 computation but not memory access, as following:
Code:
while(hash_value > target)
{
    nonce = new_nonce()
    memory_access_result = access_memory_process(utc + version + pre_block_hash + nonce + miner_pubkey + merkle_root + something else)
    hash_value = sha256d(utc + version + pre_block_hash + nonce + miner_pubkey + merkle_root + memory_access_result + something else)
}

    In my own askcoin projcect (www.askcoin.me), we name this asic-resistant sha256 algorithm as "SHA256-AR", the verify-hash code is something like this:
Code:
bool Blockchain::hash_pow(char hash_arr[32], uint32 zero_bits)
{
    uint32 zero_char_num = zero_bits / 8;

    for(uint32 i = 0; i < zero_char_num; ++i)
    {
        if(hash_arr[i] != 0)
        {
            return false;
        }
    }
    
    uint32 zero_remain_bit = zero_bits % 8;

    if(zero_remain_bit == 0)
    {
        return true;
    }
    
    return hash_arr[zero_char_num] < 1 << 8 - zero_remain_bit;
}

bool Blockchain::verify_hash(std::string block_hash, std::string block_data, uint32 zero_bits)
{
    char hash_raw[32];
    uint32 len = fly::base::base64_decode(block_hash.c_str(), block_hash.length(), hash_raw, 32);

    if(len != 32)
    {
        return false;
    }
    
    uint32 buf[16] = {0};
    char *p = (char*)buf;
    coin_hash(block_data.c_str(), block_data.length(), p);
    block_data += "another_32_bytes";
    coin_hash(block_data.c_str(), block_data.length(), p + 32);
    uint32 arr_16[16] = {0};
    
    for(uint32 i = 0; i < 16; ++i)
    {
        arr_16[i] = ntohl(buf[i]);
    }

    for(uint32 i = 0; i < ASIC_RESISTANT_DATA_NUM;)
    {
        for(int j = 0; j < 16; ++j)
        {
            arr_16[j] = (arr_16[j] + __asic_resistant_data__[i + j]) * (arr_16[j] ^ __asic_resistant_data__[i + j]);
        }
        
        i += 16;
    }
    
    for(uint32 i = 0; i < 16; ++i)
    {
        buf[i] = htonl(arr_16[i]);
    }

    std::string hash_data = block_data + fly::base::base64_encode(p, 64);
    std::string block_hash_verify = coin_hash_b64(hash_data.c_str(), hash_data.length());

    if(block_hash != block_hash_verify)
    {
        return false;
    }
    
    return hash_pow(hash_raw, zero_bits);
}
   the __asic_resistant_data__ is a big table contains predefined random uint32 data, the number of element is:
Code:
const uint32 ASIC_RESISTANT_DATA_NUM = 5 * 1024 * 1024;
1569014221
Hero Member
*
Offline Offline

Posts: 1569014221

View Profile Personal Message (Offline)

Ignore
1569014221
Reply with quote  #2

1569014221
Report to moderator
1569014221
Hero Member
*
Offline Offline

Posts: 1569014221

View Profile Personal Message (Offline)

Ignore
1569014221
Reply with quote  #2

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

Posts: 1569014221

View Profile Personal Message (Offline)

Ignore
1569014221
Reply with quote  #2

1569014221
Report to moderator
1569014221
Hero Member
*
Offline Offline

Posts: 1569014221

View Profile Personal Message (Offline)

Ignore
1569014221
Reply with quote  #2

1569014221
Report to moderator
1569014221
Hero Member
*
Offline Offline

Posts: 1569014221

View Profile Personal Message (Offline)

Ignore
1569014221
Reply with quote  #2

1569014221
Report to moderator
ETFbitcoin
Legendary
*
Offline Offline

Activity: 1764
Merit: 2029

Use SegWit and enjoy lower fees.


View Profile WWW
June 01, 2018, 05:17:19 AM
 #2

I don't have full understanding about your code, but i wonder about :
1. CryptoNight needs very fast memory such as L3 cache and EtHash needs fast memory with big amount, but both algorithm have ASIC (or at least the manufacture claim that). Are you sure your algorithm really ASIC-resistant?
2. Is your algorithm require big memory amount, very fast memory or both?

johnny.jiang
Newbie
*
Offline Offline

Activity: 2
Merit: 0


View Profile
June 01, 2018, 06:29:44 AM
 #3

Soon or later new ASICS will be developed to adapt your algorithm, unless your  algorithm can self evolution
odolvlobo
Legendary
*
Offline Offline

Activity: 2618
Merit: 1401



View Profile
June 01, 2018, 06:39:39 AM
Merited by Foxpup (1)
 #4

... because ASIC is good at sha256 computation but not memory access, ...

An ASIC is simply a chip designed for a specific purpose. There is no reason why an ASIC can't be designed to be good at memory access.

Buy stuff on Amazon at a discount with bitcoins or convert Amazon points to bitcoins: Purse.io
Join an anti-signature campaign: Click ignore on the members of signature campaigns.
lichuan
Newbie
*
Offline Offline

Activity: 126
Merit: 0


View Profile
June 01, 2018, 06:42:03 AM
 #5

I don't have full understanding about your code, but i wonder about :
1. CryptoNight needs very fast memory such as L3 cache and EtHash needs fast memory with big amount, but both algorithm have ASIC (or at least the manufacture claim that). Are you sure your algorithm really ASIC-resistant?
2. Is your algorithm require big memory amount, very fast memory or both?
You don't understand my code, in my algorithm, only need the time cost by one memory process is more than one sha256 computation in the while loop, and need the amount of memory is much more than L3 cache, this is very different from EtHash or CryptoNight.
lichuan
Newbie
*
Offline Offline

Activity: 126
Merit: 0


View Profile
June 01, 2018, 06:47:04 AM
 #6

... because ASIC is good at sha256 computation but not memory access, ...

An ASIC is simply a chip designed for a specific purpose. There is no reason why an ASIC can't be designed to be good at memory access.

It's harder to design a ASIC with very fast speed of memory access than pure computation, because the speed of memory access has many limitations.
lichuan
Newbie
*
Offline Offline

Activity: 126
Merit: 0


View Profile
June 01, 2018, 06:53:18 AM
 #7

Soon or later new ASICS will be developed to adapt your algorithm, unless your  algorithm can self evolution

No, because the amount of memory access is much more than L3 cache, so if a miner want to generate block, he/she must access data from memory, not from L3 cache or L4 (if have) cache.
ir.hn
Member
**
Offline Offline

Activity: 168
Merit: 21

Blockchain is a Digital Constitution


View Profile
June 02, 2018, 08:00:18 PM
 #8

How is this different than Scrypt of Yescrypt which have high N values set?

Traxo
Full Member
***
Online Online

Activity: 395
Merit: 201



View Profile
June 02, 2018, 09:01:37 PM
Merited by vapourminer (1)
 #9

@tromp and @anonymint analyzed this over the past years.
It's not just the latency of memory access, but the power cost.
Memory can be optimized for the access patterns and power cost profile can be optimized.
The ASIC will always be at least an order-of-magnitude more efficient than the general purpose hardware:

https://gist.github.com/shelby3/67d990230e2dc9eb8be9e43e0b0b77a7
lichuan
Newbie
*
Offline Offline

Activity: 126
Merit: 0


View Profile
June 08, 2018, 05:08:01 AM
 #10

If you want to develop a new POW coin, you can't use SHA256 directly, but you can use my method, because the existing ASIC machine is not good at process massive memory operation.
ir.hn
Member
**
Offline Offline

Activity: 168
Merit: 21

Blockchain is a Digital Constitution


View Profile
June 08, 2018, 04:20:03 PM
Merited by achow101 (1)
 #11

If you want to develop a new POW coin, you can't use SHA256 directly, but you can use my method, because the existing ASIC machine is not good at process massive memory operation.

Again look into yescrypt for example.  Memory hard algorithms aren't new.  Even scrypt can be asic resistance with high enough N value set.

How is yours different than these?

lichuan
Newbie
*
Offline Offline

Activity: 126
Merit: 0


View Profile
June 09, 2018, 03:09:28 AM
 #12

If you want to develop a new POW coin, you can't use SHA256 directly, but you can use my method, because the existing ASIC machine is not good at process massive memory operation.

Again look into yescrypt for example.  Memory hard algorithms aren't new.  Even scrypt can be asic resistance with high enough N value set.

How is yours different than these?

My algorithm combine the advantages of both SHA256 and memory access, SHA256 have been proved in bitcoin for many years.
ir.hn
Member
**
Offline Offline

Activity: 168
Merit: 21

Blockchain is a Digital Constitution


View Profile
June 09, 2018, 03:23:08 AM
 #13

If you want to develop a new POW coin, you can't use SHA256 directly, but you can use my method, because the existing ASIC machine is not good at process massive memory operation.

Again look into yescrypt for example.  Memory hard algorithms aren't new.  Even scrypt can be asic resistance with high enough N value set.

How is yours different than these?

My algorithm combine the advantages of both SHA256 and memory access, SHA256 have been proved in bitcoin for many years.

So basically what your saying is your algorithm can be a plug in replacement for sha256?  So you could plug this directly into bitcoin without any major code changes?  Soft fork, hard fork?

Here is Yescrypt pseudocode:
Code:
# ** Functions/symbols **
# ||                           Concatenate two strings
# HMAC(h, k, v)                HMAC with hash function h and key k over value v
# PBKDF2(prf, p, s, c, dklen)  PBKDF2 key derivation function
# substr(s, start, length)     Substring from start (zero-based) of length bytes
# le32dec(), le32enc()         32-bit little-endian decoding/encoding
# SIMD_[un]shuffle()           Salsa20 SIMD (un)shuffling of 32-bit words
# Integerify(B, r)             Parse B_{2r-1} as a little-endian integer
# p2floor(x)                   Largest power of 2 not greater than x
 
# ** Inputs **
string   password
string   salt
integer  t_cost
integer  m_cost
integer  outlen
 
# ** Algorithm **
N = 8 << m_cost
r = 8
 
# ** Settings hard-coded/assumed below in this pseudocode **
# p = 1
# g = 0
# flags = YESCRYPT_RW
# no ROM
 
# If m_cost is 16 MB per thread or more, pre-hash using 1/64th of m_cost first,
# to mitigate garbage collector attacks.  yescrypt_prehash() is almost the same
# as this function, but its personalization HMAC key is "yescrypt-prehash"
# rather than "yescrypt", it skips builtin SCRAM finalization, and it will not
# invoke another yescrypt_prehash().
if (N / p >= 0x100 && N / p * r >= 0x20000)
    password = yescrypt_prehash(password, salt, t_cost, m_cost / 64, 32)
 
password = HMAC(SHA-256, "yescrypt", password)
B = PBKDF2(HMAC-SHA-256, password, salt, 1, 128 * r)
password = substr(B, 0, 32)
 
# SMix1 invoked to initialize pwxform S-boxes
X = SIMD_shuffle(le32dec(B))
for i = 0 to Sbytes/128 - 1
    S[i] = X
    X = BlockMix_{Salsa20/8, 1}(X)
 
# SMix1 invoked "for real"
for i = 0 to N - 1
    V[i] = X
    if (i > 1)
        j = Wrap(Integerify(X, r), i)
        X = X xor V[j]
    X = BlockMix_pwxform{Salsa20/2, S, r}(X)
 
# SMix2
if (t_cost = 0)
    Nloop = (N + 2) / 3
else if (t_cost = 1)
    Nloop = (N * 2 + 2) / 3
else
    Nloop = N * (t - 1)
for i = 0 to Nloop - 1
    j = Integerify(X, r) mod N
    X = X xor V[j]
    V[j] = X
    X = BlockMix_pwxform{Salsa20/2, S, r}(X)
B = le32enc(SIMD_unshuffle(X))
 
out = PBKDF2(HMAC-SHA-256, password, B, 1, outlen)
 
# Builtin SCRAM (RFC 5802) support
clen = min(outlen, 32)
dk = PBKDF2(HMAC-SHA-256, password, B, 1, 32)
dk = SHA-256(HMAC(SHA-256, dk, "Client Key"))
out = substr(dk, 0, clen) || substr(out, clen, outlen - clen)
 
return out
 
# ** Helper functions **
 
# Wrap x to the range 0 to i-1
Wrap(x, i)
    n = p2floor(i)
    return (x mod n) + (i - n)

lichuan
Newbie
*
Offline Offline

Activity: 126
Merit: 0


View Profile
June 09, 2018, 07:45:49 AM
 #14

If you want to develop a new POW coin, you can't use SHA256 directly, but you can use my method, because the existing ASIC machine is not good at process massive memory operation.

Again look into yescrypt for example.  Memory hard algorithms aren't new.  Even scrypt can be asic resistance with high enough N value set.

How is yours different than these?

My algorithm combine the advantages of both SHA256 and memory access, SHA256 have been proved in bitcoin for many years.

So basically what your saying is your algorithm can be a plug in replacement for sha256?  So you could plug this directly into bitcoin without any major code changes?  Soft fork, hard fork?

Here is Yescrypt pseudocode:
Code:
# ** Functions/symbols **
# ||                           Concatenate two strings
# HMAC(h, k, v)                HMAC with hash function h and key k over value v
# PBKDF2(prf, p, s, c, dklen)  PBKDF2 key derivation function
# substr(s, start, length)     Substring from start (zero-based) of length bytes
# le32dec(), le32enc()         32-bit little-endian decoding/encoding
# SIMD_[un]shuffle()           Salsa20 SIMD (un)shuffling of 32-bit words
# Integerify(B, r)             Parse B_{2r-1} as a little-endian integer
# p2floor(x)                   Largest power of 2 not greater than x
 
# ** Inputs **
string   password
string   salt
integer  t_cost
integer  m_cost
integer  outlen
 
# ** Algorithm **
N = 8 << m_cost
r = 8
 
# ** Settings hard-coded/assumed below in this pseudocode **
# p = 1
# g = 0
# flags = YESCRYPT_RW
# no ROM
 
# If m_cost is 16 MB per thread or more, pre-hash using 1/64th of m_cost first,
# to mitigate garbage collector attacks.  yescrypt_prehash() is almost the same
# as this function, but its personalization HMAC key is "yescrypt-prehash"
# rather than "yescrypt", it skips builtin SCRAM finalization, and it will not
# invoke another yescrypt_prehash().
if (N / p >= 0x100 && N / p * r >= 0x20000)
    password = yescrypt_prehash(password, salt, t_cost, m_cost / 64, 32)
 
password = HMAC(SHA-256, "yescrypt", password)
B = PBKDF2(HMAC-SHA-256, password, salt, 1, 128 * r)
password = substr(B, 0, 32)
 
# SMix1 invoked to initialize pwxform S-boxes
X = SIMD_shuffle(le32dec(B))
for i = 0 to Sbytes/128 - 1
    S[i] = X
    X = BlockMix_{Salsa20/8, 1}(X)
 
# SMix1 invoked "for real"
for i = 0 to N - 1
    V[i] = X
    if (i > 1)
        j = Wrap(Integerify(X, r), i)
        X = X xor V[j]
    X = BlockMix_pwxform{Salsa20/2, S, r}(X)
 
# SMix2
if (t_cost = 0)
    Nloop = (N + 2) / 3
else if (t_cost = 1)
    Nloop = (N * 2 + 2) / 3
else
    Nloop = N * (t - 1)
for i = 0 to Nloop - 1
    j = Integerify(X, r) mod N
    X = X xor V[j]
    V[j] = X
    X = BlockMix_pwxform{Salsa20/2, S, r}(X)
B = le32enc(SIMD_unshuffle(X))
 
out = PBKDF2(HMAC-SHA-256, password, B, 1, outlen)
 
# Builtin SCRAM (RFC 5802) support
clen = min(outlen, 32)
dk = PBKDF2(HMAC-SHA-256, password, B, 1, 32)
dk = SHA-256(HMAC(SHA-256, dk, "Client Key"))
out = substr(dk, 0, clen) || substr(out, clen, outlen - clen)
 
return out
 
# ** Helper functions **
 
# Wrap x to the range 0 to i-1
Wrap(x, i)
    n = p2floor(i)
    return (x mod n) + (i - n)

Yes, the result value of my algorithm is sha256d value too, please refer to the hash-verify code above.
lichuan
Newbie
*
Offline Offline

Activity: 126
Merit: 0


View Profile
June 09, 2018, 07:54:05 AM
 #15

In the above verify_hash() function, the coin_hash_b64 function is defined as:

Code:
std::string coin_hash_b64(const char *data, uint32 size)
{
    char h_256[CSHA256::OUTPUT_SIZE];
    CHash256().Write(data, size).Finalize(h_256);
    std::string b64 = fly::base::base64_encode(h_256, CSHA256::OUTPUT_SIZE);
   
    return b64;
}
ir.hn
Member
**
Offline Offline

Activity: 168
Merit: 21

Blockchain is a Digital Constitution


View Profile
June 09, 2018, 01:15:30 PM
 #16

So are you saying this can be implemented in a soft fork?  Would there be any way for miners using old sha256 to fool the algorithm to accept their old type sha256 values, or skip a step of the memory hard part if their values look correct?  In other words, how is doing the memory hard part enforced?

lichuan
Newbie
*
Offline Offline

Activity: 126
Merit: 0


View Profile
June 09, 2018, 04:10:18 PM
 #17

So are you saying this can be implemented in a soft fork?  Would there be any way for miners using old sha256 to fool the algorithm to accept their old type sha256 values, or skip a step of the memory hard part if their values look correct?  In other words, how is doing the memory hard part enforced?

It need hard fork, but doesn't need any major code changes.
aliashraf
Hero Member
*****
Offline Offline

Activity: 896
Merit: 656


View Profile
June 09, 2018, 05:02:48 PM
Merited by vapourminer (1)
 #18

... because ASIC is good at sha256 computation but not memory access, ...

An ASIC is simply a chip designed for a specific purpose. There is no reason why an ASIC can't be designed to be good at memory access.

Unbelievable question from a decent bitcointalk member  Shocked

Accessing memory bus is already optimized in cpu/gpu tech and it does not make sense for a  designer/manufacturer to claim such a thing: An asic optimized for memory bus access!

Any algorithm, (I mean any algorithm) being truly memory hard by means of memory access is inherently ASIC resistant as long it has two important properties:
  • a large enough memory footprint
  • a complex enough function that is not feasible to be implemented directly on the memory bank
The latter is new and I have to explain a bit:
It suggests that the fetch operation MUST be necessary and not feasible to be bypassed by adding some extra gates to a special memory bank to perform an in-place hash (like what happened for Equihash).

 The problem with Equihash and Cryptonight is that they have not achieved the desired level of hardness but Ethash (a Dagger Hasihmoto variant) is performing well and Bitmain's E3 by no means deserves to be called an ASIC.

To put it straight:
Any educated enough computer engineer can easily confirm that a memory bound algorithm can never be optimized by means of optimization of processing power (by implementing the algorithm in ASIC for instance).

So, it is just a ridiculous and naive assumption that every PoW algorithm is vulnerable to ASIC attacks.
On the contrary, I believe that ASIC resistance (and behind, ASIC proof) is achievable no matter what Bitmain and its agents try to induce in the community.




ir.hn
Member
**
Offline Offline

Activity: 168
Merit: 21

Blockchain is a Digital Constitution


View Profile
June 09, 2018, 06:00:09 PM
Last edit: June 09, 2018, 06:21:13 PM by ir.hn
 #19

... because ASIC is good at sha256 computation but not memory access, ...

An ASIC is simply a chip designed for a specific purpose. There is no reason why an ASIC can't be designed to be good at memory access.

Unbelievable question from a decent bitcointalk member  Shocked

Accessing memory bus is already optimized in cpu/gpu tech and it does not make sense for a  designer/manufacturer to claim such a thing: An asic optimized for memory bus access!

Any algorithm, (I mean any algorithm) being truly memory hard by means of memory access is inherently ASIC resistant as long it has two important properties:
  • a large enough memory footprint
  • a complex enough function that is not feasible to be implemented directly on the memory bank
The latter is new and I have to explain a bit:
It suggests that the fetch operation MUST be necessary and not feasible to be bypassed by adding some extra gates to a special memory bank to perform an in-place hash (like what happened for Equihash).

 The problem with Equihash and Cryptonight is that they have not achieved the desired level of hardness but Ethash (a Dagger Hasihmoto variant) is performing well and Bitmain's E3 by no means deserves to be called an ASIC.

To put it straight:
Any educated enough computer engineer can easily confirm that a memory bound algorithm can never be optimized by means of optimization of processing power (by implementing the algorithm in ASIC for instance).

So, it is just a ridiculous and naive assumption that every PoW algorithm is vulnerable to ASIC attacks.
On the contrary, I believe that ASIC resistance (and behind, ASIC proof) is achievable no matter what Bitmain and its agents try to induce in the community.






I think he was just arguing semantics more than anything, just the definition of asic as application specific integrated circuit.  It is a tiring and unproductive argument though.  Technically I could make an asic for Yescrypt by removing usb ports and GPU ports and shrinking the board, maximizing copper for heat dissipation for 100% max CPU usage, etc.  The point is though it would still be a functioning computer, just designed for CPU mining.  So technically it would be an asic but not an asic by any real metric.  So basically ASIC just needs to be defined more closely to its real world form, say that to be defined as an asic, it must achieve at least an order of magnitude improvement in running a given application over general purpose computers.

But yes ASIC resistance is absolutely real; the problem is even algorithms that can be asic resistant are implemented in ways to benefit GPU's over CPU's. In this process of allowing for GPU acceleration, they make it significantly less resistant to real ASIC's.

odolvlobo
Legendary
*
Offline Offline

Activity: 2618
Merit: 1401



View Profile
June 09, 2018, 09:22:03 PM
 #20

An ASIC is simply a chip designed for a specific purpose. There is no reason why an ASIC can't be designed to be good at memory access.

Accessing memory bus is already optimized in cpu/gpu tech and it does not make sense for a  designer/manufacturer to claim such a thing: An asic optimized for memory bus access!

...

I think he was just arguing semantics more than anything, just the definition of asic as application specific integrated circuit.  It is a tiring and unproductive argument though.  Technically I could make an asic for Yescrypt by removing usb ports and GPU ports and shrinking the board, maximizing copper for heat dissipation for 100% max CPU usage, etc.  The point is though it would still be a functioning computer, just designed for CPU mining.  So technically it would be an asic but not an asic by any real metric.  So basically ASIC just needs to be defined more closely to its real world form, say that to be defined as an asic, it must achieve at least an order of magnitude improvement in running a given application over general purpose computers.
...

I'm not just arguing semantics or definitions. It seems to me that the goal of "ASIC-resistance" is really to prevent a specialized device whose performance is an order of magnitude improvement over a PC, but at the same cost. Whether it is a single chip or not is not really the point, is it?

Now, I am not an EE so humor me, but aren't there RAMs that have access speeds that are an order of magnitude greater than standard DRAM, and wouldn't using that defeat the memory access bottleneck in an ASIC-resistant design?

Buy stuff on Amazon at a discount with bitcoins or convert Amazon points to bitcoins: Purse.io
Join an anti-signature campaign: Click ignore on the members of signature campaigns.
Pages: [1] 2 »  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!