citp · maltemoeser · May 7, 2020 · Apr 22, 2020 · Apr 22, 2020 · Apr 22, 2020
diff --git a/.circleci/test_parser.sh b/.circleci/test_parser.sh
@@ -3,13 +3,13 @@ cd test
 blocksci_parser btc.json generate-config bitcoin_regtest bitcoin_regtest --disk files/btc/regtest/
 blocksci_parser btc.json doctor
 blocksci_parser btc.json update
-blocksci_check_integrity btc.json
+blocksci_check_integrity btc.json -t -n
 blocksci_parser bch.json generate-config bitcoin_cash_regtest bitcoin_cash_regtest --disk files/bch/regtest/
 blocksci_parser bch.json doctor
 blocksci_parser bch.json update
-blocksci_check_integrity bch.json
+blocksci_check_integrity bch.json -t -n
 blocksci_parser ltc.json generate-config litecoin_regtest litecoin_regtest --disk files/ltc/regtest/
 blocksci_parser ltc.json doctor
 blocksci_parser ltc.json update
-blocksci_check_integrity ltc.json
+blocksci_check_integrity ltc.json -t -n
 cd ..
diff --git a/.travis/test_parser.sh b/.travis/test_parser.sh
@@ -4,10 +4,13 @@ cd test
 blocksci_parser btc.json generate-config bitcoin_regtest bitcoin_regtest --disk files/btc/regtest/
 blocksci_parser btc.json doctor
 blocksci_parser btc.json update
+blocksci_check_integrity btc.json -t -n
 blocksci_parser bch.json generate-config bitcoin_cash_regtest bitcoin_cash_regtest --disk files/bch/regtest/
 blocksci_parser bch.json doctor
 blocksci_parser bch.json update
+blocksci_check_integrity bch.json -t -n
 blocksci_parser ltc.json generate-config litecoin_regtest litecoin_regtest --disk files/ltc/regtest/
 blocksci_parser ltc.json doctor
 blocksci_parser ltc.json update
+blocksci_check_integrity ltc.json -t -n
 cd "$TRAVIS_BUILD_DIR"
diff --git a/src/internal/address_index.cpp b/src/internal/address_index.cpp
@@ -179,40 +179,45 @@ namespace blocksci {
             assert(it->status().ok()); // Check for any errors found during the scan
         });
     }
-
-    ranges::optional<DedupAddress> AddressIndex::getNestingScriptHash(const RawAddress &searchAddress) const {
+
+    /**
+     Retrieve a list of dedup addresses that wrap the address.
+     It's possible to receive multiple results, since multisig addresses are deduplicated, but their pubkeys might be arranged in different order, leading to different wrapping addresses.
+     */
+    std::vector<DedupAddress> AddressIndex::getNestingScriptHash(const RawAddress &searchAddress) const {
+        std::vector<DedupAddress> parents;
         rocksdb::Slice key{reinterpret_cast<const char *>(&searchAddress.scriptNum), sizeof(searchAddress.scriptNum)};
         auto it = getNestedIterator(searchAddress.type);
         it->Seek(key);
-        if (it->Valid() && it->key().starts_with(key)) {
+        while (it->Valid() && it->key().starts_with(key)) {
             auto foundKey = it->key();
             foundKey.remove_prefix(sizeof(uint32_t));
             DedupAddress rawParent;
             memcpy(&rawParent, foundKey.data(), sizeof(rawParent));
-            return rawParent;
+            parents.push_back(rawParent);
+            it->Next();
         }
-        return ranges::nullopt;
+        return parents;
     }
-    
+
     std::unordered_set<DedupAddress> AddressIndex::getPossibleNestedEquivalentUp(const RawAddress &searchAddress) const {
         std::unordered_set<RawAddress> addressesToSearch{searchAddress};
         std::unordered_set<DedupAddress> searchedAddresses;
         while (addressesToSearch.size() > 0) {
             auto address = *addressesToSearch.begin();
-            auto nestingAddress = getNestingScriptHash(address);
-            if (nestingAddress) {
-                if (nestingAddress->type == DedupAddressType::SCRIPTHASH) {
-                    if (searchedAddresses.find(*nestingAddress) == searchedAddresses.end()) {
+            auto nestingAddresses = getNestingScriptHash(address);
+            for(auto nestingAddress : nestingAddresses) {
+                if (nestingAddress.type == DedupAddressType::SCRIPTHASH) {
+                    if (searchedAddresses.find(nestingAddress) == searchedAddresses.end()) {
                         for (auto type : equivAddressTypes(dedupType(AddressType::SCRIPTHASH))) {
-                            addressesToSearch.insert({nestingAddress->scriptNum, type});
+                            addressesToSearch.insert({nestingAddress.scriptNum, type});
                         }
                     }
                 }
             }
             searchedAddresses.insert({address.scriptNum, dedupType(address.type)});
-            addressesToSearch.erase(addressesToSearch.begin());
+            addressesToSearch.erase(address);
         }
         return searchedAddresses;
     }
 }
-
diff --git a/src/internal/address_index.hpp b/src/internal/address_index.hpp
@@ -92,7 +92,7 @@ namespace blocksci {
         /** Get InoutPointer objects for all outputs that belong to the given address */
         ranges::any_view<InoutPointer, ranges::category::forward> getOutputPointers(const RawAddress &address) const;
 
-        ranges::optional<DedupAddress> getNestingScriptHash(const RawAddress &searchAddress) const;
+        std::vector<DedupAddress> getNestingScriptHash(const RawAddress &searchAddress) const;
         std::unordered_set<DedupAddress> getPossibleNestedEquivalentUp(const RawAddress &searchAddress) const;
         ranges::any_view<RawAddress> getIncludingMultisigs(const RawAddress &searchAddress) const;
 

diff --git a/test/blockscipy/test_equiv_address.py b/test/blockscipy/test_equiv_address.py
@@ -0,0 +1,26 @@
+def address_types(chain_name):
+    if chain_name == "btc":
+        return ["p2sh", "p2wsh"]
+    else:
+        return ["p2sh"]
+
+
+def addresses(chain, json_data, chain_name):
+    for addr_type in address_types(chain_name):
+        for i in range(3):
+            addr = chain.address_from_string(
+                json_data["address-{}-spend-{}".format(addr_type, i)]
+            )
+            yield addr, addr_type
+
+
+def sort_addresses(lst):
+    return sorted(lst, key=lambda a: a.address_string)
+
+
+# check that equiv addresses resolve correctly in both directions
+def test_script_equivalence(chain, json_data, regtest, chain_name):
+    for addr, _ in addresses(chain, json_data, chain_name):
+        script_equiv = sort_addresses(addr.equiv(True).addresses.to_list())
+        for equiv_address in script_equiv:
+            assert script_equiv == sort_addresses(equiv_address.equiv(True).addresses.to_list())
diff --git a/tools/integrity_check/main.cpp b/tools/integrity_check/main.cpp
@@ -5,16 +5,21 @@
 //  Created by Malte Möser on 3/6/20.
 //
 
+#include <blocksci/address.hpp>
+#include <blocksci/core/dedup_address.hpp>
 #include <blocksci/chain/blockchain.hpp>
 #include <blocksci/chain/block.hpp>
-#include <blocksci/address.hpp>
 #include <blocksci/script.hpp>
 
+
+#include <internal/address_index.hpp>
 #include <internal/chain_access.hpp>
 #include <internal/data_access.hpp>
-#include <internal/script_access.hpp>
 #include <internal/dedup_address_info.hpp>
 #include <internal/hash_index.hpp>
+#include <internal/script_access.hpp>
+
+#include <range/v3/utility/optional.hpp>
 
 #include <openssl/sha.h>
 
@@ -311,35 +316,78 @@ uint256 compute_hashindex_addressrange_hash(const DataAccess &access) {
 /**
  Compute a checksum over txindex lookup data in hash index.
  */
-uint256 compute_hashindex_txindex_hash(const DataAccess &access) {
-    uint256 hash;
-    SHA256_CTX sha256;
-    SHA256_Init(&sha256);
-
+bool check_hashindex_txindex(const DataAccess &access) {
     const ChainAccess &chainAccess = access.getChain();
     auto chainDirectory = access.config.chainDirectory();
     FixedSizeFileMapper<uint256> txHashesFile(chainAccess.txHashesFilePath(chainDirectory));
     auto &hashIndex = access.hashIndex;
 
+    bool allIndexesCorrect = true;
+
     for(uint32_t i = 0; i < chainAccess.txCount(); ++i) {
         auto txindex = hashIndex->getTxIndex(*txHashesFile[i]);
-        assert(*txindex == i);
-        SHA256_Update(&sha256, &txindex, 4);
+        if(*txindex != i) {
+            allIndexesCorrect = false;
+            std::cout << "Incorrect index for transaction " << i << ". Got: " << *txindex << "." << std::endl;
+        }
     }
-    SHA256_Final(reinterpret_cast<unsigned char *>(&hash), &sha256);
-    return hash;
+    if(allIndexesCorrect) {
+        std::cout << "All txindex lookups correct for transaction hashes." << std::endl;
+    }
+    return allIndexesCorrect;
+}
+
+
+/**
+ Check that we can resolve P2(W)SH addresses from the address they wrap using the address index
+ */
+bool check_nesting_scripthash_index(const DataAccess &access) {
+    auto scripts = &access.getScripts();
+    constexpr DedupAddressType::Enum dedupType = DedupAddressType::SCRIPTHASH;
+    auto scriptCount = scripts->scriptCount(dedupType);
+    auto &addressIndex = access.addressIndex;
+
+    bool allNestingsCorrect = true;
+
+    for(uint32_t i = 1; i <= scriptCount; ++i) {
+        auto data = scripts->getScriptData<dedupType>(i);
+        if(data->hasWrappedAddress()) {
+            RawAddress wrappedAddress = data->wrappedAddress;
+            DedupAddress expectedAddress{i, dedupType};
+            auto nestingAddresses = addressIndex->getNestingScriptHash(wrappedAddress);
+
+            // nesting of multisig addresses might not be unique since keys can appear in arbitrary order
+            if(nestingAddresses.size() > 0) {
+                if(std::find(nestingAddresses.begin(), nestingAddresses.end(), expectedAddress) == nestingAddresses.end()) {
+                    allNestingsCorrect = false;
+                    std::cout << "Incorrect nesting scripthash for (" << wrappedAddress.scriptNum << ", " << wrappedAddress.type << ")." << std::endl;
+                }
+            } else {
+                allNestingsCorrect = false;
+                std::cout << "Found no nesting scripthash for (" << wrappedAddress.scriptNum << ", " << wrappedAddress.type << "). Expected: (" << i << ", " << dedupType << ")." << std::endl;
+            }
+        }
+    }
+    if(allNestingsCorrect) {
+        std::cout << "All reverse nested lookups correct for wrapped addresses." << std::endl;
+    }
+    return allNestingsCorrect;
 }
 
 int main(int argc, char * argv[]) {
     std::string configLocation;
     std::string outputFile;
     std::ofstream out;
+    bool runTxIndexCheck = false;
+    bool runNestingIndexCheck = false;
     std::streambuf *coutbuf = nullptr;
     int endBlock = 0;
 
     auto cli = (
         clipp::value("config file location", configLocation) % "Path to config file",
-        (clipp::option("--file", "-f") & clipp::value("output file", outputFile)) % "Write to file instead of std::cout"
+        (clipp::option("--file", "-f") & clipp::value("output file", outputFile)) % "Write to file instead of std::cout",
+        clipp::option("--txindex", "-t").set(runTxIndexCheck).doc("Run tx index check"),
+        clipp::option("--nestingindex", "-n").set(runNestingIndexCheck).doc("Run nesting address index check")
     );
 
     auto res = parse(argc, argv, cli);
@@ -398,10 +446,16 @@ int main(int argc, char * argv[]) {
     auto hashindex_addressrange_hash = compute_hashindex_addressrange_hash(dataAccess);
     std::cout << hashindex_addressrange_hash.GetHex() << " (ADDRESSINDEX)" <<  std::endl;
 
-    // TODO: convert to range query to improve performance
-    // auto hashindex_txindex_hash = compute_hashindex_txindex_hash(dataAccess);
-    // std::cout << hashindex_txindex_hash.GetHex()<< std::endl;
+    if(runTxIndexCheck) {
+        std::cout << std::endl << "Index: transaction hash->transaction index:" << std::endl;
+        std::cout << "Note: this check will report errors if TXIDs are not unique." << std::endl;
+        check_hashindex_txindex(dataAccess);
+    }
 
+    if(runNestingIndexCheck) {
+        std::cout << std::endl << "Index: nesting address->parent address:" << std::endl;
+        check_nesting_scripthash_index(dataAccess);
+    }
 
     if((!outputFile.empty()) && (coutbuf != nullptr)) {
         std::cout.rdbuf(coutbuf);

diff --git a/tools/parser/address_db.cpp b/tools/parser/address_db.cpp
@@ -37,7 +37,7 @@ void AddressDB::processTx(const blocksci::RawTransaction *tx, uint32_t txNum, co
         if (dedupType(a.type) == DedupAddressType::SCRIPTHASH && addedAddresses.find(a) == addedAddresses.end()) {
             addedAddresses.insert(a);
             auto scriptHash = scripts.getScriptData<DedupAddressType::SCRIPTHASH>(a.scriptNum);
-            if (scriptHash->txFirstSeen == txNum) {
+            if (scriptHash->txFirstSpent == txNum) {
                 addAddressNested(scriptHash->wrappedAddress, DedupAddress{a.scriptNum, DedupAddressType::SCRIPTHASH});
                 return true;
             } else {