import '../setup' ; import { makeRepeatedBytes } from '../helpers' ; import { createMockProvider , deployContract , link , getWallets , } from 'ethereum-waffle' ; import { keccak256 , hexStrToBuf , bufToHexString , BigNumber , } from '@pigi/core-utils' ; import { newInMemoryDB , BaseDB , SparseMerkleTreeImpl } from '@pigi/core-db' ; import MemDown from 'memdown' ; import * as RollupMerkleUtils from '../../build/RollupMerkleUtils.json' ; import debug from 'debug' ; const log = debug ( 'test:info:merkle-utils' ) ; async function createSMTfromDataBlocks ( dataBlocks ) { const treeHeight = Math . ceil ( Math . log2 ( dataBlocks . length ) ) + 1 ; log ( 'Creating tree of height:' , treeHeight - 1 ) ; const tree = await getNewSMT ( treeHeight ) ; for ( let i = 0 ; i < dataBlocks . length ; i ++ ) { await tree . update ( new BigNumber ( i , 10 ) , dataBlocks [ i ] ) ; } return tree ; } async function getNewSMT ( treeHeight ) { return SparseMerkleTreeImpl . create ( newInMemoryDB ( ) , undefined , treeHeight ) ; } function makeRandomBlockOfSize ( blockSize ) { const block = [ ] ; for ( let i = 0 ; i < blockSize ; i ++ ) { block . push ( makeRepeatedBytes ( '' + Math . floor ( Math . random ( ) * 500 + 1 ) , 32 ) ) ; } return block ; } describe ( 'RollupMerkleUtils' , ( ) => { const provider = createMockProvider ( ) ; const [ wallet1 ] = getWallets ( provider ) ; let rollupMerkleUtils ; before ( async ( ) => { rollupMerkleUtils = await deployContract ( wallet1 , RollupMerkleUtils , [ ] , { gasLimit : 6700000 , } ) ; } ) ; describe ( 'getMerkleRoot() ' , async ( ) => { it ( 'should not throw' , async ( ) => { await rollupMerkleUtils . getMerkleRoot ( [ '0x1234' , '0x4321' ] ) ; } ) ; it ( 'should produce a correct merkle tree with two leaves' , async ( ) => { const block = [ '0x1234' , '0x4321' ] ; const bufBlock = block . map ( ( data ) => hexStrToBuf ( data ) ) ; const result = await rollupMerkleUtils . getMerkleRoot ( block ) ; const tree = await createSMTfromDataBlocks ( bufBlock ) ; const root = await tree . getRootHash ( ) ; result . should . equal ( bufToHexString ( root ) ) ; } ) ; it ( 'should produce a correct sparse merkle tree with three leaves' , async ( ) => { const block = [ '0x1234' , '0x4321' , '0x0420' ] ; const bufBlock = block . map ( ( data ) => hexStrToBuf ( data ) ) ; const result = await rollupMerkleUtils . getMerkleRoot ( block ) ; const tree = await createSMTfromDataBlocks ( bufBlock ) ; const root = await tree . getRootHash ( ) ; result . should . equal ( bufToHexString ( root ) ) ; } ) ; it ( 'should produce correct merkle trees with leaves ranging from 1 to 10' , async ( ) => { for ( let i = 1 ; i < 10 ; i ++ ) { const block = [ ] ; for ( let j = 0 ; j < i ; j ++ ) { block . push ( makeRepeatedBytes ( '' + Math . floor ( Math . random ( ) * 500 + 1 ) , 32 ) ) ; } const bufBlock = block . map ( ( data ) => hexStrToBuf ( data ) ) ; const result = await rollupMerkleUtils . getMerkleRoot ( block ) ; const tree = await createSMTfromDataBlocks ( bufBlock ) ; const root = await tree . getRootHash ( ) ; result . should . equal ( bufToHexString ( root ) ) ; } } ) ; } ) ; describe ( 'computeInclusionProofRoot()' , async ( ) => { it ( 'should compute the root from inclusion proof for trees of various heights' , async ( ) => { const maxBlockSize = 5 ; const minBlockSize = 1 ; for ( let blockSize = minBlockSize ; blockSize < maxBlockSize + 1 ; blockSize ++ ) { const block = makeRandomBlockOfSize ( blockSize ) ; const bufBlock = block . map ( ( data ) => hexStrToBuf ( data ) ) ; const treeHeight = Math . ceil ( Math . log2 ( bufBlock . length ) ) ; const tree = await createSMTfromDataBlocks ( bufBlock ) ; const root = await tree . getRootHash ( ) ; await rollupMerkleUtils . setMerkleRootAndHeight ( bufToHexString ( root ) , treeHeight ) ; for ( let j = 0 ; j < block . length ; j ++ ) { const indexOfNode = j ; const inclusionProof = await tree . getMerkleProof ( new BigNumber ( indexOfNode ) , bufBlock [ indexOfNode ] ) ; const path = bufToHexString ( inclusionProof . key . toBuffer ( 'B' , 32 ) ) ; const siblings = inclusionProof . siblings . map ( ( sibBuf ) => bufToHexString ( sibBuf ) ) ; const expectedRoot = bufToHexString ( inclusionProof . rootHash ) ; const calculatedRoot = await rollupMerkleUtils . computeInclusionProofRoot ( bufToHexString ( inclusionProof . value ) , path , siblings ) ; calculatedRoot . should . equal ( expectedRoot ) ; } } } ) ; } ) ; describe ( 'verify()' , async ( ) => { it ( 'should verify all the nodes of trees at various heights' , async ( ) => { const maxBlockSize = 5 ; const minBlockSize = 1 ; for ( let blockSize = minBlockSize ; blockSize < maxBlockSize + 1 ; blockSize ++ ) { const block = makeRandomBlockOfSize ( blockSize ) ; const bufBlock = block . map ( ( data ) => hexStrToBuf ( data ) ) ; const treeHeight = Math . ceil ( Math . log2 ( bufBlock . length ) ) ; const tree = await createSMTfromDataBlocks ( bufBlock ) ; const root = await tree . getRootHash ( ) ; await rollupMerkleUtils . setMerkleRootAndHeight ( bufToHexString ( root ) , treeHeight ) ; for ( let j = 0 ; j < block . length ; j ++ ) { const indexOfNode = j ; const inclusionProof = await tree . getMerkleProof ( new BigNumber ( indexOfNode ) , bufBlock [ indexOfNode ] ) ; const path = bufToHexString ( inclusionProof . key . toBuffer ( 'B' , 32 ) ) ; const siblings = inclusionProof . siblings . map ( ( sibBuf ) => bufToHexString ( sibBuf ) ) ; const isValid = await rollupMerkleUtils . verify ( bufToHexString ( inclusionProof . rootHash ) , bufToHexString ( inclusionProof . value ) , path , siblings ) ; isValid . should . equal ( true ) ; } } } ) ; } ) ; describe ( 'update()' , async ( ) => { it ( 'should update all nodes correctly in trees of various heights' , async ( ) => { const minBlockSize = 1 ; const maxBlockSize = 5 ; for ( let blockSize = minBlockSize ; blockSize < maxBlockSize ; blockSize ++ ) { const block = makeRandomBlockOfSize ( blockSize ) ; const bufBlock = block . map ( ( data ) => hexStrToBuf ( data ) ) ; const treeHeight = Math . ceil ( Math . log2 ( bufBlock . length ) ) ; const tree = await createSMTfromDataBlocks ( bufBlock ) ; const root = await tree . getRootHash ( ) ; await rollupMerkleUtils . setMerkleRootAndHeight ( root , treeHeight ) ; for ( let leafIndex = 0 ; leafIndex < block . length ; leafIndex ++ ) { const inclusionProof = await tree . getMerkleProof ( new BigNumber ( leafIndex ) , bufBlock [ leafIndex ] ) ; const path = bufToHexString ( inclusionProof . key . toBuffer ( 'B' , 32 ) ) ; const siblings = inclusionProof . siblings . map ( ( sibBuf ) => bufToHexString ( sibBuf ) ) ; await rollupMerkleUtils . store ( bufToHexString ( inclusionProof . value ) , path , siblings ) ; } const newBlock = makeRandomBlockOfSize ( blockSize ) ; const newBufBlock = newBlock . map ( ( data ) => hexStrToBuf ( data ) ) ; for ( let leafIndex = 0 ; leafIndex < block . length ; leafIndex ++ ) { await tree . update ( new BigNumber ( leafIndex ) , newBufBlock [ leafIndex ] ) ; const inclusionProof = await tree . getMerkleProof ( new BigNumber ( leafIndex ) , newBufBlock [ leafIndex ] ) ; const path = bufToHexString ( inclusionProof . key . toBuffer ( 'B' , 32 ) ) ; await rollupMerkleUtils . update ( bufToHexString ( inclusionProof . value ) , path ) ; const newContractRoot = await rollupMerkleUtils . getRoot ( ) ; const newLocalRoot = await tree . getRootHash ( ) ; newContractRoot . should . equal ( bufToHexString ( newLocalRoot ) ) ; } } } ) . timeout ( 5000 ) ; } ) ; } ) ;