import { BigNumber , keccak256 , reverse , ZERO } from '@pigi/core-utils' ; import { MerkleIntervalInclusionProof , MerkleIntervalProofOutput , MerkleIntervalTree , MerkleIntervalTreeNode , } from '../../types/block-production' ; export class GenericMerkleIntervalTreeNode implements MerkleIntervalTreeNode { public data : Buffer ; constructor ( readonly hash , readonly lowerBound ) { this . data = Buffer . concat ( [ this . hash , this . lowerBound ] ) ; } } param index returns const getSiblingIndex = ( index ) : number => { return index + ( index % 2 === 0 ? 1 : - 1 ) ; } ; param index returns const getParentIndex = ( index ) : number => { return index === 0 ? 0 : Math . floor ( index / 2 ) ; } ; export class GenericMerkleIntervalTree implements MerkleIntervalTree { public levels : GenericMerkleIntervalTreeNode [ ] [ ] = [ [ ] ] ; public numLeaves : number ; constructor ( readonly dataBlocks ) { this . parseNumLeaves ( ) ; this . generateLeafNodes ( ) ; this . generateInternalNodes ( ) ; } public root ( ) { return this . levels [ this . levels . length - 1 ] [ 0 ] ; } public static hash ( value ) { return Buffer . from ( keccak256 ( value . toString ( 'hex' ) ) , 'hex' ) ; } param left param right public static parent ( left , right ) { if ( Buffer . compare ( left . lowerBound , right . lowerBound ) >= 0 ) { throw new Error ( 'Left lowerBound (0x' + left . lowerBound . toString ( 'hex' ) + ') not less than right lowerBound (0x' + right . lowerBound . toString ( 'hex' ) + ')' ) ; } const concatenated = Buffer . concat ( [ left . data , right . data ] ) ; return new GenericMerkleIntervalTreeNode ( GenericMerkleIntervalTree . hash ( concatenated ) , left . lowerBound ) ; } param ofLength public static emptyNode ( ofLength ) { const hash = Buffer . from ( new Array ( 32 ) . fill ( 0 ) ) ; const filledArray = new Array ( ofLength ) . fill ( 255 ) ; const index = Buffer . from ( filledArray ) ; return new GenericMerkleIntervalTreeNode ( hash , index ) ; } /**
     * Returns the number of leaves the tree has.
     */ private parseNumLeaves ( ) { this . numLeaves = this . dataBlocks . length ; } /**
     * Calculates the leaf GenericMerkleIntervalTreeNode for a given data block.
     */ public generateLeafNode ( dataBlock ) { return dataBlock ; } /**
     * Fills the bottom (level 0) of the tree by parsing each data block into a node.
     */ public generateLeafNodes ( ) { for ( let i = 0 ; i < this . dataBlocks . length ; i ++ ) { this . levels [ 0 ] [ i ] = this . generateLeafNode ( this . dataBlocks [ i ] ) ; } } /**
     * Generates the other levels of the tree once the leaf nodes have been parsed.
     */ private generateInternalNodes ( ) { const numInternalLevels = Math . ceil ( Math . log2 ( this . numLeaves ) ) ; for ( let level = 0 ; level < numInternalLevels ; level ++ ) { this . generateLevelAbove ( level ) ; } } param level private calculateNumNodesinLevel ( level ) { return Math . ceil ( this . numLeaves / 2 ** level ) ; } param level private generateLevelAbove ( level ) { this . levels [ level + 1 ] = [ ] ; const numNodesInLevel = this . calculateNumNodesinLevel ( level ) ; for ( let i = 0 ; i < numNodesInLevel ; i += 2 ) { const left = this . levels [ level ] [ i ] ; const right = i + 1 === numNodesInLevel ? GenericMerkleIntervalTree . emptyNode ( left . lowerBound . length ) : this . levels [ level ] [ i + 1 ] ; const parent = GenericMerkleIntervalTree . parent ( left , right ) ; const parentIndex = getParentIndex ( i ) ; this . levels [ level + 1 ] [ parentIndex ] = parent ; } } param leafPosition public getInclusionProof ( leafPosition ) { if ( ! ( leafPosition in this . levels [ 0 ] ) ) { throw new Error ( 'Leaf index ' + leafPosition + ' not in bottom level of tree' ) ; } const inclusionProof = [ ] ; let parentIndex ; let siblingIndex = getSiblingIndex ( leafPosition ) ; for ( let i = 0 ; i < this . levels . length - 1 ; i ++ ) { const level = this . levels [ i ] ; const node = level [ siblingIndex ] || GenericMerkleIntervalTree . emptyNode ( level [ 0 ] . lowerBound . length ) ; inclusionProof . push ( node ) ; parentIndex = getParentIndex ( siblingIndex ) ; siblingIndex = getSiblingIndex ( parentIndex ) ; } return { siblings : inclusionProof , leafPosition : new BigNumber ( leafPosition ) , } ; } param leafNode param leafPosition param inclusionProof param root returns public static verify ( leafNode , inclusionProof , rootHash ) { const rootAndBounds = GenericMerkleIntervalTree . getRootAndBounds ( leafNode , inclusionProof ) ; if ( Buffer . compare ( rootAndBounds . root . hash , rootHash ) !== 0 ) { throw new Error ( 'Invalid Merkle Index Tree roothash.' ) ; } else { return true ; } } public static getRootAndBounds ( leafNode , inclusionProof ) { if ( inclusionProof . leafPosition . lt ( ZERO ) ) { throw new Error ( 'Invalid leaf position.' ) ; } const path = reverse ( new BigNumber ( inclusionProof . leafPosition ) . toString ( 2 , inclusionProof . siblings . length ) ) ; const firstRightSiblingIndex = path . indexOf ( '0' ) ; const firstRightSibling = firstRightSiblingIndex >= 0 ? inclusionProof . siblings [ firstRightSiblingIndex ] : undefined ; let computed = leafNode ; let left ; let right ; for ( let i = 0 ; i < inclusionProof . siblings . length ; i ++ ) { const sibling = inclusionProof . siblings [ i ] ; if ( path [ i ] === '1' ) { left = sibling ; right = computed ; } else { left = computed ; right = sibling ; if ( firstRightSibling && Buffer . compare ( right . lowerBound , firstRightSibling . lowerBound ) === - 1 ) { throw new Error ( 'Invalid Merkle Index Tree proof--potential intersection detected.' ) ; } } computed = this . parent ( left , right ) ; } const implicitEnd = firstRightSibling ? firstRightSibling . lowerBound : GenericMerkleIntervalTree . emptyNode ( leafNode . lowerBound . length ) . lowerBound ; return { root : computed , upperBound : new BigNumber ( implicitEnd ) , } ; } }