dgb-wallet/packages/p2p/native/gcs.c

// BIP158 compact-filter matching, compiled to WebAssembly alongside the
// proof-of-work hashes (same module, dgbpow.wasm).
//
// Why native: a wallet scan tests every watched script (a few thousand
// with gap limits 200/100 over ~10 derivation profiles) against every
// block filter, and the SipHash key is per block, so nothing can be
// precomputed across blocks. In JavaScript that is ~3 µs per script
// even with int32 lanes; here it is well under 100 ns, which turns a
// one-year scan (2.1M DigiByte blocks) from hours into minutes.
//
// Interface (pointer-free for the caller, fixed static buffers):
//   gcs_scripts_ptr()  → byte area the JS side packs the scripts into
//   gcs_offsets_ptr()  → uint32[n+1] start offsets of each script
//   gcs_set_count(n)   → declares how many scripts are uploaded
//   gcs_key_ptr()      → 16-byte SipHash key (block hash LE, first 16 bytes)
//   gcs_filter_ptr()   → the GCS body (after the varint N), ≤ GCS_FILTER_BYTES
//   gcs_match(n_set, body_len, want_all)
//        → number of matching scripts (0 = none); with want_all=0 stops
//          at the first match. Matching script indices are written to
//          gcs_matches_ptr() (uint32[]), in no particular order.
//   gcs_limits_ptr()   → uint32[3] { max scripts, script bytes, filter bytes }
//
// Build: see build.sh (emscripten in docker).

#include <stdint.h>
#include <string.h>

#define EXPORT __attribute__((used, visibility("default")))

#define GCS_MAX_SCRIPTS 65536
#define GCS_SCRIPT_BYTES (4u * 1024 * 1024)
#define GCS_FILTER_BYTES (2u * 1024 * 1024)
#define GCS_SET_CAP      (1u << 20)   /* decoded set values kept for binary search */
#define GCS_P 19
#define GCS_M 784931ull

static uint8_t  g_scripts[GCS_SCRIPT_BYTES];
static uint32_t g_offsets[GCS_MAX_SCRIPTS + 1];
static uint32_t g_count = 0;
static uint8_t  g_key[16];
static uint8_t  g_filter[GCS_FILTER_BYTES];
static uint32_t g_matches[GCS_MAX_SCRIPTS];
static uint64_t g_set[GCS_SET_CAP];
static uint32_t g_limits[3] = { GCS_MAX_SCRIPTS, GCS_SCRIPT_BYTES, GCS_FILTER_BYTES };

EXPORT uint8_t*  gcs_scripts_ptr(void) { return g_scripts; }
EXPORT uint32_t* gcs_offsets_ptr(void) { return g_offsets; }
EXPORT uint8_t*  gcs_key_ptr(void)     { return g_key; }
EXPORT uint8_t*  gcs_filter_ptr(void)  { return g_filter; }
EXPORT uint32_t* gcs_matches_ptr(void) { return g_matches; }
EXPORT uint32_t* gcs_limits_ptr(void)  { return g_limits; }
EXPORT void gcs_set_count(uint32_t n)  { g_count = n > GCS_MAX_SCRIPTS ? GCS_MAX_SCRIPTS : n; }

// ---- SipHash-2-4 (Bitcoin Core src/crypto/siphash.cpp semantics) ----
#define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b))))
#define SIPROUND do { \
    v0 += v1; v1 = ROTL(v1, 13); v1 ^= v0; v0 = ROTL(v0, 32); \
    v2 += v3; v3 = ROTL(v3, 16); v3 ^= v2; \
    v0 += v3; v3 = ROTL(v3, 21); v3 ^= v0; \
    v2 += v1; v1 = ROTL(v1, 17); v1 ^= v2; v2 = ROTL(v2, 32); \
  } while (0)

static inline uint64_t rd64(const uint8_t* p) {
  uint64_t v; memcpy(&v, p, 8); return v; // wasm is little-endian
}

static inline uint64_t siphash24(uint64_t k0, uint64_t k1, const uint8_t* m, uint32_t len) {
  uint64_t v0 = k0 ^ 0x736f6d6570736575ull;
  uint64_t v1 = k1 ^ 0x646f72616e646f6dull;
  uint64_t v2 = k0 ^ 0x6c7967656e657261ull;
  uint64_t v3 = k1 ^ 0x7465646279746573ull;
  uint32_t full = len & ~7u, i;
  for (i = 0; i < full; i += 8) {
    uint64_t w = rd64(m + i);
    v3 ^= w; SIPROUND; SIPROUND; v0 ^= w;
  }
  uint64_t t = ((uint64_t)(len & 0xff)) << 56;
  switch (len & 7) {
    case 7: t |= ((uint64_t)m[i + 6]) << 48; /* fallthrough */
    case 6: t |= ((uint64_t)m[i + 5]) << 40; /* fallthrough */
    case 5: t |= ((uint64_t)m[i + 4]) << 32; /* fallthrough */
    case 4: t |= ((uint64_t)m[i + 3]) << 24; /* fallthrough */
    case 3: t |= ((uint64_t)m[i + 2]) << 16; /* fallthrough */
    case 2: t |= ((uint64_t)m[i + 1]) << 8;  /* fallthrough */
    case 1: t |= ((uint64_t)m[i]);
  }
  v3 ^= t; SIPROUND; SIPROUND; v0 ^= t;
  v2 ^= 0xff;
  SIPROUND; SIPROUND; SIPROUND; SIPROUND;
  return v0 ^ v1 ^ v2 ^ v3;
}

// Decode the Golomb-Rice set (unary quotient, P-bit remainder,
// cumulative) into g_set. Returns the number of values decoded (short
// on a truncated body).
static uint32_t decode_set(uint32_t n_set, uint32_t body_len) {
  const uint8_t* buf = g_filter;
  uint32_t bits = body_len * 8, pos = 0, s;
  uint64_t last = 0;
  for (s = 0; s < n_set; s++) {
    uint64_t q = 0;
    while (pos < bits && ((buf[pos >> 3] >> (7 - (pos & 7))) & 1)) { q++; pos++; }
    if (pos + 1 + GCS_P > bits) return s;
    pos++;
    uint64_t r = 0; int k;
    for (k = 0; k < GCS_P; k++, pos++) r = (r << 1) | ((buf[pos >> 3] >> (7 - (pos & 7))) & 1);
    last += (q << GCS_P) | r;
    g_set[s] = last;
  }
  return s;
}

static inline int in_set(uint64_t v, uint32_t n) {
  uint32_t lo = 0, hi = n;
  while (lo < hi) {
    uint32_t mid = lo + ((hi - lo) >> 1);
    if (g_set[mid] < v) lo = mid + 1; else hi = mid;
  }
  return lo < n && g_set[lo] == v;
}

// Decode the set once (it is already sorted), then hash each script and
// binary-search its target. No sort of the script targets is needed,
// and a typical DigiByte block (tens of elements) is a 5-6 step search.
//   Returns -1 when the filter is beyond the static buffers (the caller
//   falls back to the JS matcher), never a silently partial answer.
EXPORT int32_t gcs_match(uint32_t n_set, uint32_t body_len, int32_t want_all) {
  if (g_count == 0 || n_set == 0) return 0;
  if (n_set > GCS_SET_CAP || body_len > GCS_FILTER_BYTES) return -1;
  uint32_t n = decode_set(n_set, body_len);
  if (n == 0) return 0;
  uint64_t k0 = rd64(g_key), k1 = rd64(g_key + 8);
  uint64_t F = (uint64_t)n_set * GCS_M;
  uint32_t i, found = 0;
  for (i = 0; i < g_count; i++) {
    uint64_t h = siphash24(k0, k1, g_scripts + g_offsets[i], g_offsets[i + 1] - g_offsets[i]);
    uint64_t target = (uint64_t)(((unsigned __int128)h * F) >> 64);
    if (in_set(target, n)) {
      g_matches[found++] = i;
      if (!want_all) return (int32_t)found;
    }
  }
  return (int32_t)found;
}