API tools faq
paste
ff19

benchlab-constellationjs

ff19
Jul 7th, 2018
308
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Diff 49.82 KB | None | 0 0
raw download clone embed print report
  1. diff --git b/index.js a/index.js
  2. index 0c1c1b2..bc4992d 100755
  3. --- b/index.js
  4. +++ a/index.js
  5. @@ -1 +1 @@
  6. -module.exports = require('./src/merk.js')
  7. +module.exports = require('./src/constellation.js')
  8. diff --git b/package.json a/package.json
  9. index bbc5b32..946785d 100755
  10. --- b/package.json
  11. +++ a/package.json
  12. @@ -1,7 +1,7 @@
  13.  {
  14. -  "name": "merk",
  15. -  "version": "1.1.1",
  16. -  "description": "A Merkle tree with the simplest interface ever",
  17. +  "name": "constellationsjs",
  18. +  "version": "0.1.6",
  19. +  "description": "constellationsJS features a simple interface for Merkle Trees and works directly with dappJS, MoonCoin, MoonContracts and BenchCore.",
  20.    "main": "index.js",
  21.    "dependencies": {
  22.      "create-hash": "^1.1.3",
  23. @@ -27,6 +27,6 @@
  24.        "!test/common.js"
  25.      ]
  26.    },
  27. -  "author": "Matt Bell <[email protected]>",
  28. +  "1author": "BenchX <[email protected]>",
  29.    "license": "MIT"
  30.  }
  31. diff --git b/src/common.js a/src/common.js
  32. index 4c23d5e..2cc571e 100755
  33. --- b/src/common.js
  34. +++ a/src/common.js
  35. @@ -19,11 +19,12 @@ function isObject (value) {
  36.    return typeof value === 'object' && value != null
  37.  }
  38.  
  39. -// clones an object, without any properties of type 'object'
  40.  function baseObject (obj) {
  41.    if (!isObject(obj)) return obj
  42.    let base = {}
  43. -  if (Array.isArray(obj)) base = []
  44. +  if (Array.isArray(obj)) {
  45. +    base.length = obj.length
  46. +  }
  47.    for (let key in obj) {
  48.      let value = obj[key]
  49.      if (isObject(value)) continue
  50. @@ -32,7 +33,6 @@ function baseObject (obj) {
  51.    return base
  52.  }
  53.  
  54. -// gets an object property based on an array key path
  55.  function access (obj, path) {
  56.    if (path.length === 0) {
  57.      return [ obj, true ]
  58. @@ -48,12 +48,10 @@ function access (obj, path) {
  59.    return access(obj[key], subpath)
  60.  }
  61.  
  62. -// shallow clone
  63.  function clone (value) {
  64.    if (!isObject(value)) return value
  65.    if (Array.isArray(value)) return value.slice()
  66.    let cloned = {}
  67. -  // doesn't include symbols
  68.    for (let key in value) {
  69.      cloned[key] = value[key]
  70.    }
  71. @@ -62,13 +60,11 @@ function clone (value) {
  72.  
  73.  function pathToKey (path) {
  74.    if (path.length === 0) return symbols.root
  75. -  // TODO: support path components w/ "." character ('["foo.bar"]')
  76.    return path.join('.')
  77.  }
  78.  
  79.  function keyToPath (key) {
  80.    if (key === symbols.root) return []
  81. -  // TODO: support path components w/ "." character ('["foo.bar"]')
  82.    return key.split('.')
  83.  }
  84.  
  85. diff --git b/src/constellation.js a/src/constellation.js
  86. index 7589f79..c64dc45 100755
  87. --- b/src/constellation.js
  88. +++ a/src/constellation.js
  89. @@ -6,13 +6,11 @@ let verify = require('./verify.js')
  90.  let createProof = require('./proof.js')
  91.  let { symbols } = require('./common.js')
  92.  
  93. -async function createMerk (db) {
  94. +async function createConstellation (db) {
  95.    if (!db || db.toString() !== 'LevelUP') {
  96.      throw Error('Must provide a LevelUP instance')
  97.    }
  98.  
  99. -  // TODO: decouple state wrapper from tree
  100. -  // (could be used with any LevelUp)
  101.    let tree = Tree(db)
  102.    let mutations = MutationStore()
  103.  
  104. @@ -27,10 +25,9 @@ async function createMerk (db) {
  105.  
  106.  function assertRoot (root) {
  107.    if (root[symbols.mutations] != null) return
  108. -  throw Error('Must specify a root merk object')
  109. +  throw Error('Must specify a root constellation object')
  110.  }
  111.  
  112. -// revert to last commit
  113.  function rollback (root) {
  114.    assertRoot(root)
  115.    let mutations = root[symbols.mutations]()
  116. @@ -38,7 +35,6 @@ function rollback (root) {
  117.    mutations.rollback(unwrappedRoot)
  118.  }
  119.  
  120. -// flush to db
  121.  function commit (root) {
  122.    assertRoot(root)
  123.    let mutations = root[symbols.mutations]()
  124. @@ -46,14 +42,12 @@ function commit (root) {
  125.    return mutations.commit(db)
  126.  }
  127.  
  128. -// returns merkle root
  129.  function hash (root) {
  130.    assertRoot(root)
  131.    let tree = root[symbols.db]()
  132.    return tree.rootHash().toString('hex')
  133.  }
  134.  
  135. -// returns a merkle proof
  136.  function proof (root, query = '') {
  137.    assertRoot(root)
  138.    let tree = root[symbols.db]()
  139. @@ -67,7 +61,7 @@ function getter (symbol) {
  140.    }
  141.  }
  142.  
  143. -module.exports = Object.assign(createMerk, {
  144. +module.exports = Object.assign(createConstellation, {
  145.    mutations: getter(symbols.mutations),
  146.    rollback,
  147.    commit,
  148. diff --git b/src/json.js a/src/json.js
  149. index 26f34e0..f749d69 100755
  150. --- b/src/json.js
  151. +++ a/src/json.js
  152. @@ -2,20 +2,16 @@ let stableStringify = require('json-stable-stringify')
  153.  
  154.  const base64Prefix = ':base64:'
  155.  
  156. -// stringifies JSON deterministically, and converts Buffers to
  157. -// base64 strings (prefixed with ":base64:")
  158.  function stringify (obj) {
  159.    let convertedObj = deepClone(obj, bufferToBase64Replacer)
  160.    return stableStringify(convertedObj)
  161.  }
  162.  
  163. -// parses JSON and converts strings with ":base64:" prefix to Buffers
  164.  function parse (json) {
  165.    let obj = JSON.parse(json)
  166.    return convertBase64ToBuffers(obj)
  167.  }
  168.  
  169. -// clones an object, with a replacer function
  170.  function deepClone (obj, replacer) {
  171.    let newObj = Array.isArray(obj) ? [] : {}
  172.    Object.assign(newObj, obj)
  173. @@ -29,8 +25,6 @@ function deepClone (obj, replacer) {
  174.  }
  175.  
  176.  function bufferToBase64Replacer (value) {
  177. -  // convert JSON.stringified Buffer objects to Buffer,
  178. -  // so they can get encoded to base64
  179.    if (
  180.      typeof value === 'object' &&
  181.      value.type === 'Buffer' &&
  182. @@ -55,12 +49,10 @@ function convertBase64ToBuffers (obj) {
  183.    return replace(obj, base64ToBufferReplacer)
  184.  }
  185.  
  186. -// replaces values in an object without cloning
  187.  function replace (obj, replacer) {
  188.    for (let key in obj) {
  189.      obj[key] = replacer(obj[key])
  190.      if (typeof obj[key] === 'object' && !Buffer.isBuffer(obj[key])) {
  191. -      // recursively replace props of objects (unless it's a Buffer)
  192.        replace(obj[key], replacer)
  193.      }
  194.    }
  195. diff --git b/src/load.js a/src/load.js
  196. index e417f57..2a9aabe 100755
  197. --- b/src/load.js
  198. +++ a/src/load.js
  199. @@ -1,15 +1,11 @@
  200.  let { access, keyToPath } = require('./common.js')
  201.  let { parse } = require('./json.js')
  202.  
  203. -// load existing data if it exists
  204.  async function load (tree) {
  205. -  // TODO: decouple from tree
  206. -  // (could be levelup createReadStream)
  207.  
  208.    let rootNode = await tree.rootNode()
  209. -  if (!rootNode) return {} // no existing data
  210. +  if (!rootNode) return {}
  211.  
  212. -  // get root object
  213.    let cursor = await rootNode.min()
  214.    let root = {}
  215.  
  216. @@ -19,8 +15,6 @@ async function load (tree) {
  217.      cursor = await cursor.next()
  218.    }
  219.  
  220. -  // iterate through all keys in order,
  221. -  // create objects based on key/value
  222.    while (cursor) {
  223.      let path = keyToPath(cursor.key.slice(1))
  224.      let [ parent ] = access(root, path.slice(0, -1))
  225. diff --git b/src/mutationStore.js a/src/mutationStore.js
  226. index 298ee1f..3cd4150 100755
  227. --- b/src/mutationStore.js
  228. +++ a/src/mutationStore.js
  229. @@ -62,7 +62,9 @@ class MutationStore {
  230.  
  231.    rollback (state) {
  232.      // reapply previous values
  233. -    for (let key in this.before) {
  234. +    let beforeKeys = Object.keys(this.before)
  235. +    beforeKeys.sort()
  236. +    for (let key of beforeKeys) {
  237.        let value = this.before[key]
  238.        let path = keyToPath(key)
  239.  
  240. @@ -72,7 +74,13 @@ class MutationStore {
  241.        if (value === symbols.delete) {
  242.          delete parent[lastKey]
  243.        } else {
  244. -        updateBase(parent[lastKey], value)
  245. +        let base = parent[lastKey]
  246. +        // handle restoring a deleted array child-object
  247. +        if (Array.isArray(parent) && base == null) {
  248. +          parent[lastKey] = value
  249. +        } else {
  250. +          updateBase(base, value)
  251. +        }
  252.        }
  253.      }
  254.  
  255. diff --git b/src/node.js a/src/node.js
  256. index 0bf7d8b..cb3ef11 100755
  257. --- b/src/node.js
  258. +++ a/src/node.js
  259. @@ -5,7 +5,7 @@ let { sha256, ripemd160 } = require('./common.js')
  260.  const nullHash = Buffer.alloc(20)
  261.  
  262.  let VarString = struct.VarString(VarInt)
  263. -let codec = struct([
  264. +let adapter = struct([
  265.    ['hash', struct.Buffer(20)],
  266.    ['kvHash', struct.Buffer(20)],
  267.    ['leftHeight', struct.UInt8],
  268. @@ -36,21 +36,21 @@ function nodeKey (key) {
  269.    return 'n' + key
  270.  }
  271.  
  272. -function putNode (tx, node) {
  273. -  let nodeBytes = codec.encode(node).toString('base64')
  274. -  return tx.put(nodeKey(node.key), nodeBytes)
  275. +function putNode (ntx, node) {
  276. +  let nodeBytes = adapter.encode(node).toString('base64')
  277. +  return ntx.put(nodeKey(node.key), nodeBytes)
  278.  }
  279.  
  280. -function delNode (tx, node) {
  281. -  return tx.del(nodeKey(node.key))
  282. +function delNode (ntx, node) {
  283. +  return ntx.del(nodeKey(node.key))
  284.  }
  285.  
  286.  module.exports = function (db) {
  287. -  async function getNode (tx, key) {
  288. +  async function getNode (ntx, key) {
  289.      if (key === '') return null
  290. -    let nodeB64 = (await tx.get(nodeKey(key))).toString()
  291. +    let nodeB64 = (await ntx.get(nodeKey(key))).toString()
  292.      let nodeBytes = Buffer.from(nodeB64, 'base64')
  293. -    let decoded = codec.decode(nodeBytes)
  294. +    let decoded = adapter.decode(nodeBytes)
  295.      decoded.key = key
  296.      return new Node(decoded)
  297.    }
  298. @@ -82,28 +82,28 @@ module.exports = function (db) {
  299.        return !this.isInnerNode()
  300.      }
  301.  
  302. -    left (tx) {
  303. -      return getNode(tx, this.leftKey)
  304. +    left (ntx) {
  305. +      return getNode(ntx, this.leftKey)
  306.      }
  307.  
  308. -    right (tx) {
  309. -      return getNode(tx, this.rightKey)
  310. +    right (ntx) {
  311. +      return getNode(ntx, this.rightKey)
  312.      }
  313.  
  314. -    child (tx, left) {
  315. -      if (left) return this.left(tx)
  316. -      return this.right(tx)
  317. +    child (ntx, left) {
  318. +      if (left) return this.left(ntx)
  319. +      return this.right(ntx)
  320.      }
  321.  
  322. -    parent (tx) {
  323. -      return getNode(tx, this.parentKey)
  324. +    parent (ntx) {
  325. +      return getNode(ntx, this.parentKey)
  326.      }
  327.  
  328. -    save (tx) {
  329. -      return putNode(tx, this)
  330. +    save (ntx) {
  331. +      return putNode(ntx, this)
  332.      }
  333.  
  334. -    async setChild (tx, left, child, rebalance = true) {
  335. +    async setChild (ntx, left, child, rebalance = true) {
  336.        if (child != null) {
  337.          child.parentKey = this.key
  338.        } else {
  339. @@ -114,15 +114,15 @@ module.exports = function (db) {
  340.        this[left ? 'leftHeight' : 'rightHeight'] = child.height()
  341.  
  342.        if (rebalance && Math.abs(this.balance()) > 1) {
  343. -        return this.rebalance(tx)
  344. +        return this.rebalance(ntx)
  345.        }
  346.  
  347. -      let leftChild = left ? child : await this.left(tx)
  348. -      let rightChild = !left ? child : await this.right(tx)
  349. +      let leftChild = left ? child : await this.left(ntx)
  350. +      let rightChild = !left ? child : await this.right(ntx)
  351.        this.calculateHash(leftChild, rightChild)
  352.  
  353. -      await this.save(tx)
  354. -      await child.save(tx)
  355. +      await this.save(ntx)
  356. +      await child.save(ntx)
  357.        return this
  358.      }
  359.  
  360. @@ -130,27 +130,26 @@ module.exports = function (db) {
  361.        return this.rightHeight - this.leftHeight
  362.      }
  363.  
  364. -    async rebalance (tx) {
  365. +    async rebalance (ntx) {
  366.        let left = this.balance() < 0
  367. -      let child = await this.child(tx, left)
  368. +      let child = await this.child(ntx, left)
  369.  
  370. -      // check if we should do a double rotation
  371.        let childLeftHeavy = child.balance() < 0
  372.        let childRightHeavy = child.balance() > 0
  373.        let double = left ? childRightHeavy : childLeftHeavy
  374.        if (double) {
  375. -        let successor = await child.rotate(tx, !left)
  376. -        await this.setChild(tx, left, successor, false)
  377. +        let successor = await child.rotate(ntx, !left)
  378. +        await this.setChild(ntx, left, successor, false)
  379.        }
  380. -      return this.rotate(tx, left)
  381. +      return this.rotate(ntx, left)
  382.      }
  383.  
  384. -    async rotate (tx, left) {
  385. -      let child = await this.child(tx, left)
  386. -      let grandChild = await child.child(tx, !left)
  387. -      await this.setChild(tx, left, grandChild, false)
  388. +    async rotate (ntx, left) {
  389. +      let child = await this.child(ntx, left)
  390. +      let grandChild = await child.child(ntx, !left)
  391. +      await this.setChild(ntx, left, grandChild, false)
  392.        child.parentKey = ''
  393. -      await child.setChild(tx, !left, this, false)
  394. +      await child.setChild(ntx, !left, this, false)
  395.        return child
  396.      }
  397.  
  398. @@ -177,69 +176,61 @@ module.exports = function (db) {
  399.        return this.kvHash
  400.      }
  401.  
  402. -    async put (node, tx) {
  403. +    async put (node, ntx) {
  404.        if (node.key === this.key) {
  405. -        // same key, just update the value of this node
  406.          this.value = node.value
  407.          this.calculateKVHash()
  408. -        this.calculateHash(await this.left(tx), await this.right(tx))
  409. -        await this.save(tx)
  410. +        this.calculateHash(await this.left(ntx), await this.right(ntx))
  411. +        await this.save(ntx)
  412.          return this
  413.        }
  414.  
  415.        let left = node.key < this.key
  416. -      let child = await this.child(tx, left)
  417. +      let child = await this.child(ntx, left)
  418.        if (child == null) {
  419. -        // no child here, set node as child
  420. -        let successor = await this.setChild(tx, left, node)
  421. +        let successor = await this.setChild(ntx, left, node)
  422.          return successor
  423.        }
  424.  
  425. -      // recursively put node under child, then update self
  426. -      let newChild = await child.put(node, tx)
  427. -      let successor = await this.setChild(tx, left, newChild)
  428. +      let newChild = await child.put(node, ntx)
  429. +      let successor = await this.setChild(ntx, left, newChild)
  430.        return successor
  431.      }
  432.  
  433. -    async delete (key, tx) {
  434. +    async delete (key, ntx) {
  435.        if (key === this.key) {
  436. -        // delete this node
  437.  
  438.          if (this.isLeafNode()) {
  439. -          // no children
  440. -          await delNode(tx, this)
  441. +          await delNode(ntx, this)
  442.            return null
  443.          }
  444.  
  445. -        // promote successor child to this position
  446.          let left = this.leftHeight > this.rightHeight
  447. -        let successor = await this.child(tx, left)
  448. +        let successor = await this.child(ntx, left)
  449.          successor.parentKey = this.parentKey
  450. -        let otherNode = await this.child(tx, !left)
  451. +        let otherNode = await this.child(ntx, !left)
  452.          if (otherNode) {
  453. -          // if there is another child then put it under successor
  454. -          successor = await successor.put(otherNode, tx)
  455. +          successor = await successor.put(otherNode, ntx)
  456.          }
  457. -        await delNode(tx, this)
  458. +        await delNode(ntx, this)
  459.          return successor
  460.        }
  461.  
  462.        let left = key < this.key
  463. -      let child = await this.child(tx, left)
  464. +      let child = await this.child(ntx, left)
  465.        if (child == null) {
  466. -        // no child here, key not found
  467.          throw Error(`Key "${key}" not found`)
  468.        }
  469.  
  470. -      let newChild = await child.delete(key, tx)
  471. -      let successor = await this.setChild(tx, left, newChild)
  472. +      let newChild = await child.delete(key, ntx)
  473. +      let successor = await this.setChild(ntx, left, newChild)
  474.        return successor
  475.      }
  476.  
  477. -    async edge (left, tx = db) {
  478. +    async edge (left, ntx = db) {
  479.        let cursor = this
  480.        while (true) {
  481. -        let child = await cursor.child(tx, left)
  482. +        let child = await cursor.child(ntx, left)
  483.          if (child == null) return cursor
  484.          cursor = child
  485.        }
  486. @@ -247,29 +238,27 @@ module.exports = function (db) {
  487.      min () { return this.edge(true) }
  488.      max () { return this.edge(false) }
  489.  
  490. -    async step (left, tx = db) {
  491. -      let child = await this.child(tx, left)
  492. -      if (child) return child.edge(!left, tx)
  493. +    async step (left, ntx = db) {
  494. +      let child = await this.child(ntx, left)
  495. +      if (child) return child.edge(!left, ntx)
  496.  
  497. -      // backtrack
  498. -      let cursor = await this.parent(tx)
  499. +      let cursor = await this.parent(ntx)
  500.        while (cursor) {
  501.          let skip = left
  502.            ? cursor.key > this.key
  503.            : cursor.key < this.key
  504.          if (!skip) return cursor
  505. -        cursor = await cursor.parent(tx)
  506. +        cursor = await cursor.parent(ntx)
  507.        }
  508.  
  509. -      // reached end
  510.        return null
  511.      }
  512.      prev () { return this.step(true) }
  513.      next () { return this.step(false) }
  514.  
  515. -    async getBranchRange (from, to, tx) {
  516. -      let left = await this.left(tx)
  517. -      let right = await this.right(tx)
  518. +    async getBranchRange (from, to, ntx) {
  519. +      let left = await this.left(ntx)
  520. +      let right = await this.right(ntx)
  521.  
  522.        let branch = {
  523.          left: left ? left.hash.toString('base64') : null,
  524. @@ -278,11 +267,13 @@ module.exports = function (db) {
  525.  
  526.        async function isInRange (node) {
  527.          if (node.key < from) {
  528. -          let next = await node.next(tx)
  529. +          let next = await node.next(ntx)
  530. +          if (next == null) return true
  531.            return next.key >= from
  532.          }
  533.          if (node.key > to) {
  534. -          let prev = await node.prev(tx)
  535. +          let prev = await node.prev(ntx)
  536. +          if (prev == null) return true
  537.            return prev.key <= to
  538.          }
  539.          return true
  540. @@ -296,16 +287,16 @@ module.exports = function (db) {
  541.        }
  542.  
  543.        if (left && this.key >= from) {
  544. -        branch.left = await left.getBranchRange(from, to, tx)
  545. +        branch.left = await left.getBranchRange(from, to, ntx)
  546.        }
  547.        if (right && this.key <= to) {
  548. -        branch.right = await right.getBranchRange(from, to, tx)
  549. +        branch.right = await right.getBranchRange(from, to, ntx)
  550.        }
  551.  
  552.        return branch
  553.      }
  554.    }
  555.  
  556. -  Node.get = (key, tx = db) => getNode(db, key)
  557. +  Node.get = (key, ntx = db) => getNode(db, key)
  558.    return Node
  559.  }
  560. diff --git b/src/proof.js a/src/proof.js
  561. index c5b6ac3..469eedd 100755
  562. --- b/src/proof.js
  563. +++ a/src/proof.js
  564. @@ -1,18 +1,14 @@
  565.  module.exports = async function createProof (tree, query) {
  566. -  // range is query path, and all its child objects
  567.    let from = '.' + query
  568. -  let to = '.' + query + '/' // 1 value past `query + '.'`
  569. +  let to = '.' + query + '/'
  570.  
  571. -  // special case for root object (get all values)
  572.    if (query === '') to = '/'
  573.  
  574. -  // check if there is a match for this query
  575.    try {
  576.      await tree.get(from)
  577.    } catch (err) {
  578.      if (!err.notFound) throw err
  579.  
  580. -    // if not, query parent object
  581.      let path = query.split('.')
  582.      query = path.slice(0, -1).join('.')
  583.      from = '.' + query
  584. diff --git b/src/tree.js a/src/tree.js
  585. index fa216d2..d2350ce 100755
  586. --- b/src/tree.js
  587. +++ a/src/tree.js
  588. @@ -38,12 +38,12 @@ class Tree {
  589.      return this._rootNode.hash
  590.    }
  591.  
  592. -  async setRoot (node, tx) {
  593. +  async setRoot (node, ntx) {
  594.      await this.initialize
  595.  
  596. -    if (!tx) {
  597. -      tx = createTx(this.db)
  598. -      var createdTx = true
  599. +    if (!ntx) {
  600. +      ntx = createNtx(this.db)
  601. +      var createdNtx = true
  602.      }
  603.  
  604.      if (node != null) {
  605. @@ -54,8 +54,8 @@ class Tree {
  606.  
  607.      this._rootNode = node
  608.  
  609. -    if (createdTx) {
  610. -      await tx.commit()
  611. +    if (createdNtx) {
  612. +      await ntx.commit()
  613.      }
  614.    }
  615.  
  616. @@ -82,21 +82,21 @@ class Tree {
  617.  
  618.      let release = await this.acquireLock()
  619.  
  620. -    let tx = createTx(this.db)
  621. +    let ntx = createNtx(this.db)
  622.      let node = new this.Node({ key, value, db: this.db })
  623.  
  624.      // no root, set node as root
  625.      if (this._rootNode == null) {
  626. -      await node.save(tx)
  627. -      await this.setRoot(node, tx)
  628. -      await tx.commit()
  629. +      await node.save(ntx)
  630. +      await this.setRoot(node, ntx)
  631. +      await ntx.commit()
  632.        release()
  633.        return
  634.      }
  635.  
  636. -    let successor = await this._rootNode.put(node, tx)
  637. -    await this.setRoot(successor, tx)
  638. -    await tx.commit()
  639. +    let successor = await this._rootNode.put(node, ntx)
  640. +    await this.setRoot(successor, ntx)
  641. +    await ntx.commit()
  642.      release()
  643.    }
  644.  
  645. @@ -114,10 +114,10 @@ class Tree {
  646.  
  647.      let release = await this.acquireLock()
  648.  
  649. -    let tx = createTx(this.db)
  650. -    let successor = await this._rootNode.delete(key, tx)
  651. -    await this.setRoot(successor, tx)
  652. -    await tx.commit()
  653. +    let ntx = createNtx(this.db)
  654. +    let successor = await this._rootNode.delete(key, ntx)
  655. +    await this.setRoot(successor, ntx)
  656. +    await ntx.commit()
  657.  
  658.      release()
  659.    }
  660. @@ -133,14 +133,13 @@ class Tree {
  661.  
  662.  module.exports = old(Tree)
  663.  
  664. -// promsifies level-transactions methods
  665. -function createTx (db) {
  666. -  let tx = new Transaction(db)
  667. +function createNtx (db) {
  668. +  let ntx = new Transaction(db)
  669.    return {
  670. -    get: promisify(tx, 'get'),
  671. -    put: promisify(tx, 'put'),
  672. -    del: promisify(tx, 'del'),
  673. -    commit: promisify(tx, 'commit')
  674. +    get: promisify(ntx, 'get'),
  675. +    put: promisify(ntx, 'put'),
  676. +    del: promisify(ntx, 'del'),
  677. +    commit: promisify(ntx, 'commit')
  678.    }
  679.  }
  680.  
  681. diff --git b/src/verify.js a/src/verify.js
  682. index 3604094..a26ecc2 100755
  683. --- b/src/verify.js
  684. +++ a/src/verify.js
  685. @@ -54,9 +54,16 @@ function flatten (node, nodes = [], path = []) {
  686.    if (path.length === 0) {
  687.      node.isEdge = node.left == null || node.right == null
  688.    } else {
  689. -    node.isEdge = (path.length === 1 ||
  690. -      path.reduce((a, b) => a === b)) &&
  691. -      node.left == null && node.right == null
  692. +    let equal = true
  693. +    for (let i = 1; i < path.length; i++) {
  694. +      if (path[i] !== path[i - 1]) {
  695. +        equal = false
  696. +        break
  697. +      }
  698. +    }
  699. +    let leftEdge = path[0] === false
  700. +    let noChildOnEdge = leftEdge ? node.left == null : node.right == null
  701. +    node.isEdge = equal && noChildOnEdge
  702.    }
  703.  
  704.    nodes.push(node)
  705. @@ -77,7 +84,6 @@ module.exports = function verify (expectedRootHash, proof, query = '') {
  706.    if (query === '') to = '/'
  707.    let nodes = flatten(proof)
  708.  
  709. -  // get contiguous nodes which have key/value
  710.    let valueNodes = []
  711.    for (let node of nodes) {
  712.      if (!node.key) {
  713. @@ -87,7 +93,6 @@ module.exports = function verify (expectedRootHash, proof, query = '') {
  714.      valueNodes.push(node)
  715.    }
  716.  
  717. -  // ensure we have proof of the entire range
  718.    let checkRange = () => {
  719.      let firstKeyPastFrom = valueNodes[0].key >= from
  720.      let firstKeyIsEdge = valueNodes[0].isEdge
  721. @@ -102,12 +107,11 @@ module.exports = function verify (expectedRootHash, proof, query = '') {
  722.      }
  723.    }
  724.  
  725. -  let resultNodes = valueNodes.filter((node) => {
  726. +  let discoveryNodes = valueNodes.filter((node) => {
  727.      return node.key >= from && node.key <= to
  728.    })
  729.  
  730. -  // try getting parent object
  731. -  if (resultNodes.length === 0) {
  732. +  if (discoveryNodes.length === 0) {
  733.      let path = query.split('.')
  734.      let parentKey = '.' + path.slice(0, -1).join('.')
  735.      let valueKey = path[path.length - 1]
  736. @@ -130,24 +134,23 @@ module.exports = function verify (expectedRootHash, proof, query = '') {
  737.  
  738.    checkRange()
  739.  
  740. -  let result
  741. -  for (let node of resultNodes) {
  742. -    // remove query prefix
  743. +  let discovery
  744. +  for (let node of discoveryNodes) {
  745.      let key = node.key.slice(from.length)
  746.      if (key === '') key = symbols.root
  747.  
  748. -    // add parsed value to result
  749.      let path = keyToPath(key)
  750.      if (path[0] === '') path.shift()
  751.      let value = parse(node.value)
  752.  
  753.      if (path.length === 0) {
  754. -      result = value
  755. +      discovery = value
  756.      } else {
  757. -      let [ parent ] = access(result, path.slice(0, -1))
  758. +      if (!discovery) discovery = {}
  759. +      let [ parent ] = access(discovery, path.slice(0, -1))
  760.        let name = path[path.length - 1]
  761.        parent[name] = value
  762.      }
  763.    }
  764. -  return result
  765. +  return discovery
  766.  }
  767. diff --git b/src/wrap.js a/src/wrap.js
  768. index 03f507c..76f577f 100755
  769. --- b/src/wrap.js
  770. +++ a/src/wrap.js
  771. @@ -1,6 +1,5 @@
  772.  let { isObject, baseObject, access } = require('./common.js')
  773.  
  774. -// wraps an object with a proxy, so we can keep track of mutations
  775.  function wrap (obj, onMutate, path = []) {
  776.    function recordMutation (op, childPath, value) {
  777.      let fullPath = path.concat(childPath)
  778. @@ -17,44 +16,37 @@ function wrap (obj, onMutate, path = []) {
  779.        existed
  780.      }
  781.      onMutate(mutation)
  782. -    // TODO: replace mutations for overriden paths
  783.    }
  784.  
  785. -  // TODO: wrap array methods to record array-specific mutations,
  786. -  // otherwise ops like splices and shifts will create N mutations
  787. -
  788.    function put (obj, key, value, path = []) {
  789.      if (!isObject(value)) {
  790. -      // if we are overriding an existing object,
  791. -      // record deletion
  792.        if (isObject(obj[key])) {
  793. -        // recursively delete object props
  794.          del(obj, key)
  795.        }
  796.  
  797. -      // record parent object update
  798.        let parent = baseObject(obj)
  799.        parent[key] = value
  800.        recordMutation('put', path, parent)
  801.        return
  802.      }
  803.  
  804. -    // if we are overriding an existing non-object,
  805. -    // record update of parent base object
  806.      if (key in obj && !isObject(obj[key])) {
  807.        let base = baseObject(obj)
  808.        delete base[key]
  809.        recordMutation('put', path, base)
  810.      }
  811.  
  812. +    if (Array.isArray(obj)) {
  813. +      let parent = baseObject(obj)
  814. +      recordMutation('put', path, parent)
  815. +    }
  816. +
  817.      let base = baseObject(value)
  818.      recordMutation('put', path.concat(key), base)
  819.  
  820.      for (let childKey in value) {
  821.        let child = value[childKey]
  822.  
  823. -      // if any of our non-object children override an
  824. -      // existing object, then record deletion
  825.        if (!isObject(child)) {
  826.          if (!isObject(obj[key])) continue
  827.          if (!isObject(obj[key][childKey])) continue
  828. @@ -62,7 +54,6 @@ function wrap (obj, onMutate, path = []) {
  829.          continue
  830.        }
  831.  
  832. -      // recursively record puts for objects
  833.        put(value, childKey, child, path.concat(key))
  834.      }
  835.    }
  836. @@ -71,14 +62,12 @@ function wrap (obj, onMutate, path = []) {
  837.      let value = obj[key]
  838.  
  839.      if (!isObject(obj[key])) {
  840. -      // record parent object update
  841.        let parent = baseObject(obj)
  842.        delete parent[key]
  843.        recordMutation('put', path, parent)
  844.        return
  845.      }
  846.  
  847. -    // recursively record deletions for objects
  848.      for (let childKey in value) {
  849.        let child = value[childKey]
  850.        if (!isObject(child)) continue
  851. @@ -89,24 +78,25 @@ function wrap (obj, onMutate, path = []) {
  852.    }
  853.  
  854.    return new Proxy(obj, {
  855. -    // recursively wrap child objects when accessed
  856.      get (obj, key) {
  857.        let value = obj[key]
  858. -      if (!isObject(value)) return value
  859. +      if (typeof value === 'function') {
  860. +        return value.bind(obj)
  861. +      }
  862. +      if (!isObject(value)) {
  863. +        return value
  864. +      }
  865.  
  866. -      // if value is object, recursively wrap
  867.        let childPath = path.concat(key)
  868.        return wrap(value, onMutate, childPath)
  869.      },
  870.  
  871. -    // record mutations
  872.      set (obj, key, value) {
  873.        put(obj, key, value)
  874.        obj[key] = value
  875.        return true
  876.      },
  877.  
  878. -    // record deletions as mutations too
  879.      deleteProperty (obj, key) {
  880.        if (!(key in obj)) return true
  881.        del(obj, key)
  882. @@ -114,7 +104,6 @@ function wrap (obj, onMutate, path = []) {
  883.        return true
  884.      },
  885.  
  886. -    // ovverride ownKeys to exclude symbol properties
  887.      ownKeys () {
  888.        return Object.getOwnPropertyNames(obj)
  889.      }
  890. diff --git b/test/common.js a/test/common.js
  891. index e454af1..b26f758 100755
  892. --- b/test/common.js
  893. +++ a/test/common.js
  894. @@ -1,11 +1,10 @@
  895. -function mockDb (db) {
  896. +function simDb (db) {
  897.    let store = db ? db.store : {}
  898.  
  899.    let gets = []
  900.    let puts = []
  901.    let dels = []
  902.  
  903. -  // support callbacks for level-transactions
  904.    async function get (key, opts, cb) {
  905.      gets.push({ key })
  906.      let value = store[key]
  907. @@ -27,18 +26,17 @@ function mockDb (db) {
  908.      delete store[key]
  909.    }
  910.  
  911. -  let mockDb = {
  912. +  let simDb = {
  913.      gets, puts, dels,
  914.      get, put, del,
  915.      store,
  916.      toString: () => 'LevelUP'
  917.    }
  918.  
  919. -  // support callbacks for level-transactions
  920. -  mockDb.batch = async function (batch, cb) {
  921. +  simDb.batch = async function (batch, cb) {
  922.      try {
  923.        for (let { type, key, value } of batch) {
  924. -        await mockDb[type](key, value)
  925. +        await simDb[type](key, value)
  926.        }
  927.      } catch (err) {
  928.        if (cb) return cb(err)
  929. @@ -47,9 +45,9 @@ function mockDb (db) {
  930.      if (cb) cb()
  931.    }
  932.  
  933. -  return mockDb
  934. +  return simDb
  935.  }
  936.  
  937.  module.exports = {
  938. -  mockDb
  939. +  simDb
  940.  }
  941. diff --git b/test/constellation.js a/test/constellation.js
  942. index 6f6fa4c..94f7566 100755
  943. --- b/test/constellation.js
  944. +++ a/test/constellation.js
  945. @@ -1,37 +1,37 @@
  946.  let test = require('ava')
  947. -let { mockDb } = require('./common.js')
  948. +let { simDb } = require('./common.js')
  949.  let { symbols } = require('../src/common.js')
  950. -let merk = require('../src/merk.js')
  951. +let constellation = require('../src/constellation.js')
  952.  
  953. -test('create merk without db', async (t) => {
  954. +test('create constellation without db', async (t) => {
  955.    try {
  956. -    await merk()
  957. +    await constellation()
  958.      t.fail()
  959.    } catch (err) {
  960.      t.is(err.message, 'Must provide a LevelUP instance')
  961.    }
  962.  
  963.    try {
  964. -    await merk({})
  965. +    await constellation({})
  966.      t.fail()
  967.    } catch (err) {
  968.      t.is(err.message, 'Must provide a LevelUP instance')
  969.    }
  970.  })
  971.  
  972. -test('create merk', async (t) => {
  973. -  let db = mockDb()
  974. -  let obj = await merk(db)
  975. +test('create constellation', async (t) => {
  976. +  let db = simDb()
  977. +  let obj = await constellation(db)
  978.  
  979.    t.deepEqual(obj, {})
  980.  
  981. -  let mutations = merk.mutations(obj)
  982. +  let mutations = constellation.mutations(obj)
  983.    t.deepEqual(mutations.before, {})
  984.    t.deepEqual(mutations.after, {})
  985.  })
  986.  
  987. -test('create merk with existing data', async (t) => {
  988. -  let db = mockDb({
  989. +test('create constellation with existing data', async (t) => {
  990. +  let db = simDb({
  991.      store: {
  992.        ':root': '.foo',
  993.        'n.foo': 'G+PH6PHsNTbVHY8Kt0AJypGvIU+9uZNSZeEldRF/R+AxQJmP7oqoQAEBB3sieCI6NX0BLgYuZm9vLnkA',
  994. @@ -40,20 +40,20 @@ test('create merk with existing data', async (t) => {
  995.      }
  996.    })
  997.  
  998. -  let obj = await merk(db)
  999. +  let obj = await constellation(db)
  1000.  
  1001.    t.deepEqual(obj, {
  1002.      foo: { x: 5, y: { z: 123 } },
  1003.      bar: 'baz'
  1004.    })
  1005.  
  1006. -  let mutations = merk.mutations(obj)
  1007. +  let mutations = constellation.mutations(obj)
  1008.    t.deepEqual(mutations.before, {})
  1009.    t.deepEqual(mutations.after, {})
  1010.  })
  1011.  
  1012. -test('create merk with existing data, with no non-objects on root', async (t) => {
  1013. -  let db = mockDb({
  1014. +test('create constellation with existing data, with no non-objects on root', async (t) => {
  1015. +  let db = simDb({
  1016.      store: {
  1017.        ':root': '.foo',
  1018.        'n.foo': 'nVLY483AXQKEMrv1w66IcV3v/IG9uZNSZeEldRF/R+AxQJmP7oqoQAABB3sieCI6NX0ABi5mb28ueQA=',
  1019. @@ -61,20 +61,20 @@ test('create merk with existing data, with no non-objects on root', async (t) =>
  1020.      }
  1021.    })
  1022.  
  1023. -  let obj = await merk(db)
  1024. +  let obj = await constellation(db)
  1025.  
  1026.    t.deepEqual(obj, {
  1027.      foo: { x: 5, y: { z: 123 } }
  1028.    })
  1029.  
  1030. -  let mutations = merk.mutations(obj)
  1031. +  let mutations = constellation.mutations(obj)
  1032.    t.deepEqual(mutations.before, {})
  1033.    t.deepEqual(mutations.after, {})
  1034.  })
  1035.  
  1036.  test('rollback', async (t) => {
  1037. -  let db = mockDb()
  1038. -  let obj = await merk(db)
  1039. +  let db = simDb()
  1040. +  let obj = await constellation(db)
  1041.  
  1042.    t.deepEqual(obj, {})
  1043.  
  1044. @@ -86,50 +86,125 @@ test('rollback', async (t) => {
  1045.      bar: 'baz'
  1046.    })
  1047.  
  1048. -  merk.rollback(obj)
  1049. +  constellation.rollback(obj)
  1050.  
  1051.    t.deepEqual(obj, {})
  1052.  })
  1053.  
  1054.  test('commit', async (t) => {
  1055. -  let db = mockDb()
  1056. -  let obj = await merk(db)
  1057. +  let db = simDb()
  1058. +  let obj = await constellation(db)
  1059.  
  1060.    obj.foo = { x: 5, y: { z: 123 } }
  1061.    obj.bar = 'baz'
  1062.  
  1063. -  await merk.commit(obj)
  1064. +  await constellation.commit(obj)
  1065.  
  1066.    t.deepEqual(obj, {
  1067.      foo: { x: 5, y: { z: 123 } },
  1068.      bar: 'baz'
  1069.    })
  1070. -  t.is(merk.hash(obj).toString('hex'), '1be3c7e8f1ec3536d51d8f0ab74009ca91af214f')
  1071. +  t.is(constellation.hash(obj).toString('hex'), '1be3c7e8f1ec3536d51d8f0ab74009ca91af214f')
  1072.  
  1073. -  let mutations = merk.mutations(obj)
  1074. +  let mutations = constellation.mutations(obj)
  1075.    t.deepEqual(mutations.before, {})
  1076.    t.deepEqual(mutations.after, {})
  1077.  })
  1078.  
  1079. -test('call merk methods on non-merk object', async (t) => {
  1080. +test('call constellation methods on non-constellation object', async (t) => {
  1081.    try {
  1082. -    await merk.commit({})
  1083. +    await constellation.commit({})
  1084.      t.fail()
  1085.    } catch (err) {
  1086. -    t.is(err.message, 'Must specify a root merk object')
  1087. +    t.is(err.message, 'Must specify a root constellation object')
  1088.    }
  1089.  
  1090.    try {
  1091. -    merk.mutations({})
  1092. +    constellation.mutations({})
  1093.      t.fail()
  1094.    } catch (err) {
  1095. -    t.is(err.message, 'Must specify a root merk object')
  1096. +    t.is(err.message, 'Must specify a root constellation object')
  1097.    }
  1098.  
  1099.    try {
  1100. -    merk.rollback({})
  1101. +    constellation.rollback({})
  1102.      t.fail()
  1103.    } catch (err) {
  1104. -    t.is(err.message, 'Must specify a root merk object')
  1105. +    t.is(err.message, 'Must specify a root constellation object')
  1106.    }
  1107.  })
  1108. +
  1109. +test('rollback on array length increase', async (t) => {
  1110. +  let db = simDb()
  1111. +  let obj = await constellation(db)
  1112. +
  1113. +  obj.array = [ 1, 2, 3 ]
  1114. +
  1115. +  await constellation.commit(obj)
  1116. +
  1117. +  obj.array.push(4)
  1118. +
  1119. +  constellation.rollback(obj)
  1120. +
  1121. +  t.deepEqual(obj, { array: [ 1, 2, 3 ] })
  1122. +})
  1123. +
  1124. +test('rollback on array length increase with objects', async (t) => {
  1125. +  let db = simDb()
  1126. +  let obj = await constellation(db)
  1127. +
  1128. +  obj.array = [ {}, {}, {} ]
  1129. +
  1130. +  await constellation.commit(obj)
  1131. +
  1132. +  obj.array.push({})
  1133. +
  1134. +  constellation.rollback(obj)
  1135. +
  1136. +  t.deepEqual(obj, { array: [ {}, {}, {} ] })
  1137. +})
  1138. +
  1139. +test('rollback on array length decrease', async (t) => {
  1140. +  let db = simDb()
  1141. +  let obj = await constellation(db)
  1142. +
  1143. +  obj.array = [ 1, 2, 3 ]
  1144. +
  1145. +  await constellation.commit(obj)
  1146. +
  1147. +  obj.array.pop()
  1148. +
  1149. +  constellation.rollback(obj)
  1150. +
  1151. +  t.deepEqual(obj, { array: [ 1, 2, 3 ] })
  1152. +})
  1153. +
  1154. +test('rollback on array length decrease with objects', async (t) => {
  1155. +  let db = simDb()
  1156. +  let obj = await constellation(db)
  1157. +
  1158. +  obj.array = [ {}, {}, {} ]
  1159. +
  1160. +  await constellation.commit(obj)
  1161. +
  1162. +  obj.array.pop()
  1163. +
  1164. +  constellation.rollback(obj)
  1165. +
  1166. +  t.deepEqual(obj, { array: [ {}, {}, {} ] })
  1167. +})
  1168. +
  1169. +test('rollback on array length increase with mixed types', async (t) => {
  1170. +  let db = simDb()
  1171. +  let obj = await constellation(db)
  1172. +
  1173. +  obj.array = [ {}, {}, {}, 4, 5, 6 ]
  1174. +
  1175. +  await constellation.commit(obj)
  1176. +
  1177. +  obj.array.push({})
  1178. +
  1179. +  constellation.rollback(obj)
  1180. +
  1181. +  t.deepEqual(obj, { array: [ {}, {}, {}, 4, 5, 6 ] })
  1182. +})
  1183. diff --git b/test/mutationStore.js a/test/mutationStore.js
  1184. index b74ef53..571dab3 100755
  1185. --- b/test/mutationStore.js
  1186. +++ a/test/mutationStore.js
  1187. @@ -1,5 +1,5 @@
  1188.  let test = require('ava')
  1189. -let { mockDb } = require('./common.js')
  1190. +let { simDb } = require('./common.js')
  1191.  let { symbols } = require('../src/common.js')
  1192.  let MutationStore = require('../src/mutationStore.js')
  1193.  
  1194. @@ -159,7 +159,7 @@ test('delete multi-level non-preexisting key', (t) => {
  1195.  })
  1196.  
  1197.  test('commit', async (t) => {
  1198. -  let db = mockDb()
  1199. +  let db = simDb()
  1200.    let ms = MutationStore()
  1201.  
  1202.    ms.mutate({
  1203. @@ -191,7 +191,7 @@ test('commit', async (t) => {
  1204.  })
  1205.  
  1206.  test('mutate after commit', async (t) => {
  1207. -  let db = mockDb()
  1208. +  let db = simDb()
  1209.    let ms = MutationStore()
  1210.  
  1211.    ms.mutate({
  1212. @@ -246,7 +246,7 @@ test('mutate after commit', async (t) => {
  1213.  })
  1214.  
  1215.  test('delete after commit', async (t) => {
  1216. -  let db = mockDb()
  1217. +  let db = simDb()
  1218.    let ms = MutationStore()
  1219.  
  1220.    ms.mutate({
  1221. @@ -292,7 +292,7 @@ test('delete after commit', async (t) => {
  1222.  })
  1223.  
  1224.  test('commit deletion', async (t) => {
  1225. -  let db = mockDb()
  1226. +  let db = simDb()
  1227.    let ms = MutationStore()
  1228.  
  1229.    ms.mutate({
  1230. @@ -344,7 +344,7 @@ test('commit deletion', async (t) => {
  1231.  })
  1232.  
  1233.  test('commit without root mutation', async (t) => {
  1234. -  let db = mockDb()
  1235. +  let db = simDb()
  1236.    let ms = MutationStore()
  1237.  
  1238.    ms.mutate({
  1239. @@ -375,7 +375,7 @@ test('commit without root mutation', async (t) => {
  1240.  })
  1241.  
  1242.  test('rollback from null state', async (t) => {
  1243. -  let db = mockDb()
  1244. +  let db = simDb()
  1245.    let ms = MutationStore()
  1246.  
  1247.    let obj = {
  1248. @@ -413,7 +413,7 @@ test('rollback from null state', async (t) => {
  1249.  })
  1250.  
  1251.  test('rollback from committed state', async (t) => {
  1252. -  let db = mockDb()
  1253. +  let db = simDb()
  1254.    let ms = MutationStore()
  1255.  
  1256.    ms.mutate({
  1257. @@ -479,7 +479,7 @@ test('rollback from committed state', async (t) => {
  1258.  })
  1259.  
  1260.  test('rollback without root mutation', async (t) => {
  1261. -  let db = mockDb()
  1262. +  let db = simDb()
  1263.    let ms = MutationStore()
  1264.  
  1265.    ms.mutate({
  1266. diff --git b/test/node.js a/test/node.js
  1267. index adaa5a2..a039341 100755
  1268. --- b/test/node.js
  1269. +++ a/test/node.js
  1270. @@ -1,9 +1,9 @@
  1271.  let test = require('ava')
  1272. -let { mockDb } = require('./common.js')
  1273. +let { simDb } = require('./common.js')
  1274.  let _Node = require('../src/node.js')
  1275.  
  1276.  test('create node without key', async (t) => {
  1277. -  let db = mockDb()
  1278. +  let db = simDb()
  1279.    let Node = _Node(db)
  1280.    try {
  1281.      let node = new Node({})
  1282. @@ -14,7 +14,7 @@ test('create node without key', async (t) => {
  1283.  })
  1284.  
  1285.  test('create node without value', async (t) => {
  1286. -  let db = mockDb()
  1287. +  let db = simDb()
  1288.    let Node = _Node(db)
  1289.    try {
  1290.      let node = new Node({ key: 'foo' })
  1291. @@ -25,7 +25,7 @@ test('create node without value', async (t) => {
  1292.  })
  1293.  
  1294.  test('create node', async (t) => {
  1295. -  let db = mockDb()
  1296. +  let db = simDb()
  1297.    let Node = _Node(db)
  1298.    let node = new Node({ key: 'foo', value: 'bar' })
  1299.    t.is(node.key, 'foo')
  1300. @@ -38,27 +38,27 @@ test('create node', async (t) => {
  1301.  })
  1302.  
  1303.  test('access null links', async (t) => {
  1304. -  let db = mockDb()
  1305. +  let db = simDb()
  1306.    let Node = _Node(db)
  1307.  
  1308. -  let tx = mockDb()
  1309. +  let ntx = simDb()
  1310.    let node = new Node({ key: 'foo', value: 'bar' })
  1311.  
  1312.    async function access (getLink) {
  1313. -    let tx = mockDb()
  1314. -    t.is(await getLink.call(node, tx), null)
  1315. -    t.is(tx.gets.length, 0)
  1316. +    let ntx = simDb()
  1317. +    t.is(await getLink.call(node, ntx), null)
  1318. +    t.is(ntx.gets.length, 0)
  1319.    }
  1320.  
  1321.    await access(node.left)
  1322.    await access(node.right)
  1323.    await access(node.parent)
  1324. -  await access((tx) => node.child(tx, true))
  1325. -  await access((tx) => node.child(tx, false))
  1326. +  await access((ntx) => node.child(ntx, true))
  1327. +  await access((ntx) => node.child(ntx, false))
  1328.  })
  1329.  
  1330.  test('save node', async (t) => {
  1331. -  let db = mockDb()
  1332. +  let db = simDb()
  1333.    let Node = _Node(db)
  1334.  
  1335.    let node = new Node({ key: 'foo', value: 'bar' })
  1336. @@ -75,15 +75,15 @@ test('save node', async (t) => {
  1337.  })
  1338.  
  1339.  test('save child node', async (t) => {
  1340. -  let db = mockDb()
  1341. +  let db = simDb()
  1342.    let Node = _Node(db)
  1343.  
  1344.    let node = new Node({ key: 'foo', value: 'bar' })
  1345.    await node.save(db)
  1346.  
  1347. -  let tx = mockDb()
  1348. +  let ntx = simDb()
  1349.    let node2 = new Node({ key: 'fo', value: 'bar' })
  1350. -  node = await node.put(node2, tx)
  1351. +  node = await node.put(node2, ntx)
  1352.    t.is(node2.key, 'fo')
  1353.  
  1354.    t.is(db.gets.length, 0)
  1355. @@ -95,9 +95,9 @@ test('save child node', async (t) => {
  1356.      }
  1357.    ])
  1358.  
  1359. -  t.is(tx.gets.length, 0)
  1360. -  t.is(tx.dels.length, 0)
  1361. -  t.deepEqual(tx.puts, [
  1362. +  t.is(ntx.gets.length, 0)
  1363. +  t.is(ntx.dels.length, 0)
  1364. +  t.deepEqual(ntx.puts, [
  1365.      {
  1366.        key: 'nfoo',
  1367.        value: 'dr+bSNfQWI8G7CldNgJ45LFadOytBZ8KwnM2IWh629jJxBTapVD+iAEAA2JhcgJmbwAA'
  1368. @@ -108,78 +108,78 @@ test('save child node', async (t) => {
  1369.      }
  1370.    ])
  1371.  
  1372. -  let tx2 = mockDb()
  1373. -  t.is(await node.parent(tx2), null)
  1374. +  let ntx2 = simDb()
  1375. +  t.is(await node.parent(ntx2), null)
  1376.  
  1377.    // get parent
  1378. -  tx = mockDb(tx)
  1379. -  let parent = await node2.parent(tx)
  1380. +  ntx = simDb(ntx)
  1381. +  let parent = await node2.parent(ntx)
  1382.    t.is(parent.key, 'foo')
  1383.    t.is(parent.value, 'bar')
  1384. -  t.deepEqual(tx.gets, [ { key: 'nfoo' } ])
  1385. +  t.deepEqual(ntx.gets, [ { key: 'nfoo' } ])
  1386.  
  1387.    // get child
  1388. -  tx = mockDb(tx)
  1389. -  let child = await node.left(tx)
  1390. +  ntx = simDb(ntx)
  1391. +  let child = await node.left(ntx)
  1392.    t.is(child.key, 'fo')
  1393.    t.is(child.value, 'bar')
  1394. -  t.deepEqual(tx.gets, [ { key: 'nfo' } ])
  1395. +  t.deepEqual(ntx.gets, [ { key: 'nfo' } ])
  1396.  })
  1397.  
  1398.  test('delete child node', async (t) => {
  1399. -  let db = mockDb()
  1400. +  let db = simDb()
  1401.    let Node = _Node(db)
  1402.  
  1403.    let node = new Node({ key: 'foo', value: 'bar' })
  1404.    await node.save(db)
  1405.  
  1406. -  let tx = mockDb(db)
  1407. +  let ntx = simDb(db)
  1408.    let node2 = new Node({ key: 'fo', value: 'bar' })
  1409. -  node = await node.put(node2, tx)
  1410. +  node = await node.put(node2, ntx)
  1411.  
  1412. -  tx = mockDb(tx)
  1413. -  node = await node.delete('fo', tx)
  1414. +  ntx = simDb(ntx)
  1415. +  node = await node.delete('fo', ntx)
  1416.  
  1417. -  t.deepEqual(tx.gets, [ { key: 'nfo' } ])
  1418. -  t.deepEqual(tx.dels, [ { key: 'nfo' } ])
  1419. -  t.deepEqual(tx.puts, [
  1420. +  t.deepEqual(ntx.gets, [ { key: 'nfo' } ])
  1421. +  t.deepEqual(ntx.dels, [ { key: 'nfo' } ])
  1422. +  t.deepEqual(ntx.puts, [
  1423.      {
  1424.        key: 'nfoo',
  1425.        value: 'gdGeF1+rlOY3B4TKbNE1jNesAMmtBZ8KwnM2IWh629jJxBTapVD+iAAAA2JhcgAAAA=='
  1426.      }
  1427.    ])
  1428.  
  1429. -  tx = mockDb(tx)
  1430. -  t.is(await node.left(tx), null)
  1431. +  ntx = simDb(ntx)
  1432. +  t.is(await node.left(ntx), null)
  1433.  })
  1434.  
  1435.  test('delete parent node', async (t) => {
  1436. -  let db = mockDb()
  1437. +  let db = simDb()
  1438.    let Node = _Node(db)
  1439.  
  1440.    let node = new Node({ key: 'foo', value: 'bar' })
  1441.    await node.save(db)
  1442.  
  1443. -  let tx = mockDb(db)
  1444. +  let ntx = simDb(db)
  1445.    let node2 = new Node({ key: 'fo', value: 'bar' })
  1446. -  node = await node.put(node2, tx)
  1447. +  node = await node.put(node2, ntx)
  1448.  
  1449. -  tx = mockDb(tx)
  1450. -  node = await node.delete('foo', tx)
  1451. +  ntx = simDb(ntx)
  1452. +  node = await node.delete('foo', ntx)
  1453.  
  1454. -  t.deepEqual(tx.gets, [ { key: 'nfo' } ])
  1455. -  t.deepEqual(tx.dels, [ { key: 'nfoo' } ])
  1456. -  t.is(tx.puts.length, 0)
  1457. +  t.deepEqual(ntx.gets, [ { key: 'nfo' } ])
  1458. +  t.deepEqual(ntx.dels, [ { key: 'nfoo' } ])
  1459. +  t.is(ntx.puts.length, 0)
  1460.    t.is(node.key, 'fo')
  1461.  
  1462. -  tx = mockDb(tx)
  1463. -  t.is(await node.parent(tx), null)
  1464. +  ntx = simDb(ntx)
  1465. +  t.is(await node.parent(ntx), null)
  1466.  })
  1467.  
  1468.  test('build 1000-node tree in fixed order', async (t) => {
  1469.    t.plan(9000)
  1470.  
  1471. -  let db = mockDb()
  1472. +  let db = simDb()
  1473.    let Node = _Node(db)
  1474.  
  1475.    let root = new Node({ key: '0', value: 'value' })
  1476. @@ -236,7 +236,7 @@ test('build 1000-node tree in fixed order', async (t) => {
  1477.  })
  1478.  
  1479.  test('delete non-existent key', async (t) => {
  1480. -  let db = mockDb()
  1481. +  let db = simDb()
  1482.    let Node = _Node(db)
  1483.  
  1484.    let root = new Node({ key: '0', value: 'value' })
  1485. @@ -253,7 +253,7 @@ test('delete non-existent key', async (t) => {
  1486.  test('delete (random keys)', async (t) => {
  1487.    t.plan(21)
  1488.  
  1489. -  let db = mockDb()
  1490. +  let db = simDb()
  1491.    let Node = _Node(db)
  1492.  
  1493.    // build tree
  1494. @@ -277,7 +277,7 @@ test('delete (random keys)', async (t) => {
  1495.  })
  1496.  
  1497.  test('get branch', async (t) => {
  1498. -  let db = mockDb()
  1499. +  let db = simDb()
  1500.    let Node = _Node(db)
  1501.  
  1502.    // build tree
  1503. @@ -316,7 +316,7 @@ test('get branch', async (t) => {
  1504.  })
  1505.  
  1506.  test('get branch at edge', async (t) => {
  1507. -  let db = mockDb()
  1508. +  let db = simDb()
  1509.    let Node = _Node(db)
  1510.  
  1511.    // build tree
  1512. diff --git b/test/verify.js a/test/verify.js
  1513. index 8c8fee5..79f73e6 100755
  1514. --- b/test/verify.js
  1515. +++ a/test/verify.js
  1516. @@ -1,89 +1,89 @@
  1517.  let test = require('ava')
  1518. -let { mockDb } = require('./common.js')
  1519. -let merk = require('../src/merk.js')
  1520. +let { simDb } = require('./common.js')
  1521. +let constellation = require('../src/constellation.js')
  1522.  
  1523.  test('verify single-node root proof', async (t) => {
  1524. -  let db = mockDb()
  1525. -  let state = await merk(db)
  1526. +  let db = simDb()
  1527. +  let state = await constellation(db)
  1528.    state.foo = 'bar'
  1529. -  await merk.commit(state)
  1530. +  await constellation.commit(state)
  1531.  
  1532. -  let rootHash = merk.hash(state)
  1533. -  let proof = await merk.proof(state)
  1534. -  let value = merk.verify(rootHash, proof)
  1535. +  let rootHash = constellation.hash(state)
  1536. +  let proof = await constellation.proof(state)
  1537. +  let value = constellation.verify(rootHash, proof)
  1538.  
  1539.    t.deepEqual(value, { foo: 'bar' })
  1540.  })
  1541.  
  1542.  test('verify single-node non-object child proof', async (t) => {
  1543. -  let db = mockDb()
  1544. -  let state = await merk(db)
  1545. +  let db = simDb()
  1546. +  let state = await constellation(db)
  1547.    state.foo = 'bar'
  1548. -  await merk.commit(state)
  1549. +  await constellation.commit(state)
  1550.  
  1551. -  let rootHash = merk.hash(state)
  1552. -  let proof = await merk.proof(state, 'foo')
  1553. -  let value = merk.verify(rootHash, proof, 'foo')
  1554. +  let rootHash = constellation.hash(state)
  1555. +  let proof = await constellation.proof(state, 'foo')
  1556. +  let value = constellation.verify(rootHash, proof, 'foo')
  1557.  
  1558.    t.is(value, 'bar')
  1559.  })
  1560.  
  1561.  test('verify multi-node root proof', async (t) => {
  1562. -  let db = mockDb()
  1563. -  let state = await merk(db)
  1564. +  let db = simDb()
  1565. +  let state = await constellation(db)
  1566.    state.foo = 'bar'
  1567.    state.baz = { x: 123 }
  1568. -  await merk.commit(state)
  1569. +  await constellation.commit(state)
  1570.  
  1571. -  let rootHash = merk.hash(state)
  1572. -  let proof = await merk.proof(state)
  1573. -  let value = merk.verify(rootHash, proof)
  1574. +  let rootHash = constellation.hash(state)
  1575. +  let proof = await constellation.proof(state)
  1576. +  let value = constellation.verify(rootHash, proof)
  1577.  
  1578.    t.deepEqual(value, { foo: 'bar', baz: { x: 123 } })
  1579.  })
  1580.  
  1581.  test('verify multi-node child proof', async (t) => {
  1582. -  let db = mockDb()
  1583. -  let state = await merk(db)
  1584. +  let db = simDb()
  1585. +  let state = await constellation(db)
  1586.    state.foo = 'bar'
  1587.    state.baz = { x: 123 }
  1588. -  await merk.commit(state)
  1589. +  await constellation.commit(state)
  1590.  
  1591. -  let rootHash = merk.hash(state)
  1592. -  let proof = await merk.proof(state, 'baz')
  1593. -  let value = merk.verify(rootHash, proof, 'baz')
  1594. +  let rootHash = constellation.hash(state)
  1595. +  let proof = await constellation.proof(state, 'baz')
  1596. +  let value = constellation.verify(rootHash, proof, 'baz')
  1597.  
  1598.    t.deepEqual(value, { x: 123 })
  1599.  })
  1600.  
  1601.  test('verify multi-node non-object child proof', async (t) => {
  1602. -  let db = mockDb()
  1603. -  let state = await merk(db)
  1604. +  let db = simDb()
  1605. +  let state = await constellation(db)
  1606.    state.foo = 'bar'
  1607.    state.baz = { x: 123 }
  1608. -  await merk.commit(state)
  1609. +  await constellation.commit(state)
  1610.  
  1611. -  let rootHash = merk.hash(state)
  1612. -  let proof = await merk.proof(state, 'baz.x')
  1613. -  let value = merk.verify(rootHash, proof, 'baz.x')
  1614. +  let rootHash = constellation.hash(state)
  1615. +  let proof = await constellation.proof(state, 'baz.x')
  1616. +  let value = constellation.verify(rootHash, proof, 'baz.x')
  1617.  
  1618.    t.is(value, 123)
  1619.  })
  1620.  
  1621.  test('verify with incorrect root hash', async (t) => {
  1622. -  let db = mockDb()
  1623. -  let state = await merk(db)
  1624. +  let db = simDb()
  1625. +  let state = await constellation(db)
  1626.  
  1627.    state.foo = 'bar'
  1628. -  await merk.commit(state)
  1629. -  let rootHash = merk.hash(state)
  1630. +  await constellation.commit(state)
  1631. +  let rootHash = constellation.hash(state)
  1632.  
  1633.    state.baz = { x: 123 }
  1634. -  await merk.commit(state)
  1635. +  await constellation.commit(state)
  1636.  
  1637. -  let proof = await merk.proof(state, 'baz')
  1638. +  let proof = await constellation.proof(state, 'baz')
  1639.    try {
  1640. -    merk.verify(rootHash, proof, 'baz')
  1641. +    constellation.verify(rootHash, proof, 'baz')
  1642.      t.fail()
  1643.    } catch (err) {
  1644.      t.is(err.message, 'Proof does not match expected root hash')
  1645. @@ -91,15 +91,15 @@ test('verify with incorrect root hash', async (t) => {
  1646.  })
  1647.  
  1648.  test('verify with array range', async (t) => {
  1649. -  let db = mockDb()
  1650. -  let state = await merk(db)
  1651. +  let db = simDb()
  1652. +  let state = await constellation(db)
  1653.  
  1654.    // state.abc = {n: 123}
  1655.    // state.array = [{n: 0}, {n: 1}, {n: 2}, {n: 3}]
  1656.    // state.xyz = {n: 456}
  1657. -  // await merk.commit(state)
  1658. -  // let rootHash = merk.hash(state)
  1659. -  // let proof = await merk.proof(state, 'array')
  1660. +  // await constellation.commit(state)
  1661. +  // let rootHash = constellation.hash(state)
  1662. +  // let proof = await constellation.proof(state, 'array')
  1663.  
  1664.    let rootHash = 'ac2323c6ebaafb3174c6dfac855ed0652f4651af'
  1665.    let proof = {
  1666. @@ -119,28 +119,28 @@ test('verify with array range', async (t) => {
  1667.      value: '{"n":1}'
  1668.    }
  1669.  
  1670. -  let value = merk.verify(rootHash, proof, 'array')
  1671. +  let value = constellation.verify(rootHash, proof, 'array')
  1672.    t.deepEqual(value, [{n: 0}, {n: 1}, {n: 2}, {n: 3}])
  1673.  })
  1674.  
  1675.  test('verify with array child', async (t) => {
  1676. -  let db = mockDb()
  1677. -  let state = await merk(db)
  1678. +  let db = simDb()
  1679. +  let state = await constellation(db)
  1680.  
  1681.    state.abc = {n: 123}
  1682.    state.array = [{n: 0}, {n: 1}, {n: 2}, {n: 3}]
  1683.    state.xyz = {n: 456}
  1684. -  await merk.commit(state)
  1685. -  let rootHash = merk.hash(state)
  1686. -  let proof = await merk.proof(state, 'array.1')
  1687. +  await constellation.commit(state)
  1688. +  let rootHash = constellation.hash(state)
  1689. +  let proof = await constellation.proof(state, 'array.1')
  1690.  
  1691. -  let value = merk.verify(rootHash, proof, 'array.1')
  1692. +  let value = constellation.verify(rootHash, proof, 'array.1')
  1693.    t.deepEqual(value, {n: 1})
  1694.  })
  1695.  
  1696.  test('verify with unproven range', async (t) => {
  1697. -  let db = mockDb()
  1698. -  let state = await merk(db)
  1699. +  let db = simDb()
  1700. +  let state = await constellation(db)
  1701.  
  1702.    let rootHash = 'ac2323c6ebaafb3174c6dfac855ed0652f4651af'
  1703.    let proof = {
  1704. @@ -161,7 +161,7 @@ test('verify with unproven range', async (t) => {
  1705.    }
  1706.  
  1707.    try {
  1708. -    merk.verify(rootHash, proof, 'array')
  1709. +    constellation.verify(rootHash, proof, 'array')
  1710.      t.fail()
  1711.    } catch (err) {
  1712.      t.is(err.message, 'First key greater than beginning of range')
  1713. @@ -169,8 +169,8 @@ test('verify with unproven range', async (t) => {
  1714.  })
  1715.  
  1716.  test('verify with unproven range', async (t) => {
  1717. -  let db = mockDb()
  1718. -  let state = await merk(db)
  1719. +  let db = simDb()
  1720. +  let state = await constellation(db)
  1721.  
  1722.    let rootHash = 'ac2323c6ebaafb3174c6dfac855ed0652f4651af'
  1723.    let proof = {
  1724. @@ -191,9 +191,36 @@ test('verify with unproven range', async (t) => {
  1725.    }
  1726.  
  1727.    try {
  1728. -    merk.verify(rootHash, proof, 'array')
  1729. +    constellation.verify(rootHash, proof, 'array')
  1730.      t.fail()
  1731.    } catch (err) {
  1732.      t.is(err.message, 'Last key less than end of range')
  1733.    }
  1734.  })
  1735. +
  1736. +test('verify with range that was previously broken', async (t) => {
  1737. +  let db = simDb()
  1738. +  let state = await constellation(db)
  1739. +
  1740. +  let rootHash = '8cbbf63175e9390054c2155419ccea4ce38508a0'
  1741. +  let proof = require('./fixtures/blockchat.json')
  1742. +
  1743. +  constellation.verify(rootHash, proof, 'messages')
  1744. +  t.pass()
  1745. +})
  1746. +
  1747. +test('verify with single-node tree with no root object', async (t) => {
  1748. +  let db = simDb()
  1749. +  let state = await constellation(db)
  1750. +
  1751. +  state.foo = { beep: 'boop' }
  1752. +
  1753. +  await constellation.commit(state)
  1754. +
  1755. +  let proof = await constellation.proof(state)
  1756. +
  1757. +  let rootHash = '4a492d386d845c19a691698b91d9afaddba0a0fb'
  1758. +  let value = constellation.verify(rootHash, proof)
  1759. +
  1760. +  t.pass()
  1761. +})
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!