ERROR: AcceptBlockHeader: Consensus::CheckBlockHeader: ..., high-hash, proof of work failed

MagicalTux commented

2024-11-20 10:56:17 +00:00

(Migrated from github.com)

When compiling monacoin, the chain fails to sync with the following error:

ERROR: AcceptBlockHeader: Consensus::CheckBlockHeader: 5673823195ab7bf3319edaddaff782662e3fc75761de98b347605fea9350f821, high-hash, proof of work failed

Googling this error brings up a report, with some responses mentioning bdb compatibility, however since bdb is used for the wallet only and not for on-chain data, it should have no impact whatsoever.

References found online:

This block seems to be at the heart of the issue:

https://blockbook.electrum-mona.org/block/450000

At block 450000 mona has switched from scrypt to Lyra2REv2_DGW proof of work algorithm, my guess is that the compile environment might have had an effect on the algorithm and is causing the issue. I was hoping running tests would allow finding more information however the tests didn't compile at first and do not seem to want to run.

When compiling monacoin, the chain fails to sync with the following error: ``` ERROR: AcceptBlockHeader: Consensus::CheckBlockHeader: 5673823195ab7bf3319edaddaff782662e3fc75761de98b347605fea9350f821, high-hash, proof of work failed ``` Googling this error brings up a report, with some responses mentioning bdb compatibility, however since bdb is used for the wallet only and not for on-chain data, it should have no impact whatsoever. References found online: * https://web3.askmona.org/22958 * https://askmona.org/3763 This block seems to be at the heart of the issue: * https://blockbook.electrum-mona.org/block/450000 At block 450000 mona has switched from scrypt to Lyra2REv2_DGW proof of work algorithm, my guess is that the compile environment might have had an effect on the algorithm and is causing the issue. I was hoping running tests would allow finding more information however the tests didn't compile at first and do not seem to want to run.

MagicalTux commented

2024-11-20 11:26:13 +00:00

(Migrated from github.com)

450000-4500024までは上の直近25ブロックまでさかのぼってDGWv3アルゴリズムでエラーが出ないようにPowLimit(1e0fffff)の値が入っています。
なのでこの場合だとbnTargetの中がPowLimitの値が入っているためtrueが返ると思われます。
実際の動作ですが細かい数値は内容作ってコンパイルしないといけないのでちょっと何とも言えないです。

When checking, the block target is 00000fffff000000000000000000000000000000000000000000000000000000

The hash value obtained is cba2241c7eace873b8b79ff413b682bb02e790fd81a57a8c0f00db6531e80223 which is obviously wrong.

> 450000-4500024までは上の直近25ブロックまでさかのぼってDGWv3アルゴリズムでエラーが出ないようにPowLimit(1e0fffff)の値が入っています。 > なのでこの場合だとbnTargetの中がPowLimitの値が入っているためtrueが返ると思われます。 > 実際の動作ですが細かい数値は内容作ってコンパイルしないといけないのでちょっと何とも言えないです。 When checking, the block target is `00000fffff000000000000000000000000000000000000000000000000000000` The hash value obtained is `cba2241c7eace873b8b79ff413b682bb02e790fd81a57a8c0f00db6531e80223` which is obviously wrong.

MagicalTux commented

2024-11-20 11:40:54 +00:00

(Migrated from github.com)

Some debugging data

The raw block header: 030000002539610f9c6b910c354032b3f70045edfbdc75a5da9ed6c53fcdca78851eb9be8078d8cefa1b499ae86da3758df5d48a187236e29c450acd930ee98e0f7a08df4cd00756ffff0f1ec5320000

lyra2re2 hash states at various points:

lyra2re2 blake256: 98160f18b42578d03a39b85bee9d2d24246371ac8b3b80bc7beed4650a6841a1
lyra2re2 keccak256: df1c352648e0fdfa058ed1ee608d1ff737fa5ddf0ac982b5fd255c56465c9c2a
lyra2re2 cubehash256: 9e830a1316bde68df235361893fde097a84171613987566001ddf67eaf095293
lyra2re2 LYRA2: 3253ee1fea2ffab1b7ea2a314efdb2f5e90f978a7f4f9db5fc0d2f80ba36a080
lyra2re2 skein256: d8731c75f3f8a9d12b49a0c398c84604532261b9f95bcb3905257934e14d6d1f
lyra2re2 cubehash256: 525741ccfd92260355375c5972a072462c35113a6191fdf1fda178a089095a3b
lyra2re2 bmw256: cb3726205803d7fa15c1ba871638e6cbe8f19ae44969d870571e60d1d2e127de

Final bmw256 value is indeed used after bytes reversal.

Some debugging data The raw block header: `030000002539610f9c6b910c354032b3f70045edfbdc75a5da9ed6c53fcdca78851eb9be8078d8cefa1b499ae86da3758df5d48a187236e29c450acd930ee98e0f7a08df4cd00756ffff0f1ec5320000` lyra2re2 hash states at various points: ``` lyra2re2 blake256: 98160f18b42578d03a39b85bee9d2d24246371ac8b3b80bc7beed4650a6841a1 lyra2re2 keccak256: df1c352648e0fdfa058ed1ee608d1ff737fa5ddf0ac982b5fd255c56465c9c2a lyra2re2 cubehash256: 9e830a1316bde68df235361893fde097a84171613987566001ddf67eaf095293 lyra2re2 LYRA2: 3253ee1fea2ffab1b7ea2a314efdb2f5e90f978a7f4f9db5fc0d2f80ba36a080 lyra2re2 skein256: d8731c75f3f8a9d12b49a0c398c84604532261b9f95bcb3905257934e14d6d1f lyra2re2 cubehash256: 525741ccfd92260355375c5972a072462c35113a6191fdf1fda178a089095a3b lyra2re2 bmw256: cb3726205803d7fa15c1ba871638e6cbe8f19ae44969d870571e60d1d2e127de ``` Final bmw256 value is indeed used after bytes reversal.

MagicalTux commented

2024-11-20 11:46:46 +00:00

(Migrated from github.com)

Test with a working implementation:

lyra2re2 blake256: 98160f18b42578d03a39b85bee9d2d24246371ac8b3b80bc7beed4650a6841a1
lyra2re2 keccak256: df1c352648e0fdfa058ed1ee608d1ff737fa5ddf0ac982b5fd255c56465c9c2a
lyra2re2 cubehash256: 9e830a1316bde68df235361893fde097a84171613987566001ddf67eaf095293
lyra2re2 lyra2: 3253ee1fea2ffab1b7ea2a314efdb2f5e90f978a7f4f9db5fc0d2f80ba36a080
lyra2re2 ske: d8731c75f3f8a9d12b49a0c398c84604532261b9f95bcb3905257934e14d6d1f
lyra2re2 cubehash256: 525741ccfd92260355375c5972a072462c35113a6191fdf1fda178a089095a3b
lyra2re2 bmw256: b25b282350cbd420c61c3400d2d8cf1a665b72ff52c1986ad4e4b6051c060000

The issue appears at the end on bmw256

Test with a working implementation: ``` lyra2re2 blake256: 98160f18b42578d03a39b85bee9d2d24246371ac8b3b80bc7beed4650a6841a1 lyra2re2 keccak256: df1c352648e0fdfa058ed1ee608d1ff737fa5ddf0ac982b5fd255c56465c9c2a lyra2re2 cubehash256: 9e830a1316bde68df235361893fde097a84171613987566001ddf67eaf095293 lyra2re2 lyra2: 3253ee1fea2ffab1b7ea2a314efdb2f5e90f978a7f4f9db5fc0d2f80ba36a080 lyra2re2 ske: d8731c75f3f8a9d12b49a0c398c84604532261b9f95bcb3905257934e14d6d1f lyra2re2 cubehash256: 525741ccfd92260355375c5972a072462c35113a6191fdf1fda178a089095a3b lyra2re2 bmw256: b25b282350cbd420c61c3400d2d8cf1a665b72ff52c1986ad4e4b6051c060000 ``` The issue appears at the end on bmw256

MagicalTux commented

2024-11-20 12:03:18 +00:00

(Migrated from github.com)

Each time I run monacoin the value for bmw256 changes, which makes me think this function is using some piece of uninitialized memory.

run 1:

lyra2re2 cubehash256: 525741ccfd92260355375c5972a072462c35113a6191fdf1fda178a089095a3b
lyra2re2 bmw256: 0bdd34183a7124d8771fccef09cd7a40ba028eaf1f9f87db2014c14b014165e8

run 2:

lyra2re2 cubehash256: 525741ccfd92260355375c5972a072462c35113a6191fdf1fda178a089095a3b
lyra2re2 bmw256: 2148262d9d2cb372f6ae7355d01d5193b5d6a4dd330941c2b2f5024d86c14129

Each time I run monacoin the value for bmw256 changes, which makes me think this function is using some piece of uninitialized memory. run 1: ``` lyra2re2 cubehash256: 525741ccfd92260355375c5972a072462c35113a6191fdf1fda178a089095a3b lyra2re2 bmw256: 0bdd34183a7124d8771fccef09cd7a40ba028eaf1f9f87db2014c14b014165e8 ``` run 2: ``` lyra2re2 cubehash256: 525741ccfd92260355375c5972a072462c35113a6191fdf1fda178a089095a3b lyra2re2 bmw256: 2148262d9d2cb372f6ae7355d01d5193b5d6a4dd330941c2b2f5024d86c14129 ```

👀 1

MagicalTux commented

2024-11-20 12:41:17 +00:00

(Migrated from github.com)

Modifying bmw32_init() to do a memset on the context causes the value to not vary anymore, but it is still not correct, meaning there is other parts of uninitialized memory somewhere.

Compiling monacoin with -ftrivial-auto-var-init=zero in CFLAGS fully "solves" the issue.

This confirms the implementation of bmw256 is using uninitialized variables. It is likely the official build has something to the effect of -ftrivial-auto-var-init=zero included, however for people like me who want to build their binaries it might be an issue.

Modifying `bmw32_init()` to do a `memset` on the context causes the value to not vary anymore, but it is still not correct, meaning there is other parts of uninitialized memory somewhere. Compiling monacoin with `-ftrivial-auto-var-init=zero` in `CFLAGS` fully "solves" the issue. This confirms the implementation of bmw256 is using uninitialized variables. It is likely the official build has something to the effect of `-ftrivial-auto-var-init=zero` included, however for people like me who want to build their binaries it might be an issue.

👍 1

MagicalTux commented

2024-11-20 15:05:43 +00:00

(Migrated from github.com)

The issue happens somewhere near the end of bmw32_close, probably in compress_small but compress_small is made of so many macros in macros it's quite difficult to track the issue, and adding some debug tends to make the issue disappear.

The issue happens somewhere near the end of `bmw32_close`, probably in `compress_small` but `compress_small` is made of so many macros in macros it's quite difficult to track the issue, and adding some debug tends to make the issue disappear.

MagicalTux commented

2024-11-20 16:06:11 +00:00

(Migrated from github.com)

I'll give up for now, at the very least this makes things a bit better (the result becomes wrong in a fixed way instead of being random):

diff '--color=auto' -bBrU3 monacoin-0.20.4.orig/src/crypto/Lyra2RE/bmw.c monacoin-0.20.4/src/crypto/Lyra2RE/bmw.c
--- monacoin-0.20.4.orig/src/crypto/Lyra2RE/bmw.c	2024-11-20 12:00:49.821050144 +0900
+++ monacoin-0.20.4/src/crypto/Lyra2RE/bmw.c	2024-11-21 00:40:20.179704052 +0900
@@ -609,6 +609,7 @@
 static void
 bmw32_init(sph_bmw_small_context *sc, const sph_u32 *iv)
 {
+	memset(sc, 0, sizeof(sph_bmw_small_context));
 	memcpy(sc->H, iv, sizeof sc->H);
 	sc->ptr = 0;
 #if SPH_64

I'll give up for now, at the very least this makes things a bit better (the result becomes wrong in a fixed way instead of being random): ```patch diff '--color=auto' -bBrU3 monacoin-0.20.4.orig/src/crypto/Lyra2RE/bmw.c monacoin-0.20.4/src/crypto/Lyra2RE/bmw.c --- monacoin-0.20.4.orig/src/crypto/Lyra2RE/bmw.c 2024-11-20 12:00:49.821050144 +0900 +++ monacoin-0.20.4/src/crypto/Lyra2RE/bmw.c 2024-11-21 00:40:20.179704052 +0900 @@ -609,6 +609,7 @@ static void bmw32_init(sph_bmw_small_context *sc, const sph_u32 *iv) { + memset(sc, 0, sizeof(sph_bmw_small_context)); memcpy(sc->H, iv, sizeof sc->H); sc->ptr = 0; #if SPH_64 ```

MagicalTux commented

2024-11-25 07:33:00 +00:00

(Migrated from github.com)

Confirmed adding a call to zeroStack() as defined below at the beginning of compress_small makes the issue go away, confirming use of uninitialized memory in that function.

inline static void __attribute__((optimize("O0"))) zeroStack() {
        char st[65536];
        memset(st, 0, sizeof(st));
}

Confirmed adding a call to `zeroStack()` as defined below at the beginning of `compress_small` makes the issue go away, confirming use of uninitialized memory in that function. ```c inline static void __attribute__((optimize("O0"))) zeroStack() { char st[65536]; memset(st, 0, sizeof(st)); } ```

wakiyamap commented

2024-11-25 07:43:34 +00:00

(Migrated from github.com)

@MagicalTux
Thanks!
……Are you planning on making a pull request?

@MagicalTux Thanks! ……Are you planning on making a pull request?

MagicalTux commented

2024-11-25 08:23:16 +00:00

(Migrated from github.com)

@wakiyamap

I'm hoping to make one once I'm able to do a proper fix, and not just hide the issue by clearing the stack.

@wakiyamap I'm hoping to make one once I'm able to do a proper fix, and not just hide the issue by clearing the stack.

👍 1

MagicalTux commented

2024-11-25 09:30:07 +00:00

(Migrated from github.com)

To test the final part of the issue, I've extracted the problematic code & testing it in a separate environment.

~/projects/monadebug $ make clean test CFLAGS="-Wall -g -ggdb -O2 -pipe"
rm -f bmw.o main.o
cc -Wall -g -ggdb -O2 -pipe   -c -o bmw.o bmw.c
cc -Wall -g -ggdb -O2 -pipe   -c -o main.o main.c
cc -Wall -g -ggdb -O2 -pipe -o monadebug bmw.o main.o
./monadebug
inputhex dump: 525741ccfd92260355375c5972a072462c35113a6191fdf1fda178a089095a3b
hex dump: 2148262d9d2cb372f6ae7355d01d5193b5d6a4dd330941c2b2f5024d86c14129
~/projects/monadebug $ make clean test CFLAGS="-Wall -g -ggdb -O0 -pipe"
rm -f bmw.o main.o
cc -Wall -g -ggdb -O0 -pipe   -c -o bmw.o bmw.c
cc -Wall -g -ggdb -O0 -pipe   -c -o main.o main.c
cc -Wall -g -ggdb -O0 -pipe -o monadebug bmw.o main.o
./monadebug
inputhex dump: 525741ccfd92260355375c5972a072462c35113a6191fdf1fda178a089095a3b
hex dump: b25b282350cbd420c61c3400d2d8cf1a665b72ff52c1986ad4e4b6051c060000

Just setting -O0 causes the right value to be returned, which is puzzling. I tried various detection tools like -fsanitize=address but when specifying those options the issue disappears. -fno-strict-aliasing also causes the issue to disappear.

To test the final part of the issue, I've extracted the problematic code & testing it in a [separate environment](https://github.com/MagicalTux/monadebug). ``` ~/projects/monadebug $ make clean test CFLAGS="-Wall -g -ggdb -O2 -pipe" rm -f bmw.o main.o cc -Wall -g -ggdb -O2 -pipe -c -o bmw.o bmw.c cc -Wall -g -ggdb -O2 -pipe -c -o main.o main.c cc -Wall -g -ggdb -O2 -pipe -o monadebug bmw.o main.o ./monadebug inputhex dump: 525741ccfd92260355375c5972a072462c35113a6191fdf1fda178a089095a3b hex dump: 2148262d9d2cb372f6ae7355d01d5193b5d6a4dd330941c2b2f5024d86c14129 ~/projects/monadebug $ make clean test CFLAGS="-Wall -g -ggdb -O0 -pipe" rm -f bmw.o main.o cc -Wall -g -ggdb -O0 -pipe -c -o bmw.o bmw.c cc -Wall -g -ggdb -O0 -pipe -c -o main.o main.c cc -Wall -g -ggdb -O0 -pipe -o monadebug bmw.o main.o ./monadebug inputhex dump: 525741ccfd92260355375c5972a072462c35113a6191fdf1fda178a089095a3b hex dump: b25b282350cbd420c61c3400d2d8cf1a665b72ff52c1986ad4e4b6051c060000 ``` Just setting `-O0` causes the right value to be returned, which is puzzling. I tried various detection tools like `-fsanitize=address` but when specifying those options the issue disappears. `-fno-strict-aliasing` also causes the issue to disappear.

MagicalTux commented

2024-11-26 03:38:07 +00:00

(Migrated from github.com)

It turns out that when compress_small is included multiple times in the same function (by inlining), gcc may reorder the content of the functions as part of the optimization, and if things aren't written correctly this can cause data to be read incorrectly.

This issue comes from gcc's aggressive optimization and assumption code isn't doing weird typecasting. Unfortunately, sph is doing some weird typecasting (a char* becomes a void* to later become a sph_uint32*) and because of the strict aliasing rules gcc assumes the pointers to be different, and orders reads according to that assumption, resulting in garbage.

This can be easily fixed by using memcpy instead of just casting a void to sph_uint32* which will be optimized nicely anyway since memcpy is a builtin function in all recent compilers.

It turns out that when `compress_small` is included multiple times in the same function (by inlining), gcc may reorder the content of the functions as part of the optimization, and if things aren't written correctly this can cause data to be read incorrectly. This issue comes from gcc's aggressive optimization and assumption code isn't doing weird typecasting. Unfortunately, sph is doing some weird typecasting (a `char*` becomes a `void*` to later become a `sph_uint32*`) and because of the strict aliasing rules gcc assumes the pointers to be different, and orders reads according to that assumption, resulting in garbage. This can be easily fixed by using `memcpy` instead of just casting a void to `sph_uint32*` which will be optimized nicely anyway since memcpy is a builtin function in all recent compilers.

Rows
Columns

ERROR: AcceptBlockHeader: Consensus::CheckBlockHeader: ..., high-hash, proof of work failed #121