import { Hash , hashArray , toBuffer , hashToBuffer , combineHashBuffers } from "../utils" ; function getNextLayer ( elements ) { return elements . reduce ( ( layer , element , index , arr ) => { if ( index % 2 === 0 ) { layer . push ( combineHashBuffers ( element , arr [ index + 1 ] ) ) ; } return layer ; } , [ ] ) ; } /**
 * This function produces the hashes and the merkle tree
 * If there are no elements, return empty array of array
 */ function getLayers ( elements ) { if ( elements . length === 0 ) { return [ [ ] ] ; } const layers = [ ] ; layers . push ( elements ) ; while ( layers [ layers . length - 1 ] . length > 1 ) { layers . push ( getNextLayer ( layers [ layers . length - 1 ] ) ) ; } return layers ; } /**
 * This function takes a given index and determines if it is the first or second element in a pair, then returns the first element of the pair
 * If the given index is the last element in a layer with an odd number of elements, then null is returned
 * E.g 1:
 *
 * layer = [ A, B, C, D ],
 * if index = 2, then return A
 * if index = 3, then return C
 *
 * E.g 2:
 *
 * layer = [ A, B, C, D, E]
 * if index = 5, then return null
 * if index = 4, then return C
 */ function getPair ( index , layer ) { const pairIndex = index % 2 ? index - 1 : index + 1 ; if ( pairIndex < layer . length ) { return layer [ pairIndex ] ; } return null ; } /**
 * Finds all the "uncle" nodes required to prove a given element in the merkle tree
 */ function getProof ( index , layers ) { let i = index ; const proof = layers . reduce ( ( current , layer ) => { const pair = getPair ( i , layer ) ; if ( pair ) { current . push ( pair ) ; } i = Math . floor ( i / 2 ) ; return current ; } , [ ] ) ; return proof ; } export class MerkleTree { public elements : Buffer [ ] ; public layers : Buffer [ ] [ ] ; public constructor ( _elements ) { this . elements = hashArray ( _elements ) ; if ( this . elements . some ( ( e ) => ! ( e . length === 32 && Buffer . isBuffer ( e ) ) ) ) { throw new Error ( "elements must be 32 byte buffers" ) ; } this . layers = getLayers ( this . elements ) ; } public getRoot ( ) { return this . layers [ this . layers . length - 1 ] [ 0 ] ; } public getProof ( _element ) { const element = toBuffer ( _element ) ; const index = this . elements . findIndex ( ( e ) => e . equals ( element ) ) ; if ( index === - 1 ) { throw new Error ( "Element not found" ) ; } return getProof ( index , this . layers ) ; } } param _proof param _root param _element export const checkProof = function ( _proof , _root , _element ) { const proof = _proof . map ( ( step ) => hashToBuffer ( step ) ) ; const root = hashToBuffer ( _root ) ; const element = hashToBuffer ( _element ) ; const proofRoot = proof . reduce ( ( hash , pair ) => combineHashBuffers ( hash , pair ) , element ) ; return root . equals ( proofRoot ) ; } ;