Skip to content

Instantly share code, notes, and snippets.

@serapath

serapath/merkleproof.js

Created May 10, 2021 22:21
Show Gist options
  • Save serapath/12a76c5d6d8fb85bb9f9f7f11a28c09a to your computer and use it in GitHub Desktop.
Save serapath/12a76c5d6d8fb85bb9f9f7f11a28c09a to your computer and use it in GitHub Desktop.
Download ZIP
merkle proof
Raw
merkleproof.js
/******************************************************************************
MERKLE PROOF
*******************************************************************************
EXAMPLE 1: (as a regular indexed tree)
,---0 = 0000 0000 0000 0000 // LVL_0 : 0 + 2 * 0 (chunk 0)
,---1 = 0000 0000 0000 0001 // LVL_1 : 1 + 4 * 0 (chunk 1)
| `---2 = 0000 0000 0000 0010 // LVL_0 : 0 + 2 * 1 (chunk 2)
|
,---3 = 0000 0000 0000 0011 // LVL_2 : 3 + 8 * 0 (chunk 3)
| |
| | ,---4 = 0000 0000 0000 0100 // LVL_0 : 0 + 2 * 2 (chunk 4)
| `---5 = 0000 0000 0000 0101 // LVL_1 : 1 + 4 * 1 (chunk 5)
| `---6 = 0000 0000 0000 0110 // LVL_0 : 0 + 2 * 3 (chunk 6)
|
|
,---7 = 0000 0000 0000 0111 // LVL_3 : 7 + 16 * 0 (chunk 7)
| |
| |
| | ,---8 = 0000 0000 0000 1000 // LVL_0 : 0 + 2 * 4 (chunk 8)
| | ,---9 = 0000 0000 0000 1001 // LVL_1 : 1 + 4 * 2 (chunk 9)
| | | `---10 = 0000 0000 0000 1010 // LVL_0 : 0 + 2 * 5 (chunk 10)
| | |
| `---11 = 0000 0000 0000 1011 // LVL_2 : 3 + 8 * 1 (chunk 11)
| |
| | ,---12 = 0000 0000 0000 1100 // LVL_0 : 0 + 2 * 6 (chunk 12)
| `---13 = 0000 0000 0000 1101 // LVL_1 : 1 + 4 * 3 (chunk 13)
| `---14 = 0000 0000 0000 1110 // LVL_0 : 0 + 2 * 7 (chunk 14)
|
|
|
--15 = 0000 0000 0000 1111 // LVL_4 : 15 + 32 * 0 (chunk 15)
|
|
|
| ,---16 = 0000 0000 0001 0000 // LVL_0 : 0 + 2 * 8 (chunk 16)
| ,---17 = 0000 0000 0001 0001 // LVL_1 : 1 + 4 * 4 (chunk 17)
| | `---18 = 0000 0000 0001 0010 // LVL_0 : 0 + 2 * 9 (chunk 18)
| |
| ,---19 = 0000 0000 0001 0011 // LVL_2 : 3 + 8 * 2 (chunk 19)
| | |
| | | ,---20 = 0000 0000 0001 0100 // LVL_0 : 0 + 2 * 10 (chunk 20)
| | `---21 = 0000 0000 0001 0101 // LVL_1 : 1 + 4 * 5 (chunk 21)
| | `---22 = 0000 0000 0001 0110 // LVL_0 : 0 + 2 * 11 (chunk 22)
| |
| |
`---23 = 0000 0000 0001 0111 // LVL_3 : 7 + 16 * 1 (chunk 23)
|
|
| ,---24 = 0000 0000 0001 1000 // LVL_0 : 0 + 2 * 12 (chunk 24)
| ,---25 = 0000 0000 0001 1001 // LVL_1 : 1 + 4 * 6 (chunk 25)
| | `---26 = 0000 0000 0001 1010 // LVL_0 : 0 + 2 * 13 (chunk 26)
| |
`---27 = 0000 0000 0001 1011 // LVL_2 : 3 + 8 * 3 (chunk 27)
|
| ,---28 = 0000 0000 0001 1100 // LVL_0 : 0 + 2 * 14 (chunk 28)
`---29 = 0000 0000 0001 1101 // LVL_1 : 1 + 4 * 7 (chunk 29)
`---30 = 0000 0000 0001 1110 // LVL_0 : 0 + 2 * 15 (chunk 30)
*******************************************************************************
EXAMPLE 1: (tree nodes sorted by LEVEL)
,---0 = 0000 0000 0000 0000 // LVL_0 : 0 + 2 * 0
| `---2 = 0000 0000 0000 0010 // LVL_0 : 0 + 2 * 1
| | ,---4 = 0000 0000 0000 0100 // LVL_0 : 0 + 2 * 2
| `---6 = 0000 0000 0000 0110 // LVL_0 : 0 + 2 * 3
| | ,---8 = 0000 0000 0000 1000 // LVL_0 : 0 + 2 * 4
| | | `---10 = 0000 0000 0000 1010 // LVL_0 : 0 + 2 * 5
| | ,---12 = 0000 0000 0000 1100 // LVL_0 : 0 + 2 * 6
| `---14 = 0000 0000 0000 1110 // LVL_0 : 0 + 2 * 7
| ,---16 = 0000 0000 0001 0000 // LVL_0 : 0 + 2 * 8
| | `---18 = 0000 0000 0001 0010 // LVL_0 : 0 + 2 * 9
| | | ,---20 = 0000 0000 0001 0100 // LVL_0 : 0 + 2 * 10
| | `---22 = 0000 0000 0001 0110 // LVL_0 : 0 + 2 * 11
| ,---24 = 0000 0000 0001 1000 // LVL_0 : 0 + 2 * 12
| | `---26 = 0000 0000 0001 1010 // LVL_0 : 0 + 2 * 13
| ,---28 = 0000 0000 0001 1100 // LVL_0 : 0 + 2 * 14
`---30 = 0000 0000 0001 1110 // LVL_0 : 0 + 2 * 15
,---1 = 0000 0000 0000 0001 // LVL_1 : 1 + 4 * 0
| `---5 = 0000 0000 0000 0101 // LVL_1 : 1 + 4 * 1
| | ,---9 = 0000 0000 0000 1001 // LVL_1 : 1 + 4 * 2
| `---13 = 0000 0000 0000 1101 // LVL_1 : 1 + 4 * 3
| ,---17 = 0000 0000 0001 0001 // LVL_1 : 1 + 4 * 4
| | `---21 = 0000 0000 0001 0101 // LVL_1 : 1 + 4 * 5
| ,---25 = 0000 0000 0001 1001 // LVL_1 : 1 + 4 * 6
`---29 = 0000 0000 0001 1101 // LVL_1 : 1 + 4 * 7
,---3 = 0000 0000 0000 0011 // LVL_2 : 3 + 8 * 0
| `---11 = 0000 0000 0000 1011 // LVL_2 : 3 + 8 * 1
| ,---19 = 0000 0000 0001 0011 // LVL_2 : 3 + 8 * 2
`---27 = 0000 0000 0001 1011 // LVL_2 : 3 + 8 * 3
,---7 = 0000 0000 0000 0111 // LVL_3 : 7 + 16 * 0
`---23 = 0000 0000 0001 0111 // LVL_3 : 7 + 16 * 1
---15 = 0000 0000 0000 1111 // LVL_4 : 15 + 32 * 0
*******************************************************************************
OBSERVATIONS
******************************************************************************/
function get_index (multiplier, level) {
/****************************************************************************
,---19 = 0000 0000 0001 0011 // LVL_2 : 3 + 8 * 2
---23 = 0000 0000 0001 0111 // LVL_3 : 7 + 16 * 1
`---27 = 0000 0000 0001 1011 // LVL_2 : 3 + 8 * 3
*****************************************************************************
OBSERVATION: D = BBBB BBBB BBBB BBBB // LVL_Z : X + Y * M
*****************************************************************************
e.g.: multiplier = 2, level = 2
(D = get_index(2, 2)) === 19 =: 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1
****************************************************************************/
const Z = level // = 2
const M = multiplier // = 2
const Y = (2n ** (Z + 1n)) // = 8
const X = (2n ** Z) - 1n // = 3
const D = X + Y * M // 19 = 3 + 8 * 2
const hash_index = D
return hash_index
}
function get_level (hash_index) {
/****************************************************************************
,---19 = 0000 0000 0001 0011 // LVL_2 : 3 + 8 * 2
---23 = 0000 0000 0001 0111 // LVL_3 : 7 + 16 * 1
`---27 = 0000 0000 0001 1011 // LVL_2 : 3 + 8 * 3
*****************************************************************************
OBSERVATION: by counting "lower" (=little endianness) "1"s until first "0"
*****************************************************************************
e.g.: hash_index = 27
*****************************************************************************
27 =: 0 0 0 0 0 0 0 0 0 0 0 1 1 0[1 1]
(Z = get_level(27)) === 2
****************************************************************************/
for (var mask = 1n, Z = 0n; hash_index & mask; mask <<= 1n) Z++
return Z
}
function get_multiplier (hash_index, level) {
/****************************************************************************
,---19 = 0000 0000 0001 0011 // LVL_2 : 3 + 8 * 2
---23 = 0000 0000 0001 0111 // LVL_3 : 7 + 16 * 1
`---27 = 0000 0000 0001 1011 // LVL_2 : 3 + 8 * 3
*****************************************************************************
OBSERVATION: by shifting away all "lowest" (=little endianness) "1"s including the first "0"
=> all remaining digits represent the multiplier
*****************************************************************************
e.g.: level = 2, hash_index = 19
*****************************************************************************
19 =: [+ + +]0 0 0 0 0 0 0 0 0 0 0 1 0[0 1 1]
(M = get_multiplier(19, 2)) === 2 =: [0 0 0]0 0 0 0 0 0 0 0 0 0 0 1 0[- - -]
****************************************************************************/
const M = hash_index >> (level + 1n) // e.g. M = 19 >> (2 + 1)
return M
}
function is_lower (multiplier) {
/****************************************************************************
,---19 = 0000 0000 0001 0011 // LVL_2 : 3 + 8 * 2
---23 = 0000 0000 0001 0111 // LVL_3 : 7 + 16 * 1
`---27 = 0000 0000 0001 1011 // LVL_2 : 3 + 8 * 3
*****************************************************************************
OBSERVATION: the first bit of the multiplier indicates the branch
*****************************************************************************
19 =: [+ + +]0 0 0 0 0 0 0 0 0 0 0 1 0[0 1 1]
(M = get_multiplier(19, 2)) === 2 =: [0 0 0]0 0 0 0 0 0 0 0 0 0 0 1 0[- - -]
e.g.: multiplier = 2
*****************************************************************************
2 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
1 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
(bool = is_lower(2)) === true
****************************************************************************/
const bit = multiplier & 1n // (bit = 2n & 1n) === 0
const bool = !bit // = !0
return bool
}
function get_sibling (t, n) {
/***************************************************************************
BITWISE XOR OPERATOR: ^
USE CASE: `keep bits the same`
(A ^ 0) === A
USE CASE: `toggle/flip bits`
(1 ^ 1) === 0
(0 ^ 1) === 1
const mask = 0b01111110
const x1 = 208 // 0b11010000
const y1 = x1 ^ mask // 0b10101110 === 174
BITWISE LEFT SHIFT OPERATOR: <<
USE CASE: `multiplying by 2**N`
(A << B) === A * (2 ** B) === A * Math.pow(2, B)
(170 << 3) === 170 * (2 ** 3) === 170 * 8 === 1360
****************************************************************************
,---17=L = 0 0 0 0 0 0 0 0 0 0 0 1 0[0]0 1
---19=P = 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1
`---21=H = 0 0 0 0 0 0 0 0 0 0 0 1 0[1]0 1
,---0=L = 0 0 0 0 0 0 0 0 0 0 0 0 0 0[0]0
---1=P = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
`---2=H = 0 0 0 0 0 0 0 0 0 0 0 0 0 0[1]0
****************************************************************************
OBSERVATION: flip the bit after the lowest "1"s and the separating "0"
****************************************************************************
e.g.:
t = 21 = 0 0 0 0 0 0 0 0 0 0 0 1 0[1]0 1
level = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 = 1 // for (var m = 1n, level = 0n; t & m; m <<= 1n) level++
mask = 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 // (1n << (level + 1)) = (1 << 2) = 1**(2**2)
sibling = 0 0 0 0 0 0 0 0 0 0 0 1 0[0]0 1 = 17
t = 17 = 0 0 0 0 0 0 0 0 0 0 0 1 0[0]0 1
level = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 // = 1 = for (var m = 1n, level = 0n; t & m; m <<= 1n) level++
mask = 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 // (1 << 2) = 1**(2**2)
sibling = 0 0 0 0 0 0 0 0 0 0 0 1 0[1]0 1 = 21
t = 2 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0[1]0
level = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 = 0 // for (var m = 1n, level = 0n; t & m; m <<= 1n) level++
mask = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 // (1n << (level + 1)) = (1 << 1) = 1 * (2**1)
sibling = 0 0 0 0 0 0 0 0 0 0 0 0 0 0[0]0 = 0 //
t = 0 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0[0]0
level = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 // = 0 = for (var m = 1n, level = 0n; t & m; m <<= 1n) level++
mask = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 // (1 << 1) = 1**(2**1)
sibling = 0 0 0 0 0 0 0 0 0 0 0 0 0 0[1]0 = 2
****************************************************************************/
// for (var m = 1n, level = 0n; t & m; m <<= 1n) level++
// const n = 1n << level
const mask = n << 1n // (n * (2**1))
// const mask = 1n << (level + 1) // === (1n << level) << 1n
const sibling = t ^ mask
return sibling
}
function get_parent (t, n) {
/****************************************************************************
,---0=L = 0 0 0 0 0 0 0 0 0 0 0 0 0 0[0 0] // LVL_0 : 0 + 2 * 0
---1=P = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
`---2=H = 0 0 0 0 0 0 0 0 0 0 0 0 0 0[1 0] // LVL_0 : 0 + 2 * 1
,---17=L = 0 0 0 0 0 0 0 0 0 0 0 1 0[0 0]1 // LVL_1 : 1 + 4 * 4
---19=P = 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1
`---21=H = 0 0 0 0 0 0 0 0 0 0 0 1 0[1 0]1 // LVL_1 : 1 + 4 * 5
*****************************************************************************
OBSERVATION: set the bit after the lowest "1"s and set the next higher bit to "0"
t = B B B B B B B B B B B B B[b,0]1
parent = B B B B B B B B B B B B B[0,1]1
*****************************************************************************
level = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 // = 1 = for (var m = 1n, level = 0n; t & m; m <<= 1n) level++
n = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 // = 1n << level
n1 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 // = n << 1
mask = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 // = ~(n1)
-----------------------------------------------------------------------
t = 2 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0[1 0]
L = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 // = t & mask
parent = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 = 1 // = L | n
-----------------------------------------------------------------------
t = 0 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0[0 0]
L = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 // = t & mask
parent = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 = 1 // = L | n
*****************************************************************************
level = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 // = 1 = for (var m = 1n, level = 0n; t & m; m <<= 1n) level++
n = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 // = 1n << level
n1 = 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 // = n << 1
mask = 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 // = ~(n1)
-----------------------------------------------------------------------
t = 17 = 0 0 0 0 0 0 0 0 0 0 0 1 0[0 0]1
L = 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 // = t & mask
parent = 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 = 19 // = L | n
-----------------------------------------------------------------------
t = 21 = 0 0 0 0 0 0 0 0 0 0 0 1 0[1 0]1
L = 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 // = t & mask
parent = 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 = 19 // = L | n
*****************************************************************************
parent = (t & ~(n << 1)) | n
****************************************************************************/
const mask = ~(n << 1n)
const L = t & mask
const parent = L | n
return parent
}
function dec2bin (dec) {
return dec.toString(2).padStart(64, '0')
}
// function pad (x) {
// return `${x}`.padStart(2, ' ')
// }
// console.log('x ', pad(x), `=`, dec2bin(x))
// console.log('y ', pad(y), `=`, dec2bin(y))
/******************************************************************************
CALCULATE
******************************************************************************/
function calculate_one (index, version) {
const max = version + 1n
return { path: calculate(index, version), root: calculate(max, max) }
}
function calculate_version (version) {
const out = { indexes: [] }
out.indexes.push(calculate_paths(version))
out.root = calculate_root(version)
return out
}
function calculate_all (versions) {
const out = { indexes: [] }
for (var i = 0n, max = versions + 1n; i < max; i++) {
out.indexes.push(calculate_paths(i))
out.root = calculate_root(i)
}
return out
}
function calculate_paths (version) {
const out = []
for (var j = 0n, max = version + 1n; j < max; j++) {
const merkle_proof_indexes = calculate(j, version)
out.push(merkle_proof_indexes)
console.log(`calculate(${version},${j}) =>`, merkle_proof_indexes)
}
return out
}
function calculate_root (max_index) {
const [version, chunk_idx] = [max_index + 1n, max_index + 1n]
const children_of_root = calculate(chunk_idx, version)
console.log(`calculate(${version}) =>`, children_of_root)
console.log('-----------------------------')
return children_of_root
}
function calculate (chunk_idx, version) {
/****************************************************************************
bitwise operations on Big Integers work as expected up to 64bits.
given a chunk (=block) is on average 64kb large it supports merkleization
of almost up to many zettabytes in size ((2*64) * 64kb)
****************************************************************************/
if (typeof chunk_idx !== 'bigint') throw new Error('`chunk_idx` must be a bigint')
if (typeof version !== 'bigint') throw new Error('`version` must be a bigint')
if (version < 0) throw new Error('`version` must be non negative')
if (chunk_idx < 0) throw new Error('`chunk_idx` must be non negative')
if (chunk_idx > version) throw new Error('`chunk_idx` must not be bigger than `version`')
const max_hash_index = (version << 1n) // version * (2**1)
const chunk_hash_index = (chunk_idx << 1n) // chunk_idx * (2**1)
const max_bigint = 2n ** (64n - 1n) - 1n
const max_version = 2n ** (64n - 2n) - 1n
if (max_hash_index > max_bigint) throw new Error('max `version` supported is ' + max_version)
const level = 0n
const out = []
/***************************************************************************/
var a = chunk_hash_index // e.g. 6 (chunk_index = 3)
var b = max_hash_index // e.g. 10 (version = 5)
var intersected = (a === b)
var bbb = false // whether some descendant of x is greater than version
var siblingA, siblingB, parentA, parentB
// while (a <= max_hash_index) {}
// siblingA = get_sibling(a)
// if (siblingA <= max_hash_index) out.push(siblingA)
// a = get_parent(a)
// LESEZEICHEN
// // siblingB = get_sibling(b, n)
// // parentA = get_parent(a, n)
// // parentB = get_parent(b, n)
// }
for (var n = 1n << level; n <= version; n <<= 1n, a = parentA, b = parentB) {
// e.g. n = (1, 2, 4, 8, 16, 32, 64, ...)
// n: 1 === 0 0001 -> (n <<= 1n): 2 === 0 0010
// n: 2 === 0 0010 -> (n <<= 1n): 4 === 0 0100
// n: 4 === 0 0100 -> (n <<= 1n): 8 === 0 1000
// n: 8 === 0 1000 -> (n <<= 1n): 16 === 1 0000
//------------------------------------------------------------------
// version = 5, chunkd_index = 3
/**
| level | n | a | siblingA | parentA | b | siblingB | parentB |
|-------|----|----|----------|---------|----|----------|---------|
| 0 | 1 | 6 | 4 | 5 | 10 | 8 | 9 |
| 1 | 2 | 5 | 1 | 3 | 9 | 13 | 11 |
| 2 | 4 | 3 | 11 | 7 | 11 | 3 | 7 |
| 3 | 8 | - | - | - | - | - | - |
**/
siblingA = get_sibling(a, n)
siblingB = get_sibling(b, n)
parentA = get_parent(a, n)
parentB = get_parent(b, n)
// n = 1, level = 0
// a = 6, siblingA = 4, parentA = 5
// b = 10, siblingB = 8, parentB = 9
// n = 2, level = 1
// a = 5, siblingA = 1, parentA = 3
// b = 9, siblingB = 13, parentB = 11
// n = 4, level = 2
// a = 3, siblingA = 11, parentA = 7
// b = 11, siblingB = 3, parentB = 7
// n = 8, level = 3
// n > version
// 1. `a` never starts out higher than `b`
// 2. at most they start out `a === b`
// 3. but otherwise always `a < b`
// if amount of tree leaves is not 2**x
// at some point BEFORE `a === b`, it is possible, that
// while walking from b (=MAX) towards ROOT, that
// parentB < siblingB, which means:
if (intersected) { // after a and b meet on their path to the root
// if SIBLING < PARENT ==> LOWER SUBTREE
if (siblingB < parentB) out.push(siblingB)
} else if (parentA === parentB) { // they meet for the first time
intersected = true
// if no decendant > version
if (!bbb) out.push(b)
} else { // a and b have not met yet
// => so `a < b`
// if no decendant of PARENT > version &&
if (!bbb && (parentB > b)) { // PARENT > B ==> HIGHER BRANCH
bbb = true
out.push(b)
} else if (bbb && (b > parentB)) out.push(siblingB)
out.push(siblingA) // A: default means add `sibling(a)` + repeat with parentA
}
/****************************************************************************
e.g.: a0 = chunk_hash_index = 6, b0 = max_hash_index = 10
,---0
,---[1] level: 0, n: 1
| `---2 level: 1, n: 2
,---3 = a2
| | ,---[4] level: 2, n: 4
| `---5 = a1
| `---6 = a0
,---7 = (a3 === b3)
| | ,---8 level: 3, n: 8
| | ,---(9) = b1
| | | `---10 = b0
-------------------------------
| `---11 = b2
| | ,---12
| `---13
| `---14
--15
| ,---16 level: 4, n: 16
| ,---17
| | `---18
| ,---19
| | | ,---20
| | `---21
| | `---22
`---23
| ,---24
| ,---25
| | `---26
`---27
| ,---28
`---29
`---30
level: 5, n: 32
****************************************************************************/
/****************************************************************************
e.g.: a0 = chunk_hash_index = 6, b0 = max_hash_index = 10
,---0
,---[1] level: 0, n: 1
| `---2 level: 1, n: 2
,---3 = a2
| | ,---[4] level: 2, n: 4
| `---5 = a1
| `---6 = a0
,---7 = (a3 === b3)
| | ,---8 level: 3, n: 8
| | ,---(9) = b1
| | | `---10 = b0
-------------------------------
| `---11 = b2
| | ,---12
| `---13
| `---14
--15
| ,---16 level: 4, n: 16
| ,---17
| | `---18
| ,---19
| | | ,---20
| | `---21
| | `---22
`---23
| ,---24
| ,---25
| | `---26
`---27
| ,---28
`---29
`---30
level: 5, n: 32
****************************************************************************/
}
// // ------------------------
// const hash_idx = chunk_idx << 1n
// const level = get_level(hash_idx)
// const multiplier = get_multiplier(hash_idx, level)
// aa && console.log('hash_idx', hash_idx)
// console.log(`level: ${level}, multiplier: ${multiplier}`)
// if (is_lower(multiplier)) {
// aa && console.log('hash_idx is lower')
// } else {
// aa && console.log('hash_idx is higher')
// }
// const hash_index = get_index(multiplier, level)
// aa && console.log('hash_idx === hash_index', hash_idx === hash_index)
// // ------------------------
// // @TODO: ... ..
// aa && console.log(`version: ${version}, chunk: ${chunk_idx}`)
// aa && console.log(`x: ${x}, y: ${y}`)
// // ------------------------
return out.sort((a,b) => a > b ? 1 : -1)
}
var aa = !true
console.log(JSON.stringify((() => {
const max_example = (2n ** (64n - 2n)) - 2n
// return calculate_one(max_example, max_example)
// return calculate_one(3n, 5n)
// return calculate_version(5n)
return calculate_all(15n)
})(), (K, V) => typeof V === 'bigint' ? V.toString() : V, 0))
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
/*
// => Retrieve the root hashes for given index
// ==> get be hashes together into the TREE HASH
feed.rootHashes(5, (err, roots) => {
for (var i = 0; i < roots.length; i++) {
console.log(roots[i]) // => Node {
// index: location in the merkle tree of this root,
// size: total bytes in children of this root,
// hash: hash of the children of this root (32-byte buffer)
// }
}
})
// Get a signature proving the correctness of the block at index, or the whole stream.
feed.signature([index], (err, signature) => {
console.log(signature) // => {
// index: lastSignedBlock,
// signature: Buffer
// }
})
FOR CHAIN: check feed.verify!!!!
*/
generate_tree(15)
function generate_tree (x) {
const dec2bin = dec => (dec >>> 0).toString(2)
const bin2dec = bin => parseInt(bin, 2).toString(10)
// ...
const max = (x * 2)
const height = Math.floor(Math.log2(max))
// const layers = Array.from({ length: height })
const lines = []
// for (var i = 0, j = 1, len1 = height + 1; i < len1; i++) {
// layers[i] = []
// j <<= 1 // j ** 2
for (var k = 0, len2 = max + 1; k < len2; k++) {
const rest = (1 << i) - 1
const mod = (1 << (i+1))
if (k % mod === rest) {
const pad = `---- `.repeat(height - i)
lines.push(`${pad} ${k}`)
}
// 0..15
// if (k % 2 === 0) layers[0].push(k)
// if (k % 4 === 1) layers[1].push(k)
// if (k % 8 === 3) layers[2].push(k)
// if (k % 16 === 7) layers[3].push(k)
// if (k % 32 === 15) layers[4].push(k)
}
console.log(JSON.stringify(lines, 0, 2))
// }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment