lxr

README

LXRHash

Lookup XoR Hash: First RAM Hash Algorithm

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 shuffled into one large byte lookup table. We then index into this large table to translate the state built up while hashing into deterministic but random byte values.

Using a 1GB lookup table results in a RAM Hash PoW algorithm that spends over 90% of its execution time waiting on memory (RAM) than it does computing the hash. This means far less power consumption, and ASIC and GPU resistence. The ideal platform for PoW using a RAM Hash is a Single Board Computer like a Raspberry PI 4 with 2GB of memory.

All parameters are specified. The size of the lookup table is specified in bits for the index, the seed used to shuffle the lookup table, the number of rounds to shuffle the table, and the size of the resulting hash.

Because the LXRHash is parameterized in this way, as computers get faster and larger memory caches, the LXRHash can be set to use 2GB or 16GB or more. The Memory bottleneck to computation is much easier to manage than attempts to find computational algorithms that cannot be executed faster and cheaper with custom hardware, or specialty hardware like GPUs.

So to quickly interate over LXRHash features:

• 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
• LXRHash can be fast by using small lookup tables
• ASIC implementations for small tables would be very easy and very fast
• LXRHash only uses iterators (for indexing) shifts, binary ANDs and XORs, and random byte lookups
• The use case for LXRHash is 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.

Testing

To run the LXRHash benchmark test:

cd testing
go test

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
• func AbortSettings(target uint64) (abortByte int, abortVal uint8)
• func GetUserTablePath() (string, error)
• func Release(hash *LXRHash)
• type HashParallelItem
• type LXRHash
  • func Init(seed, bitsize, hashsize, passes uint64) *LXRHash
  • func (lx LXRHash) BenchmarkFlatHash(ctx context.Context, duration time.Duration, goroutines uint) (uint64, time.Duration)
  • func (lx LXRHash) BenchmarkHash(ctx context.Context, duration time.Duration, goroutines uint) (uint64, time.Duration)
  • func (lx LXRHash) FlatHash(src []byte) []byte
  • func (lx *LXRHash) GenerateTable()
  • func (lx LXRHash) Hash(src []byte) []byte
  • func (lx LXRHash) HashParallel(base []byte, batch [][]byte) [][]byte
  • func (lx *LXRHash) Init(Seed, MapSizeBits, HashSize, Passes uint64)
  • func (lx *LXRHash) InitFromPath(Seed, MapSizeBits, HashSize, Passes uint64, TablePath string) (string, error)
  • 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

Functions

func AbortSettings

func AbortSettings(target uint64) (abortByte int, abortVal uint8)

AbortSettings indicated the proper settings to abort if a hash is found to be less than the target. Aborting early can save a few hash table accesses

func GetUserTablePath

func GetUserTablePath() (string, error)

func Release

func Release(hash *LXRHash)

Release releases a singleton. If all references to the singleton have been released, the singleton is destroyed and can be garbage collected

Types

type HashParallelItem

type HashParallelItem struct {
	// contains filtered or unexported fields
}

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
}

LXRHash holds one instance of a hash function with a specific seed and map size

func Init

func Init(seed, bitsize, hashsize, passes uint64) *LXRHash

Init provides access to shared instances of LXRHash without having to instantiate multiple bytemaps. Two separate calls to Init() will result in a reference to the same object.

func (LXRHash) BenchmarkFlatHash

func (lx LXRHash) BenchmarkFlatHash(ctx context.Context, duration time.Duration, goroutines uint) (uint64, time.Duration)

BenchmarkHash will run a benchmark for the specified duration using the FlatHash function. Returns the number of hashes calculated and the real duration of the benchmark. If no goroutines are specified it will use the total number of available cores.

func (LXRHash) BenchmarkHash

func (lx LXRHash) BenchmarkHash(ctx context.Context, duration time.Duration, goroutines uint) (uint64, time.Duration)

BenchmarkHash will run a benchmark for the specified duration using the regular Hash function. Returns the number of hashes calculated and the real duration of the benchmark. If no goroutines are specified it will use the total number of available cores.

func (LXRHash) FlatHash

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

FlatHash takes the arbitrary input and returns the resulting hash of length HashSize Does not use anonymous functions

func (*LXRHash) GenerateTable

func (lx *LXRHash) GenerateTable()

GenerateTable generates the bytemap. Initializes the map with an incremental sequence of bytes, then does P passes, shuffling each element in a deterministic manner.

func (LXRHash) Hash

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

Hash takes the arbitrary input and returns the resulting hash of length HashSize

func (LXRHash) HashParallel

func (lx LXRHash) HashParallel(base []byte, batch [][]byte) [][]byte

HashParallel takes the arbitrary input and returns the resulting hash of length HashSize. The batch must have at least one entry. The base is prefixed to all items in the batch.

func (*LXRHash) Init

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

Init initializes the hash with the given values

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

Panics when MapSizeBits is < 8 and on other error conditions

func (*LXRHash) InitFromPath

func (lx *LXRHash) InitFromPath(Seed, MapSizeBits, HashSize, Passes uint64, TablePath string) (string, error)

Initialize the hash with the given values, reading the hash table from the specified path

Seed - a 64-bit starting value MapSizeBits - size of the map as an exponent of 2, i.e., 10 -> map size of 2 ^ 10 = 1024; between 8 and 34 bits inclusive. HashSize - number of bits in the hash, truncated to a byte boundary Passes - number of shuffles of the ByteMap TablePath - the file system path of the directory which holds hash table files

Because hash table files can be large, sharing them between applications is desirable. Suggested shared hash table paths:

Windows: %ProgramData%/LXRHash
macOS:   /Library/Application\ Support/org.pegnet.LXRHash
Linux:   /var/lib/LXRHash
BSD:     /var/db/LXRHash

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 attempts to load the ByteMap from disk. If that doesn't exist, a new one will be generated and saved.

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 caches the bytemap to disk so it only has to be generated once