Merge pull request #1945 from MetaMask/useLocalNonce

Use local nonce

5 files changed, 255 insertions, 58 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index 970ae2e06..c5290ed99 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -2,6 +2,7 @@
 
 ## Current Master
 
+- Improve nonce calculation, to prevent bug where people are unable to send transactions reliably.
 - Remove link to eth-tx-viz from identicons in tx history.
 
 ## 3.9.9 2017-8-18
diff --git a/app/scripts/controllers/transactions.js b/app/scripts/controllers/transactions.js
index 1bcee60ab..6f49c9633 100644
--- a/app/scripts/controllers/transactions.js
+++ b/app/scripts/controllers/transactions.js
@@ -33,6 +33,13 @@ module.exports = class TransactionController extends EventEmitter {
           err: undefined,
         })
       },
+      getConfirmedTransactions: (address) => {
+        return this.getFilteredTxList({
+          from: address,
+          status: 'confirmed',
+          err: undefined,
+        })
+      },
     })
     this.query = new EthQuery(this.provider)
     this.txProviderUtil = new TxProviderUtil(this.provider)
diff --git a/app/scripts/lib/nonce-tracker.js b/app/scripts/lib/nonce-tracker.js
index 8328e81ec..30c59fa46 100644
--- a/app/scripts/lib/nonce-tracker.js
+++ b/app/scripts/lib/nonce-tracker.js
@@ -1,13 +1,14 @@
-const EthQuery = require('eth-query')
+const EthQuery = require('ethjs-query')
 const assert = require('assert')
 const Mutex = require('await-semaphore').Mutex
 
 class NonceTracker {
 
-  constructor ({ provider, getPendingTransactions }) {
+  constructor ({ provider, getPendingTransactions, getConfirmedTransactions }) {
     this.provider = provider
     this.ethQuery = new EthQuery(provider)
     this.getPendingTransactions = getPendingTransactions
+    this.getConfirmedTransactions = getConfirmedTransactions
     this.lockMap = {}
   }
 
@@ -25,21 +26,14 @@ class NonceTracker {
     await this._globalMutexFree()
     // await lock free, then take lock
     const releaseLock = await this._takeMutex(address)
-    // calculate next nonce
-    // we need to make sure our base count
-    // and pending count are from the same block
-    const currentBlock = await this._getCurrentBlock()
-    const pendingTransactions = this.getPendingTransactions(address)
-    const pendingCount = pendingTransactions.length
-    assert(Number.isInteger(pendingCount), `nonce-tracker - pendingCount is not an integer - got: (${typeof pendingCount}) "${pendingCount}"`)
-    const baseCountHex = await this._getTxCount(address, currentBlock)
-    const baseCount = parseInt(baseCountHex, 16)
-    assert(Number.isInteger(baseCount), `nonce-tracker - baseCount is not an integer - got: (${typeof baseCount}) "${baseCount}"`)
-    const nextNonce = baseCount + pendingCount
+    // evaluate multiple nextNonce strategies
+    const nonceDetails = {}
+    const localNonceResult = await this._getlocalNextNonce(address)
+    nonceDetails.local = localNonceResult.details
+    const networkNonceResult = await this._getNetworkNextNonce(address)
+    nonceDetails.network = networkNonceResult.details
+    const nextNonce = Math.max(networkNonceResult.nonce, localNonceResult.nonce)
     assert(Number.isInteger(nextNonce), `nonce-tracker - nextNonce is not an integer - got: (${typeof nextNonce}) "${nextNonce}"`)
-    // collect the numbers used to calculate the nonce for debugging
-    const blockNumber = currentBlock.number
-    const nonceDetails = { blockNumber, baseCount, baseCountHex, pendingCount }
     // return nonce and release cb
     return { nextNonce, nonceDetails, releaseLock }
   }
@@ -53,15 +47,6 @@ class NonceTracker {
     })
   }
 
-  async _getTxCount (address, currentBlock) {
-    const blockNumber = currentBlock.number
-    return new Promise((resolve, reject) => {
-      this.ethQuery.getTransactionCount(address, blockNumber, (err, result) => {
-        err ? reject(err) : resolve(result)
-      })
-    })
-  }
-
   async _globalMutexFree () {
     const globalMutex = this._lookupMutex('global')
     const release = await globalMutex.acquire()
@@ -83,12 +68,70 @@ class NonceTracker {
     return mutex
   }
 
+  async _getNetworkNextNonce (address) {
+    // calculate next nonce
+    // we need to make sure our base count
+    // and pending count are from the same block
+    const currentBlock = await this._getCurrentBlock()
+    const blockNumber = currentBlock.blockNumber
+    const baseCountHex = await this.ethQuery.getTransactionCount(address, blockNumber)
+    const baseCount = parseInt(baseCountHex, 16)
+    assert(Number.isInteger(baseCount), `nonce-tracker - baseCount is not an integer - got: (${typeof baseCount}) "${baseCount}"`)
+    const nonceDetails = { blockNumber, baseCountHex, baseCount }
+    return { name: 'network', nonce: baseCount, details: nonceDetails }
+  }
+
+  async _getlocalNextNonce (address) {
+    let nextNonce
+    // check our local tx history for the highest nonce (if any)
+    const confirmedTransactions = this.getConfirmedTransactions(address)
+    const pendingTransactions = this.getPendingTransactions(address)
+    const transactions = confirmedTransactions.concat(pendingTransactions)
+    const highestConfirmedNonce = this._getHighestNonce(confirmedTransactions)
+    const highestPendingNonce = this._getHighestNonce(pendingTransactions)
+    const highestNonce = this._getHighestNonce(transactions)
+
+    const haveHighestNonce = Number.isInteger(highestNonce)
+    if (haveHighestNonce) {
+      // next nonce is the nonce after our last
+      nextNonce = highestNonce + 1
+    } else {
+      // no local tx history so next must be first (zero)
+      nextNonce = 0
+    }
+    const nonceDetails = { highestNonce, haveHighestNonce, highestConfirmedNonce, highestPendingNonce }
+    return { name: 'local', nonce: nextNonce, details: nonceDetails }
+  }
+
+  _getPendingTransactionCount (address) {
+    const pendingTransactions = this.getPendingTransactions(address)
+    return this._reduceTxListToUniqueNonces(pendingTransactions).length
+  }
+
+  _reduceTxListToUniqueNonces (txList) {
+    const reducedTxList = txList.reduce((reducedList, txMeta, index) => {
+      if (!index) return [txMeta]
+      const nonceMatches = txList.filter((txData) => {
+        return txMeta.txParams.nonce === txData.txParams.nonce
+      })
+      if (nonceMatches.length > 1) return reducedList
+      reducedList.push(txMeta)
+      return reducedList
+    }, [])
+    return reducedTxList
+  }
+
+  _getHighestNonce (txList) {
+    const nonces = txList.map((txMeta) => parseInt(txMeta.txParams.nonce, 16))
+    const highestNonce = Math.max.apply(null, nonces)
+    return highestNonce
+  }
+
   // this is a hotfix for the fact that the blockTracker will
   // change when the network changes
   _getBlockTracker () {
     return this.provider._blockTracker
   }
-
 }
 
 module.exports = NonceTracker
diff --git a/test/lib/mock-tx-gen.js b/test/lib/mock-tx-gen.js
new file mode 100644
index 000000000..7aea09c59
--- /dev/null
+++ b/test/lib/mock-tx-gen.js
@@ -0,0 +1,40 @@
+const extend = require('xtend')
+const BN = require('ethereumjs-util').BN
+const template = {
+  'status': 'submitted',
+  'txParams': {
+    'from': '0x7d3517b0d011698406d6e0aed8453f0be2697926',
+    'gas': '0x30d40',
+    'value': '0x0',
+    'nonce': '0x3',
+  },
+}
+
+class TxGenerator {
+
+  constructor () {
+    this.txs = []
+  }
+
+  generate (tx = {}, opts = {}) {
+    let { count, fromNonce } = opts
+    let nonce = fromNonce || this.txs.length
+    let txs = []
+    for (let i = 0; i < count; i++) {
+      txs.push(extend(template, {
+        txParams: {
+          nonce: hexify(nonce++),
+        }
+      }, tx))
+    }
+    this.txs = this.txs.concat(txs)
+    return txs
+  }
+
+}
+
+function hexify (number) {
+  return '0x' + (new BN(number)).toString(16)
+}
+
+module.exports = TxGenerator
diff --git a/test/unit/nonce-tracker-test.js b/test/unit/nonce-tracker-test.js
index 36025a360..11f99751c 100644
--- a/test/unit/nonce-tracker-test.js
+++ b/test/unit/nonce-tracker-test.js
@@ -1,41 +1,147 @@
 const assert = require('assert')
 const NonceTracker = require('../../app/scripts/lib/nonce-tracker')
+const MockTxGen = require('../lib/mock-tx-gen')
+let providerResultStub = {}
 
 describe('Nonce Tracker', function () {
-  let nonceTracker, provider, getPendingTransactions, pendingTxs
-
-
-  beforeEach(function () {
-    pendingTxs = [{
-      'status': 'submitted',
-      'txParams': {
-        'from': '0x7d3517b0d011698406d6e0aed8453f0be2697926',
-        'gas': '0x30d40',
-        'value': '0x0',
-        'nonce': '0x0',
-      },
-    }]
-
-
-    getPendingTransactions = () => pendingTxs
-    provider = {
-      sendAsync: (_, cb) => { cb(undefined, {result: '0x0'}) },
-      _blockTracker: {
-        getCurrentBlock: () => '0x11b568',
-      },
-    }
-    nonceTracker = new NonceTracker({
-      provider,
-      getPendingTransactions,
-    })
-  })
+  let nonceTracker, provider
+  let getPendingTransactions, pendingTxs
+  let getConfirmedTransactions, confirmedTxs
 
   describe('#getNonceLock', function () {
-    it('should work', async function () {
-      this.timeout(15000)
-      const nonceLock = await nonceTracker.getNonceLock('0x7d3517b0d011698406d6e0aed8453f0be2697926')
-      assert.equal(nonceLock.nextNonce, '1', 'nonce should be 1')
-      await nonceLock.releaseLock()
+
+    describe('with 3 confirmed and 1 pending', function () {
+      beforeEach(function () {
+        const txGen = new MockTxGen()
+        confirmedTxs = txGen.generate({ status: 'confirmed' }, { count: 3 })
+        pendingTxs = txGen.generate({ status: 'submitted' }, { count: 1 })
+        nonceTracker = generateNonceTrackerWith(pendingTxs, confirmedTxs, '0x1')
+      })
+
+      it('should work', async function () {
+        this.timeout(15000)
+        const nonceLock = await nonceTracker.getNonceLock('0x7d3517b0d011698406d6e0aed8453f0be2697926')
+        assert.equal(nonceLock.nextNonce, '4', 'nonce should be 4')
+        await nonceLock.releaseLock()
+      })
+
+      it('should use localNonce if network returns a nonce lower then a confirmed tx in state', async function () {
+        this.timeout(15000)
+        const nonceLock = await nonceTracker.getNonceLock('0x7d3517b0d011698406d6e0aed8453f0be2697926')
+        assert.equal(nonceLock.nextNonce, '4', 'nonce should be 4')
+        await nonceLock.releaseLock()
+      })
+    })
+
+    describe('with no previous txs', function () {
+      beforeEach(function () {
+        nonceTracker = generateNonceTrackerWith([], [])
+      })
+
+      it('should return 0', async function () {
+        this.timeout(15000)
+        const nonceLock = await nonceTracker.getNonceLock('0x7d3517b0d011698406d6e0aed8453f0be2697926')
+        assert.equal(nonceLock.nextNonce, '0', 'nonce should be 0')
+        await nonceLock.releaseLock()
+      })
+    })
+
+    describe('with multiple previous txs with same nonce', function () {
+      beforeEach(function () {
+        const txGen = new MockTxGen()
+        confirmedTxs = txGen.generate({ status: 'confirmed' }, { count: 1 })
+        pendingTxs = txGen.generate({
+          status: 'submitted',
+          txParams: { nonce: '0x01' },
+        }, { count: 5 })
+
+        nonceTracker = generateNonceTrackerWith(pendingTxs, confirmedTxs)
+      })
+
+      it('should return nonce after those', async function () {
+        this.timeout(15000)
+        const nonceLock = await nonceTracker.getNonceLock('0x7d3517b0d011698406d6e0aed8453f0be2697926')
+        assert.equal(nonceLock.nextNonce, '2', `nonce should be 2 got ${nonceLock.nextNonce}`)
+        await nonceLock.releaseLock()
+      })
+    })
+
+    describe('when local confirmed count is higher than network nonce', function () {
+      beforeEach(function () {
+        const txGen = new MockTxGen()
+        confirmedTxs = txGen.generate({ status: 'confirmed' }, { count: 2 })
+        nonceTracker = generateNonceTrackerWith([], confirmedTxs)
+      })
+
+      it('should return nonce after those', async function () {
+        this.timeout(15000)
+        const nonceLock = await nonceTracker.getNonceLock('0x7d3517b0d011698406d6e0aed8453f0be2697926')
+        assert.equal(nonceLock.nextNonce, '2', `nonce should be 2 got ${nonceLock.nextNonce}`)
+        await nonceLock.releaseLock()
+      })
+    })
+
+    describe('when local pending count is higher than other metrics', function () {
+      beforeEach(function () {
+        const txGen = new MockTxGen()
+        pendingTxs = txGen.generate({ status: 'submitted' }, { count: 2 })
+        nonceTracker = generateNonceTrackerWith(pendingTxs, [])
+      })
+
+      it('should return nonce after those', async function () {
+        this.timeout(15000)
+        const nonceLock = await nonceTracker.getNonceLock('0x7d3517b0d011698406d6e0aed8453f0be2697926')
+        assert.equal(nonceLock.nextNonce, '2', `nonce should be 2 got ${nonceLock.nextNonce}`)
+        await nonceLock.releaseLock()
+      })
+    })
+
+    describe('when provider nonce is higher than other metrics', function () {
+      beforeEach(function () {
+        const txGen = new MockTxGen()
+        pendingTxs = txGen.generate({ status: 'submitted' }, { count: 2 })
+        nonceTracker = generateNonceTrackerWith(pendingTxs, [], '0x05')
+      })
+
+      it('should return nonce after those', async function () {
+        this.timeout(15000)
+        const nonceLock = await nonceTracker.getNonceLock('0x7d3517b0d011698406d6e0aed8453f0be2697926')
+        assert.equal(nonceLock.nextNonce, '5', `nonce should be 5 got ${nonceLock.nextNonce}`)
+        await nonceLock.releaseLock()
+      })
+    })
+
+    describe('when there are some pending nonces below the remote one and some over.', function () {
+      beforeEach(function () {
+        const txGen = new MockTxGen()
+        pendingTxs = txGen.generate({ status: 'submitted' }, { count: 5 })
+        nonceTracker = generateNonceTrackerWith(pendingTxs, [], '0x03')
+      })
+
+      it('should return nonce after those', async function () {
+        this.timeout(15000)
+        const nonceLock = await nonceTracker.getNonceLock('0x7d3517b0d011698406d6e0aed8453f0be2697926')
+        assert.equal(nonceLock.nextNonce, '5', `nonce should be 5 got ${nonceLock.nextNonce}`)
+        await nonceLock.releaseLock()
+      })
     })
   })
 })
+
+function generateNonceTrackerWith (pending, confirmed, providerStub = '0x0') {
+  const getPendingTransactions = () => pending
+  const getConfirmedTransactions = () => confirmed
+  providerResultStub.result = providerStub
+  const provider = {
+    sendAsync: (_, cb) => { cb(undefined, providerResultStub) },
+    _blockTracker: {
+      getCurrentBlock: () => '0x11b568',
+    },
+  }
+  return new NonceTracker({
+    provider,
+    getPendingTransactions,
+    getConfirmedTransactions,
+  })
+}
+