moolb-js

commit 5d1e01f54efbe0e7fdaea1579682fafd2890b8c5
Author: nolash <dev@holbrook.no>
Date:   Thu, 29 Oct 2020 20:43:21 +0100

Initial commit

Diffstat:
A
bloom.js
 | 
100
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 100 insertions(+), 0 deletions(-)
diff --git a/bloom.js b/bloom.js
@@ -0,0 +1,100 @@
+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;
+};
+
+// merges the bloom filter bytes in parameter with the object's
+// \param bloomBytes bytes to merge. MUST be equal length of object's
+// \return true on success, false on fail
+Bloom.prototype.merge = function(bloomBytes) {
+	if (bloomBytes.length != this.filter.length) {
+		console.error("lengths must match (" + bloomBytes + " != " + this.filter.length);
+		return false;
+	}
+	for (var i = 0; i < this.filter.length; i++) {
+		if (this.filter[i] != bloomBytes[i]) {
+			dbg("merging " + ": before " + this.filter[i] + " after " + (this.filter[i] | bloomBytes[i]));
+			this.filter[i] |= bloomBytes[i];
+		}
+	}
+	return true;
+};
+
+// returns the actual bytes of the bloomfilter
+Bloom.prototype.bytes = function() {
+	return this.filter;
+};
+
+// 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));