diff --git a/src/script/script.cpp b/src/script/script.cpp
--- a/src/script/script.cpp
+++ b/src/script/script.cpp
@@ -268,28 +268,50 @@
 MinimalizeBigEndianArray(const std::vector<uint8_t> &data) {
     std::vector<uint8_t> res;
 
+    // Can't encode more than this, go ahead and grab as much room as we could
+    // possibly need
+    res.reserve(data.size());
+
     // Ensure we have a byte to work with.
     if (data.size() == 0) {
         return res;
     }
 
-    // Check for a negative bit
-    uint8_t msb = data[0] & 0x80;
-    bool start = false;
+    // Store the MSB
+    uint8_t neg = data[0] & 0x80;
+    bool havePushed = false;
     for (size_t i = 0; i < data.size(); ++i) {
         uint8_t x = data[i];
-        if (i == 0 && (x & 0x7f) == 0) {
-            continue;
+
+        // Remove any MSB that might exist
+        if (i == 0) {
+            x &= 0x7f;
         }
-        if (!start && x == 0) {
+
+        // If we haven't pushed anything, and the current value is zero, keep
+        // ignoring bytes.
+        if (!havePushed && x == 0) {
             continue;
         }
-        start = true;
+
+        // Record that we have begun pushing, and store the current value.
+        havePushed = true;
         res.push_back(x);
     }
 
-    if (res.size() != 0) {
-        res[0] |= msb;
+    // Give us at least one byte
+    if (res.size() == 0) {
+        res.push_back(0);
+    }
+
+    // Only add back the sign if a value has been pushed.  This implies the
+    // result is non-zero.
+    if (havePushed) {
+        // If the MSB is currently occupied, we need one extra byte.
+        if ((res[0] & 0x80) != 0) {
+            res.insert(res.begin(), 0);
+        }
+        res[0] |= neg;
     }
 
     return res;
diff --git a/src/test/script_tests.cpp b/src/test/script_tests.cpp
--- a/src/test/script_tests.cpp
+++ b/src/test/script_tests.cpp
@@ -415,19 +415,39 @@
 } // namespace
 
 BOOST_AUTO_TEST_CASE(minimize_big_endian_test) {
-    std::vector<uint8_t> input(
-        {{0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x01}});
-    std::vector<uint8_t> negInput(
-        {{0x80, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x01}});
+    // Empty array case
+    BOOST_CHECK(MinimalizeBigEndianArray(std::vector<uint8_t>()) == std::vector<uint8_t>());
+
+    // Zero arrays of various lengths
+    std::vector<uint8_t> zeroArray({{0x00}});
+    std::vector<uint8_t> negZeroArray({{0x80}});
+    for (int i = 0; i < 16; i++) {
+        if (i > 0) {
+            zeroArray.push_back(0x00);
+            negZeroArray.push_back(0x00);
+        }
 
-    std::vector<uint8_t> check({0x01, 0x00, 0x00, 0x01});
-    std::vector<uint8_t> negCheck({0x81, 0x00, 0x00, 0x01});
+        BOOST_CHECK(MinimalizeBigEndianArray(zeroArray) ==
+            std::vector<uint8_t>({{0x00}}));
 
-    std::vector<uint8_t> out = MinimalizeBigEndianArray(input);
-    std::vector<uint8_t> negOut = MinimalizeBigEndianArray(negInput);
+        // -0 should always evaluate to 0x00
+        BOOST_CHECK(MinimalizeBigEndianArray(negZeroArray) ==
+            std::vector<uint8_t>({{0x00}}));
+    }
 
-    BOOST_CHECK(out == check);
-    BOOST_CHECK(negOut == negCheck);
+    // Shouldn't minimalize this array to a negative number
+    std::vector<uint8_t> notNegArray({{0x00, 0x80}});
+    for (int i = 0; i < 16; i++) {
+        notNegArray.push_back(i);
+        BOOST_CHECK(MinimalizeBigEndianArray(notNegArray) == notNegArray);
+    }
+
+    // Shouldn't minimalize these arrays at all
+    std::vector<uint8_t> noMinArray;
+    for (int i = 1; i < 0x80; i++) {
+        noMinArray.push_back(i);
+        BOOST_CHECK(MinimalizeBigEndianArray(noMinArray) == noMinArray);
+    }
 }
 
 BOOST_AUTO_TEST_CASE(script_build) {