SMIP: GPU-POST Phase II (WIP)

[0xgfgc]

Motivation

Tortoise beacon VRF.

Algorithm Outline

Phase I: create the PoST initialization but tweak it so that for every scrypt output label before truncating the 256-bit output into ℓ ≤ 256 bits (and storing to disk these bits) we compare the full 256 bits against 256-bit constant parameter D and if this label is smaller than than D then we store the index of this label (if we already found label smaller than D and we already stored its index, then we simply overwrite it with the new index – I’m assuming that the index is 64-bit words and therefore the write operation is atomic, I don’t think that we need index whose size is more than 64-bit because even if we store 1 bit of the scrypt output per index the total storage would be more than 2 million terabytes).

Phase II: if we didn’t find any label smaller than D in phase1, then we continue with a “dry” run of the initialization that continue from the last index onwards but doesn’t write anything to disk (so there’s no need for it to truncate the scrypt outputs), and when it find a label smaller than D it stores its index and terminates.

API Design

1. Add 2 config options scryptPositions() options param: 1. Compute leafs. 2. Compute PoW. One of these config options should be turned on by api client.

enum {
    COMPUTE_LEAFS = 1 << 0,
    COMPUTE_POW = 1 << 1,
};

Motivation

API clients can just stop calling the method with the 2nd option set, after the POW was solved and in case the algorithm needs to progress to phase II (described above) then the api client will just call the method with the 2nd config option on as label computation is not needed.

2. Add these new method params:

uint64_t D, // Target D for the POW computation
uint32_t options, // compute leafs and or compute pow
uint64_t idx_solution, // index of output where output < D if POW compute was on

3. Implementation

   • If option 1 is on then a compute iteration (an api method execution on the gpu) computes the labels and stores them in the output buffer (the current lib functionality).
   • If option 2 is on, then the comparison with D is executed when a has for an index is computed, and an index that solves the POW is outputted by the API. (idx_solution method output param).

4. API method after the changes above:

int scryptPositions(
    const uint8_t *id,          // 32 bytes
    uint64_t start_position,    // e.g. 0
    uint64_t end_position,      // e.g. 49,999
    uint32_t hash_len_bits, // (1...256) for each hash output, the number of prefix BIYS to copy into the buffer
    const uint8_t *salt,        // 32 bytes
    uint8_t *out,               // memory buffer large enough to include hash_len_bits * number of requested hashes
    uint32_t N,             // scrypt N
    uint32_t R,             // scrypt r
    uint32_t P,             // scrypt p

    uint64_t D,                             // Target D for the POW computation
    uint32_t options,           // compute leafs and or compute pow
    uint64_t idx_solution            // index of output where output < D if POW compute was on
);

API usage pattern

1. Start calling scryptPositions() with both options set so both leaf computation and D comparison are made.
2. If a solution is found before all leaves were computed in an iteration then store idx_solution and unset the POW option from future calls to scryptPositions(). 3.if all leaves computed and a solution was not found then continue calling with larger indexes with only POW option set until a solution is found.