WebCrypto zero-trust lottery
Choosing a prize winner usually involves using a simple list of participants and the True Random Number Generator. That unfortunately makes the generator a trusted third-party.
Browsers that implement the WebCrypto API can be used to conduct a truly zero-trust, secure lottery in less than 200 lines of modern JavaScript code.
The implementation below uses several ES6 features:
- Arrow functions
- Rest parameters
- Spread operator
- Template strings
- Generators
- Promises
- Array.from
- WebCrypto digests
Both Firefox 40 and Chrome 45 support all these features but Chrome needs to have Experimental JavaScript flag enabled at chrome://flags/#enable-javascript-harmony. Microsoft Edge can also be used but needs to have Experimental JavaScript features enabled at about:flags.
Views
The function below is used in conjunction with template strings to interleave template text with values provided inside placeholders. The placeholder values are automatically sanitized.
function html(parts, ...values) {
var replacements = {
'"': '"',
'\'': ''',
'<': '<',
'>': '>',
'&': '&'
};
var replaceEntities = text =>
text.replace(/["'<>&]/g, match => replacements[match]);
var div = document.createElement('div');
div.innerHTML = parts.map((part, index) =>
part + replaceEntities(String(values[index] || ''))
).join('');
return div.firstElementChild;
}For example the input field below contains an unsafe HTML string:
The code below properly escapes the input string while leaving the template tags:
var node = html`<div>you <b>typed</b> ${input.value}.</div>`;
output.appendChild(node);This template is then used to construct a dialog. The dialog is a small form used to present information or obtain an answer to the query.
function showDialog(type, title, value) {
var info = document.getElementById('info');
var row = html`<form class="${type || ''}">
<label><span>${title}</span>
<input value="${value}" class="value code" required/></label>
<input type="submit" value="OK"/>
</form>`;
info.appendChild(row);
var input = row.querySelector('input');
input.select();
input.focus();
var ok = row.querySelector('input[type="submit"]');
return new Promise(resolve =>
row.addEventListener('submit', function submit(e) {
e.preventDefault();
row.removeEventListener('click', submit);
ok.parentElement.removeChild(ok);
input.readOnly = true;
resolve(input.value);
}));
}
var showInfo = showDialog.bind(null, 'infor');
var showError = showDialog.bind(null, 'error');
var showPrompt = showDialog.bind(null, '');The answer is returned through a Promise. The code below asks a question and displays it in a dialog box:
showPrompt('Test').then(alert);Rejection sampling
To generate cryptographically secure random values the crypto.getRandomValues API is used.
The function fills a one byte array with random number and takes the remainder after divison (modulo) by the maximum number. Unfortunately this operation does not produce uniform distribution — some numbers would be selected more often than others.
from([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
.select(() => crypto.getRandomValues(new Uint8Array(1))[0] % 10)
.limit(iterations(100000))
.into(graphs.bar(uintgraph));As the number of trials increases it becomes apparent that 6, 7, 8 and 9 would be less frequently selected than the rest. Even though the random bytes from getRandomValues are uniformly distributed between 0 to 255 the modulo operation skews the distribution of 0 to 9.
The graphic below illustrates how all values from the random byte are mapped to a number from 0 to 9. Because the last row (numbers from 250 and above) contains only six elements instead of ten the results are more likely to contain numbers from 0 to 5 than these above 5.
To generate uniformly distributed values from 0 (inclusive) to max (exclusive) a rejection sampling method is used.
In this method values that would cause the distribution skew (in this example 250 and above) are completely rejected and a new random number is drawn.
function getRandomInt(max) {
console.assert(max <= 256, "Max must not be greater than 256.");
var value = crypto.getRandomValues(new Uint8Array(1))[0];
if (value >= Math.floor(256 / max) * max) {
return getRandomInt(max);
}
return value % max;
}from([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
.select(() => getRandomInt(10))
.limit(iterations(100000))
.into(graphs.bar(getrandomintgraph));Now the distribution is normal and all numbers are equally likely to be drawn.
Math.random can also be used to generate uniformly distributed random numbers. This method is faster but not cryptographically secure.
from([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
.select(() => Math.floor(Math.random() * 10))
.limit(iterations(100000))
.into(graphs.bar(mathgraph));It is important to use Math.floor instead of Math.round to keep the numbers uniformly distributed.
The example below uses round. That makes 0 and 9 twice as unlikely to be drawn out as other numbers.
from([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
.select(() => Math.round(Math.random() * 9))
.limit(iterations(100000))
.into(graphs.bar(mathroundgraph));Handling bytes
To manage arrays of bytes a simple wrapper around Uint8Array is used. This wrapper adds comparison and equality test methods as well as printing bytes into hex-encoded human readable form.
function Bytes(bytes) {
this.bytes = new Uint8Array(bytes);
}
Bytes.prototype = {
get length() {
return this.bytes.length;
},
compareTo: function(other) {
return this.toString().localeCompare(other.toString());
},
equals: function(other) {
return this.toString() === other.toString();
},
toString: function() {
return Array.from(this.bytes)
.map(byte => byte.toString(16))
.map(byte => byte.length < 2 ? '0' + byte : byte)
.join('');
},
digest: function() {
return crypto.subtle.digest({
name: 'SHA-256'
}, this.bytes).then(digest => new Bytes(digest));
}
};
Bytes.parse = function(text) {
var bytes = text.match(/.{2}/g);
if (!bytes) {
throw new Error('Invalid format: ' + text);
}
return new Bytes(bytes.map(byte => {
var number = parseInt(byte, 16);
if (isNaN(number)) {
throw new Error('Invalid byte: ' + byte);
}
return number;
}));
};
Bytes.random = function(count) {
return new Bytes(crypto.getRandomValues(new Uint8Array(count)));
};
function getRandomBytes(min, max) {
return Bytes.random(min + getRandomInt(max - min));
}The digest function returns a Promise object that will resolve to a hash of bytes.
User interaction
UI object handles interaction with user and data conversion. All functions on this object return Promises.
var ui = {
getPlayersCount: () =>
showPrompt('How many players?', 2).then(Number),
sendOwnDigest: showInfo.bind(null,
'Send your digest to everyone:'),
pasteOtherDigest: () => showPrompt(
'Paste here other participants\' digest (order does not matter):').then(Bytes.parse),
cannotParseDigest: showError.bind(null,
'Cannot parse digest. Ignoring.'),
sendOwnSecret: showInfo.bind(null,
'Send your secret to everyone:'),
pasteOtherSecret: () => showPrompt(
'Paste here other participants\' secret:').then(Bytes.parse),
noDigestForSecret: showError.bind(null,
'Secret does not match any digest. Ignoring.'),
duplicateSecret: showError.bind(null,
'Secret has been already added. Ignoring.'),
cannotParseSecret: showError.bind(null,
'Cannot parse secret. Ignoring.'),
winnerDigest: showPrompt.bind(null, 'Winner holds this digest:'),
unknownError: showError.bind(null, 'Something went wrong!')
};Lottery
Main algorthm is implemented as an asynchronous function using generators. Each yield statement consumes a Promise value and suspends the execution until the promise is settled.
The algorithm operates in two phases:
- generate a secret and gather digests of secrets from all other parties,
- all parties reveal their secrets and the winner is selected.
To protect against brute-force digest attacks a random padding is used, similarily to the Bitcoin Multilottery example.
var document = (function(original) {
return {
getElementById: function(id) {
return original.getElementById('bottom');
},
createElement: function() {
return original.createElement.apply(original, arguments);
}
};
}(window.document));function async(generatorFunction) {
function start(generator, resolve, reject) {
function resume(method, value) {
try {
var result = generator[method](value);
if (result.done) {
resolve(result.value);
} else {
result.value.then(resumeNext, resumeThrow);
}
} catch (e) {
reject(e);
}
}
var resumeNext = resume.bind(null, 'next');
var resumeThrow = resume.bind(null, 'throw');
resumeNext();
}
return (...args) => new Promise(start.bind(this, generatorFunction(...args)));
}function* drawWinner(ui, getRandomBytes, padding) {
var howMany = yield ui.getPlayersCount();
var ownSecret = getRandomBytes(padding, padding + howMany);
var ownDigest = yield ownSecret.digest();
yield ui.sendOwnDigest(ownDigest);
var digests = [ ownDigest ];
do {
try {
digests.push(yield ui.pasteOtherDigest());
} catch (e) {
yield ui.cannotParseDigest(e);
}
} while (digests.length < howMany);
yield ui.sendOwnSecret(ownSecret);
var secrets = [ ownSecret ];
do {
try {
const secret = yield ui.pasteOtherSecret();
const digest = yield secret.digest();
if (!digests.some(i => i.equals(digest))) {
yield ui.noDigestForSecret(secret);
} else if (secrets.some(i => i.equals(secret))) {
yield ui.duplicateSecret(secret);
} else {
secrets.push(secret);
}
} catch (e) {
yield ui.cannotParseSecret(e);
}
} while (secrets.length < digests.length);
var winner = secrets
.map(secret => secret.length - padding)
.reduce((a, b) => a + b, 0) % howMany;
digests.sort((a, b) => a.compareTo(b));
return digests[winner];
}
async(drawWinner)(ui, getRandomBytes, 32)
.then(ui.winnerDigest, ui.unknownError);Currently the function uses generators and the async polyfill but in the future it can be replaced with an ES7 async function.
This entire script in one page can also be accessed on GitHub.
Comments
Revisions
- Initial version.