Skip to content

Uncompress blake3 inputs on-demand #90

@lucidLuckylee

Description

@lucidLuckylee

The current version of the blake3 hash function can at most hash 640 inputs. Several chunk scripts already use more than that even with 29bit limbs. For the hash function these 29bit stack entries would have to be serialized to bytes roughly quadrupling the number of stack elements meant to be hashed. This approach seems infeasible.

Therefore, we aim to store all u32 in a single stack element either by:
a) Geting rid of the u8_xor_table and facilitate u32_xor with another (yet to be found) approach that works directly on 32 bit stack elements.
b) Serializing 32 bit stack elements to bytes on demand ONLY in the hash function as it seems to be the only script that requires bytes (in particular because of the xor operation).

TODOs in case of b):

  • Change blake_3_var_length to serialize message (input) values to bytes on-demand only when they are used in the compression function
  • Change blake3_var_length to keep the inputs on the stack
  • Implement u32 operations (u32_add, u32_sub, etc.) on 32 bit stack elements using Bitcoins arithmetic opcodes in combination with e.g. OP_SIZE to handle overflow (note that Bitcoins arithmetic opcodes are signed and we need unsigned operations)
  • Optional: Explore 32bit limbs for Field elements (as this might not be worth)

These change should allow us to hash 636 256 32 (or 29) bit stack elements with blake3_var_length

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions