pad_IBLT.patch

diff --git a/src/blockrelay/graphene.cpp b/src/blockrelay/graphene.cpp
index 7f49162..7ad515a 100644
--- a/src/blockrelay/graphene.cpp
+++ b/src/blockrelay/graphene.cpp
@@ -25,9 +25,19 @@
 
 static bool ReconstructBlock(CNode *pfrom, const bool fXVal, int &missingCount, int &unnecessaryCount);
 
+std::vector<size_t> ArgSort(const std::vector<uint256> &items)
+{
+    std::vector<size_t> idxs(items.size());
+    std::iota(idxs.begin(), idxs.end(), 0);
+
+    std::sort(idxs.begin(), idxs.end(), [&items](size_t idx1, size_t idx2) { return items[idx1] < items[idx2]; });
+
+    return idxs;
+}
+
 CMemPoolInfo::CMemPoolInfo(uint64_t _nTx) : nTx(_nTx) {}
 CMemPoolInfo::CMemPoolInfo() { this->nTx = 0; }
-CGrapheneBlock::CGrapheneBlock(const CBlockRef pblock, uint64_t nReceiverMemPoolTx)
+CGrapheneBlock::CGrapheneBlock(const CBlockRef pblock, uint64_t nReceiverMemPoolTx, uint64_t nSenderMempoolPlusBlock)
 {
     header = pblock->GetBlockHeader();
     nBlockTxs = pblock->vtx.size();
@@ -41,7 +51,12 @@ CGrapheneBlock::CGrapheneBlock(const CBlockRef pblock, uint64_t nReceiverMemPool
             vAdditionalTxs.push_back(tx);
     }
 
-    pGrapheneSet = new CGrapheneSet(nReceiverMemPoolTx, blockHashes, true);
+    std::vector<size_t> sortedIdxs = ArgSort(blockHashes);
+    int ct = 0;
+    for (auto idx : sortedIdxs)
+        LOG(GRAPHENE, "%d: block %s\n", ++ct, blockHashes[idx].ToString());
+
+    pGrapheneSet = new CGrapheneSet(nReceiverMemPoolTx, nSenderMempoolPlusBlock, blockHashes, true);
 }
 
 CGrapheneBlock::~CGrapheneBlock()
@@ -287,6 +302,8 @@ bool CRequestGrapheneBlockTx::HandleMessage(CDataStream &vRecv, CNode *pfrom)
         CGrapheneBlockTx grapheneBlockTx(grapheneRequestBlockTx.blockhash, vTx);
         pfrom->PushMessage(NetMsgType::GRAPHENETX, grapheneBlockTx);
         pfrom->txsSent += vTx.size();
+        LOG(GRAPHENE, "Graphene rerequest tx size: %d\n",
+                ::GetSerializeSize(grapheneBlockTx, SER_NETWORK, PROTOCOL_VERSION));
     }
 
     return true;
@@ -1396,7 +1413,9 @@ void SendGrapheneBlock(CBlockRef pblock, CNode *pfrom, const CInv &inv, const CM
     {
         try
         {
-            CGrapheneBlock grapheneBlock(MakeBlockRef(*pblock), mempoolinfo.nTx);
+            uint64_t nSenderMempoolPlusBlock = std::max(0, (int)(GetGrapheneMempoolInfo().nTx + pblock->vtx.size() - 1)); // exclude coinbase
+
+            CGrapheneBlock grapheneBlock(MakeBlockRef(*pblock), mempoolinfo.nTx, nSenderMempoolPlusBlock);
             int nSizeBlock = pblock->GetBlockSize();
             int nSizeGrapheneBlock = ::GetSerializeSize(grapheneBlock, SER_NETWORK, PROTOCOL_VERSION);
 
@@ -1414,6 +1433,12 @@ void SendGrapheneBlock(CBlockRef pblock, CNode *pfrom, const CInv &inv, const CM
                 LOG(GRAPHENE, "Sent graphene block - size: %d vs block size: %d => peer: %s\n", nSizeGrapheneBlock,
                     nSizeBlock, pfrom->GetLogName());
 
+                LOG(GRAPHENE, "Filter bytes: %d, Iblt bytes: %d, Rank bytes: %d, AddTx: %d\n",
+                        grapheneBlock.pGrapheneSet->GetFilterSerializationSize(),
+                        grapheneBlock.pGrapheneSet->GetIbltSerializationSize(),
+                        grapheneBlock.pGrapheneSet->GetRankSerializationSize(),
+                        grapheneBlock.GetAdditionalTxSerializationSize());
+
                 graphenedata.UpdateFilter(grapheneBlock.pGrapheneSet->GetFilterSerializationSize());
                 graphenedata.UpdateIblt(grapheneBlock.pGrapheneSet->GetIbltSerializationSize());
                 graphenedata.UpdateRank(grapheneBlock.pGrapheneSet->GetRankSerializationSize());
diff --git a/src/blockrelay/graphene.h b/src/blockrelay/graphene.h
index a4278b3..4c3958a 100644
--- a/src/blockrelay/graphene.h
+++ b/src/blockrelay/graphene.h
@@ -53,7 +53,7 @@ public:
     CGrapheneSet *pGrapheneSet;
 
 public:
-    CGrapheneBlock(const CBlockRef pblock, uint64_t nReceiverMemPoolTx);
+    CGrapheneBlock(const CBlockRef pblock, uint64_t nReceiverMemPoolTx, uint64_t nSenderMempoolPlusBlock);
     CGrapheneBlock() : pGrapheneSet(nullptr) {}
     ~CGrapheneBlock();
     /**
diff --git a/src/blockrelay/graphene_set.cpp b/src/blockrelay/graphene_set.cpp
index 2c22515..b243381 100644
--- a/src/blockrelay/graphene_set.cpp
+++ b/src/blockrelay/graphene_set.cpp
@@ -14,7 +14,18 @@
 #include <cmath>
 #include <numeric>
 
+std::vector<size_t> TxIDArgSort(const std::vector<uint256> &items)
+{
+    std::vector<size_t> idxs(items.size());
+    std::iota(idxs.begin(), idxs.end(), 0);
+
+    std::sort(idxs.begin(), idxs.end(), [&items](size_t idx1, size_t idx2) { return items[idx1] < items[idx2]; });
+
+    return idxs;
+}
+
 CGrapheneSet::CGrapheneSet(size_t _nReceiverUniverseItems,
+    uint64_t nSenderUniverseItems,
     const std::vector<uint256> &_itemHashes,
     bool _ordered,
     bool fDeterministic)
@@ -29,31 +40,38 @@ CGrapheneSet::CGrapheneSet(size_t _nReceiverUniverseItems,
 
     FastRandomContext insecure_rand(fDeterministic);
 
+    // Infer various receiver quantities
+    uint64_t nReceiverExcessItems = std::min((int)nReceiverUniverseItems, std::max(0, (int)(nSenderUniverseItems - nItems)));
+    uint64_t nReceiverMissingItems = std::max(1, (int)(nItems - (nReceiverUniverseItems - nReceiverExcessItems)));
+
+    LOG(GRAPHENE, "mempoolinfo.nTx: %d, nSenderMempoolPlusBlock %d \n", nReceiverUniverseItems, nSenderUniverseItems);
+    LOG(GRAPHENE, "receiver has at most %d excess txs in mempool\n", nReceiverExcessItems);
+    LOG(GRAPHENE, "receiver has at most %d missing from block\n", nReceiverMissingItems);
+
     // Optimal symmetric differences between receiver and sender IBLTs
     // This is the parameter "a" from the graphene paper
-    double optSymDiff = 1;
+    double optSymDiff = std::max(1, (int)nReceiverMissingItems);
     try
     {
-        if (nItems < nReceiverUniverseItems + 1)
-            optSymDiff = OptimalSymDiff(nItems, nReceiverUniverseItems);
+        if (nItems <= nReceiverUniverseItems + nReceiverMissingItems)
+            optSymDiff = OptimalSymDiff(nItems, nReceiverUniverseItems, nReceiverExcessItems, nReceiverMissingItems);
     }
     catch (const std::runtime_error &e)
     {
         LOG(GRAPHENE, "failed to optimize symmetric difference for graphene: %s\n", e.what());
     }
 
-    // Sender's estimate of number of items in both block and receiver mempool
-    // This is the parameter "mu" from the graphene paper
-    uint64_t nItemIntersect = std::min(nItems, nReceiverUniverseItems) - 1;
-
     // Set false positive rate for Bloom filter based on optSymDiff
     double fpr;
-    uint64_t nReceiverExcessItems = nReceiverUniverseItems - nItemIntersect;
     if (optSymDiff >= nReceiverExcessItems)
         fpr = FILTER_FPR_MAX;
     else
         fpr = optSymDiff / float(nReceiverExcessItems);
 
+    // So far we have only made room for false positives in the IBLT
+    // Make more room for missing items
+    optSymDiff += nReceiverMissingItems;
+
     // Construct Bloom filter
     pSetFilter = new CBloomFilter(
         nItems, fpr, insecure_rand.rand32(), BLOOM_UPDATE_ALL, true, std::numeric_limits<uint32_t>::max());
@@ -64,6 +82,8 @@ CGrapheneSet::CGrapheneSet(size_t _nReceiverUniverseItems,
     pSetIblt = new CIblt(nIbltCells);
     std::map<uint64_t, uint256> mapCheapHashes;
 
+    LOG(GRAPHENE, "constructed IBLT with %d cells\n", nIbltCells);
+
     for (const uint256 &itemHash : _itemHashes)
     {
         uint64_t cheapHash = itemHash.GetCheapHash();
@@ -98,7 +118,7 @@ CGrapheneSet::CGrapheneSet(size_t _nReceiverUniverseItems,
 }
 
 
-double CGrapheneSet::OptimalSymDiff(uint64_t nBlockTxs, uint64_t nReceiverPoolTx)
+double CGrapheneSet::OptimalSymDiff(uint64_t nBlockTxs, uint64_t nReceiverPoolTx, uint64_t nReceiverExcessTxs, uint64_t nReceiverMissingTxs)
 {
     /* Optimal symmetric difference between block txs and receiver mempool txs passing
      * though filter to use for IBLT.
@@ -109,21 +129,19 @@ double CGrapheneSet::OptimalSymDiff(uint64_t nBlockTxs, uint64_t nReceiverPoolTx
      * The total size in bytes of a graphene block is given by T(a) = F(a) + L(a) as defined
      * in the code below. (Note that meta parameters for the Bloom Filter and IBLT are ignored).
      */
-    assert(nReceiverPoolTx >= nBlockTxs - 1); // Assume reciever is missing only one tx
+    assert(nBlockTxs >= 0);
+    assert(nReceiverPoolTx >= 0);
+    assert(nReceiverExcessTxs >= 0);
+    LOG(GRAPHENE, "INSIDE Opt nReceiverExcessTxs: %d nReceiverPoolTx: %d\n", nReceiverExcessTxs, nReceiverPoolTx);
+    assert(nReceiverExcessTxs <= nReceiverPoolTx); // Excess contained in mempool
+    assert(nReceiverMissingTxs >= 0);
+    assert(nReceiverMissingTxs <= nBlockTxs); // Can't be missing more txs than are in block
 
     if (nReceiverPoolTx > LARGE_MEM_POOL_SIZE)
         throw std::runtime_error("Receiver mempool is too large for optimization");
 
-    // Because we assumed the receiver is only missing only one tx
-    uint64_t nBlockAndReceiverPoolTx = nBlockTxs - 1;
-
-    // Techinically there should be no symdiff here, but we need to have at least one entry in
-    // the IBLT, otherwise the Bloom filter must have fpr = 0
-    if (nReceiverPoolTx == nBlockAndReceiverPoolTx)
-        return 1;
-
-    auto fpr = [nReceiverPoolTx, nBlockAndReceiverPoolTx](uint64_t a) {
-        float _fpr = a / float(nReceiverPoolTx - nBlockAndReceiverPoolTx);
+    auto fpr = [nReceiverExcessTxs](uint64_t a) {
+        float _fpr = a / float(nReceiverExcessTxs);
 
         return _fpr < FILTER_FPR_MAX ? _fpr : FILTER_FPR_MAX;
     };
@@ -166,6 +184,7 @@ std::vector<uint64_t> CGrapheneSet::Reconcile(const std::vector<uint256> &receiv
     CIblt localIblt((*pSetIblt));
     localIblt.reset();
 
+    int passedFilter = 0;
     for (const uint256 &itemHash : receiverItemHashes)
     {
         uint64_t cheapHash = itemHash.GetCheapHash();
@@ -180,8 +199,10 @@ std::vector<uint64_t> CGrapheneSet::Reconcile(const std::vector<uint256> &receiv
         {
             receiverSet.insert(cheapHash);
             localIblt.insert(cheapHash, IBLT_NULL_VALUE);
+            passedFilter += 1;
         }
     }
+    LOG(GRAPHENE, "%d txs passed receiver Bloom filter\n", passedFilter);
 
     mapCheapHashes.clear();
     return Reconcile(receiverSet, localIblt);
@@ -195,14 +216,21 @@ std::vector<uint64_t> CGrapheneSet::Reconcile(const std::map<uint64_t, uint256>
     CIblt localIblt((*pSetIblt));
     localIblt.reset();
 
+    std::vector<uint256> passedTxIds;
     for (const auto &entry : mapCheapHashes)
     {
         if ((*pSetFilter).contains(entry.second))
         {
             receiverSet.insert(entry.first);
             localIblt.insert(entry.first, IBLT_NULL_VALUE);
+            passedTxIds.push_back(entry.second);
         }
     }
+    std::vector<size_t> sortedIdxs = TxIDArgSort(passedTxIds);
+    int ct = 0;
+    for (auto idx : sortedIdxs)
+        LOG(GRAPHENE, "%d: recovered %s\n", ++ct, passedTxIds[idx].ToString());
+
     return Reconcile(receiverSet, localIblt);
 }
 
@@ -215,6 +243,8 @@ std::vector<uint64_t> CGrapheneSet::Reconcile(std::set<uint64_t> &receiverSet, c
     if (!((*pSetIblt) - localIblt).listEntries(senderHas, receiverHas))
         throw std::runtime_error("Graphene set IBLT did not decode");
 
+    LOG(GRAPHENE, "senderHas: %d, receiverHas: %d\n", senderHas.size(), receiverHas.size());
+
     // Remove false positives from receiverSet
     for (const std::pair<uint64_t, std::vector<uint8_t> > &kv : receiverHas)
         receiverSet.erase(kv.first);
diff --git a/src/blockrelay/graphene_set.h b/src/blockrelay/graphene_set.h
index b5da4c0..c193a32 100644
--- a/src/blockrelay/graphene_set.h
+++ b/src/blockrelay/graphene_set.h
@@ -50,6 +50,7 @@ public:
     // The default constructor is for 2-phase construction via deserialization
     CGrapheneSet() : ordered(false), nReceiverUniverseItems(0), pSetFilter(nullptr), pSetIblt(nullptr) {}
     CGrapheneSet(size_t _nReceiverUniverseItems,
+        uint64_t nSenderUniverseItems,
         const std::vector<uint256> &_itemHashes,
         bool _ordered = false,
         bool fDeterministic = false);
@@ -63,7 +64,7 @@ public:
      * The total size in bytes of a graphene block is given by T(a) = F(a) + L(a) as defined
      * in the code below. (Note that meta parameters for the Bloom Filter and IBLT are ignored).
      */
-    double OptimalSymDiff(uint64_t nBlockTxs, uint64_t nReceiverPoolTx);
+    double OptimalSymDiff(uint64_t nBlockTxs, uint64_t nReceiverPoolTx, uint64_t nReceiverExcessTxs = 0, uint64_t nReceiverMissingTxs = 1);
 
     // Pass the transaction hashes that the local machine has to reconcile with the remote and return a list
     // of cheap hashes in the block in the correct order
diff --git a/src/test/graphene_tests.cpp b/src/test/graphene_tests.cpp
index c4dad2b..78d0e9d 100644
--- a/src/test/graphene_tests.cpp
+++ b/src/test/graphene_tests.cpp
@@ -31,7 +31,7 @@ BOOST_AUTO_TEST_CASE(graphene_set_encodes_and_decodes)
 
     // unordered graphene sets
     {
-        CGrapheneSet senderGrapheneSet(6, senderItems, false, true);
+        CGrapheneSet senderGrapheneSet(6, 6, senderItems, false, true);
         std::vector<uint64_t> reconciledCheapHashes = senderGrapheneSet.Reconcile(receiverItems);
 
         std::vector<uint64_t> senderCheapHashes;
@@ -48,7 +48,7 @@ BOOST_AUTO_TEST_CASE(graphene_set_encodes_and_decodes)
 
     // ordered graphene sets
     {
-        CGrapheneSet senderGrapheneSet(6, senderItems, true, true);
+        CGrapheneSet senderGrapheneSet(6, 6, senderItems, true, true);
         std::vector<uint64_t> reconciledCheapHashes = senderGrapheneSet.Reconcile(receiverItems);
 
         std::vector<uint64_t> senderCheapHashes;
@@ -87,7 +87,7 @@ BOOST_AUTO_TEST_CASE(graphene_set_decodes_multiple_sizes)
                 receiverItems.push_back(SerializeHash(GetHash(nNumHashes)));
             }
 
-            CGrapheneSet senderGrapheneSet(receiverItems.size(), senderItems, true, true);
+            CGrapheneSet senderGrapheneSet(receiverItems.size(), receiverItems.size(), senderItems, true, true);
             std::vector<uint64_t> reconciledCheapHashes = senderGrapheneSet.Reconcile(receiverItems);
 
             BOOST_CHECK_EQUAL_COLLECTIONS(reconciledCheapHashes.begin(), reconciledCheapHashes.end(),
@@ -103,7 +103,7 @@ BOOST_AUTO_TEST_CASE(graphene_set_decodes_multiple_sizes)
                 receiverItems.push_back(SerializeHash(GetHash(nNumHashes)));
             }
 
-            CGrapheneSet senderGrapheneSet(receiverItems.size(), senderItems, true, true);
+            CGrapheneSet senderGrapheneSet(receiverItems.size(), receiverItems.size(), senderItems, true, true);
             std::vector<uint64_t> reconciledCheapHashes = senderGrapheneSet.Reconcile(receiverItems);
 
             BOOST_CHECK_EQUAL_COLLECTIONS(reconciledCheapHashes.begin(), reconciledCheapHashes.end(),
@@ -153,7 +153,7 @@ BOOST_AUTO_TEST_CASE(graphene_set_can_serde)
     CDataStream ss(SER_DISK, 0);
 
     senderItems.push_back(SerializeHash(3));
-    CGrapheneSet sentGrapheneSet(1, senderItems, true);
+    CGrapheneSet sentGrapheneSet(1, 1, senderItems, true);
     CGrapheneSet receivedGrapheneSet;
 
     ss << sentGrapheneSet;
diff --git a/src/test/test_bitcoin_fuzzy.cpp b/src/test/test_bitcoin_fuzzy.cpp
index 9534dd7..221cd3a 100644
--- a/src/test/test_bitcoin_fuzzy.cpp
+++ b/src/test/test_bitcoin_fuzzy.cpp
@@ -526,7 +526,7 @@ protected:
 
         try
         {
-            gs = std::make_shared<CGrapheneSet>(nReceiverUniverseItems, itemHashes, ordered, fDeterministic);
+            gs = std::make_shared<CGrapheneSet>(nReceiverUniverseItems, nReceiverUniverseItems, itemHashes, ordered, fDeterministic);
 
             while (!ds->empty())
             {