commit 8543b07c1ca2a68f756e1f878b92463d38732a46
parent 7cd7011ab5041fb81667c514a86cab12a113a4ed
Author: nolash <dev@holbrook.no>
Date: Fri, 30 Oct 2020 20:15:54 +0100
Change inputs to uint8array, move execution code to mocha test
Diffstat:
| D | bloom.js | | | 80 | ------------------------------------------------------------------------------- |
| A | moolb/moolb.js | | | 108 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | package.json | | | 27 | +++++++++++++++++++++++++++ |
3 files changed, 135 insertions(+), 80 deletions(-)
diff --git a/bloom.js b/bloom.js
@@ -1,80 +0,0 @@
-let sha = require('jssha');
-
-// block numbers 6000000
-// false positive probability 2%
-//
-// m = ceil((n * log(p)) / log(1 / pow(2, log(2))));
-// m = ceil((6000000 * log(0.1)) / log(1 / pow(2, log(2))))
-// = 3917675
-//var bloomBits = 29600000;
-var bloomBits = 8192 * 8;
-var bloomBytes = bloomBits / 8;
-
-// hashing rounds to match a filter entry
-var bloomRounds = 3;
-
-// Creates a new bloom object.
-// \param bytes optional, set the filter to Uint8Array of bytes of length according to global var bloomBytes. If not set, creates a new empty filter
-function Bloom(bytes) {
- if (bytes !== undefined) {
- if (bytes.length != bloomBytes) {
- console.error("bloom bytes must be length " + bloomBytes + ", have " + bytes.length);
- return false;
- }
- this.filter = new Uint8Array(bytes);
- } else {
- this.filter = new Uint8Array(bloomBytes);
- }
-}
-
-// add entry to bloom filter
-// \param blockNumber block number to add
-Bloom.prototype.add = function(blockNumber) {
- for (var i = 0; i < bloomRounds; i++) {
- var result = hashBloom(blockNumber, i);
- console.log(result)
- var bytepos = parseInt(parseInt(result, 10) / 8, 10);
- var bitpos = parseInt(result, 10) % 8;
- this.filter[bytepos] |= 1 << bitpos;
- console.debug("setpos ", bytepos, bitpos);
- }
-};
-
-// checks if the block number has been added to the bloom filter
-// \param blockNumber block number to check
-// \return false if not found in filter
-// \todo check if we can merely return on false
-Bloom.prototype.check = function(blockNumber) {
- var ok = true;
- for (var i = 0; i < bloomRounds; i++) {
- var result = hashBloom(blockNumber, i);
- var bytepos = parseInt(parseInt(result, 10) / 8, 10);
- if (this.filter[bytepos] == undefined) {
- ok = false;
- } else {
- var test = 1 << (0xff & (parseInt(result, 10) % 8));
- if ((this.filter[bytepos] & test) == 0) {
- ok = false;
- }
- }
- }
- return ok;
-};
-
-
-// a single bloom hash round
-function hashBloom(data, salt) {
- var h = new sha("SHA-256", "TEXT");
- console.log('hashing ', data.toString(), salt.toString());
- h.update(data.toString());
- h.update(salt.toString());
- hx = "0x"+h.getHash("HEX")
- console.log('hx', hx)
- return parseInt(BigInt(hx) % BigInt(bloomBits), 10);
-}
-
-a = new Uint8Array(bloomBytes);
-b = new Bloom(a);
-b.add(1024);
-console.log(b.check(1024));
-console.log(b.check(1023));
diff --git a/moolb/moolb.js b/moolb/moolb.js
@@ -0,0 +1,108 @@
+module.exports = {
+ 'Bloom': Bloom,
+}
+
+let crypto = require('crypto');
+
+// block numbers 6000000
+// false positive probability 2%
+//
+// m = ceil((n * log(p)) / log(1 / pow(2, log(2))));
+// m = ceil((6000000 * log(0.1)) / log(1 / pow(2, log(2))))
+// = 3917675
+
+// Creates a new bloom object.
+// \param size of filter in bits, aligned to byte boundary
+// \param number of rounds to hash
+// \param hasher function, which must take two Uint8Array parameters 'data' and 'salt'. If not sef, hashBloomDefault will be used.
+function Bloom(bits, rounds, hasher) {
+ this.bits = bits;
+ this.bytes = parseInt(bits / 8, 10);
+ this.rounds = rounds;
+ if (this.hasher === undefined) {
+ this.hasher = hashBloomDefault;
+ }
+ if (this.bytes * 8 != this.bits) {
+ console.error('number of bits must be on byte boundary');
+ return false;
+ } else {
+ this.filter = new Uint8Array(this.bytes);
+ }
+}
+
+// add entry to bloom filter
+// \param value to add
+Bloom.prototype.add = function(v) {
+ a = new ArrayBuffer(4);
+ iw = new DataView(a);
+ for (var i = 0; i < this.rounds; i++) {
+ iw.setUint32(0, i);
+ let result = this.hasher(v, iw);
+ console.debug(result)
+ let resultHex = Array.prototype.map.call(new Uint8Array(result), x => ('00' + x.toString(16)).slice(-2)).join('');
+ let resultInt = parseInt(BigInt('0x'+resultHex) % BigInt(this.bits), 10);
+ let bytepos = parseInt(resultInt / 8, 10);
+ let bitpos = parseInt(resultInt, 10) % 8;
+ this.filter[bytepos] |= 1 << bitpos;
+ console.debug("setpos ", bytepos, bitpos);
+ }
+};
+
+// checks if the block number has been added to the bloom filter
+// \param value to check for
+// \return false if not found in filter
+Bloom.prototype.check = function(v) {
+ var ok = true;
+ a = new ArrayBuffer(4);
+ iw = new DataView(a);
+ for (let i = 0; i < this.rounds; i++) {
+ iw.setUint32(0, i);
+ let result = this.hasher(v, iw);
+ let resultHex = Array.prototype.map.call(new Uint8Array(result), x => ('00' + x.toString(16)).slice(-2)).join('');
+ let resultInt = parseInt(BigInt('0x'+resultHex) % BigInt(this.bits), 10);
+ let bytepos = parseInt(resultInt / 8, 10);
+ if (this.filter[bytepos] == undefined) {
+ console.error('byte pos ' + bytepos + ' is undefined!');
+ return false;
+ //ok = false;
+ } else {
+ let test = 1 << (0xff & (resultInt % 8));
+ if ((this.filter[bytepos] & test) == 0) {
+ return false;
+ //ok = false;
+ }
+ }
+ }
+ return ok;
+};
+
+// return the verbatim filter
+// \return Uint8Array filter
+Bloom.prototype.bytes = function() {
+ return this.filter;
+};
+
+
+// Default hashing function used in Bloom.add() - sha256
+// \param data to insert in filter
+// \param salt, typically a sequence number
+// \return Uint8Array digest
+function hashBloomDefault(data, salt) {
+ h = crypto.createHash('sha256');
+ h.update(data);
+ h.update(salt);
+ //return Uint8Array.from(h.digest());
+ return h.digest();
+}
+
+
+// a single bloom hash round
+function hashBloom(data, salt) {
+ var h = new sha("SHA-256", "TEXT");
+ console.log('hashing ', data.toString(), salt.toString());
+ h.update(data.toString());
+ h.update(salt.toString());
+ hx = "0x"+h.getHash("HEX")
+ console.log('hx', hx)
+ return parseInt(BigInt(hx) % BigInt(bloomBits), 10);
+}
diff --git a/package.json b/package.json
@@ -0,0 +1,27 @@
+{
+ "name": "moolb",
+ "version": "0.0.4",
+ "description": "Simple bloom filter with pluggable hash backend",
+ "main": "dist/index.js",
+ "directories": {
+ "tests": "new_test"
+ },
+ "files": [
+ "moolb"
+ ],
+ "dependencies": {
+ "mocha": "^7.2.0"
+ },
+ "scripts": {
+ "test": "mocha --reporter spec ./tests"
+ },
+ "repository": {
+ "type": "git",
+ "url": "https://gitlab.com/nolash/block-syncer-js"
+ },
+ "author": "Louis Holbrook <npm@holbrook.no> (https://holbrook.no)",
+ "license": "GPL-3.0-or-later",
+ "engine": {
+ "node": "^12.0.0"
+ }
+}
