I took a closer look at the Hashing algorithm today, particularly when combined with the data we input. For every iteration, the miner calculates the hash of OPRHash | nonce, meaning the first 32 bytes are always the same. The Hashing algorithm contains two steps, the first of which just runs across the entire range of input in order.

For every call to Hash from a miner, the first 32 iterations of step 1 will always be the same and yield the same data. So I decided to see what happens if you cache the values from step1 up until that point, continuing with just the nonce, and discovered it's a moderate speed improvement of 12%:

BenchmarkHash-8       	  300000	      6077 ns/op	     351 B/op	       3 allocs/op
BenchmarkPreCache-8   	  300000	      5370 ns/op	     352 B/op	       3 allocs/op

The pre-caching code is available here: https://github.com/WhoSoup/LXRHash/blob/a3b83647ad54f924cf0f18d457c2eeee29332ce0/lxrhash.go#L58-L105

The test file contains the two benchmarks as well as a test that checks whether the two different versions are the same: https://github.com/WhoSoup/LXRHash/blob/factomize-precache/lxrhash_test.go

An easy fix would be for miners to hash nonce | OPRHash instead. Precaching the millions of nonces is not faster than just calculating the hash for it, but putting the nonce first has a cascading effect oprhash. Alternatively, run step 1 from highest to lowest index.

So the Idea here is to make the state run through the ByteMap and build the state with (mostly) a fixed number of bytes and ByteMap lookups.

This will work better for PoW, less so for general cryptographic hashing.

Implemented in this branch as LXRHash2

The cost of creating a new closure for every call to Hash() while mining ends up being a significant amount of around 5.5 percent. My benchmarking:

BenchmarkHash/hash_old-8         	   20000	     98505 ns/op	     351 B/op	       2 allocs/op
BenchmarkHash/hash_2-8           	   20000	     92955 ns/op	     351 B/op	       2 allocs/op
BenchmarkHash/hash_old_again-8   	   20000	     98105 ns/op	     351 B/op	       2 allocs/op
BenchmarkHash/hash_2_again-8     	   20000	     92805 ns/op	     351 B/op	       2 allocs/op

I've written Benchmarking and comparison tests that can be pulled from: https://github.com/WhoSoup/LXRHash/tree/41a2c34e6dde097a4b92c4d817a755abb3fcd699

There's a unit test in there that ensures both the old and the new function produce identical hashes, so functionally they're equivalent. The only thing changed is that the closures have been refactored out.

I'm also going to submit a PR with a cleaned up refactored version.

Create a PegNet daemon to provide pricing information, and tPNT balances for addresses.

Need file headers to conform to best practices using MIT License

A few updates to the sim miner for performance testing

The goal here is to be able to use any cryptographic hash for a blockchain, but only replace how PoW is measured.

In traditional blockchains, PoW is generally calculated by taking the leading bits of the hash and considering the smaller integer value of those bits as being a higher difficulty. PegNet considers the higher integer value of those bits as being a higher difficulty, but this isn't too different.

By adding two functions, LxrPoW() and PoW(), the LXRHash can be used with any Hash function to do a more complex PoW calculation that makes PoW most reasonable for CPU mining.

LxrPoW() makes computation of PoW CPU hard
PoW() takes a hash of a higher integer value can compresses it to a uniform 8 bytes.

The compression of PoW() first counts how many of the leading bytes have a value of 0xFF. If the difficulty is defined where the leading bit is 0 and the last bit is 63, then:

Bits 0-3 is the count of leading 0xFF
Bits 4-63 are the following bits of the hash

This allows Difficulty to be represented by 60 to 180 bits of a hash in 64 bits.

When using LXRHash concurrently the Golang race condition detector will report something like this:

WARNING: DATA RACE
Write at 0x0000016da3c0 by goroutine 79:
  github.com/pegnet/LXRHash.(*LXRHash).Hash()
      /home/paul/go/pkg/mod/github.com/pegnet/!l!x!r![email protected]/lxrhash.go:101 +0x48b

Previous write at 0x0000016da3c0 by goroutine 78:
  github.com/pegnet/LXRHash.(*LXRHash).Hash()
      /home/paul/go/pkg/mod/github.com/pegnet/!l!x!r![email protected]/lxrhash.go:101 +0x48b

Which points to this assignment: https://github.com/pegnet/LXRHash/blob/master/lxrhash.go#L101
While I understand it doesn't have any impact on the LXR hash produced, it's annoying to have this warning shows up when testing my own software that uses LXR hash. Could this be somehow fixed so that this false-positive doesn't show up when testing race conditions? Thank you.

While analyzing fatd ram allocation, I noticed that LXR sometimes eats up 2GB instead of the expected 1GB, with 1 GB being used for the bytemap (expected) and 1 GB being used in the ioutil.ReadFile buffer (not expected). This allocated system memory then keeps sticking around sometimes, but other times it gets released.

We should investigate the behavior of this further and possibly instead of reading the entire file into memory via ReadFile, we can read it in chunks in order to avoid the additional allocation.

Hashes and ciphers usually have known answer tests associated with the reference implementation.

This provides a canonical digest for anyone writing their own implementation of LXR Hash to check against.

I would suggest we default to 30 bits (1 GB)
Remove references to a particular application (PegNet) from the code and comments.

Will not be a part of the main branch. Testing only.

Set up LXRHash on rpi.
Raspberry pi 3 model A +
4.14.98-v7+ Raspian OS
armv71 chip

Benchmark test fails with “overflows int”,

(Excuse the poor photo above ^ took a pic of it running on my tv :) )

This seems to be an issue generally with Go running on 32 bit systems. Here are some related issues:
https://stackoverflow.com/questions/26185795/int-overflow-on-32-bit-systems
thanos-io/thanos#365
golang/go#23086

I haven't worked with GO, so this issues beyond me.

The algorithm was needlessly complex.
Added more byte accesses to do a better job of blowing the processor caches
Tests of 8 bits of map vs 33 bits of bytemap demonstrate a 90 percent impact on memory access, 10 percent on execution.

The ReadTable function currently expects to write a large file to the user's home directory. This interface should change (or a new interface added) to allow for the specification of a different directory. This makes sense for several reasons:

1. If LXRHash is used in a daemon or service, there may not be a home directory to use.
2. It would be nice to share these files between all users on a system.
3. The user may wish to store the file on a faster medium than that which stores the user's home directory.

I'm happy to submit a PR if one is welcome.

Review of the shifts demonstrated some value in ensuring each byte accessed in sequence plays a role in selecting the next byte in sequence. This involves paying attention of where the byte is applied in s1, s2, and as. It also involves how they are used in indexing the ByteMap.

This issue adjusts the shifts and adds some documentation.

We did a reorg and removed the default instance of the LXRHash, and this broke the unit tests.

Other fixes include added the go mod support to create the vendor package, because we need to use a particular version of the factom go library.

Added vendor to the .gitignore

Put the set of configuration variables for the unit tests in the unit test directory. It is hard on automated testing to use 1GB ByteMaps

Added code to place the ByteMap files in a .lxrhash directory off of the home directory of the user.

Currently the LXRHash creates the ByteMap file in the current directory of any application when it is running and it uses the LXRHash. This is obviously not a good approach.

However, this approach too could be better, so it remains a subject of interest.

tl;dr: if you want to prevent a high cpu cache hit rate with a very small amount of space, we need to re-order the input

I wanted to test the effect of CPU cache sizes on the performance of LXR Hash. The cache line of i7 processors is 64 bytes big, meaning it caches that much sequential memory in one request.

For the LRU cache, I used: https://github.com/hashicorp/golang-lru

My methodology:

1. I saved the index of every single request to ByteMap
2. I played through the indexes and got the specific cache line by floor(index / 64)
3. If that cache line was present in the cache, it counts as a hit
4. If that cache line is not present, it is added.
5. Divide the number of hits by the total requests to ByteMap

It turns out that when performing a mining run of 1000 sequential nonces appended to a base, the cache hit rate is about 50%, and this is true for a cache size of only 128 KB, meaning that CPUs can potentially fit that into L2 cache opposed to L3, and you can speed up the algorithm as much as 50% with a very small amount of cache. (please note that the 50% hit rate holds true for 1,000 runs as it does for 100,000 runs)

Using random input, the cache hit rate is close to zero, growing a fraction the larger the cache is as you would expect.

So I went a step further and implemented a pseudo-random function that shuffles the input in a deterministic manner. This resulted in a similar cache hit rate as the random input while performing a mining run.

This behavior is backed up by empirical evidence:

BenchmarkHash/random_input-8         	   10000	    157108 ns/op	     288 B/op	       2 allocs/op
BenchmarkHash/run_input-8            	   20000	     98155 ns/op	     288 B/op	       2 allocs/op

There's a roughly 40% speed increase on sequential data opposed to random data. This can be accomplished using a very small amount of cache.

For our specific purposes, this can also be avoided by, yet again, running faststep and step backward (since the different nonce will have a cascading effect on the static opr hash). For a more generalized solution, the input can be pseudo-shuffled in an algorithm like:

	for i := 0; i < len(src); i++ {
		swp := i*int(src[i]) + (len(src)-1-i)*int(src[(len(src)-1-i)%len(src)])
		swp = swp % len(src)
		src[i], src[swp] = src[swp], src[i]
	}

(though ideally something that produces a bit better results)

The LXRHash had a few errors introduced by the removal of the closures. On further contemplation and research, I believe improvements in speed may have been due to not using the hs[] slice in the computation of the hash in step.

In any event, I think the code became much harder to deal with due to needing to pass the state in and out.

Also adding fixes to the nonce hashing issue, some git lint, and other fixes.

Instead of calling panic(), the Init, ReadTable and WriteTable functions in table.go should return the error. Using LXRHash from a larger program is made more difficult because of these panic() calls.

I'm happy to submit a PR. I thought I should open this discussion to make sure that others agree.