diff --git a/configure.ac b/configure.ac
--- a/configure.ac
+++ b/configure.ac
@@ -1309,7 +1309,7 @@
   AC_CONFIG_SUBDIRS([src/univalue])
 fi
 
-ac_configure_args="${ac_configure_args} --disable-shared --with-pic --with-bignum=no --enable-module-recovery --disable-jni"
+ac_configure_args="${ac_configure_args} --disable-shared --with-pic --with-bignum=no --enable-module-recovery --enable-module-multiset --disable-jni"
 AC_CONFIG_SUBDIRS([src/secp256k1])
 
 AC_OUTPUT
diff --git a/src/secp256k1/CMakeLists.txt b/src/secp256k1/CMakeLists.txt
--- a/src/secp256k1/CMakeLists.txt
+++ b/src/secp256k1/CMakeLists.txt
@@ -80,6 +80,13 @@
 	#TODO: ECDH benchmark
 endif()
 
+# MultiSet module
+option(SECP256K1_ENABLE_MODULE_MULTISET "Build libsecp256k1's MULTISET module" ON)
+if(SECP256K1_ENABLE_MODULE_MULTISET)
+	set(ENABLE_MODULE_ECDH 1)
+
+endif()
+
 # Generate the config
 configure_file(src/libsecp256k1-config.h.cmake.in src/libsecp256k1-config.h ESCAPE_QUOTES)
 target_compile_definitions(secp256k1 PRIVATE HAVE_CONFIG_H)
diff --git a/src/secp256k1/Makefile.am b/src/secp256k1/Makefile.am
--- a/src/secp256k1/Makefile.am
+++ b/src/secp256k1/Makefile.am
@@ -175,3 +175,8 @@
 if ENABLE_MODULE_RECOVERY
 include src/modules/recovery/Makefile.am.include
 endif
+
+if ENABLE_MODULE_MULTISET
+include src/modules/multiset/Makefile.am.include
+endif
+
diff --git a/src/secp256k1/configure.ac b/src/secp256k1/configure.ac
--- a/src/secp256k1/configure.ac
+++ b/src/secp256k1/configure.ac
@@ -129,6 +129,11 @@
     [enable_module_ecdh=$enableval],
     [enable_module_ecdh=no])
 
+AC_ARG_ENABLE(module_multiset,
+    AS_HELP_STRING([--enable-module-multiset],[enable multiset operations (experimental)]),
+    [enable_module_multiset=$enableval],
+    [enable_module_multiset=no])
+
 AC_ARG_ENABLE(module_recovery,
     AS_HELP_STRING([--enable-module-recovery],[enable ECDSA pubkey recovery module (default is no)]),
     [enable_module_recovery=$enableval],
@@ -431,6 +436,10 @@
   AC_DEFINE(ENABLE_MODULE_ECDH, 1, [Define this symbol to enable the ECDH module])
 fi
 
+if test x"$enable_module_multiset" = x"yes"; then
+  AC_DEFINE(ENABLE_MODULE_MULTISET, 1, [Define this symbol to enable the multiset module])
+fi
+
 if test x"$enable_module_recovery" = x"yes"; then
   AC_DEFINE(ENABLE_MODULE_RECOVERY, 1, [Define this symbol to enable the ECDSA pubkey recovery module])
 fi
@@ -480,6 +489,7 @@
 AM_CONDITIONAL([USE_BENCHMARK], [test x"$use_benchmark" = x"yes"])
 AM_CONDITIONAL([USE_ECMULT_STATIC_PRECOMPUTATION], [test x"$set_precomp" = x"yes"])
 AM_CONDITIONAL([ENABLE_MODULE_ECDH], [test x"$enable_module_ecdh" = x"yes"])
+AM_CONDITIONAL([ENABLE_MODULE_MULTISET], [test x"$enable_module_multiset" = x"yes"])
 AM_CONDITIONAL([ENABLE_MODULE_RECOVERY], [test x"$enable_module_recovery" = x"yes"])
 AM_CONDITIONAL([USE_JNI], [test x"$use_jni" == x"yes"])
 AM_CONDITIONAL([USE_EXTERNAL_ASM], [test x"$use_external_asm" = x"yes"])
diff --git a/src/secp256k1/include/secp256k1_multiset.h b/src/secp256k1/include/secp256k1_multiset.h
new file mode 100644
--- /dev/null
+++ b/src/secp256k1/include/secp256k1_multiset.h
@@ -0,0 +1,110 @@
+/**********************************************************************
+ * Copyright (c) 2017 Tomas van der Wansem                            *
+ * Distributed under the MIT software license, see the accompanying   *
+ * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
+ **********************************************************************/
+
+
+#ifndef _SECP256K1_MULTISET__
+# define _SECP256K1_MULTISET__
+
+# include "secp256k1.h"
+
+
+# ifdef __cplusplus
+extern "C" {
+# endif
+
+
+/** Opaque multiset; this is actually a group element **/
+typedef struct {
+    unsigned char d[96];
+} secp256k1_multiset;
+
+
+
+/** Initialize a multiset
+ *  The resulting multiset the multiset for no data elements
+ *
+ *  Returns: 1: success
+ *           0: invalid parameter
+ *  Args:    ctx:      pointer to a context object (cannot be NULL)
+ *  Out:     multiset: the resulting multiset
+ */
+SECP256K1_API int secp256k1_multiset_init(
+  const secp256k1_context* ctx,
+  secp256k1_multiset *multiset
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2);
+
+
+/** Adds an element to a multiset from single data element
+ *
+ *  Returns: 1: success
+ *           0: invalid parameter
+ *  Args:    ctx:      pointer to a context object (cannot be NULL)
+ *  Out:     multiset: the multiset to update
+ *  In:      input:    the data to add
+ *           inputLen: the size of the data to add
+ */
+SECP256K1_API int secp256k1_multiset_add(
+  const secp256k1_context* ctx,
+  secp256k1_multiset *multiset,
+  const unsigned char *input,
+  size_t inputLen
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3);
+
+/** Removes an element from a multiset
+ *
+ *  Returns: 1: success
+ *           0: invalid parameter
+ *  Args:    ctx:      pointer to a context object (cannot be NULL)
+ *  Out:     multiset: the multiset to update
+ *  In:      input:    the data to remove
+ *           inputLen: the size of the data to remove
+ */
+SECP256K1_API int secp256k1_multiset_remove(
+  const secp256k1_context* ctx,
+  secp256k1_multiset *multiset,
+  const unsigned char *input,
+  size_t inputLen
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3);
+
+
+
+/** Combines two multisets
+ *
+ *  Returns: 1: success
+ *           0: invalid parameter
+ *  Args:    ctx:      pointer to a context object (cannot be NULL)
+ *  In/Out:  multiset: the multiset to which the input must be added
+ *  In:      input:    the multiset to add
+ */
+SECP256K1_API int secp256k1_multiset_combine(
+  const secp256k1_context* ctx,
+  secp256k1_multiset *multiset,
+  const secp256k1_multiset *input
+
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3);
+
+
+/** Converts a multiset to a hash
+ *
+ *  Returns: 1: success
+ *           0: invalid parameter
+ *  Args:    ctx:      pointer to a context object (cannot be NULL)
+ *  Out:     hash:     the resulting 32-byte hash
+ *  In:      multiset: the multiset to hash
+ */
+SECP256K1_API int secp256k1_multiset_finalize(
+  const secp256k1_context* ctx,
+  unsigned char *resultHash,
+  const secp256k1_multiset *multiset
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3);
+
+
+
+# ifdef __cplusplus
+}
+# endif
+
+#endif
diff --git a/src/secp256k1/src/bench_multiset.c b/src/secp256k1/src/bench_multiset.c
new file mode 100644
--- /dev/null
+++ b/src/secp256k1/src/bench_multiset.c
@@ -0,0 +1,52 @@
+/**********************************************************************
+ * Copyright (c) 2017 Tomas van der Wansem                            *
+ * Distributed under the MIT software license, see the accompanying   *
+ * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
+ **********************************************************************/
+
+#include "include/secp256k1.h"
+#include "include/secp256k1_multiset.h"
+#include "util.h"
+#include "bench.h"
+
+secp256k1_context *ctx;
+
+#define UNUSED(x) (void)(x)
+
+void bench_multiset(void* arg) {
+    static int it=0;
+    unsigned n,m;
+    unsigned char result[32];
+    secp256k1_multiset multiset;
+
+    UNUSED(arg);
+    secp256k1_multiset_init(ctx, &multiset);
+
+    for (m=0; m < 300000; m++)
+    {
+        unsigned char buf[32*3];
+        secp256k1_multiset x;
+
+        for(n = 0; n < sizeof(buf); n++)
+            buf[n] = it++;
+
+        secp256k1_multiset_add(ctx, &x, buf, sizeof(buf));
+
+    }
+
+    secp256k1_multiset_finalize(ctx, result, &multiset);
+}
+
+void bench_multiset_setup(void* arg) {
+    UNUSED(arg);
+}
+
+int main(void) {
+
+    ctx = secp256k1_context_create(SECP256K1_CONTEXT_VERIFY);
+
+    run_benchmark("multiset", bench_multiset, bench_multiset_setup, NULL, NULL, 5, 1);
+
+    secp256k1_context_destroy(ctx);
+    return 0;
+}
diff --git a/src/secp256k1/src/modules/multiset/Makefile.am.include b/src/secp256k1/src/modules/multiset/Makefile.am.include
new file mode 100644
--- /dev/null
+++ b/src/secp256k1/src/modules/multiset/Makefile.am.include
@@ -0,0 +1,8 @@
+include_HEADERS += include/secp256k1_multiset.h
+noinst_HEADERS += src/modules/multiset/main_impl.h
+noinst_HEADERS += src/modules/multiset/tests_impl.h
+if USE_BENCHMARK
+noinst_PROGRAMS += bench_multiset
+bench_multiset_SOURCES = src/bench_multiset.c
+bench_multiset_LDADD = libsecp256k1.la $(SECP_LIBS) $(COMMON_LIB)
+endif
diff --git a/src/secp256k1/src/modules/multiset/README.md b/src/secp256k1/src/modules/multiset/README.md
new file mode 100644
--- /dev/null
+++ b/src/secp256k1/src/modules/multiset/README.md
@@ -0,0 +1,82 @@
+Secp256k1 multiset module
+=========================
+
+Abstract
+--------
+
+This module allows calculating a cryptographically secure hash for a
+set with the properties:
+
+* The order of the elements of the set does not effect the hash
+* Elements can be added to the set without recalculating the entire set
+
+Or mathematically, it is:
+
+* Commutative: H(a,b) = H(b,a)
+* Associative: H(H(a,b),c) = H(a,H(b,c))
+
+Hence it behaves similar to XORing the hashes of the individual elements, 
+but without the cryptographic weakness of XOR.
+
+Motivation
+----------
+
+The multiset can be used by cryptocurrencies to cheaply create and 
+maintain a commitment to the full UTXO set as proposed by Pieter Wiulle [1]
+
+It can also be used with a bucketed approach to enable cheap UTXO-proofs as
+proposed by Tomas van der Wansem [2]
+
+Usage
+-----
+
+    // Construct a multiset of (data1,data3)
+
+    unsigned char data1[100],data2[150],data3[175];
+    ...
+    secp256k1_multiset x,y;
+    secp256k1_multiset_init  (context, &x);
+
+    // add all 3 data elements
+    secp256k1_multiset_add(context, &y, data1, sizeof(data1));
+    secp256k1_multiset_add(context, &y, data2, sizeof(data2));
+    secp256k1_multiset_add(context, &y, data3, sizeof(data3));
+
+    // remove data2
+    secp256k1_multiset_remove(context, &y, data2, sizeof(data2));
+
+    // convert to hash
+    secp256k1_multiset_finalize(context, hashBuffer, &x);
+
+Algorithm
+---------
+
+Using Elliptic Curves as multisets is described in [4].
+
+This implementation uses trial-and-hash [3] to convert the hash into
+point on the secp256k1 curve which serves as multiset. The curve's 
+group operations are then used to add and remove multisets. 
+Associativity and Commutativity then follow.
+
+Security
+--------
+The hash is secure against collision attacks.
+
+The algorithm used is susceptible to timing attacks. Therefore it does
+not securely conceal the underlying data being hashed.
+
+For the purpose of UTXO commitments this is not relevant.
+
+Faster and constant time algorithms exists [4] but only for char-2 curves.
+
+References
+----------
+
+[1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014337.html
+
+[2] https://lists.linuxfoundation.org/pipermail/bitcoin-ml/2017-September/000240.html
+
+[3] https://eprint.iacr.org/2009/226.pdf
+
+[4] https://arxiv.org/pdf/1601.06502.pdf
+
diff --git a/src/secp256k1/src/modules/multiset/main_impl.h b/src/secp256k1/src/modules/multiset/main_impl.h
new file mode 100644
--- /dev/null
+++ b/src/secp256k1/src/modules/multiset/main_impl.h
@@ -0,0 +1,196 @@
+/**********************************************************************
+ * Copyright (c) 2017 Tomas van der Wansem                            *
+ * Distributed under the MIT software license, see the accompanying   *
+ * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
+ **********************************************************************/
+
+#ifndef _SECP256K1_MODULE_MULTISET_MAIN_
+#define _SECP256K1_MODULE_MULTISET_MAIN_
+
+
+#include "include/secp256k1_multiset.h"
+
+#include "hash.h"
+#include "field.h"
+#include "group.h"
+
+/** Converts a group element (Jacobian) to a multiset.
+ *  Requires the field elements to be normalized
+ *  Infinite uses special value, z = 0
+ */
+static void multiset_from_gej_var(secp256k1_multiset *target, const secp256k1_gej *input) {
+    if (input->infinity) {
+        memset(&target->d, 0, sizeof(target->d));
+    }
+    else {
+        secp256k1_fe_get_b32(target->d, &input->x);
+        secp256k1_fe_get_b32(target->d+32, &input->y);
+        secp256k1_fe_get_b32(target->d+64, &input->z);
+    }
+}
+
+/** Converts a multiset to group element (Jacobian)
+ *  Infinite uses special value, z = 0
+ */
+static void gej_from_multiset_var(secp256k1_gej *target,  const secp256k1_multiset *input) {
+    secp256k1_fe_set_b32(&target->x, input->d);
+    secp256k1_fe_set_b32(&target->y, input->d+32);
+    secp256k1_fe_set_b32(&target->z, input->d+64);
+
+    target->infinity = secp256k1_fe_is_zero(&target->z) ? 1 : 0;
+}
+
+/** Converts a data element to a group element (affine)
+ *
+ *  We use trial-and-rehash which is fast but non-constant time.
+ *  Though constant time algo's exist we are not concerned with timing attacks
+ *  as we make no attempt to hide the underlying data
+ *
+ *  Pass inverse=0 to generate the group element, or inverse=1 to generate its inverse
+ */
+static void ge_from_data_var(secp256k1_ge *target, const unsigned char *input, size_t inputLen, int inverse) {
+    secp256k1_sha256 hasher;
+    unsigned char buffer[8+32];
+    unsigned char trial[32];
+    uint64_t prefix;
+
+    /* Hash to buffer, leaving space for 8-byte prefix */
+    secp256k1_sha256_initialize(&hasher);
+    secp256k1_sha256_write(&hasher, input, inputLen);
+    secp256k1_sha256_finalize(&hasher, buffer+8);
+
+    /* Loop through trials, with 50% success per loop
+     * We can assume it ends within 2^64. */
+    for(prefix=0; 1; prefix++)
+    {
+        secp256k1_fe x;
+
+        /* Set prefix in little-endian */
+        buffer[0] = prefix & 0xFF;
+        buffer[1] = (prefix>>8) & 0xFF;
+        buffer[2] = (prefix>>16) & 0xFF;
+        buffer[3] = (prefix>>24) & 0xFF;
+        buffer[4] = (prefix>>32) & 0xFF;
+        buffer[5] = (prefix>>40) & 0xFF;
+        buffer[6] = (prefix>>48) & 0xFF;
+        buffer[7] = (prefix>>56) & 0xFF;
+
+        /* Hash to trial  */
+        secp256k1_sha256_initialize(&hasher);
+        secp256k1_sha256_write(&hasher, buffer, sizeof(buffer));
+        secp256k1_sha256_finalize(&hasher, trial);
+
+        if (!secp256k1_fe_set_b32(&x, trial)) {
+            continue;
+        }
+
+        /* We let y is even be the element and odd be its inverse */
+        if (!secp256k1_ge_set_xo_var(target, &x, inverse)) {
+            continue;
+        }
+
+        VERIFY_CHECK(secp256k1_ge_is_valid_var(target));
+        VERIFY_CHECK(!secp256k1_ge_is_infinity(target));
+        break;
+    }
+}
+
+/** Adds or removes a data element */
+static int multiset_add_remove(const secp256k1_context* ctx, secp256k1_multiset *multiset, const unsigned char *input, size_t inputLen, int remove) {
+    secp256k1_ge newelm;
+    secp256k1_gej source, target;
+
+    VERIFY_CHECK(ctx != NULL);
+    ARG_CHECK(multiset != NULL);
+    ARG_CHECK(input != NULL);
+
+    gej_from_multiset_var(&source, multiset);
+    ge_from_data_var(&newelm, input, inputLen, remove);
+
+    secp256k1_gej_add_ge_var(&target, &source, &newelm, NULL);
+
+    secp256k1_fe_normalize(&target.x);
+    secp256k1_fe_normalize(&target.y);
+    secp256k1_fe_normalize(&target.z);
+    multiset_from_gej_var(multiset, &target);
+
+    return 1;
+}
+
+/** Adds a data element to the multiset */
+int secp256k1_multiset_add(const secp256k1_context* ctx, secp256k1_multiset *multiset, const unsigned char *input, size_t inputLen) {
+    return multiset_add_remove(ctx, multiset, input, inputLen, 0);
+}
+
+/** Removes a data element from the multiset */
+int secp256k1_multiset_remove(const secp256k1_context* ctx, secp256k1_multiset *multiset, const unsigned char *input, size_t inputLen) {
+    return multiset_add_remove(ctx, multiset, input, inputLen, 1);
+}
+
+/** Adds input multiset to multiset */
+int secp256k1_multiset_combine(const secp256k1_context* ctx, secp256k1_multiset *multiset, const secp256k1_multiset *input) {
+    secp256k1_gej gej_multiset, gej_input, gej_result;
+
+    VERIFY_CHECK(ctx != NULL);
+    ARG_CHECK(multiset != NULL);
+    ARG_CHECK(input != NULL);
+
+    gej_from_multiset_var(&gej_multiset, multiset);
+    gej_from_multiset_var(&gej_input, input);
+
+    secp256k1_gej_add_var(&gej_result, &gej_multiset, &gej_input, NULL);
+
+    secp256k1_fe_normalize(&gej_result.x);
+    secp256k1_fe_normalize(&gej_result.y);
+    secp256k1_fe_normalize(&gej_result.z);
+    multiset_from_gej_var(multiset, &gej_result);
+
+    return 1;
+}
+
+/** Hash the multiset into resultHash */
+int secp256k1_multiset_finalize(const secp256k1_context* ctx, unsigned char *resultHash, const secp256k1_multiset *multiset) {
+    secp256k1_sha256 hasher;
+    unsigned char buffer[64];
+    secp256k1_gej gej;
+    secp256k1_ge ge;
+
+    VERIFY_CHECK(ctx != NULL);
+    ARG_CHECK(resultHash != NULL);
+    ARG_CHECK(multiset != NULL);
+
+    gej_from_multiset_var(&gej, multiset);
+    if (gej.infinity) {
+
+        memset(buffer, 0x00, sizeof(buffer));
+    } else {
+
+        /* we must normalize to affine first */
+        secp256k1_ge_set_gej(&ge, &gej);
+        secp256k1_fe_normalize(&ge.x);
+        secp256k1_fe_normalize(&ge.y);
+        secp256k1_fe_get_b32(buffer, &ge.x);
+        secp256k1_fe_get_b32(buffer+32, &ge.y);
+    }
+
+    secp256k1_sha256_initialize(&hasher);
+    secp256k1_sha256_write(&hasher, buffer, sizeof(buffer));
+    secp256k1_sha256_finalize(&hasher, resultHash);
+
+    return 1;
+}
+
+/** Inits the multiset with the constant for empty data,
+ *  represented by the Jacobian GE infinite
+ */
+int secp256k1_multiset_init(const secp256k1_context* ctx, secp256k1_multiset *multiset) {
+    const secp256k1_gej inf = SECP256K1_GEJ_CONST_INFINITY;
+
+    VERIFY_CHECK(ctx != NULL);
+
+    multiset_from_gej_var(multiset, &inf);
+
+    return 1;
+}
+
+#endif /* _SECP256K1_MODULE_MULTISET_MAIN_ */
diff --git a/src/secp256k1/src/modules/multiset/tests_impl.h b/src/secp256k1/src/modules/multiset/tests_impl.h
new file mode 100644
--- /dev/null
+++ b/src/secp256k1/src/modules/multiset/tests_impl.h
@@ -0,0 +1,322 @@
+/**********************************************************************
+ * Copyright (c) 2017 Tomas van der Wansem                            *
+ * Distributed under the MIT software license, see the accompanying   *
+ * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
+ **********************************************************************/
+
+#ifndef _SECP256K1_MODULE_MULTISET_TESTS_
+#define _SECP256K1_MODULE_MULTISET_TESTS_
+
+
+#include "include/secp256k1.h"
+#include "include/secp256k1_multiset.h"
+#include "util.h"
+#include "testrand.h"
+
+#define DATALEN   64*3
+#define DATACOUNT 100
+
+
+#define CHECK_EQUAL(a,b) { \
+    unsigned char hash1[32]; \
+    unsigned char hash2[32]; \
+    secp256k1_multiset_finalize(ctx, hash1, (a)); \
+    secp256k1_multiset_finalize(ctx, hash2, (b)); \
+    CHECK(memcmp(hash1,hash2,sizeof(hash1))==0); \
+}
+
+#define CHECK_NOTEQUAL(a,b) { \
+    unsigned char hash1[32]; \
+    unsigned char hash2[32]; \
+    secp256k1_multiset_finalize(ctx, hash1, (a)); \
+    secp256k1_multiset_finalize(ctx, hash2, (b)); \
+    CHECK(memcmp(hash1,hash2,sizeof(hash1))!=0); \
+}
+
+static unsigned char elements[DATACOUNT][DATALEN];
+
+/* Create random data */
+static void initdata(void) {
+    int n,m;
+    for(n=0; n < DATACOUNT; n++) {
+        for(m=0; m < DATALEN/4; m++) {
+            ((uint32_t*) elements[n])[m] = secp256k1_rand32();
+        }
+
+    }
+}
+
+void test_unordered(void) {
+
+    /* Check if multisets are uneffected by order */
+
+    secp256k1_multiset empty, r1,r2,r3;
+
+    secp256k1_multiset_init(ctx, &empty);
+    secp256k1_multiset_init(ctx, &r1);
+    secp256k1_multiset_init(ctx, &r2);
+    secp256k1_multiset_init(ctx, &r3);
+
+    secp256k1_multiset_add(ctx, &r1, elements[0], DATALEN);
+    secp256k1_multiset_add(ctx, &r2, elements[1], DATALEN);
+
+    CHECK_NOTEQUAL(&r1,&r2); /* M(0,1)!=M() */
+
+    secp256k1_multiset_add(ctx, &r1, elements[1], DATALEN);
+    secp256k1_multiset_add(ctx, &r2, elements[0], DATALEN);
+    CHECK_EQUAL(&r1,&r2); /* M(0,1)==M(1,0) */
+
+    secp256k1_multiset_init(ctx, &r1);
+    secp256k1_multiset_init(ctx, &r2);
+    secp256k1_multiset_init(ctx, &r3);
+
+    CHECK_EQUAL(&r1,&r2); /* M()==M() */
+
+    secp256k1_multiset_add(ctx, &r1, elements[0], DATALEN);
+    secp256k1_multiset_add(ctx, &r1, elements[1], DATALEN);
+    secp256k1_multiset_add(ctx, &r1, elements[2], DATALEN);
+
+    secp256k1_multiset_add(ctx, &r2, elements[2], DATALEN);
+    secp256k1_multiset_add(ctx, &r2, elements[0], DATALEN);
+    secp256k1_multiset_add(ctx, &r2, elements[1], DATALEN);
+
+    secp256k1_multiset_add(ctx, &r3, elements[1], DATALEN);
+    secp256k1_multiset_add(ctx, &r3, elements[0], DATALEN);
+    secp256k1_multiset_add(ctx, &r3, elements[2], DATALEN);
+
+    CHECK_EQUAL(&r1,&r2); /* M(0,1,2)==M(2,0,1) */
+    CHECK_EQUAL(&r1,&r3); /* M(0,1,2)==M(1,0,2) */
+
+
+    secp256k1_multiset_combine(ctx, &r3, &empty);
+    CHECK_EQUAL(&r1,&r3); /* M(1,0,2)+M()=M(0,1,2) */
+
+    secp256k1_multiset_combine(ctx, &r3, &r2);
+    CHECK_NOTEQUAL(&r1,&r3); /* M(1,0,2)+M(0,1,2)!=M(0,1,2) */
+
+}
+
+void test_combine(void) {
+
+    /* Testing if combining is effectively the same as adding the elements */
+
+    secp256k1_multiset empty, r1,r2,r3;
+
+    secp256k1_multiset_init(ctx, &empty);
+    secp256k1_multiset_init(ctx, &r1);
+    secp256k1_multiset_init(ctx, &r2);
+    secp256k1_multiset_init(ctx, &r3);
+
+    secp256k1_multiset_add(ctx, &r1, elements[0], DATALEN);
+    secp256k1_multiset_add(ctx, &r2, elements[1], DATALEN);
+    CHECK_NOTEQUAL(&r1,&r2); /* M(0) != M(1) */
+
+    secp256k1_multiset_add(ctx, &r1, elements[1], DATALEN);
+    secp256k1_multiset_add(ctx, &r2, elements[0], DATALEN);
+    CHECK_EQUAL(&r1,&r2); /* M(1,0) == M(0,1) */
+
+    secp256k1_multiset_init(ctx, &r1);
+    secp256k1_multiset_init(ctx, &r2);
+    secp256k1_multiset_init(ctx, &r3);
+
+    CHECK_EQUAL(&r1,&r2); /* M() == M() */
+
+    secp256k1_multiset_add(ctx, &r1, elements[0], DATALEN);
+    secp256k1_multiset_add(ctx, &r1, elements[1], DATALEN);
+    secp256k1_multiset_add(ctx, &r1, elements[2], DATALEN);
+
+    secp256k1_multiset_add(ctx, &r2, elements[2], DATALEN);
+    secp256k1_multiset_add(ctx, &r3, elements[0], DATALEN);
+    secp256k1_multiset_add(ctx, &r3, elements[1], DATALEN);
+    secp256k1_multiset_combine(ctx, &r2, &r3);
+    CHECK_EQUAL(&r1,&r2); /* M(0,1,2) == M(2)+M(0,1) */
+
+    secp256k1_multiset_init(ctx, &r2);
+    secp256k1_multiset_init(ctx, &r3);
+    secp256k1_multiset_add(ctx, &r2, elements[2], DATALEN);
+    secp256k1_multiset_add(ctx, &r2, elements[0], DATALEN);
+    secp256k1_multiset_add(ctx, &r3, elements[1], DATALEN);
+    secp256k1_multiset_combine(ctx, &r2, &r3);
+    CHECK_EQUAL(&r1,&r2); /* M(0,1,2) == M(2,0)+M(1) */
+
+    secp256k1_multiset_combine(ctx, &r2, &empty);
+    CHECK_EQUAL(&r1,&r2); /* M(0,1,2)+M() == M(0,1,2) */
+    secp256k1_multiset_combine(ctx, &r2, &r1);
+    CHECK_NOTEQUAL(&r1,&r2); /* M(0,1,2)+M(0,1,2) != M(0,1,2) */
+}
+
+
+void test_remove(void) {
+
+    /* Testing removal of elements */
+    secp256k1_multiset empty, r1,r2,r3;
+
+    secp256k1_multiset_init(ctx, &empty);
+    secp256k1_multiset_init(ctx, &r1);
+    secp256k1_multiset_init(ctx, &r2);
+    secp256k1_multiset_init(ctx, &r3);
+
+    CHECK_EQUAL(&r1,&r2); /* M()==M() */
+
+    secp256k1_multiset_add   (ctx, &r1, elements[0], DATALEN);
+    secp256k1_multiset_add   (ctx, &r1, elements[1], DATALEN);
+    secp256k1_multiset_add   (ctx, &r1, elements[3], DATALEN);
+    secp256k1_multiset_add   (ctx, &r1, elements[9], DATALEN);
+    secp256k1_multiset_add   (ctx, &r1, elements[8], DATALEN);
+
+    secp256k1_multiset_add   (ctx, &r2, elements[1], DATALEN);
+    secp256k1_multiset_add   (ctx, &r2, elements[9], DATALEN);
+    secp256k1_multiset_add   (ctx, &r2, elements[11], DATALEN);
+    secp256k1_multiset_add   (ctx, &r2, elements[10], DATALEN);
+    secp256k1_multiset_add   (ctx, &r2, elements[0], DATALEN);
+    secp256k1_multiset_remove(ctx, &r2, elements[10], DATALEN);
+    secp256k1_multiset_add   (ctx, &r2, elements[3], DATALEN);
+    secp256k1_multiset_add   (ctx, &r2, elements[8], DATALEN);
+    secp256k1_multiset_remove(ctx, &r2, elements[11], DATALEN);
+
+    secp256k1_multiset_add   (ctx, &r3, elements[9], DATALEN);
+    secp256k1_multiset_add   (ctx, &r3, elements[15], DATALEN);
+    secp256k1_multiset_add   (ctx, &r3, elements[15], DATALEN);
+    secp256k1_multiset_add   (ctx, &r3, elements[1], DATALEN);
+    secp256k1_multiset_add   (ctx, &r3, elements[9], DATALEN);
+    secp256k1_multiset_remove(ctx, &r3, elements[15], DATALEN);
+    secp256k1_multiset_add   (ctx, &r3, elements[0], DATALEN);
+    secp256k1_multiset_remove(ctx, &r3, elements[15], DATALEN);
+    secp256k1_multiset_remove(ctx, &r3, elements[9], DATALEN);
+    secp256k1_multiset_add   (ctx, &r3, elements[3], DATALEN);
+    secp256k1_multiset_add   (ctx, &r3, elements[8], DATALEN);
+
+    CHECK_EQUAL(&r1,&r2); /* M(0,1,3,9,8)==M(1,9,11,10,9,3,8)-M(10,11) */
+    CHECK_EQUAL(&r1,&r3); /* M(0,1,3,9,8)==M(9,15,15,1,9,0,3,8)-M(15,15,9) */
+    CHECK_NOTEQUAL(&r1,&empty); /* M(0,1,3,9,8)!=M() */
+
+    secp256k1_multiset_remove(ctx, &r3, elements[8], DATALEN);
+    CHECK_NOTEQUAL(&r1,&r3); /* M(0,1,3,9,8)-M(8)!=M(0,1,3,9,8) */
+
+    secp256k1_multiset_remove(ctx, &r2, elements[0], DATALEN);
+    secp256k1_multiset_remove(ctx, &r2, elements[9], DATALEN);
+    secp256k1_multiset_remove(ctx, &r2, elements[8], DATALEN);
+    secp256k1_multiset_remove(ctx, &r2, elements[1], DATALEN);
+    secp256k1_multiset_remove(ctx, &r2, elements[3], DATALEN);
+
+    CHECK_EQUAL(&r2,&empty); /* M(0,1,3,9,8)-M(0,1,3,9,8)==M() */
+}
+
+void test_duplicate(void) {
+
+    /* Test if the multiset properly handles duplicates */
+    secp256k1_multiset empty, r1,r2,r3;
+
+    secp256k1_multiset_init(ctx, &empty);
+    secp256k1_multiset_init(ctx, &r1);
+    secp256k1_multiset_init(ctx, &r2);
+    secp256k1_multiset_init(ctx, &r3);
+
+    secp256k1_multiset_add   (ctx, &r1, elements[0], DATALEN);
+    secp256k1_multiset_add   (ctx, &r1, elements[0], DATALEN);
+    secp256k1_multiset_add   (ctx, &r1, elements[1], DATALEN);
+    secp256k1_multiset_add   (ctx, &r1, elements[1], DATALEN);
+
+    secp256k1_multiset_add   (ctx, &r2, elements[0], DATALEN);
+    secp256k1_multiset_add   (ctx, &r2, elements[1], DATALEN);
+
+    CHECK_NOTEQUAL(&r1, &r2); /* M(0,0,1,1)!=M(0,1) */
+
+    secp256k1_multiset_add   (ctx, &r2, elements[0], DATALEN);
+    secp256k1_multiset_add   (ctx, &r2, elements[1], DATALEN);
+    CHECK_EQUAL(&r1, &r2); /* M(0,0,1,1)!=M(0,0,1,1) */
+
+    secp256k1_multiset_add   (ctx, &r1, elements[0], DATALEN);
+    secp256k1_multiset_add   (ctx, &r1, elements[1], DATALEN);
+    secp256k1_multiset_add   (ctx, &r3, elements[0], DATALEN);
+    secp256k1_multiset_add   (ctx, &r3, elements[1], DATALEN);
+
+    secp256k1_multiset_combine(ctx, &r2, &r3);
+    CHECK_EQUAL(&r1, &r2); /* M(0,0,0,1,1,1)!=M(0,0,1,1)+M(0,1) */
+}
+
+void test_empty(void) {
+
+    /* Test if empty set properties hold */
+
+    secp256k1_multiset empty, r1,r2;
+
+    secp256k1_multiset_init(ctx, &empty);
+    secp256k1_multiset_init(ctx, &r1);
+    secp256k1_multiset_init(ctx, &r2);
+
+    CHECK_EQUAL(&empty,&r1); /* M()==M() */
+
+    /* empty + empty = empty */
+    secp256k1_multiset_combine(ctx, &r1, &r2);
+    CHECK_EQUAL(&empty, &r1); /* M()+M()==M() */
+}
+
+void test_testvector(void) {
+    /* Tests known values from the specification */
+
+    const unsigned char d1[113] = {
+        0x98,0x20,0x51,0xfd,0x1e,0x4b,0xa7,0x44,0xbb,0xbe,0x68,0x0e,0x1f,0xee,0x14,0x67,0x7b,0xa1,0xa3,0xc3,0x54,0x0b,0xf7,0xb1,0xcd,0xb6,0x06,0xe8,0x57,0x23,0x3e,0x0e,
+        0x00,0x00,0x00,0x00,0x03,0x00,0xf2,0x05,0x2a,0x01,0x00,0x00,0x00,0x43,0x41,0x04,0x96,0xb5,0x38,0xe8,0x53,0x51,0x9c,0x72,0x6a,0x2c,0x91,0xe6,0x1e,0xc1,0x16,0x00,
+        0xae,0x13,0x90,0x81,0x3a,0x62,0x7c,0x66,0xfb,0x8b,0xe7,0x94,0x7b,0xe6,0x3c,0x52,0xda,0x75,0x89,0x37,0x95,0x15,0xd4,0xe0,0xa6,0x04,0xf8,0x14,0x17,0x81,0xe6,0x22,
+        0x94,0x72,0x11,0x66,0xbf,0x62,0x1e,0x73,0xa8,0x2c,0xbf,0x23,0x42,0xc8,0x58,0xee,0xac };
+
+    const unsigned char d2[113] = {
+        0xd5,0xfd,0xcc,0x54,0x1e,0x25,0xde,0x1c,0x7a,0x5a,0xdd,0xed,0xf2,0x48,0x58,0xb8,0xbb,0x66,0x5c,0x9f,0x36,0xef,0x74,0x4e,0xe4,0x2c,0x31,0x60,0x22,0xc9,0x0f,0x9b,
+        0x00,0x00,0x00,0x00,0x05,0x00,0xf2,0x05,0x2a,0x01,0x00,0x00,0x00,0x43,0x41,0x04,0x72,0x11,0xa8,0x24,0xf5,0x5b,0x50,0x52,0x28,0xe4,0xc3,0xd5,0x19,0x4c,0x1f,0xcf,
+        0xaa,0x15,0xa4,0x56,0xab,0xdf,0x37,0xf9,0xb9,0xd9,0x7a,0x40,0x40,0xaf,0xc0,0x73,0xde,0xe6,0xc8,0x90,0x64,0x98,0x4f,0x03,0x38,0x52,0x37,0xd9,0x21,0x67,0xc1,0x3e,
+        0x23,0x64,0x46,0xb4,0x17,0xab,0x79,0xa0,0xfc,0xae,0x41,0x2a,0xe3,0x31,0x6b,0x77,0xac };
+
+    const unsigned char d3[113] = {
+        0x44,0xf6,0x72,0x22,0x60,0x90,0xd8,0x5d,0xb9,0xa9,0xf2,0xfb,0xfe,0x5f,0x0f,0x96,0x09,0xb3,0x87,0xaf,0x7b,0xe5,0xb7,0xfb,0xb7,0xa1,0x76,0x7c,0x83,0x1c,0x9e,0x99,
+        0x00,0x00,0x00,0x00,0x09,0x00,0xf2,0x05,0x2a,0x01,0x00,0x00,0x00,0x43,0x41,0x04,0x94,0xb9,0xd3,0xe7,0x6c,0x5b,0x16,0x29,0xec,0xf9,0x7f,0xff,0x95,0xd7,0xa4,0xbb,
+        0xda,0xc8,0x7c,0xc2,0x60,0x99,0xad,0xa2,0x80,0x66,0xc6,0xff,0x1e,0xb9,0x19,0x12,0x23,0xcd,0x89,0x71,0x94,0xa0,0x8d,0x0c,0x27,0x26,0xc5,0x74,0x7f,0x1d,0xb4,0x9e,
+        0x8c,0xf9,0x0e,0x75,0xdc,0x3e,0x35,0x50,0xae,0x9b,0x30,0x08,0x6f,0x3c,0xd5,0xaa,0xac };
+
+    /* Expected resulting multisets */
+    const unsigned char exp_m1[32]     = { 0x5e,0x29,0x49,0x84,0xc0,0xb6,0xff,0x1c,0x89,0x7b,0xdb,0xb6,0xf7,0xcf,0x3e,0xf8,0x01,0xe2,0xf1,0x3b,0xc7,0x34,0x28,0xaa,0xcd,0xf8,0xcb,0x8d,0x3b,0xd2,0xf0,0xe5 };
+    const unsigned char exp_m2[32]     = { 0x93,0x70,0x80,0xb6,0x6c,0x2b,0x37,0x2d,0x35,0x39,0x88,0xd6,0xc0,0x92,0x22,0x78,0x8f,0x88,0xa5,0x13,0x0a,0x13,0x32,0xeb,0xc1,0x49,0x5a,0xa3,0xa7,0xfa,0xb4,0xfb };
+    const unsigned char exp_m3[32]     = { 0x70,0x2d,0x3b,0xe4,0x1a,0x0d,0xcf,0xba,0x9a,0x48,0x21,0x15,0x86,0x4c,0x42,0x80,0x55,0xc6,0x52,0x0c,0x61,0x72,0xa9,0x4b,0x14,0xaa,0x2c,0x2e,0xc0,0x09,0x4c,0xd9 };
+    const unsigned char exp_m1m2[32]   = { 0x48,0x09,0x8f,0x4c,0xa9,0xbb,0x5d,0xac,0x27,0x3e,0x56,0x31,0x6d,0xb6,0x41,0x23,0x69,0xed,0x1f,0xa8,0xbe,0xb5,0x79,0x57,0x05,0x32,0xd1,0x63,0x47,0xfe,0xfc,0xcc };
+    const unsigned char exp_m1m2m3[32] = { 0x41,0x1c,0xaf,0xe7,0x4b,0x66,0xd1,0xb7,0x9a,0xe4,0x1e,0x63,0x2e,0x0d,0xe1,0xa3,0xb7,0x41,0x9a,0x25,0xdb,0xf0,0xa6,0x6a,0x1f,0x3b,0x4d,0x6e,0xb6,0xdc,0xc3,0xd2 };
+
+    unsigned char m1[32],m2[32],m3[32],m1m2[32],m1m2m3[32];
+    secp256k1_multiset r1,r2,r3;
+
+    secp256k1_multiset_init(ctx, &r1);
+    secp256k1_multiset_init(ctx, &r2);
+    secp256k1_multiset_init(ctx, &r3);
+
+    secp256k1_multiset_add    (ctx, &r1, d1, sizeof(d1));
+    secp256k1_multiset_add    (ctx, &r2, d2, sizeof(d2));
+    secp256k1_multiset_add    (ctx, &r3, d3, sizeof(d3));
+
+    secp256k1_multiset_finalize(ctx, m1, &r1);
+    secp256k1_multiset_finalize(ctx, m2, &r2);
+    secp256k1_multiset_finalize(ctx, m3, &r3);
+
+    secp256k1_multiset_combine(ctx, &r1, &r2);
+    secp256k1_multiset_finalize(ctx, m1m2, &r1);
+
+    secp256k1_multiset_combine(ctx, &r1, &r3);
+    secp256k1_multiset_finalize(ctx, m1m2m3, &r1);
+
+    CHECK(memcmp(m1,exp_m1,32)==0);
+    CHECK(memcmp(m2,exp_m2,32)==0);
+    CHECK(memcmp(m3,exp_m3,32)==0);
+    CHECK(memcmp(m1m2,exp_m1m2,32)==0);
+    CHECK(memcmp(m1m2m3,exp_m1m2m3,32)==0);
+}
+
+void run_multiset_tests(void) {
+
+    initdata();
+    test_unordered();
+    test_combine();
+    test_remove();
+    test_empty();
+    test_duplicate();
+    test_testvector();
+}
+
+#endif /* _SECP256K1_MODULE_MULTISET_TESTS_ */
diff --git a/src/secp256k1/src/secp256k1.c b/src/secp256k1/src/secp256k1.c
--- a/src/secp256k1/src/secp256k1.c
+++ b/src/secp256k1/src/secp256k1.c
@@ -579,6 +579,10 @@
 # include "modules/ecdh/main_impl.h"
 #endif
 
+#ifdef ENABLE_MODULE_MULTISET
+# include "modules/multiset/main_impl.h"
+#endif
+
 #ifdef ENABLE_MODULE_RECOVERY
 # include "modules/recovery/main_impl.h"
 #endif
diff --git a/src/secp256k1/src/tests.c b/src/secp256k1/src/tests.c
--- a/src/secp256k1/src/tests.c
+++ b/src/secp256k1/src/tests.c
@@ -4403,6 +4403,10 @@
 # include "modules/ecdh/tests_impl.h"
 #endif
 
+#ifdef ENABLE_MODULE_MULTISET
+# include "modules/multiset/tests_impl.h"
+#endif
+
 #ifdef ENABLE_MODULE_RECOVERY
 # include "modules/recovery/tests_impl.h"
 #endif
@@ -4520,6 +4524,10 @@
     run_ecdsa_openssl();
 #endif
 
+#ifdef ENABLE_MODULE_MULTISET
+    run_multiset_tests();
+#endif
+
 #ifdef ENABLE_MODULE_RECOVERY
     /* ECDSA pubkey recovery tests */
     run_recovery_tests();