MerkleTreeWithHistory.test.js 6.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219
  1. /* global artifacts, web3, contract, assert */
  2. require('chai')
  3. .use(require('bn-chai')(web3.utils.BN))
  4. .use(require('chai-as-promised'))
  5. .should()
  6. const { takeSnapshot, revertSnapshot } = require('../lib/ganacheHelper')
  7. const MerkleTreeWithHistory = artifacts.require('./MerkleTreeWithHistoryMock.sol')
  8. const hasherContract = artifacts.require('./Hasher.sol')
  9. const MerkleTree = require('../lib/MerkleTree')
  10. const hasherImpl = require('../lib/Poseidon')
  11. const { ETH_AMOUNT, MERKLE_TREE_HEIGHT, EMPTY_ELEMENT } = process.env
  12. // eslint-disable-next-line no-unused-vars
  13. function BNArrayToStringArray(array) {
  14. const arrayToPrint = []
  15. array.forEach(item => {
  16. arrayToPrint.push(item.toString())
  17. })
  18. return arrayToPrint
  19. }
  20. contract('MerkleTreeWithHistory', accounts => {
  21. let merkleTreeWithHistory
  22. let hasherInstance
  23. let levels = MERKLE_TREE_HEIGHT || 16
  24. let zeroValue = EMPTY_ELEMENT || 1337
  25. const sender = accounts[0]
  26. // eslint-disable-next-line no-unused-vars
  27. const value = ETH_AMOUNT || '1000000000000000000'
  28. let snapshotId
  29. let prefix = 'test'
  30. let tree
  31. let hasher
  32. before(async () => {
  33. tree = new MerkleTree(
  34. levels,
  35. zeroValue,
  36. null,
  37. prefix,
  38. )
  39. hasherInstance = await hasherContract.deployed()
  40. await MerkleTreeWithHistory.link(hasherContract, hasherInstance.address)
  41. merkleTreeWithHistory = await MerkleTreeWithHistory.new(levels, zeroValue)
  42. snapshotId = await takeSnapshot()
  43. })
  44. describe('#constructor', () => {
  45. it('should initialize', async () => {
  46. const filled_subtrees = await merkleTreeWithHistory.filled_subtrees()
  47. filled_subtrees[0].should.be.eq.BN(zeroValue)
  48. const zeros = await merkleTreeWithHistory.zeros()
  49. zeros[0].should.be.eq.BN(zeroValue)
  50. })
  51. })
  52. describe('merkleTreeLib', () => {
  53. it('index_to_key', () => {
  54. assert.equal(
  55. MerkleTree.index_to_key('test', 5, 20),
  56. 'test_tree_5_20',
  57. )
  58. })
  59. it('tests insert', async () => {
  60. hasher = new hasherImpl()
  61. tree = new MerkleTree(
  62. 2,
  63. zeroValue,
  64. null,
  65. prefix,
  66. )
  67. await tree.insert('5')
  68. let { root, path_elements } = await tree.path(0)
  69. const calculated_root = hasher.hash(null,
  70. hasher.hash(null, '5', path_elements[0]),
  71. path_elements[1]
  72. )
  73. // console.log(root)
  74. assert.equal(root, calculated_root)
  75. })
  76. it('creation odd elements count', async () => {
  77. const elements = [12, 13, 14, 15, 16, 17, 18, 19, 20]
  78. for(const [, el] of Object.entries(elements)) {
  79. await tree.insert(el)
  80. }
  81. const batchTree = new MerkleTree(
  82. levels,
  83. zeroValue,
  84. elements,
  85. prefix,
  86. )
  87. for(const [i] of Object.entries(elements)) {
  88. const pathViaConstructor = await batchTree.path(i)
  89. const pathViaUpdate = await tree.path(i)
  90. pathViaConstructor.should.be.deep.equal(pathViaUpdate)
  91. }
  92. })
  93. it('should find an element', async () => {
  94. const elements = [12, 13, 14, 15, 16, 17, 18, 19, 20]
  95. for(const [, el] of Object.entries(elements)) {
  96. await tree.insert(el)
  97. }
  98. let index = tree.getIndexByElement(13)
  99. index.should.be.equal(1)
  100. index = tree.getIndexByElement(19)
  101. index.should.be.equal(7)
  102. index = tree.getIndexByElement(12)
  103. index.should.be.equal(0)
  104. index = tree.getIndexByElement(20)
  105. index.should.be.equal(8)
  106. index = tree.getIndexByElement(42)
  107. index.should.be.equal(false)
  108. })
  109. it('creation even elements count', async () => {
  110. const elements = [12, 13, 14, 15, 16, 17]
  111. for(const [, el] of Object.entries(elements)) {
  112. await tree.insert(el)
  113. }
  114. const batchTree = new MerkleTree(
  115. levels,
  116. zeroValue,
  117. elements,
  118. prefix,
  119. )
  120. for(const [i] of Object.entries(elements)) {
  121. const pathViaConstructor = await batchTree.path(i)
  122. const pathViaUpdate = await tree.path(i)
  123. pathViaConstructor.should.be.deep.equal(pathViaUpdate)
  124. }
  125. })
  126. it.skip('creation using 30000 elements', () => {
  127. const elements = []
  128. for(let i = 1000; i < 31001; i++) {
  129. elements.push(i)
  130. }
  131. console.time('MerkleTree')
  132. tree = new MerkleTree(
  133. levels,
  134. zeroValue,
  135. elements,
  136. prefix,
  137. )
  138. console.timeEnd('MerkleTree')
  139. // 2,7 GHz Intel Core i7
  140. // 1000 : 1949.084ms
  141. // 10000: 19456.220ms
  142. // 30000: 63406.679ms
  143. })
  144. })
  145. describe('#insert', () => {
  146. it('should insert', async () => {
  147. let rootFromContract
  148. for (let i = 1; i < 11; i++) {
  149. await merkleTreeWithHistory.insert(i, { from: sender })
  150. await tree.insert(i)
  151. let { root } = await tree.path(i - 1)
  152. rootFromContract = await merkleTreeWithHistory.getLastRoot()
  153. root.should.be.equal(rootFromContract.toString())
  154. }
  155. })
  156. it('should reject if tree is full', async () => {
  157. levels = 6
  158. zeroValue = 1337
  159. merkleTreeWithHistory = await MerkleTreeWithHistory.new(levels, zeroValue)
  160. for (let i = 0; i < 2**levels; i++) {
  161. await merkleTreeWithHistory.insert(i+42).should.be.fulfilled
  162. }
  163. let error = await merkleTreeWithHistory.insert(1337).should.be.rejected
  164. error.reason.should.be.equal('Merkle tree is full. No more leafs can be added')
  165. error = await merkleTreeWithHistory.insert(1).should.be.rejected
  166. error.reason.should.be.equal('Merkle tree is full. No more leafs can be added')
  167. })
  168. it.skip('hasher gas', async () => {
  169. levels = 6
  170. zeroValue = 1337
  171. merkleTreeWithHistory = await MerkleTreeWithHistory.new(levels, zeroValue)
  172. const gas = await merkleTreeWithHistory.hashLeftRight.estimateGas(zeroValue, zeroValue)
  173. console.log('gas', gas - 21000)
  174. })
  175. })
  176. afterEach(async () => {
  177. await revertSnapshot(snapshotId.result)
  178. // eslint-disable-next-line require-atomic-updates
  179. snapshotId = await takeSnapshot()
  180. hasher = new hasherImpl()
  181. tree = new MerkleTree(
  182. levels,
  183. zeroValue,
  184. null,
  185. prefix,
  186. null,
  187. hasher,
  188. )
  189. })
  190. })