lxr

README

LXRHash

Lookup XoR Hash

LXRHash uses an XOR/Shift random number generator coupled with a lookup table of randomized sets of bytes.
The lookup table consists of any number of 256 byte tables combined and sorted in one large table. We then index into this large table to effectively look through the entire combination of tables as we translate the source data into a hash.

All parameters are specified. The size of the lookup table (in numbers of 256 byte tables), the seed used to shuffle the lookup table, the number of rounds to shuffle the table, and the size of the resulting hash.

LXRHash has some interesting qualities. Very large lookup tables will blow the memory caches on pretty much any processor or computer architecture. The size of the table can be increased to counter improvements in memory caching.
The number of bytes in the resulting hash can be increased for more security (greater hash space), without significantly more processing time. Note, while this approach can be fast, this implemenation isn't. The use case is aimed at Proof of Work (PoW), not cryptographic hashing.

The Lookup

The look up table has equal numbers of every byte value, and shuffled deterministically. When hashing, the bytes from the source data are used to build offsets and state that are in turn used to map the next byte of source.

In developing this hash, the goal was to produce very randomized hashes as outputs, with a strong avalanche response to any change to any source byte. This is the prime requirement of PoW. Because of the limited time to perform hashing in a blockchain, collision avoidence is important but not critical. More critical is ensuring engineering the output of the hash isn't possible.

LRXHash was origionally developed as a thought experiment, yet the result yeilds some interesting qualities.

• the lookup table can be any size, so making a version that is ASIC resistant is possible by using very big lookup tables. Such tables blow the processor caches on CPUs and GPUs, making the speed of the hash dependent on random access of memory, not processor power. Using 1 GB lookup table, a very fast ASIC improving hashing is limited to about ~10% of the computational time for the hash. 90% of the time hashing isn't spent on computation but is spent waiting for memory access.
• at smaller lookup table sizes where processor caches work, LXRHash can be modified to be very fast.
• LXRHash would be an easy ASIC design as it only uses counters, decrements, XORs, and shifts.
• the hash is trivially altered by changing the size of the lookup table, the seed, size of the hash produced. Change any parameter and you change the space from which hashes are produced.
• The Microprocessor in most computer systems accounts for 10x the power requirements of memory. If we consider PoW on a device over time, then LXRHash is estimated to reduce power requirements by about a factor of 10.

While this hash may be reasonable for use as PoW in mining on an immutable ledger that provides its own security, not nearly enough testing has been done to use as a fundamental part in cryptography or security. For fun, it would be cool to do such testing.

Documentation

Overview

Copyright (c) of parts are held by the various contributors Licensed under the MIT License. See LICENSE file in the project root for full license information.

Copyright (c) of parts are held by the various contributors Licensed under the MIT License. See LICENSE file in the project root for full license information.

Copyright (c) of parts are held by the various contributors Licensed under the MIT License. See LICENSE file in the project root for full license information.

Index

• Constants
• type LXRHash
  • func (lx *LXRHash) GenerateTable()
  • func (lx LXRHash) Hash(src []byte) []byte
  • func (lx *LXRHash) Init(Seed, MapSizeBits, HashSize, Passes uint64)
  • func (lx *LXRHash) Log(msg string)
  • func (lx *LXRHash) ReadTable()
  • func (lx *LXRHash) Verbose(val bool)
  • func (lx *LXRHash) WriteTable(filename string)

Constants

const (
	Seed        = uint64(0xFAFAECECFAFAECEC) // The seed defines a "hash space".
	MapSizeBits = uint64(30)                 // Default table size
	Passes      = uint64(5)                  // Default number of shuffles of the tables
	HashSize    = uint64(256)                // Default hash size.
)

Default Seed

Types

type LXRHash

type LXRHash struct {
	ByteMap     []byte // Integer Offsets
	MapSize     uint64 // Size of the translation table
	MapSizeBits uint64 // Size of the ByteMap in Bits
	Passes      uint64 // Passes to generate the rand table
	Seed        uint64 // An arbitrary number used to create the tables.
	HashSize    uint64 // Number of bytes in the hash
	// contains filtered or unexported fields
}

func (*LXRHash) GenerateTable

func (lx *LXRHash) GenerateTable()

GenerateTable Build a table with a rather simplistic but with many passes, adequately randomly ordered bytes. We do some straight forward bitwise math to initialize and scramble our ByteMap.

func (LXRHash) Hash

func (lx LXRHash) Hash(src []byte) []byte

func (*LXRHash) Init

func (lx *LXRHash) Init(Seed, MapSizeBits, HashSize, Passes uint64)

Init() We use our own algorithm for initializing the map struct. This is an fairly large table of byte values we use to map bytes to other byte values to enhance the avalanche nature of the hash as well as increase the memory footprint of the hash.

Seed is a 64 bit starting point MapSizeBits is the number of bits to use for the MapSize, i.e. 10 = mapsize of 1024 HashSize is the number of bits in the hash; truncated to a byte bountry Passes is the number of shuffles of the ByteMap performed. Each pass shuffles all byte values in the map

func (*LXRHash) Log

func (lx *LXRHash) Log(msg string)

Log is a wrapper function that only prints information when verbose is enabled

func (*LXRHash) ReadTable

func (lx *LXRHash) ReadTable()

ReadTable When a lookup table is on the disk, this will allow one to read it.

func (*LXRHash) Verbose

func (lx *LXRHash) Verbose(val bool)

Verbose enables or disables the output of progress indicators to the console

func (*LXRHash) WriteTable

func (lx *LXRHash) WriteTable(filename string)

WriteTable When playing around with the algorithm, it is nice to generate files and use them off the disk. This allows the user to do that, and save the cost of regeneration between Lxrhash runs.