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;
}
Topic: I found a way to implement real asic-resistant POW algorithm - page 2. (Read 720 times)
In the above verify_hash() function, the coin_hash_b64 function is defined as:
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.
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)
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.
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?
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.
@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
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
How is this different than Scrypt of Yescrypt which have high N values set?
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.
... 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.
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. 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?
... 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.
Soon or later new ASICS will be developed to adapt your algorithm, unless your algorithm can self evolution
Hi, everyone
As we know, the mining process is like this:
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:
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:
the __asic_resistant_data__ is a big table contains predefined random uint32 data, the number of element is:
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)
}
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);
}
Code:
const uint32 ASIC_RESISTANT_DATA_NUM = 5 * 1024 * 1024;
Jump to: