Javascript Ring Signature Experiment

ring_signature.js

const BigInteger = require('bigi');
const _ = require('lodash');

const prova = require('prova-lib');
const crypto = require('crypto');
const bitcoin = require('bitgo-utxo-lib');

const ecurve = require('ecurve');
let secp256k1 = ecurve.getCurveByName('secp256k1');

/**
 * H(x * G)
 * @param pubkey
 * @returns {*}
 */
const keyHashScalar = (pubkey) => {
  const pubkeyBuffer = Buffer.from(pubkey, 'hex');
  const pubkeyHash = crypto.createHash('sha256').update(pubkeyBuffer).digest('hex');
  return BigInteger.fromHex(pubkeyHash).mod(secp256k1.n);
};

/**
 * H(x * G) * G
 * @param pubkey
 * @param generator
 * @returns {*}
 */
const keyHashPoint = (pubkey) => {
  const hGenerator = keyHashGenerator(secp256k1.G.getEncoded(true).toString('hex'));
  const scalar = keyHashScalar(pubkey);
  return hGenerator.multiply(scalar);
};

/**
 *
 * @param pubkey
 * @returns {*}
 */
const keyHashGenerator = (pubkey) => {
  const scalar = keyHashScalar(pubkey);


  let currentGenerator = secp256k1.pointFromX(false, scalar);
  let isOnCurve = secp256k1.isOnCurve(currentGenerator);
  let offset = BigInteger.fromHex('01');
  while (!isOnCurve) {
    // if the point is not on the curve, we increment x by one until it is
    currentGenerator = secp256k1.pointFromX(false, scalar.add(offset).mod(secp256k1.n));
    isOnCurve = secp256k1.isOnCurve(currentGenerator);
    offset = offset.add(offset);
  }

  return currentGenerator;
};

/**
 * returns x * H(x * G) * G
 * x is the privkey, xG is the pubkey, H is a hash function
 * @param privkey
 * @returns {*}
 */
const keyImage = (privkey) => {
  const privkeyObject = prova.ECPair.fromPrivateKeyBuffer(Buffer.from(privkey, 'hex'));
  const knownPubkey = privkeyObject.getPublicKeyBuffer().toString('hex');
  const pubkeyHashPoint = keyHashPoint(knownPubkey);
  return pubkeyHashPoint.multiply(privkeyObject.d);
};

const pointToBuffer = (ecPoint) => {
  return (new prova.ECPair(null, ecPoint)).getPublicKeyBuffer();
};

const createCommitment = (message, leftValue, rightValue) => {
  const messageBuffer = Buffer.from(message, 'utf-8');
  const leftBuffer = pointToBuffer(leftValue);
  const rightBuffer = pointToBuffer(rightValue);
  const fullBuffer = Buffer.concat([messageBuffer, leftBuffer, rightBuffer]);
  return crypto.createHash('sha256').update(fullBuffer).digest('hex');
};

const printBufferArray = (buffers) => {
  const hexBuffers = buffers.map(b => b.toString('hex'));
  console.log(JSON.stringify(hexBuffers, null, 4));
};

const serializeSignature = ([privkeyImage, firstCommitment, ...randomValues]) => {
  // convert the point to a public key
  const keyImageBuffer = pointToBuffer(privkeyImage);
  const commitmentBuffer = Buffer.from(firstCommitment, 'hex');
  const randomValueBuffers = randomValues.map(v => v.toBuffer());
  const signatureBuffers = [keyImageBuffer, commitmentBuffer, ...randomValueBuffers];
  const sigScript = bitcoin.script.compile(signatureBuffers);
  return sigScript.toString('hex');
};

const deserializeSignature = (signature) => {
  const signatureBuffers = bitcoin.script.decompile(Buffer.from(signature, 'hex'));
  printBufferArray(signatureBuffers);
  const [privkeyImageBuffer, firstCommitmentBuffer, ...randomValueBuffers] = signatureBuffers;
  const privkeyImage = prova.ECPair.fromPublicKeyBuffer(privkeyImageBuffer).__Q;
  const firstCommitment = firstCommitmentBuffer.toString('hex');
  const randomValues = randomValueBuffers.map(b => BigInteger.fromBuffer(b));
  return [privkeyImage, firstCommitment, ...randomValues];
};



const ringSign = (pubkeys, privkey, message) => {

  // obtain the index of the public key whose private key we know
  const privkeyObject = prova.ECPair.fromPrivateKeyBuffer(Buffer.from(privkey, 'hex'));
  const knownPubkey = privkeyObject.getPublicKeyBuffer().toString('hex');
  const knownPubkeyIndex = pubkeys.indexOf(knownPubkey);
  if (knownPubkeyIndex === -1) {
    throw new Error('no supported public keys present');
  }

  const ringSize = pubkeys.length;
  const ringIndex = (index) => index % ringSize;

  const privkeyImage = keyImage(privkey);

  // initialize commitments and random values
  const commitments = _.times(ringSize, _.constant(null));
  const randomValues = _.times(ringSize, () => BigInteger.fromHex(crypto.randomBytes(32).toString('hex')).mod(secp256k1.n));
  randomValues[knownPubkeyIndex] = null;

  // start with the first index
  const alpha = BigInteger.fromHex(crypto.randomBytes(32).toString('hex')).mod(secp256k1.n); // some random integer
  const generator = secp256k1.G;

  const leftValue = generator.multiply(alpha);
  const rightValue = keyHashPoint(pubkeys[knownPubkeyIndex]).multiply(alpha);
  commitments[ringIndex(knownPubkeyIndex + 1)] = createCommitment(message, leftValue, rightValue);



  // fill the remainder of the ring
  for (let i = 1; i < ringSize; i++) {
    const currentIndex = ringIndex(knownPubkeyIndex + i);
    const currentRandomValue = randomValues[currentIndex];
    const currentCommitment = commitments[currentIndex];
    const currentCommitmentNumber = BigInteger.fromHex(currentCommitment).mod(secp256k1.n);
    const currentPubkey = pubkeys[currentIndex];
    const currentPubkeyObject = prova.ECPair.fromPublicKeyBuffer(Buffer.from(currentPubkey, 'hex'));
    const currentPubkeyPoint = currentPubkeyObject.__Q;

    // calculate current L(i) = s(i)*G + c(i) * P(i)
    const currentLeftValue = generator.multiply(currentRandomValue).add(currentPubkeyPoint.multiply(currentCommitmentNumber));

    // calculate current R(i) = s(i)*H(P(i))*G + c(i) * I
    const currentPubkeyHashpoint = keyHashPoint(currentPubkey);
    const currentRightValue = currentPubkeyHashpoint.multiply(currentRandomValue).add(privkeyImage.multiply(currentCommitmentNumber));

    commitments[ringIndex(currentIndex + 1)] = createCommitment(message, currentLeftValue, currentRightValue);
  }


  // calculate the necessary random value (s) for the original commitment

  // left:
  // alpha * G = s * G + c * P <=> alpha = s + c * x <=> s = alpha - c * x

  // right:
  // alpha * H(P) = s * H(P) + c * I <=> alpha * h(P) = s * h(P) + c * x * h(P) <=> alpha = s + c * x <=> s = alpha - c * x
  const referenceCommitment = commitments[knownPubkeyIndex];
  const referenceCommitmentNumber = BigInteger.fromHex(referenceCommitment).mod(secp256k1.n);
  randomValues[knownPubkeyIndex] = alpha.subtract(referenceCommitmentNumber.multiply(privkeyObject.d).mod(secp256k1.n)).mod(secp256k1.n);

  const signature = [privkeyImage, commitments[0], ...randomValues];
  return serializeSignature(signature);

};

const verifySignature = (pubkeys, message, signature) => {

  const [privkeyImage, firstCommitment, ...randomValues] = deserializeSignature(signature);

  const ringSize = randomValues.length;
  const ringIndex = (index) => index % ringSize;

  const commitments = _.times(ringSize, _.constant(null));
  commitments[0] = firstCommitment;

  const generator = secp256k1.G;

  for (let i = 0; i < ringSize; i++) {
    const currentRandomValue = randomValues[i];
    const currentCommitment = commitments[i];
    const currentCommitmentNumber = BigInteger.fromHex(currentCommitment).mod(secp256k1.n);
    const currentPubkey = pubkeys[i];
    const currentPubkeyObject = prova.ECPair.fromPublicKeyBuffer(Buffer.from(currentPubkey, 'hex'));
    const currentPubkeyPoint = currentPubkeyObject.__Q;

    // calculate current L(i) = s(i)*G + c(i) * P(i)
    const currentLeftValue = generator.multiply(currentRandomValue).add(currentPubkeyPoint.multiply(currentCommitmentNumber));

    // calculate current R(i) = s(i) * H(P(i)) * G + c(i) * I
    const currentPubkeyHashpoint = keyHashPoint(currentPubkey);
    const currentRightValue = currentPubkeyHashpoint.multiply(currentRandomValue).add(privkeyImage.multiply(currentCommitmentNumber));

    commitments[ringIndex(i + 1)] = createCommitment(message, currentLeftValue, currentRightValue);
  }

  return firstCommitment === commitments[0];
};


const pubkeys = [
  '030150cddea7de0bf54aa2da85234937636638a6301246f4c2dab247e103cafa4f',
  '02fb012e6d60c4fc2d9d6db605f5a998986991c8d60c107b36268fea586cdace2b',
  '0219877ed8cc48ed3ac0b4e0295aaecb3b00dc3c1c49049fc566780d054dec1986',
  '039cababc826209b092ac3bd58d807199a4b344d8110999704ed45740d5a963965',
  '035051041f8ab6deff643f255220780490a38fcabc1dd8ef588a5ac856aaccd141'
];
const privkey = 'e5d5ca46ab3fe61af6a001e02a5b979ee2c1f205c94804dd575aa6134de43ab3';
const message = 'Arik is rolling his own crypto';

const signature = ringSign(pubkeys, privkey, message);
console.dir(signature);
const verification = verifySignature(pubkeys, message, signature);
console.log(verification);