moolb-js

Bloom filter for javascript with pluggable hasher backend
git clone git://git.defalsify.org/moolb-js.git
Info | Log | Files | Refs | README

moolb.js (4655B)


      1 let crypto = undefined;
      2 
      3 (function() {
      4 	if (typeof module !== 'undefined' && typeof exports !== 'undefined') {
      5 		let nodeCrypto = require('crypto');
      6 		function hashWrapper(nodeCrypto, alg) {
      7 			this.alg = alg;
      8 			this.crypto = nodeCrypto.createHash(alg);
      9 		}
     10 		hashWrapper.prototype.update = function(d) {
     11 			this.crypto.update(d);
     12 		}
     13 		hashWrapper.prototype.digest = async function() {
     14 			z = this.crypto.digest(this.data);
     15 			return new Uint8Array(z);
     16 		}
     17 
     18 		function cryptoWrapper(nodeCrypto) {
     19 			this.crypto = nodeCrypto
     20 		}
     21 		cryptoWrapper.prototype.createHash = function(alg) {
     22 			return new hashWrapper(this.crypto, alg);
     23 		}
     24 		module.exports = {
     25 			Bloom: Bloom,
     26 			fromBytes: fromBytes,
     27 		};
     28 		crypto = new cryptoWrapper(nodeCrypto);
     29 	} else {
     30 		function hashWrapper(webCrypto, alg) {
     31 			this.alg = alg;
     32 			this.crypto = webCrypto;
     33 			this.data = undefined;
     34 		}
     35 		hashWrapper.prototype.update = function(d) {
     36 			if (this.data != undefined) {
     37 				throw "cannot append";
     38 			}
     39 			this.data = d;
     40 		}
     41 		hashWrapper.prototype.digest = async function() {
     42 			z = await this.crypto.subtle.digest('SHA-256', this.data);
     43 			return new Uint8Array(z);
     44 		}
     45 
     46 		function cryptoWrapper(webCrypto) {
     47 			this.crypto = webCrypto
     48 		}
     49 		cryptoWrapper.prototype.createHash = function(alg) {
     50 			return new hashWrapper(this.crypto, alg);
     51 		}
     52 
     53 		crypto = new cryptoWrapper(window.crypto);
     54 		window.Bloom = Bloom;
     55 		window.bloomFromBytes = fromBytes;
     56 	}
     57 })()
     58 
     59 
     60 // block numbers 6000000 
     61 // false positive probability 2%
     62 //
     63 // m = ceil((n * log(p)) / log(1 / pow(2, log(2))));
     64 // m = ceil((6000000 * log(0.1)) / log(1 / pow(2, log(2))))
     65 // = 3917675
     66 
     67 // Creates a new bloom object.
     68 // \param size of filter in bits, aligned to byte boundary
     69 // \param number of rounds to hash
     70 // \param hasher function, which must take two Uint8Array parameters 'data' and 'salt'. If not sef, hashBloomDefault will be used.
     71 function Bloom(bits, rounds, hasher) {
     72 	this.bits = bits;
     73 	this.bytes = parseInt(bits / 8, 10);
     74 	this.rounds = rounds;
     75 	if (this.hasher === undefined) {
     76 		this.hasher = hashBloomDefault;
     77 	}
     78 	if (this.bytes * 8 != this.bits) {
     79 		console.error('number of bits must be on byte boundary');
     80 		return false;
     81 	} else {
     82 		this.filter = new Uint8Array(this.bytes);
     83 	}
     84 }
     85 
     86 // add entry to bloom filter
     87 // \param value to add
     88 Bloom.prototype.add = async function(v) {
     89 	let a = new ArrayBuffer(v.byteLength + 4);
     90 	let iw = new DataView(a);
     91 	for (let i = 0; i < v.byteLength; i++) {
     92 		iw.setUint8(i, v[i]);
     93 	}
     94 	console.log(iw, v);
     95 	for (var i = 0; i < this.rounds; i++) {
     96 		iw.setInt32(v.byteLength, i);
     97 		let result = await this.hasher(iw);
     98 		let resultHex = Array.prototype.map.call(new Uint8Array(result), x => ('00' + x.toString(16)).slice(-2)).join('');
     99 		let resultInt = parseInt(BigInt('0x'+resultHex) % BigInt(this.bits), 10);
    100 		let bytepos = parseInt(resultInt / 8, 10);
    101 		let bitpos = parseInt(resultInt, 10) % 8;
    102 		this.filter[bytepos] |= 1 << bitpos;
    103 		//console.log("setpos ", bytepos, bitpos);
    104 	}
    105 };
    106 
    107 // checks if the block number has been added to the bloom filter
    108 // \param value to check for
    109 // \return false if not found in filter
    110 Bloom.prototype.check = async function(v) {
    111 	let a = new ArrayBuffer(v.byteLength + 4);
    112 	let iw = new DataView(a);
    113 	for (let i = 0; i < v.byteLength; i++) {
    114 		iw.setUint8(i, v[i]);
    115 	}
    116 	for (let i = 0; i < this.rounds; i++) {
    117 		iw.setInt32(v.byteLength, i);
    118 		let result = await this.hasher(iw);
    119 		//console.log('result', result);
    120 		let resultHex = Array.prototype.map.call(new Uint8Array(result), x => ('00' + x.toString(16)).slice(-2)).join('');
    121 		let resultInt = parseInt(BigInt('0x'+resultHex) % BigInt(this.bits), 10);
    122 		let bytepos = parseInt(resultInt / 8, 10);
    123 		//console.log("setpos ", bytepos, resultInt % 8);
    124 		if (this.filter[bytepos] === undefined) {
    125 			console.error('byte pos ' + bytepos + ' is undefined (filter length ' + this.filter.byteLength + ')');
    126 			return false;
    127 		} else {
    128 			let test = 1 << (0xff & (resultInt % 8));
    129 			if ((this.filter[bytepos] & test) == 0) {
    130 				return false;
    131 			}
    132 		}
    133 	}
    134 	return true;
    135 };
    136 
    137 // return the verbatim filter
    138 // \return Uint8Array filter
    139 Bloom.prototype.bytes = function() {
    140 	return this.filter;
    141 };
    142 
    143 
    144 // Default hashing function used in Bloom.add() - sha256
    145 // \param data to insert in filter
    146 // \param salt, typically a sequence number
    147 // \return Uint8Array digest
    148 async function hashBloomDefault(data, salt) {
    149 	let h = crypto.createHash('sha256');
    150 	h.update(data);
    151 	z = await h.digest();
    152 	return Uint8Array.from(z);
    153 }
    154 
    155 function fromBytes(bytes, rounds, hasher) {
    156 	let bits = bytes.byteLength * 8;
    157 	let b = new Bloom(bits, rounds, hasher);
    158 	b.filter = bytes;
    159 	return b;
    160 }