merkelize-airdrop

#!/usr/bin/env node

'use strict';

const assert = require('bsert');
const fs = require('bfile');
const Path = require('path');
const bio = require('bufio');
const pgp = require('bcrypto/lib/pgp');
const ssh = require('bcrypto/lib/ssh');
const base64 = require('bcrypto/lib/encoding/base64');
const pem = require('bcrypto/lib/encoding/pem');
const blake2b = require('bcrypto/lib/blake2b');
const sha256 = require('bcrypto/lib/sha256');
const merkle = require('bcrypto/lib/mrkl');
const random = require('bcrypto/lib/random');
const hkdf = require('bcrypto/lib/hkdf');
const AirdropKey = require('../lib/key');
const {PGPMessage, PGPPublicKey} = pgp;
const {SSHPublicKey} = ssh;

/*
 * Constants
 */

assert(process.argv.length > 2);

const PREFIX = Path.resolve(process.argv[2]);
const BUILD_DIR = Path.resolve(__dirname, '..', 'build');
const TREE_FILE = Path.resolve(__dirname, '..', 'build', 'tree.bin');
const TREE_JSON = Path.resolve(__dirname, '..', 'etc', 'tree.json');
const NONCE_DIR = Path.resolve(__dirname, '..', 'build', 'nonces');
const MAX_AIRDROP = 924800000 * 1e6;
const SUBTREE_LEAVES = 8;

// Max ciphertext size for RSA 1024
// PKCS1v1.5 is `klen - 2 * hlen - 2`
// meaning we only have a max of 62
// bytes to play around with. Our
// nonce is already 32 bytes, so our
// PRNG seed ends up being 30 bytes.
const SEED_SIZE = 30;

/*
 * Main
 */

async function main() {
  const hasher = new Hasher();
  const checksum = await hasher.hash();
  const leaves = hasher.leaves;

  console.log(
    'Wrote merkle tree with %d keys and %d leaves.',
    hasher.total,
    leaves.length
  );

  const root = hasher.hashTree();
  const reward = Math.floor(MAX_AIRDROP / (leaves.length + hasher.shares));

  console.log('Checksum: %s', checksum.toString('hex'));
  console.log('Tree Root: %s', root.toString('hex'));
  console.log('Leaves: %d', leaves.length);
  console.log('Keys: %d', hasher.total);
  console.log('Depth: %d', getDepth(leaves.length));
  console.log('Subdepth: %d', getDepth(SUBTREE_LEAVES));
  console.log('Faucet: %s', hasher.faucet);
  console.log('Shares: %s', hasher.shares);
  console.log('Reward: %d', reward);

  assert((leaves.length + hasher.shares) * reward <= MAX_AIRDROP);

  const json = JSON.stringify({
    checksum: checksum.toString('hex'),
    root: root.toString('hex'),
    leaves: leaves.length,
    keys: hasher.total,
    subleaves: SUBTREE_LEAVES,
    depth: getDepth(leaves.length),
    subdepth: getDepth(SUBTREE_LEAVES),
    faucet: hasher.faucet,
    shares: hasher.shares,
    reward,
    checksums: hasher.checksums.map(h => h.toString('hex'))
  }, null, 2);

  return fs.writeFile(TREE_JSON, json + '\n');
}

/*
 * Hasher
 */

class Hasher {
  constructor() {
    this.leaves = [];
    this.buckets = [];
    this.checksums = [];
    this.existing = new Set();
    this.total = 0;
    this.faucet = 0;
    this.shares = 0;

    for (let i = 0; i < 256; i++)
      this.buckets.push([]);
  }

  pushNonce(key, seed) {
    assert(key instanceof AirdropKey);
    assert(Buffer.isBuffer(seed));

    const bucket = key.bucket();
    const [nonce, newKey] = key.generate();

    key.applyNonce(nonce);

    const ct = key.encrypt(nonce, seed);

    this.buckets[bucket].push(ct);

    return newKey;
  }

  async hash() {
    await fs.remove(BUILD_DIR);
    await fs.mkdirp(NONCE_DIR, 0o755);

    await this.readExisting();
    await this.hashGithub();
    await this.hashStrongset();
    await this.hashHackerNews();
    await this.writeNonces();

    return this.writeTree();
  }

  async readExisting() {
    const faucet = await readJSON(PREFIX, 'faucet.json');

    // Format:
    // {
    //   email: String,
    //   github: String|null, // username
    //   pgp: String|null, // email
    //   freenode: String|null, // username
    //   address: String,
    //   shares: Number
    // }
    for (const {github, pgp, shares} of faucet) {
      if (github)
        this.existing.add(github.toLowerCase());

      if (pgp)
        this.existing.add(pgp.toLowerCase());

      this.faucet += 1;
      this.shares += shares;
    }
  }

  async hashGithub() {
    const sshKeys = await readJSON(PREFIX, 'github-ssh.json');
    const pgpKeys = await readJSON(PREFIX, 'github-pgp.json');

    assert(Array.isArray(sshKeys));
    assert(Array.isArray(pgpKeys));
    assert.strictEqual(sshKeys.length, pgpKeys.length);

    let validKeys = 0;
    let validUsers = 0;
    let invalidKeys = 0;
    let invalidUsers = 0;

    for (let i = 0; i < sshKeys.length; i++) {
      const [id, name, ssh] = sshKeys[i];
      const [id2, name2, pgp] = pgpKeys[i];

      if ((i % 1000) === 0)
        console.log('Github progress: %d / %d', i, sshKeys.length);

      assert(Number.isSafeInteger(id) && id >= 0);
      assert(Number.isSafeInteger(id2) && id2 >= 0);
      assert(typeof name === 'string');
      assert(typeof name2 === 'string');
      assert(Array.isArray(ssh));
      assert(Array.isArray(pgp));
      assert.strictEqual(id, id2);
      assert.strictEqual(name, name2);

      if (this.existing.has(name.toLowerCase())) {
        console.log('Already have github user: %s', name);
        continue;
      }

      const total = ssh.length + pgp.length;

      if (total === 0)
        continue;

      // User gets the same PRNG seed for each key.
      const hashes = [];
      const seed = generateSeed();
      const [valid1, invalid1] = this.parsePGPKeys(name, pgp, hashes, seed);
      const [valid2, invalid2] = this.parseSSHKeys(name, ssh, hashes, seed);
      const valid = valid1 + valid2;
      const invalid = invalid1 + invalid2;

      invalidKeys += invalid;

      assert(invalid <= total);

      if (invalid === total) {
        assert(hashes.length === 0);
        invalidUsers += 1;
        continue;
      }

      assert(hashes.length > 0);
      assert(hashes.length <= SUBTREE_LEAVES);

      validKeys += valid;
      validUsers += 1;

      padSubtree(hashes, seed);

      this.leaves.push(hashes);
    }

    this.total += validKeys;

    console.log('Valid github users: %d', validUsers);
    console.log('Valid github keys: %d', validKeys);
    console.log('Invalid github users: %d', invalidUsers);
    console.log('Invalid github keys: %d', invalidKeys);
  }

  parseSSHKeys(name, keys, hashes, seed) {
    assert(typeof name === 'string');
    assert(Array.isArray(keys));
    assert(Array.isArray(hashes));
    assert(Buffer.isBuffer(seed));

    const sorted = keys.slice();

    // Sort by most recent.
    sorted.sort((a, b) => b.id - a.id);

    let valid = 0;
    let invalid = 0;

    // [id, name, [[k1-id, k1-base64],...]]
    for (const [id, str] of sorted) {
      assert(Number.isSafeInteger(id) && id >= 0);
      assert(typeof str === 'string');

      const pubkey = SSHPublicKey.fromString(str);

      let key;
      try {
        key = AirdropKey.fromSSH(pubkey);
      } catch (e) {
        if (e.message === 'Unsupported algorithm.') {
          invalid += 1;
          continue;
        }
        throw e;
      }

      if (!key.validate()) {
        invalid += 1;
        continue;
      }

      if (hashes.length === SUBTREE_LEAVES) {
        invalid += 1;
        continue;
      }

      valid += 1;

      const newKey = this.pushNonce(key, seed);

      hashes.push(key.hash());
      hashes.push(newKey.hash());
    }

    return [valid, invalid];
  }

  parsePGPKeys(name, keys, hashes, seed) {
    assert(typeof name === 'string');
    assert(Array.isArray(keys));
    assert(Array.isArray(hashes));
    assert(Buffer.isBuffer(seed));

    const sorted = keys.slice();

    // Sort by most recent.
    sorted.sort((a, b) => b.id - a.id);

    let valid = 0;
    let invalid = 0;

    // [
    //   id,
    //   name,
    //   [
    //     [
    //       k1-id,
    //       k1-parent-id,
    //       k1-key-id,
    //       k1-base64,
    //       [[email, verified], ...],
    //       k1-uses,
    //       k1-created,
    //       k1-expires,
    //       k1-depth
    //     ],
    //     ...
    //   ]
    // ]
    for (const [id, parent, keyID, str, emails] of sorted) {
      assert(Number.isSafeInteger(id) && id >= 0);
      assert(parent === -1 || Number.isSafeInteger(parent) && parent >= 0);
      assert(typeof keyID === 'string' && keyID.length === 16);
      assert(typeof str === 'string');
      assert(Array.isArray(emails));

      // No subkeys.
      if (parent !== -1) {
        invalid += 1;
        continue;
      }

      let ok = false;

      for (const [email, verified] of emails) {
        assert(typeof email === 'string');
        assert((verified >>> 0) === verified);
        assert(verified === 0 || verified === 1);

        if (verified) {
          ok = true;
          break;
        }
      }

      if (!ok) {
        invalid += 1;
        continue;
      }

      const data = base64.decode(str);

      let pubkey;
      try {
        pubkey = PGPPublicKey.decode(data);
      } catch (e) {
        invalid += 1;
        continue;
      }

      const hexID = pubkey.id().toString('hex');

      if (hexID !== keyID) {
        console.log(
          'Warning: PGP Key ID %s != %s for %s! (gh)',
          hexID, keyID, name);
        invalid += 1;
        continue;
      }

      let key;
      try {
        key = AirdropKey.fromPGP(pubkey);
      } catch (e) {
        if (e.message === 'Unsupported algorithm.') {
          invalid += 1;
          continue;
        }
        throw e;
      }

      if (!key.validate()) {
        invalid += 1;
        continue;
      }

      if (hashes.length === SUBTREE_LEAVES) {
        invalid += 1;
        continue;
      }

      valid += 1;

      const newKey = this.pushNonce(key, seed);

      hashes.push(key.hash());
      hashes.push(newKey.hash());
    }

    return [valid, invalid];
  }

  async hashStrongset() {
    const str = await readText(PREFIX, 'strongset.asc');

    let i = 0;
    let valid = 0;
    let invalid = 0;

    for (const block of pem.decode(str, true)) {
      const keyID = block.headers.get('Key-ID');
      assert(keyID);

      if ((i++ % 1000) === 0)
        console.log('Strongset progress: %d / %d', i, 60603);

      const email = block.headers.get('Email');

      if (email && this.existing.has(email.trim().toLowerCase())) {
        console.log('Already have strongset member: %s', email);
        continue;
      }

      const msg = PGPMessage.decode(block.data);
      assert(msg.packets.length > 0);

      const pkt = msg.packets[0];

      assert.strictEqual(pkt.type, pgp.packetTypes.PUBLIC_KEY);

      const pubkey = pkt.body;
      const hexID = pubkey.id().toString('hex');

      if (hexID !== keyID) {
        const name = block.headers.get('User-ID');
        console.log(
          'Warning: PGP Key ID %s != %s for %s! (ss)',
          hexID, keyID, name);
        invalid += 1;
        continue;
      }

      let key;
      try {
        key = AirdropKey.fromPGP(pubkey);
      } catch (e) {
        if (e.message === 'Unsupported algorithm.') {
          invalid += 1;
          continue;
        }
        throw e;
      }

      if (!key.validate()) {
        invalid += 1;
        continue;
      }

      valid += 1;

      const seed = generateSeed();
      const newKey = this.pushNonce(key, seed);
      const hashes = [];

      hashes.push(key.hash());
      hashes.push(newKey.hash());

      this.total += hashes.length;

      padSubtree(hashes, seed);

      this.leaves.push(hashes);
    }

    this.total += valid;

    console.log('Valid strongset members: %d', valid);
    console.log('Invalid strongset members: %d', invalid);
  }

  async hashHackerNews() {
    const hnKeys = await readJSON(PREFIX, 'hn-keys.json');

    let i = 0;
    let valid = 0;
    let invalid = 0;

    // [
    //   hackernews-username,
    //   keybase-username,
    //   [
    //     key_fingerprint,
    //     kid,
    //     key_type,
    //     ctime,
    //     mtime,
    //     bundle
    //   ],
    //   [[currency, address], ...]
    // ]

    // eslint-disable-next-line
    for (const [username, keybase, primary, addrs] of hnKeys) {
      // eslint-disable-next-line
      const [fp, kid, ktype, ctime, mtime, bundle] = primary;

      if ((i++ % 1000) === 0)
        console.log('HN progress: %d / %d', i, hnKeys.length);

      const msg = PGPMessage.fromString(bundle);
      assert(msg.packets.length > 0);

      const pkt = msg.packets[0];
      assert.strictEqual(pkt.type, pgp.packetTypes.PUBLIC_KEY);

      const pubkey = pkt.body;
      const id = pubkey.fingerprint().toString('hex');

      if (id !== fp) {
        console.log(
          'Warning: PGP Key ID %s != %s for %s! (hn)',
          id, fp, username);
        invalid += 1;
        continue;
      }

      let key;
      try {
        key = AirdropKey.fromPGP(pubkey);
      } catch (e) {
        if (e.message === 'Unsupported algorithm.') {
          invalid += 1;
          continue;
        }
        throw e;
      }

      if (!key.validate()) {
        invalid += 1;
        continue;
      }

      valid += 1;

      const seed = generateSeed();
      const newKey = this.pushNonce(key, seed);
      const hashes = [];

      hashes.push(key.hash());
      hashes.push(newKey.hash());

      padSubtree(hashes, seed);

      this.leaves.push(hashes);
    }

    this.total += valid;

    console.log('Valid hackernews users: %d', valid);
    console.log('Invalid hackernews users: %d', invalid);
  }

  async writeNonces() {
    let total = 0;

    for (let i = 0; i < 256; i++) {
      const nonces = this.buckets[i];
      const path = Path.resolve(NONCE_DIR, `${pad(i)}.bin`);

      let size = 0;

      for (const ct of nonces)
        size += 2 + ct.length;

      const bw = bio.write(size);

      for (const ct of nonces) {
        bw.writeU16(ct.length);
        bw.writeBytes(ct);
      }

      const raw = bw.render();

      this.checksums.push(sha256.digest(raw));

      await fs.writeFile(path, raw);

      total += size;
    }

    console.log('Wrote buckets (size=%dmb).', total / 1024 / 1024);
  }

  async writeTree() {
    this.leaves.sort((a, b) => {
      const x = merkle.createRoot(blake2b, a);
      const y = merkle.createRoot(blake2b, b);
      return x.compare(y);
    });

    const size = 4 + this.leaves.length * SUBTREE_LEAVES * 32;
    const bw = bio.write(size);

    bw.writeU32(this.leaves.length);

    for (const hashes of this.leaves) {
      assert(hashes.length === SUBTREE_LEAVES);

      for (const hash of hashes)
        bw.writeBytes(hash);
    }

    const raw = bw.render();

    await fs.writeFile(TREE_FILE, raw);

    return sha256.digest(raw);
  }

  hashTree() {
    const tree = [];

    for (const hashes of this.leaves)
      tree.push(merkle.createRoot(blake2b, hashes));

    return merkle.createRoot(blake2b, tree);
  }
}

/*
 * Helpers
 */

async function readText(...args) {
  const file = Path.resolve(...args);
  return fs.readFile(file, 'utf8');
}

async function readJSON(...args) {
  const str = await readText(...args);
  return JSON.parse(str);
}

function getDepth(size) {
  assert((size >>> 0) === size);

  let depth = 0;

  while (size > 1) {
    depth += 1;
    size = (size + 1) >>> 1;
  }

  return depth;
}

function pad(index) {
  assert((index & 0xff) === index);

  let str = index.toString(10);

  while (str.length < 3)
    str = '0' + str;

  return str;
}

function generateSeed() {
  const entropy = random.randomBytes(64);
  const hash = sha256.digest(entropy);

  assert(hash.length >= SEED_SIZE);

  return hash.slice(0, SEED_SIZE);
}

function padSubtree(hashes, seed) {
  assert(Array.isArray(hashes));
  assert(Buffer.isBuffer(seed));

  const len = SUBTREE_LEAVES * 32;
  const prk = hkdf.extract(sha256, seed);
  const raw = hkdf.expand(sha256, prk, null, len);

  let i = 0;

  while (hashes.length < SUBTREE_LEAVES) {
    hashes.push(raw.slice(i, i + 32));
    i += 32;
  }

  return hashes.sort(compare);
}

function compare(a, b) {
  return a.compare(b);
}

/*
 * Execute
 */

main().catch((err) => {
  console.error(err.stack);
  process.exit(1);
});