./sinetek_

Looking at Crypto coins block explorers, I was wondering in the case of altcoins if the Merkle Root field is still computed the same way as in Bitcoin.

There’s already a lot of information on the general theory behind a Merkle Tree, so please refer to external sources for a better introduction. Here is instead a small worked example of how this applies to Bitcoin and as we will see, also Vertcoin.

QByteArray sha256d(QByteArray in)
{
QCryptographicHash hash (QCryptographicHash::Sha256);

hash.addData(in);

QByteArray res1 = hash.result();
hash.reset();
hash.addData(res1);

return hash.result();
}

This simple function computes the SHA256d hash of a byte array, as used everywhere in Bitcoin.

For the simple case where Tx count = 1, the Merkle root is simply the hash of the first transaction.

For a block with more transactions, let’s illustrate.

a = 32e60eb21632597c1c1545c63fae57df8d4455648b7d97150b7dcee706749588
b = 1deed158ada568b9b193473095c8eb2cef2cffe60ccce15c3c82f599a09767a8

However there’s a bug with taking these values directly. It turns out Satoshi decided to flip the hash values for whatever arbitrary reason. We’ll need to unflip them to the correct endianness for our trees to grow correctly.

QByteArray reverse_hash (QByteArray in)
{
QByteArray res;
if (in.length() != 32) return QByteArray::fromHex(“”);

for (int i = 0; i < 32; ++i)
{
res.append(in[31 – i]);
}

return res;
}

Applying this, we now get:

a’ = 88957406e7ce7d0b15977d8b6455448ddf57ae3fc645151c7c593216b20ee632
b’ = a86797a099f5823c5ce1cc0ce6ff2cef2cebc895304793b1b968a5ad58d1ee1d

Then from theory we know that in our case, Root = Hash ( A | B).

Compute this, flip the bytes again, and you get the correct Merkle root as displayed in the explorer.

QByteArray c = a + b;
QByteArray m = sha256d( c );
m = reverse_hash(m);

For blocks with more transactions, repeat this process by merging more pairs.

Conclusion

The same process is used for both Bitcoin and Vertcoin, as well as probably a lot of other alts. Displayed hash values are byte-flipped around.

Since WordPress is not very good at displaying inline C++, here is the complete code example.

Instead of looping around, there’s a simpler way.

diff --git a/kernel/elf.cpp b/kernel/elf.cpp
index 8bee7c5..ca2d50c 100644
--- a/kernel/elf.cpp
+++ b/kernel/elf.cpp
@@ -42,12 +42,9 @@
namespace Sortix {
namespace ELF {

-static bool is_power_of_two(uintptr_t value)
+static bool is_power_of_two(uintptr_t x)
{
- for ( uintptr_t i = 0; i < sizeof(uintptr_t) * 8; i++ )
- if ( (uintptr_t) 1 << i == value )
- return true;
- return false;
+ return (x != 0) && ((x & (x - 1)) == 0);
}

The code in question is found in the excellent hobby OS sortix.

Unfortunately, when you try running certain games on a mac, on a case sensistive HFS+ filesystem, you might hit a roadblock.

Steam itself will run fine.

Fortunately there is a solution by using OpenZFS. I won’t go into the details of installing ZFS on a mac as there is plenty of information out there. I simply use homebrew for that kind of thing. Refer to the OpenZFS Wiki, they have instructions on how to install using homebrew.

Method for Creating the Filesystem Image

OpenZFS supports creating a pool inside a file, so this is what we are going to do.

mkfile -n 5g steam_disk.zfs
zpool create -O casesensitivity=insensitive steam_pool /Users/$USER/steam_disk.zfs

Then you will get a shiny new volume with the required properties under /Volumes/steam_pool/. Fire up Steam, tell it to install there.

Enjoy, and don’t forget to read up on ZFS basics if you don’t know how to export and import a pool.

zpool export steam_pool
zpool import -d /Users/$USER/ -a

There are various ways of adjusting the brightness on laptop panels. If you are running the correct Intel driver, it should be a matter of poking around the sysctl’s.

~% sysctl -a | grep lcd
hw.acpi.video.lcd0.levels: 100 100 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
hw.acpi.video.lcd0.economy: 100
hw.acpi.video.lcd0.fullpower: 100
hw.acpi.video.lcd0.brightness: 60
hw.acpi.video.lcd0.active: 0

From that we know that the correct one to adjust is lcd0.brightness.

~% sudo sysctl hw.acpi.video.lcd0.brightness=50

I’m running Linux. Follow the instructions from Cross building NetBSD on Linux:

===> Successful make release
===> build.sh ended: Fri Nov 4 12:38:00 EDT 2016
===> Summary of results:
build.sh command: ./build.sh -U -u -m amd64 release
build.sh started: Fri Nov 4 10:17:30 EDT 2016
NetBSD version: 7.0.2
MACHINE: amd64
MACHINE_ARCH: x86_64
Build platform: Linux 4.8.6-1-ARCH x86_64
HOST_SH: /usr/bin/sh
MAKECONF file: /etc/mk.conf (File not found)
TOOLDIR path: /home/sinetek/dev/building-netbsd/usr/src/obj/tooldir.Linux-4.8.6-1-ARCH-x86_64
DESTDIR path: /home/sinetek/dev/building-netbsd/usr/src/obj/destdir.amd64
RELEASEDIR path: /home/sinetek/dev/building-netbsd/usr/src/obj/releasedir
Updated makewrapper: /home/sinetek/dev/building-netbsd/usr/src/obj/tooldir.Linux-4.8.6-1-ARCH-x86_64/bin/nbmake-amd64
Successful make release
build.sh ended: Fri Nov 4 12:38:00 EDT 2016
===> .

Then we build a custom configuration file for the kernel.
Drat. The config file for GENERIC already includes urtwn.
Let’s see what we can do poking around. Let’s grab the device id from Linux.

$ lsusb
Bus 001 Device 009: ID 07b8:8179 AboCom Systems Inc

Let’s poke around the driver. I found something interesting in if_urtwn.c.
From /sys/dev/usb/usbdevs.h I see that the constants I want are ABOCOM, and REALTEK RTL8188EU.
Let’s add these in.

diff –git a/sys/dev/usb/if_urtwn.c b/sys/dev/usb/if_urtwn.c
index 379365e..3294e54 100644
— a/sys/dev/usb/if_urtwn.c
+++ b/sys/dev/usb/if_urtwn.c
@@ -167,6 +167,7 @@ static const struct urtwn_dev {
URTWN_RTL8188E_DEV(ELECOM, WDC150SU2M),
URTWN_RTL8188E_DEV(REALTEK, RTL8188ETV),
URTWN_RTL8188E_DEV(REALTEK, RTL8188EU),
+ URTWN_RTL8188E_DEV(ABOCOM, RTL8188EU),
};
#undef URTWN_DEV
#undef URTWN_RTL8188E_DEV

… and the usbdevs:

diff –git a/sys/dev/usb/usbdevs b/sys/dev/usb/usbdevs
index bfe82a2..1bc213f 100644
— a/sys/dev/usb/usbdevs
+++ b/sys/dev/usb/usbdevs
@@ -640,6 +640,7 @@ product ABOCOM XX9 0x4104 XX9
product ABOCOM UFE2000 0x420a UFE2000 USB2.0 Fast Ethernet Adapter
product ABOCOM WL54 0x6001 WL54
product ABOCOM RTL8192CU 0x8178 RTL8192CU
+product ABOCOM RTL8188EU 0x8179 RTL8188EU
product ABOCOM RTL8188CU_1 0x8188 RTL8188CU
product ABOCOM RTL8188CU_2 0x8189 RTL8188CU
product ABOCOM XX10 0xabc1 XX10

Regenerate the correct usb dev headers.

$ TOOL_AWK=awk bmake -f Makefile.usbdevs usbdevs.h

Rebuild the kernel, then rebuild the iso image:

./build.sh -U -u -m amd64 release
./build.sh -U -u -m amd64 iso-image

Test. Mad Success!!