diff --git a/src/radix.h b/src/radix.h
--- a/src/radix.h
+++ b/src/radix.h
@@ -347,7 +347,7 @@
         RadixNode &operator=(const RadixNode &) = delete;
 
         std::atomic<RadixElement> *get(uint32_t level, const K &key) {
-            return &children[(key >> (level * BITS)) & MASK];
+            return &children[T::IndexFromKey(key, level * BITS, MASK)];
         }
 
         bool isShared() const { return refcount > 0; }
diff --git a/src/test/radix_tests.cpp b/src/test/radix_tests.cpp
--- a/src/test/radix_tests.cpp
+++ b/src/test/radix_tests.cpp
@@ -4,6 +4,9 @@
 
 #include <radix.h>
 
+#include <arith_uint256.h>
+#include <uint256.h>
+
 #include <test/lcg.h>
 #include <test/util/setup_common.h>
 
@@ -17,20 +20,83 @@
 template <typename K> struct TestElement {
     K key;
 
-    TestElement(K keyIn) : key(keyIn) {}
+    TestElement(K keyIn) : key(std::move(keyIn)) {}
     const K &getId() const { return key; }
 
     IMPLEMENT_RCU_REFCOUNT(uint32_t);
 };
 
-template <typename K> void testInsert() {
-    using E = TestElement<K>;
+template <typename K> struct TestElementInt : TestElement<K> {
+    TestElementInt(K keyIn) : TestElement<K>(std::move(keyIn)) {}
+
+    // Required by radix.h
+    static size_t IndexFromKey(const K &k, uint32_t depth, int mask) {
+        return (k >> depth) & mask;
+    }
+
+    // Test only
+    static K ToKey(K k) { return k; }
+
+    static auto SignedMin() {
+        return std::numeric_limits<typename std::make_signed<K>::type>::min();
+    }
+    static auto SignedMax() {
+        return std::numeric_limits<typename std::make_signed<K>::type>::max();
+    }
+    static auto MinusOne() {
+        return std::numeric_limits<typename std::make_unsigned<K>::type>::max();
+    }
+    static auto MinusTwo() {
+        return std::numeric_limits<
+                   typename std::make_unsigned<K>::type>::max() -
+               1;
+    }
+};
+
+struct TestElementUint256 : TestElement<uint256> {
+    TestElementUint256(uint256 keyIn)
+        : TestElement<uint256>(std::move(keyIn)) {}
+
+    // Required by radix.h
+    static size_t IndexFromKey(const uint256 &k, uint32_t depth, int mask) {
+        auto index = UintToArith256(k) >> depth;
+        return index.GetLow64() & mask;
+    }
+
+    // Test only
+    static uint256 ToKey(const uint256 &k) { return k; }
+    static uint256 ToKey(uint64_t k) { return ArithToUint256(k); }
+
+    static uint256 SignedMin() {
+        return uint256S(
+            "8000000000000000000000000000000000000000000000000000000000000000");
+    }
+    static uint256 SignedMax() {
+        return uint256S(
+            "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
+    }
+    static uint256 MinusOne() {
+        return uint256S(
+            "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
+    }
+    static uint256 MinusTwo() {
+        return uint256S(
+            "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE");
+    }
+};
+
+template <typename E> void testInsert() {
     RadixTree<E> mytree;
 
-    auto zero = RCUPtr<E>::make(0);
-    auto one = RCUPtr<E>::make(1);
-    auto two = RCUPtr<E>::make(2);
-    auto three = RCUPtr<E>::make(3);
+    auto keyZero = E::ToKey(0);
+    auto keyOne = E::ToKey(1);
+    auto keyTwo = E::ToKey(2);
+    auto keyThree = E::ToKey(3);
+
+    auto zero = RCUPtr<E>::make(keyZero);
+    auto one = RCUPtr<E>::make(keyOne);
+    auto two = RCUPtr<E>::make(keyTwo);
+    auto three = RCUPtr<E>::make(keyThree);
 
     // Inserting a new element into the tree returns true.
     BOOST_CHECK(mytree.insert(one));
@@ -49,12 +115,10 @@
     BOOST_CHECK(!mytree.insert(three));
 
     // Check extreme values.
-    using SK = typename std::make_signed<K>::type;
-    auto maxsigned = RCUPtr<E>::make(std::numeric_limits<SK>::max());
-    auto minsigned = RCUPtr<E>::make(std::numeric_limits<SK>::min());
-    using UK = typename std::make_unsigned<K>::type;
-    auto minusone = RCUPtr<E>::make(std::numeric_limits<UK>::max());
-    auto minustwo = RCUPtr<E>::make(std::numeric_limits<UK>::max() - 1);
+    auto maxsigned = RCUPtr<E>::make(E::SignedMax());
+    auto minsigned = RCUPtr<E>::make(E::SignedMin());
+    auto minusone = RCUPtr<E>::make(E::MinusOne());
+    auto minustwo = RCUPtr<E>::make(E::MinusTwo());
 
     // Insert them into the tree.
     BOOST_CHECK(mytree.insert(maxsigned));
@@ -74,62 +138,61 @@
 }
 
 BOOST_AUTO_TEST_CASE(insert_test) {
-    testInsert<int32_t>();
-    testInsert<uint32_t>();
-    testInsert<int64_t>();
-    testInsert<uint64_t>();
+    testInsert<TestElementInt<int32_t>>();
+    testInsert<TestElementInt<uint32_t>>();
+    testInsert<TestElementInt<int64_t>>();
+    testInsert<TestElementInt<uint64_t>>();
+
+    testInsert<TestElementUint256>();
 }
 
-template <typename K> void testGet() {
-    using E = TestElement<K>;
+template <typename E> void testGet() {
     RadixTree<E> mytree;
 
-    auto zero = RCUPtr<E>::make(0);
-    auto one = RCUPtr<E>::make(1);
-    auto two = RCUPtr<E>::make(2);
-    auto three = RCUPtr<E>::make(3);
+    auto keyZero = E::ToKey(0);
+    auto keyOne = E::ToKey(1);
+    auto keyTwo = E::ToKey(2);
+    auto keyThree = E::ToKey(3);
+
+    auto zero = RCUPtr<E>::make(keyZero);
+    auto one = RCUPtr<E>::make(keyOne);
+    auto two = RCUPtr<E>::make(keyTwo);
+    auto three = RCUPtr<E>::make(keyThree);
 
     // There are no elements in the tree so far.
-    BOOST_CHECK_EQUAL(mytree.get(1), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(keyOne), NULLPTR(E));
 
     // Insert an element into the tree and check it is there.
     BOOST_CHECK(mytree.insert(one));
-    BOOST_CHECK_EQUAL(mytree.get(1), one);
+    BOOST_CHECK_EQUAL(mytree.get(keyOne), one);
 
     // Let's insert more elements and check they are recovered properly.
-    BOOST_CHECK_EQUAL(mytree.get(0), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(keyZero), NULLPTR(E));
     BOOST_CHECK(mytree.insert(zero));
-    BOOST_CHECK_EQUAL(mytree.get(0), zero);
-    BOOST_CHECK_EQUAL(mytree.get(1), one);
+    BOOST_CHECK_EQUAL(mytree.get(keyZero), zero);
+    BOOST_CHECK_EQUAL(mytree.get(keyOne), one);
 
     // More elements.
-    BOOST_CHECK_EQUAL(mytree.get(2), NULLPTR(E));
-    BOOST_CHECK_EQUAL(mytree.get(3), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(keyTwo), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(keyThree), NULLPTR(E));
     BOOST_CHECK(mytree.insert(two));
     BOOST_CHECK(mytree.insert(three));
 
-    BOOST_CHECK_EQUAL(mytree.get(0), zero);
-    BOOST_CHECK_EQUAL(mytree.get(1), one);
-    BOOST_CHECK_EQUAL(mytree.get(2), two);
-    BOOST_CHECK_EQUAL(mytree.get(3), three);
-
-    // Check extreme values.
-    using SK = typename std::make_signed<K>::type;
-    K maxsk = std::numeric_limits<SK>::max();
-    K minsk = std::numeric_limits<SK>::min();
-    using UK = typename std::make_unsigned<K>::type;
-    K maxuk = std::numeric_limits<UK>::max();
+    BOOST_CHECK_EQUAL(mytree.get(keyZero), zero);
+    BOOST_CHECK_EQUAL(mytree.get(keyOne), one);
+    BOOST_CHECK_EQUAL(mytree.get(keyTwo), two);
+    BOOST_CHECK_EQUAL(mytree.get(keyThree), three);
 
-    auto maxsigned = RCUPtr<E>::make(maxsk);
-    auto minsigned = RCUPtr<E>::make(minsk);
-    auto minusone = RCUPtr<E>::make(maxuk);
-    auto minustwo = RCUPtr<E>::make(maxuk - 1);
+    auto maxsigned = RCUPtr<E>::make(E::SignedMax());
+    auto minsigned = RCUPtr<E>::make(E::SignedMin());
+    auto minusone = RCUPtr<E>::make(E::MinusOne());
+    auto minustwo = RCUPtr<E>::make(E::MinusTwo());
 
     // Check that they are not in the tree.
-    BOOST_CHECK_EQUAL(mytree.get(maxsk), NULLPTR(E));
-    BOOST_CHECK_EQUAL(mytree.get(minsk), NULLPTR(E));
-    BOOST_CHECK_EQUAL(mytree.get(maxuk), NULLPTR(E));
-    BOOST_CHECK_EQUAL(mytree.get(maxuk - 1), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(E::SignedMax()), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(E::SignedMin()), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(E::MinusOne()), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(E::MinusTwo()), NULLPTR(E));
 
     // Insert into the tree.
     BOOST_CHECK(mytree.insert(maxsigned));
@@ -138,39 +201,45 @@
     BOOST_CHECK(mytree.insert(minustwo));
 
     // And now they all are in the tree.
-    BOOST_CHECK_EQUAL(mytree.get(0), zero);
-    BOOST_CHECK_EQUAL(mytree.get(1), one);
-    BOOST_CHECK_EQUAL(mytree.get(2), two);
-    BOOST_CHECK_EQUAL(mytree.get(3), three);
-    BOOST_CHECK_EQUAL(mytree.get(maxsk), maxsigned);
-    BOOST_CHECK_EQUAL(mytree.get(minsk), minsigned);
-    BOOST_CHECK_EQUAL(mytree.get(maxuk), minusone);
-    BOOST_CHECK_EQUAL(mytree.get(maxuk - 1), minustwo);
+    BOOST_CHECK_EQUAL(mytree.get(keyZero), zero);
+    BOOST_CHECK_EQUAL(mytree.get(keyOne), one);
+    BOOST_CHECK_EQUAL(mytree.get(keyTwo), two);
+    BOOST_CHECK_EQUAL(mytree.get(keyThree), three);
+    BOOST_CHECK_EQUAL(mytree.get(E::SignedMax()), maxsigned);
+    BOOST_CHECK_EQUAL(mytree.get(E::SignedMin()), minsigned);
+    BOOST_CHECK_EQUAL(mytree.get(E::MinusOne()), minusone);
+    BOOST_CHECK_EQUAL(mytree.get(E::MinusTwo()), minustwo);
 }
 
 BOOST_AUTO_TEST_CASE(get_test) {
-    testGet<int32_t>();
-    testGet<uint32_t>();
-    testGet<int64_t>();
-    testGet<uint64_t>();
+    testGet<TestElementInt<int32_t>>();
+    testGet<TestElementInt<uint32_t>>();
+    testGet<TestElementInt<int64_t>>();
+    testGet<TestElementInt<uint64_t>>();
+
+    testGet<TestElementUint256>();
 }
 
-template <typename K> void testRemove() {
-    using E = TestElement<K>;
+template <typename E> void testRemove() {
     RadixTree<E> mytree;
 
-    auto zero = RCUPtr<E>::make(0);
-    auto one = RCUPtr<E>::make(1);
-    auto two = RCUPtr<E>::make(2);
-    auto three = RCUPtr<E>::make(3);
+    auto keyZero = E::ToKey(0);
+    auto keyOne = E::ToKey(1);
+    auto keyTwo = E::ToKey(2);
+    auto keyThree = E::ToKey(3);
+
+    auto zero = RCUPtr<E>::make(keyZero);
+    auto one = RCUPtr<E>::make(keyOne);
+    auto two = RCUPtr<E>::make(keyTwo);
+    auto three = RCUPtr<E>::make(keyThree);
 
     // Removing an element that isn't in the tree returns false.
-    BOOST_CHECK(!mytree.remove(1));
+    BOOST_CHECK(!mytree.remove(keyOne));
 
     // Insert an element into the tree and check you can remove it.
     BOOST_CHECK(mytree.insert(one));
-    BOOST_CHECK(mytree.remove(1));
-    BOOST_CHECK_EQUAL(mytree.get(1), NULLPTR(E));
+    BOOST_CHECK(mytree.remove(keyOne));
+    BOOST_CHECK_EQUAL(mytree.get(keyOne), NULLPTR(E));
 
     // Insert several elements and remove them.
     BOOST_CHECK(mytree.insert(zero));
@@ -178,33 +247,27 @@
     BOOST_CHECK(mytree.insert(two));
     BOOST_CHECK(mytree.insert(three));
 
-    BOOST_CHECK(mytree.remove(0));
-    BOOST_CHECK(mytree.remove(1));
-    BOOST_CHECK(mytree.remove(2));
-    BOOST_CHECK(mytree.remove(3));
+    BOOST_CHECK(mytree.remove(keyZero));
+    BOOST_CHECK(mytree.remove(keyOne));
+    BOOST_CHECK(mytree.remove(keyTwo));
+    BOOST_CHECK(mytree.remove(keyThree));
 
-    BOOST_CHECK_EQUAL(mytree.get(0), NULLPTR(E));
-    BOOST_CHECK_EQUAL(mytree.get(1), NULLPTR(E));
-    BOOST_CHECK_EQUAL(mytree.get(2), NULLPTR(E));
-    BOOST_CHECK_EQUAL(mytree.get(3), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(keyZero), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(keyOne), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(keyTwo), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(keyThree), NULLPTR(E));
 
     // Once the elements are removed, removing them again returns false.
-    BOOST_CHECK(!mytree.remove(0));
-    BOOST_CHECK(!mytree.remove(1));
-    BOOST_CHECK(!mytree.remove(2));
-    BOOST_CHECK(!mytree.remove(3));
+    BOOST_CHECK(!mytree.remove(keyZero));
+    BOOST_CHECK(!mytree.remove(keyOne));
+    BOOST_CHECK(!mytree.remove(keyTwo));
+    BOOST_CHECK(!mytree.remove(keyThree));
 
     // Check extreme values.
-    using SK = typename std::make_signed<K>::type;
-    K maxsk = std::numeric_limits<SK>::max();
-    K minsk = std::numeric_limits<SK>::min();
-    using UK = typename std::make_unsigned<K>::type;
-    K maxuk = std::numeric_limits<UK>::max();
-
-    auto maxsigned = RCUPtr<E>::make(maxsk);
-    auto minsigned = RCUPtr<E>::make(minsk);
-    auto minusone = RCUPtr<E>::make(maxuk);
-    auto minustwo = RCUPtr<E>::make(maxuk - 1);
+    auto maxsigned = RCUPtr<E>::make(E::SignedMax());
+    auto minsigned = RCUPtr<E>::make(E::SignedMin());
+    auto minusone = RCUPtr<E>::make(E::MinusOne());
+    auto minustwo = RCUPtr<E>::make(E::MinusTwo());
 
     // Insert them all.
     BOOST_CHECK(mytree.insert(zero));
@@ -217,34 +280,36 @@
     BOOST_CHECK(mytree.insert(minustwo));
 
     // Delete them all
-    BOOST_CHECK(mytree.remove(0));
-    BOOST_CHECK(mytree.remove(1));
-    BOOST_CHECK(mytree.remove(2));
-    BOOST_CHECK(mytree.remove(3));
-    BOOST_CHECK(mytree.remove(maxsk));
-    BOOST_CHECK(mytree.remove(minsk));
-    BOOST_CHECK(mytree.remove(maxuk));
-    BOOST_CHECK(mytree.remove(maxuk - 1));
-
-    BOOST_CHECK_EQUAL(mytree.get(0), NULLPTR(E));
-    BOOST_CHECK_EQUAL(mytree.get(1), NULLPTR(E));
-    BOOST_CHECK_EQUAL(mytree.get(2), NULLPTR(E));
-    BOOST_CHECK_EQUAL(mytree.get(3), NULLPTR(E));
-    BOOST_CHECK_EQUAL(mytree.get(maxsk), NULLPTR(E));
-    BOOST_CHECK_EQUAL(mytree.get(minsk), NULLPTR(E));
-    BOOST_CHECK_EQUAL(mytree.get(maxuk), NULLPTR(E));
-    BOOST_CHECK_EQUAL(mytree.get(maxuk - 1), NULLPTR(E));
+    BOOST_CHECK(mytree.remove(keyZero));
+    BOOST_CHECK(mytree.remove(keyOne));
+    BOOST_CHECK(mytree.remove(keyTwo));
+    BOOST_CHECK(mytree.remove(keyThree));
+    BOOST_CHECK(mytree.remove(E::SignedMax()));
+    BOOST_CHECK(mytree.remove(E::SignedMin()));
+    BOOST_CHECK(mytree.remove(E::MinusOne()));
+    BOOST_CHECK(mytree.remove(E::MinusTwo()));
+
+    BOOST_CHECK_EQUAL(mytree.get(keyZero), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(keyOne), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(keyTwo), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(keyThree), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(E::SignedMax()), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(E::SignedMin()), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(E::MinusOne()), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(E::MinusTwo()), NULLPTR(E));
 }
 
 BOOST_AUTO_TEST_CASE(remove_test) {
-    testRemove<int32_t>();
-    testRemove<uint32_t>();
-    testRemove<int64_t>();
-    testRemove<uint64_t>();
+    testRemove<TestElementInt<int32_t>>();
+    testRemove<TestElementInt<uint32_t>>();
+    testRemove<TestElementInt<int64_t>>();
+    testRemove<TestElementInt<uint64_t>>();
+
+    testRemove<TestElementUint256>();
 }
 
 BOOST_AUTO_TEST_CASE(const_element_test) {
-    using C = const TestElement<uint64_t>;
+    using C = const TestElementInt<uint64_t>;
     RadixTree<C> mytree;
 
     BOOST_CHECK(mytree.insert(RCUPtr<C>::make(0)));
@@ -278,7 +343,7 @@
     BOOST_CHECK(!mytree.remove(3));
 }
 
-void CheckConstTree(const RadixTree<TestElement<uint64_t>> &mytree,
+void CheckConstTree(const RadixTree<TestElementInt<uint64_t>> &mytree,
                     bool expected) {
     BOOST_CHECK_EQUAL(!!mytree.get(0), expected);
     BOOST_CHECK_EQUAL(!!mytree.get(1), expected);
@@ -287,7 +352,7 @@
 }
 
 BOOST_AUTO_TEST_CASE(const_tree_test) {
-    using E = TestElement<uint64_t>;
+    using E = TestElementInt<uint64_t>;
     RadixTree<E> mytree;
 
     CheckConstTree(mytree, false);
@@ -308,7 +373,7 @@
 }
 
 BOOST_AUTO_TEST_CASE(test_cow) {
-    using E = TestElement<uint32_t>;
+    using E = TestElementInt<uint32_t>;
 
     RadixTree<E> mytree;
 
@@ -359,7 +424,7 @@
 }
 
 BOOST_AUTO_TEST_CASE(test_move) {
-    using E = TestElement<uint32_t>;
+    using E = TestElementInt<uint32_t>;
 
     RadixTree<E> mytree;
 
@@ -385,7 +450,7 @@
 #define ELEMENTS 65536
 
 BOOST_AUTO_TEST_CASE(insert_stress_test) {
-    using E = TestElement<uint32_t>;
+    using E = TestElementInt<uint32_t>;
 
     RadixTree<E> mytree;
     std::atomic<uint32_t> success{0};