From 886f06ee6bbca2e6e05109dbd7e264bdea35238f Mon Sep 17 00:00:00 2001
From: Ian Coleman <coleman.ian@gmail.com>
Date: Fri, 25 Nov 2016 14:24:58 +1100
Subject: [PATCH] Card entropy calculation bugfix

See https://github.com/iancoleman/bip39/issues/33
---
 src/js/entropy.js |  96 +++++++++++++++++++++---
 tests.js          | 182 ++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 260 insertions(+), 18 deletions(-)

diff --git a/src/js/entropy.js b/src/js/entropy.js
index f41cf80..8a0c799 100644
--- a/src/js/entropy.js
+++ b/src/js/entropy.js
@@ -16,6 +16,8 @@
 
 window.Entropy = new (function() {
 
+    var TWO = new BigInteger(2);
+
     // matchers returns an array of the matched events for each type of entropy.
     // eg
     // matchers.binary("010") returns ["0", "1", "0"]
@@ -124,7 +126,6 @@ window.Entropy = new (function() {
         // eg the second last card can be only one of two, not one of fifty two
         // so the added entropy for that card is only one bit at most
         if (base.asInt == 52) {
-            // Get the maximum value WITHOUT replacement
             var totalDecks = Math.ceil(base.parts.length / 52);
             var totalCards = totalDecks * 52;
             var totalCombos = factorial(52).pow(totalDecks);
@@ -135,18 +136,77 @@ window.Entropy = new (function() {
             var currentCombos = totalCombos.divide(remainingCombos);
             var numberOfBits = Math.log2(currentCombos);
             var maxWithoutReplace = BigInteger.pow(2, numberOfBits);
-            // aggresive flooring of numberOfBits by BigInteger.pow means a
-            // more accurate result can be had for small numbers using the
-            // built-in Math.pow function.
-            if (numberOfBits < 32) {
-                maxWithoutReplace = BigInteger(Math.round(Math.pow(2, numberOfBits)));
+            // Use a bunch of sorted decks to measure entropy from, populated
+            // as needed.
+            var sortedDecks = [];
+            // Initialize the final entropy value for these cards
+            var entropyInt = BigInteger.ZERO;
+            // Track how many instances of each card have been used, and thus
+            // how many decks are in use.
+            var cardCounts = {};
+            // Track the total bits of entropy that remain, which diminishes as
+            // each card is drawn.
+            var totalBitsLeft = numberOfBits;
+            // Work out entropy contribution of each card drawn
+            for (var i=0; i<base.parts.length; i++) {
+                // Get the card that was drawn
+                var cardLower = base.parts[i];
+                var card = cardLower.toUpperCase();
+                // Initialize the deck for this card if needed, to track how
+                // much entropy it adds.
+                if (!(card in cardCounts)) {
+                    cardCounts[card] = 0;
+                }
+                // Get the deck this card is from
+                var deckIndex = cardCounts[card];
+                while (deckIndex > sortedDecks.length-1) {
+                    sortedDecks.push(getSortedDeck());
+                }
+                // See how many bits this card contributes (depends on how many
+                // are left in the deck it's from)
+                var deckForCard = sortedDecks[deckIndex];
+                var cardsLeftInDeck = deckForCard.length;
+                var additionalBits = Math.log2(cardsLeftInDeck);
+                // Work out the min and max value for this card
+                var nextTotalBitsLeft = totalBitsLeft - additionalBits;
+                var minPossibleNewEntropy = TWO.pow(nextTotalBitsLeft).subtract(1);
+                var maxPossibleNewEntropy = TWO.pow(totalBitsLeft).subtract(1);
+                var diff = maxPossibleNewEntropy.subtract(minPossibleNewEntropy);
+                // BigInteger aggresively floors numbers which greatly affects
+                // the small numbers. In that case, use native Math library
+                var useBigInt = totalBitsLeft >= 32;
+                if (!useBigInt) {
+                    minPossibleNewEntropy = Math.round(Math.pow(2, nextTotalBitsLeft)-1);
+                    maxPossibleNewEntropy = Math.round(Math.pow(2, totalBitsLeft)-1);
+                    diff = maxPossibleNewEntropy - minPossibleNewEntropy;
+                }
+                // Scale the value between possible min and max depending on
+                // this card value
+                var thisCardIndex = deckForCard.indexOf(card);
+                var toAdd = BigInteger.ZERO;
+                if (cardsLeftInDeck > 1) {
+                    if (useBigInt) {
+                        toAdd = diff.multiply(thisCardIndex)
+                            .divide(deckForCard.length - 1)
+                            .add(minPossibleNewEntropy);
+                    }
+                    else {
+                        var ratio = thisCardIndex / (deckForCard.length -1);
+                        var f = diff * ratio;
+                        toAdd = new BigInteger(f).add(minPossibleNewEntropy);
+                    }
+                }
+                // Add this card entropy to existing entropy
+                entropyInt = entropyInt.add(toAdd);
+                // Remove this card from the deck it comes from
+                deckForCard.splice(thisCardIndex,1);
+                // Ensure the next insance of this card uses the next deck
+                cardCounts[card] = cardCounts[card] + 1;
+                // Next card drawn has less total remaining bits to work with
+                totalBitsLeft = nextTotalBitsLeft;
             }
-            // Get the maximum value WITH replacement
-            var maxWithReplace = BigInteger.pow(52, base.parts.length);
-            // Calculate the new value by scaling the original value down
-            var withoutReplace = entropyInt.multiply(maxWithoutReplace).divide(maxWithReplace);
-            // Left pad with zeros based on number of bits
-            var entropyBin = withoutReplace.toString(2);
+            // Convert to binary
+            var entropyBin = entropyInt.toString(2);
             var numberOfBitsInt = Math.floor(numberOfBits);
             while (entropyBin.length < numberOfBitsInt) {
                 entropyBin = "0" + entropyBin;
@@ -177,6 +237,18 @@ window.Entropy = new (function() {
         return e;
     }
 
+    function getSortedDeck() {
+        var s = [];
+        var suits = "CDHS";
+        var values = "A23456789TJQK";
+        for (var i=0; i<suits.length; i++) {
+            for (var j=0; j<values.length; j++) {
+                s.push(values[j]+suits[i]);
+            }
+        }
+        return s;
+    }
+
     function getBase(str) {
         // Need to get the lowest base for the supplied entropy.
         // This prevents interpreting, say, dice rolls as hexadecimal.
diff --git a/tests.js b/tests.js
index 03ce9e1..0ce34bd 100644
--- a/tests.js
+++ b/tests.js
@@ -2185,9 +2185,9 @@ page.open(url, function(status) {
         try {
             var cards = [
                 [ "ac", "00000" ],
-                [ "acqs", "00000110001" ],
-                [ "acks", "00000110010" ],
-                [ "2cac", "00000110011" ],
+                [ "acqs", "00001100011" ],
+                [ "acks", "00001100100" ],
+                [ "2cac", "00001100101" ],
                 [ "2c", "00001" ],
                 [ "3d", "01111" ],
                 [ "4h", "11101" ],
@@ -2200,8 +2200,8 @@ page.open(url, function(status) {
                 [ "jd", "10111" ],
                 [ "qh", "100101" ],
                 [ "ks", "110011" ],
-                [ "ks2c", "101000101001" ],
-                [ "KS2C", "101000101001" ],
+                [ "ks2c", "101001011100" ],
+                [ "KS2C", "101001011100" ],
             ];
             for (var i=0; i<cards.length; i++) {
                 var card = cards[i][0];
@@ -2209,7 +2209,7 @@ page.open(url, function(status) {
                 e = Entropy.fromString(card);
                 console.log(e.binary + " " + result);
                 if (e.binaryStr !== result) {
-                    return "card entropy not parsed correctly: " + result + " != " + e.binaryStr;
+                    return "card entropy " + card + " not parsed correctly: " + result + " != " + e.binaryStr;
                 }
             }
         }
@@ -2724,6 +2724,136 @@ page.open(url, function(status) {
             words: 18,
             strength: "extremely strong",
         },
+        // Additional entropy from each card decreases as deck is depleted.
+        // Check the boundaries of this depletion
+        // See table at https://github.com/iancoleman/bip39/issues/33#issuecomment-262855862
+        // for following values of 'events, bits, words'
+        // 2 cards remaining = 21 words
+        {
+            entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjs",
+            type: "card (2 missing: QS KS)",
+            events: 50,
+            bits: 224,
+            words: 21,
+            strength: "extremely strong",
+        },
+        // 3 cards remaining = 18 words
+        {
+            entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9sts",
+            type: "card (3 missing: JS QS KS)",
+            events: 49,
+            bits: 222, // table uses different rounding - 222.99604
+            words: 18,
+            strength: "extremely strong",
+        },
+        // 13 cards remaining = 18 words
+        {
+            entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkh",
+            type: "card",
+            events: 39,
+            bits: 193,
+            words: 18,
+            strength: "extremely strong",
+        },
+        // 14 cards remaining = 15 words
+        {
+            entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqh",
+            type: "card",
+            events: 38,
+            bits: 189,
+            words: 15,
+            strength: "very strong",
+        },
+        // 21 cards remaining = 15 words
+        {
+            entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h",
+            type: "card",
+            events: 31,
+            bits: 160,
+            words: 15,
+            strength: "very strong",
+        },
+        // 22 cards remaining = 12 words
+        {
+            entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h",
+            type: "card",
+            events: 30,
+            bits: 155,
+            words: 12,
+            strength: "strong",
+        },
+        // 27 cards remaining = 12 words
+        {
+            entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqd",
+            type: "card",
+            events: 25,
+            bits: 132,
+            words: 12,
+            strength: "strong",
+        },
+        // 28 cards remaining = 9 words
+        {
+            entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjd",
+            type: "card",
+            events: 24,
+            bits: 127,
+            words: 9,
+            strength: "weak",
+        },
+        // 34 cards remaining = 9 words
+        {
+            entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d",
+            type: "card",
+            events: 18,
+            bits: 97,
+            words: 9,
+            strength: "weak",
+        },
+        // 35 cards remaining = 6 words
+        {
+            entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d",
+            type: "card",
+            events: 17,
+            bits: 92,
+            words: 6,
+            strength: "very weak",
+        },
+        // 40 cards remaining = 6 words
+        {
+            entropy: "ac2c3c4c5c6c7c8c9ctcjcqc",
+            type: "card",
+            events: 12,
+            bits: 66,
+            words: 6,
+            strength: "very weak",
+        },
+        // 41 cards remaining = 3 words
+        {
+            entropy: "ac2c3c4c5c6c7c8c9ctcjc",
+            type: "card",
+            events: 11,
+            bits: 61,
+            words: 3,
+            strength: "extremely weak",
+        },
+        // 46 cards remaining = 3 words
+        {
+            entropy: "ac2c3c4c5c6c",
+            type: "card",
+            events: 6,
+            bits: 33,
+            words: 3,
+            strength: "extremely weak",
+        },
+        // 47 cards remaining = 0 words
+        {
+            entropy: "ac2c3c4c5c",
+            type: "card",
+            events: 5,
+            bits: 28,
+            words: 0,
+            strength: "extremely weak",
+        },
     ];
     // use entropy
     page.evaluate(function() {
@@ -2946,6 +3076,46 @@ page.open(url, function(status) {
 });
 },
 
+// Github issue 33
+// https://github.com/iancoleman/bip39/issues/33
+// Final cards should contribute entropy
+function() {
+page.open(url, function(status) {
+    // use entropy
+    page.evaluate(function() {
+        $(".use-entropy").prop("checked", true).trigger("change");
+        $(".entropy").val("7S 9H 9S QH 8C KS AS 7D 7C QD 4S 4D TC 2D 5S JS 3D 8S 8H 4C 3C AC 3S QC 9C JC 7H AD TD JD 6D KH 5C QS 2S 6S 6H JH KD 9D-6C TS TH 4H KC 5H 2H AH 2C 8D 3H 5D").trigger("input");
+    });
+    // get the mnemonic
+    waitForGenerate(function() {
+        var originalPhrase = page.evaluate(function() {
+            return $(".phrase").val();
+        });
+        // Set the last 12 cards to be AS
+        page.evaluate(function() {
+            $(".addresses").empty();
+            $(".entropy").val("7S 9H 9S QH 8C KS AS 7D 7C QD 4S 4D TC 2D 5S JS 3D 8S 8H 4C 3C AC 3S QC 9C JC 7H AD TD JD 6D KH 5C QS 2S 6S 6H JH KD 9D-AS AS AS AS AS AS AS AS AS AS AS AS").trigger("input");
+        });
+        // get the new mnemonic
+        waitForGenerate(function() {
+            var newPhrase = page.evaluate(function() {
+                return $(".phrase").val();
+            });
+            if (newPhrase == originalPhrase) {
+                console.log("Changing last 12 cards does not change mnemonic");
+                console.log("Original:");
+                console.log(originalPhrase);
+                console.log("New:");
+                console.log(newPhrase);
+                fail();
+            }
+            next();
+        });
+    });
+});
+},
+
+
 // If you wish to add more tests, do so here...
 
 // Here is a blank test template
-- 
2.41.0