difficulty.py

"""Difficulty: calculate or check the PoW difficulty (preceding null bits) of an input"""

from hashlib import new
from sys import argv


def calculate(hash: bytes, bigendian: bool = True) -> int:
    """Calculate the difficulty (number of preceding null bits)."""
    # prepare variables
    number = int.from_bytes(hash, byteorder = 'big' if bigendian else 'little')
    length = len(hash)
    trailing_bits = 0

    # shift off bits until a null result is achieved
    while number != 0 and trailing_bits < length * 8:
        number = number >> 1
        trailing_bits += 1

    # difficulty achieved is the preceeding null bits
    return length * 8 - trailing_bits

def calculate_linear(hash: bytes, bigendian: bool = True) -> int:
    """Calculates the difficulty as the expected average number of tries."""
    return 2**calculate(hash, bigendian)

def calculate_query_bytes(target: bytes, hash_len: int) -> int:
    """Calculates the expected number of tries to find a hash containing the
        target sequence of bytes.
    """
    target_len = len(target)
    permutations = hash_len - target_len + 1
    return 2**(target_len*8)/permutations

def check(diff: int, hash: bytes, bigendian: bool = True) -> bool:
    """Checks if a hash meets the minimum difficulty threshold (preceeding null bits)."""
    # prepare variables
    number = int.from_bytes(hash, byteorder='big' if bigendian else 'little')
    length = len(hash)

    # raise exception if difficulty is impossible to achieve
    if diff > length * 8:
        raise Exception('Difficulty cannot exceed bit length of input')

    # shift off all but {diff} preceding bits
    preceding_bits = number >> (length * 8 - diff)

    # it meets the difficulty if preceding bits are 0
    return preceding_bits == 0


def license():
    """Copyleft (c) 2022 k98kurz

        Permission to use, copy, modify, and/or distribute this software
        for any purpose with or without fee is hereby granted, provided
        that the above copyleft notice and this permission notice appear in
        all copies.

        THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
        WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
        WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
        AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
        CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
        OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
        NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
        CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
    """
    return license.__doc__


def usage(name):
    print('Calculate difficulty of a given hash/value or check if it reaches a threshold.')
    print(f'usage: {name} [check:{{number}}|calc|linear|query] [hash:{{hashlib_algo}}|hex|str] [input_string] [bigendian=True]')
    print(f'\toperators:')
    print(f'\t\tcalc\t\tcalculate the number of preceding null bits of the given hash')
    print(f'\t\tlinear\t\tcalculate the average expected number of tries of the given hash')
    print(f'\t\tquery\t\tcalculate the average expected number of tries for a 32 byte hash containing the input_string')
    print(f'\tmodes:')
    print(f'\t\thash:{{hashlib_algo}}\thash the input_string before running the operation')
    print(f'\t\t\thash mode is not available for the query operation')
    print(f'\t\thex\t\tinterpret the input_string as hexadecimal')
    print(f'\t\tstr\t\tinterpret the input_string as a utf-8 string')
    print(f'\tbigendian\t(bool) the endianess for byte interpretation is big or little')
    print(f'\texamples:')
    print(f'\t\t`{name} check:8 hex 0001` checks if the hex string 0001 has 8 preceding null bits; should return `pass`')
    print(f'\t\t`{name} check:1 hash:sha256 1234` checks if the hex string 0001 has 8 preceding null bits; should return `pass`')
    print(f'\t\t`{name} calc hex 0f` calculates the number of preceding null bits in the hex string 0f; should return 4')
    print(f'\t\t`{name} linear hex 0f` calculates the expected number of tries to get the number of preceding null bits in the hex string 0f; should return 16')
    print(f'\t\t`{name} query str X` calculates the expected number of tries to find a hash containing the hex string 0f; should return 8.0')


def main(args):
    """Main function for invoking as cli tool."""
    if len(args) < 4:
        return usage(args[0])

    # parse arguments
    op = args[1].split(':')
    mode = args[2].split(':')
    input = args[3]
    bigendian = True if len(args) < 5 or args[4] in ('True', 'true', '1') else False

    if len(op) == 1:
        # calculate or query
        if op[0] in ('calc', 'linear'):
            if len(mode) == 1:
                # default mode, i.e. no hashing
                input = bytearray.fromhex(input) if mode[0] == 'hex' else bytes(input, 'utf-8')
                print(calculate_linear(input, bigendian) if op[0] == 'linear' else calculate(input, bigendian))
            else:
                # hashing mode
                if 'shake' in mode[1]:
                    input = new(mode[1], bytes(input, 'utf-8')).digest(len(input))
                else:
                    input = new(mode[1], bytes(input, 'utf-8')).digest()
                print(calculate_linear(input, bigendian) if op[0] == 'linear' else calculate(input, bigendian))
        elif op[0] == 'query':
            if len(mode) == 1:
                # default mode, i.e. no hashing
                input = bytearray.fromhex(input) if mode[0] == 'hex' else bytes(input, 'utf-8')
                print(calculate_query_bytes(input, 32))
            else:
                print('error: hashing mode not available for query operation')
    else:
        # difficulty checking op
        if len(mode) == 1:
            # default mode, i.e. no hashing
            input = bytearray.fromhex(input) if mode[0] == 'hex' else bytes(input, 'utf-8')
            print('pass' if check(int(op[1]), input, bigendian) else 'fail')
        else:
            # hashing mode
            if 'shake' in mode[1]:
                input = new(mode[1], bytes(input, 'utf-8')).digest(len(input))
            else:
                input = new(mode[1], bytes(input, 'utf-8')).digest()
            print('pass' if check(int(op[1]), input, bigendian) else 'fail')


# cli
if __name__ == '__main__':
    main(argv)