I found a way to implement real asic-resistant POW algorithm

[lichuan]

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;

[1713529003]

1713529003

[1713529003]

1713529003

[johnny.jiang]

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

[odolvlobo]

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

[lichuan]

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]

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

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]

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

[Traxo]

@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]

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]

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]

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]

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]

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]

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]

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]

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]

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

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]

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

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]

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?

[tromp]

Whether it is a single chip or not is not really the point, is it?

To me that is really the point. A competitive single chip ASIC is a big hot-running chip requiring tons of design talent and access to the latest and greatest fabrication technology. This leads to manufacturing centralization and to noisy mining rigs that become obsolete within a year or two.

On the other hand, a chip that needs to interface to separate commodity memory chips can remain smaller, run cooler, and be implemented in a less than bleeding-edge technology, since it only needs to be fast enough to saturate the memory interface.

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?

Yes, there is SRAM, but it still has a limited bandwidth.