From c1855f6052aca806fdb51be01b30dfeee8b55f40 Mon Sep 17 00:00:00 2001
From: Jim Posen <jimpo@coinbase.com>
Date: Tue, 23 Jan 2018 17:25:30 -0800
Subject: blockfilter: Construction of basic block filters.

---
 src/blockfilter.cpp            | 40 +++++++++++++++++++++++++++++++
 src/blockfilter.h              | 35 ++++++++++++++++++++++++++++
 src/test/blockfilter_tests.cpp | 53 ++++++++++++++++++++++++++++++++++++++++++
 src/undo.h                     |  1 +
 4 files changed, 129 insertions(+)

diff --git a/src/blockfilter.cpp b/src/blockfilter.cpp
index 52d8f8c296..1119b54901 100644
--- a/src/blockfilter.cpp
+++ b/src/blockfilter.cpp
@@ -4,6 +4,8 @@
 
 #include <blockfilter.h>
 #include <hash.h>
+#include <primitives/transaction.h>
+#include <script/script.h>
 #include <streams.h>
 
 /// SerType used to serialize parameters in GCS filter encoding.
@@ -193,3 +195,41 @@ bool GCSFilter::MatchAny(const ElementSet& elements) const
     const std::vector<uint64_t> queries = BuildHashedSet(elements);
     return MatchInternal(queries.data(), queries.size());
 }
+
+static GCSFilter::ElementSet BasicFilterElements(const CBlock& block,
+                                                 const CBlockUndo& block_undo)
+{
+    GCSFilter::ElementSet elements;
+
+    for (const CTransactionRef& tx : block.vtx) {
+        for (const CTxOut& txout : tx->vout) {
+            const CScript& script = txout.scriptPubKey;
+            if (script[0] == OP_RETURN) continue;
+            elements.emplace(script.begin(), script.end());
+        }
+    }
+
+    for (const CTxUndo& tx_undo : block_undo.vtxundo) {
+        for (const Coin& prevout : tx_undo.vprevout) {
+            const CScript& script = prevout.out.scriptPubKey;
+            elements.emplace(script.begin(), script.end());
+        }
+    }
+
+    return elements;
+}
+
+BlockFilter::BlockFilter(BlockFilterType filter_type, const CBlock& block, const CBlockUndo& block_undo)
+    : m_filter_type(filter_type), m_block_hash(block.GetHash())
+{
+    switch (m_filter_type) {
+    case BlockFilterType::BASIC:
+        m_filter = GCSFilter(m_block_hash.GetUint64(0), m_block_hash.GetUint64(1),
+                             BASIC_FILTER_P, BASIC_FILTER_M,
+                             BasicFilterElements(block, block_undo));
+        break;
+
+    default:
+        throw std::invalid_argument("unknown filter_type");
+    }
+}
diff --git a/src/blockfilter.h b/src/blockfilter.h
index d45d31046f..afb8d7a7b7 100644
--- a/src/blockfilter.h
+++ b/src/blockfilter.h
@@ -9,8 +9,10 @@
 #include <stdint.h>
 #include <vector>
 
+#include <primitives/block.h>
 #include <serialize.h>
 #include <uint256.h>
+#include <undo.h>
 
 /**
  * This implements a Golomb-coded set as defined in BIP 158. It is a
@@ -71,4 +73,37 @@ public:
     bool MatchAny(const ElementSet& elements) const;
 };
 
+constexpr uint8_t BASIC_FILTER_P = 19;
+constexpr uint32_t BASIC_FILTER_M = 784931;
+
+enum BlockFilterType : uint8_t
+{
+    BASIC = 0,
+};
+
+/**
+ * Complete block filter struct as defined in BIP 157.
+ */
+class BlockFilter
+{
+private:
+    BlockFilterType m_filter_type;
+    uint256 m_block_hash;
+    GCSFilter m_filter;
+
+public:
+
+    // Construct a new BlockFilter of the specified type from a block.
+    BlockFilter(BlockFilterType filter_type, const CBlock& block, const CBlockUndo& block_undo);
+
+    BlockFilterType GetFilterType() const { return m_filter_type; }
+
+    const GCSFilter& GetFilter() const { return m_filter; }
+
+    const std::vector<unsigned char>& GetEncodedFilter() const
+    {
+        return m_filter.GetEncoded();
+    }
+};
+
 #endif // BITCOIN_BLOCKFILTER_H
diff --git a/src/test/blockfilter_tests.cpp b/src/test/blockfilter_tests.cpp
index 339a7fcfeb..4fe34dedcb 100644
--- a/src/test/blockfilter_tests.cpp
+++ b/src/test/blockfilter_tests.cpp
@@ -2,7 +2,11 @@
 // Distributed under the MIT software license, see the accompanying
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
+#include <test/test_bitcoin.h>
+
 #include <blockfilter.h>
+#include <serialize.h>
+#include <streams.h>
 
 #include <boost/test/unit_test.hpp>
 
@@ -31,4 +35,53 @@ BOOST_AUTO_TEST_CASE(gcsfilter_test)
     }
 }
 
+BOOST_AUTO_TEST_CASE(blockfilter_basic_test)
+{
+    CScript included_scripts[5], excluded_scripts[2];
+
+    // First two are outputs on a single transaction.
+    included_scripts[0] << std::vector<unsigned char>(0, 65) << OP_CHECKSIG;
+    included_scripts[1] << OP_DUP << OP_HASH160 << std::vector<unsigned char>(1, 20) << OP_EQUALVERIFY << OP_CHECKSIG;
+
+    // Third is an output on in a second transaction.
+    included_scripts[2] << OP_1 << std::vector<unsigned char>(2, 33) << OP_1 << OP_CHECKMULTISIG;
+
+    // Last two are spent by a single transaction.
+    included_scripts[3] << OP_0 << std::vector<unsigned char>(3, 32);
+    included_scripts[4] << OP_4 << OP_ADD << OP_8 << OP_EQUAL;
+
+    // OP_RETURN output is an output on the second transaction.
+    excluded_scripts[0] << OP_RETURN << std::vector<unsigned char>(4, 40);
+
+    // This script is not related to the block at all.
+    excluded_scripts[1] << std::vector<unsigned char>(5, 33) << OP_CHECKSIG;
+
+    CMutableTransaction tx_1;
+    tx_1.vout.emplace_back(100, included_scripts[0]);
+    tx_1.vout.emplace_back(200, included_scripts[1]);
+
+    CMutableTransaction tx_2;
+    tx_2.vout.emplace_back(300, included_scripts[2]);
+    tx_2.vout.emplace_back(0, excluded_scripts[0]);
+
+    CBlock block;
+    block.vtx.push_back(MakeTransactionRef(tx_1));
+    block.vtx.push_back(MakeTransactionRef(tx_2));
+
+    CBlockUndo block_undo;
+    block_undo.vtxundo.emplace_back();
+    block_undo.vtxundo.back().vprevout.emplace_back(CTxOut(400, included_scripts[3]), 1000, true);
+    block_undo.vtxundo.back().vprevout.emplace_back(CTxOut(500, included_scripts[4]), 10000, false);
+
+    BlockFilter block_filter(BlockFilterType::BASIC, block, block_undo);
+    const GCSFilter& filter = block_filter.GetFilter();
+
+    for (const CScript& script : included_scripts) {
+        BOOST_CHECK(filter.Match(GCSFilter::Element(script.begin(), script.end())));
+    }
+    for (const CScript& script : excluded_scripts) {
+        BOOST_CHECK(!filter.Match(GCSFilter::Element(script.begin(), script.end())));
+    }
+}
+
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/undo.h b/src/undo.h
index a1398b7624..4a78238944 100644
--- a/src/undo.h
+++ b/src/undo.h
@@ -6,6 +6,7 @@
 #ifndef BITCOIN_UNDO_H
 #define BITCOIN_UNDO_H
 
+#include <coins.h>
 #include <compressor.h>
 #include <consensus/consensus.h>
 #include <primitives/transaction.h>
-- 
cgit v1.2.3