x11 hashing algorithm -- test vectors?

nmarley

Active Member
Jun 28, 2014
366
424
133
A few projects are starting to port the x11 hash algorithm to various languages, e.g. native Javascript, Objective-C. I'm wondering if there exist test vectors for x11 which can be tested against to ensure no errors are made in porting it to other languages.

It occurred to me that "the Dash blockchain" could be considered test vectors, but it gets complicated as to which values should be hashed, and in what order should they be concatenated, endianness, etc.

Does anyone know if any x11 test vectors have already been created?
 
  • Like
Reactions: AndyDark

AndyDark

Well-known Member
Sep 10, 2014
353
705
163
It's a great point Nathan.

The ObjC X11 hash implementation has been live for a while in the iOS wallet but the JS version was just completed and currently reviewing it.

Currently the JS version tests are pretty basic https://github.com/QuantumExplorer/x11-hash-js/blob/master/test/test.js but the best test will be validating the block headers up through a synced chain which is the main usecase, first we need to integrate it into our Bitcore / SPV libs though to set this test up - once this is done we will be publishing various Bitcore libs to the official DashPay github soon as we're building a lot of the Evolution functionality on there.
 
  • Like
Reactions: nmarley

UdjinM6

Official Dash Dev
Dash Core Team
Moderator
May 20, 2014
3,637
3,536
1,183
Another simple example is https://github.com/UdjinM6/node-x11-hash/blob/master/test/test.js :rolleyes:
...
It occurred to me that "the Dash blockchain" could be considered test vectors, but it gets complicated as to which values should be hashed, and in what order should they be concatenated, endianness, etc.
...
Well, there is no need to over-complicate things:
Code:
dash-cli getblockheader 000007d91d1254d60e2dd1ae580383070a4ddffa4c64c2eeb4a2f9ecc0414343 false
;)
 
  • Like
Reactions: nmarley

nmarley

Active Member
Jun 28, 2014
366
424
133
The ObjC X11 hash implementation has been live for a while in the iOS wallet but the JS version was just completed and currently reviewing it.

Currently the JS version tests are pretty basic https://github.com/QuantumExplorer/x11-hash-js/blob/master/test/test.js but the best test will be validating the block headers up through a synced chain which is the main usecase, first we need to integrate it into our Bitcore / SPV libs though to set this test up - once this is done we will be publishing various Bitcore libs to the official DashPay github soon as we're building a lot of the Evolution functionality on there.
Yes, yes, perfect! Thank you.



Well, there is no need to over-complicate things:
Code:
dash-cli getblockheader 000007d91d1254d60e2dd1ae580383070a4ddffa4c64c2eeb4a2f9ecc0414343 false
;)
This is *exactly* what I was searching for. Wow. Took a while to get the specifics correct in C, but was able to hash the header (converted to binary), reverse the result and hex-encode to get this exact string. Perfect.

We outta give you a medal or something, because I don't know how *any* of the Dash projects would survive without you.



I'll probably use the string examples from above along with the Dash checkpoint blocks found in chainparams.cpp to create test vectors for my own use, and any future ports.

Cheers all!
 

AndyDark

Well-known Member
Sep 10, 2014
353
705
163
Another simple example is https://github.com/UdjinM6/node-x11-hash/blob/master/test/test.js :rolleyes:


Well, there is no need to over-complicate things:
Code:
dash-cli getblockheader 000007d91d1254d60e2dd1ae580383070a4ddffa4c64c2eeb4a2f9ecc0414343 false
;)
@UdjinM6 & @QuantumExplorer - The major issue is actually the x11 JS performance in browsers compared to NodeJS, it's under half the performance in Chrome and like 10% the performance in Mozilla.

I was able to get 30+% improvement in Node by refactoring forward-for loops to reverse-while loops (which use less instructions) but in Mozilla this totally kills performance (unexpectedly, and probably Mozilla is converting backwards filled arrays to sparse arrays).

So then i tried forward while loops and some allocation reduction which makes the improvement more balanced with Mozilla and Node up and Chrome just a bit improved, results below.

Top: Chrome, Midlle: Firefox, Bottom: NodeJS
Left/Right: before/after optimize

upload_2016-7-25_0-35-29.png

I pushed the browser benchmark: https://github.com/andyfreer/x11-hash-js/commit/00d82f94387ae057b4edf23d911729030dae7ddb - but before/after tests need to be run consecutively because results differ a lot in the browser (probably depends what's running/ whether the browser thread's core is turboed)

I will push what I did tonight tomorrow probably but this needs some attention we should probably setup some bounties or something to optimize this further from the remaining budget.

EDIT: I pushed the optimization for the shared libs which were the low-hanging fruit https://github.com/QuantumExplorer/x11-hash-js/commit/7428675fc103857e87b36b782523388c2841d25e
 
Last edited:

QuantumExplorer

Active Member
Core Developer
Aug 20, 2014
126
161
93
@andy Cool that you found those improvements, well done! Even though I knew while is slightly faster than for loops in javascript, I didn't realize it could have such an impact.

In chrome at least 60-70% (didn't do the math) seems to be going to groestl, care to replace all the for loops there and see what happens?

I have a flight tmr and am busy tonight otherwise I would do it myself. (or you can wait for me to do it when I have time).
 
Last edited:

AndyDark

Well-known Member
Sep 10, 2014
353
705
163
@QuantumExplorer thanks, i will definitely put more time into it, this week is pretty busy though.

There's optimization we can also do with allocations too. The problem is with JavaScript being JavaScript, the different browser runtimes use different heuristics so we just need to make sure we get balanced performance between the major browsers (and e.g. how they handle dynamic memory allocation).

I will look into it some more and add Safari and IE to the testing too when I get more time for it, there's no major rush, the other Evo projects are more pressing right now.
 
  • Like
Reactions: chenriquelira