From 6732fc7fde22d37a78318d350baaeb1c03158fab Mon Sep 17 00:00:00 2001 From: naughtyfox Date: Mon, 12 Nov 2018 20:46:00 +0300 Subject: Fix issue 4793 - M/N multisig transaction signature --- src/common/CMakeLists.txt | 6 ++- src/common/combinator.cpp | 50 ++++++++++++++++++++++++ src/common/combinator.h | 96 +++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 150 insertions(+), 2 deletions(-) create mode 100644 src/common/combinator.cpp create mode 100644 src/common/combinator.h (limited to 'src/common') diff --git a/src/common/CMakeLists.txt b/src/common/CMakeLists.txt index aed9bfee7..3045c003c 100644 --- a/src/common/CMakeLists.txt +++ b/src/common/CMakeLists.txt @@ -43,7 +43,8 @@ set(common_sources spawn.cpp threadpool.cpp updates.cpp - aligned.c) + aligned.c + combinator.cpp) if (STACK_TRACE) list(APPEND common_sources stack_trace.cpp) @@ -77,7 +78,8 @@ set(common_private_headers stack_trace.h threadpool.h updates.h - aligned.h) + aligned.h + combinator.h) monero_private_headers(common ${common_private_headers}) diff --git a/src/common/combinator.cpp b/src/common/combinator.cpp new file mode 100644 index 000000000..cb4fbc908 --- /dev/null +++ b/src/common/combinator.cpp @@ -0,0 +1,50 @@ +// Copyright (c) 2018, The Monero Project +// +// All rights reserved. +// +// Redistribution and use in source and binary forms, with or without modification, are +// permitted provided that the following conditions are met: +// +// 1. Redistributions of source code must retain the above copyright notice, this list of +// conditions and the following disclaimer. +// +// 2. Redistributions in binary form must reproduce the above copyright notice, this list +// of conditions and the following disclaimer in the documentation and/or other +// materials provided with the distribution. +// +// 3. Neither the name of the copyright holder nor the names of its contributors may be +// used to endorse or promote products derived from this software without specific +// prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY +// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF +// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL +// THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, +// STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF +// THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +// +// Parts of this file are originally copyright (c) 2012-2013 The Cryptonote developers + +#include "combinator.h" + +namespace tools { + +uint64_t combinations_count(uint32_t k, uint32_t n) +{ + if (k > n) { + throw std::runtime_error("k must not be greater than n"); + } + + uint64_t c = 1; + for (uint64_t i = 1; i <= k; ++i) { + c *= n--; + c /= i; + } + + return c; +} + +} diff --git a/src/common/combinator.h b/src/common/combinator.h new file mode 100644 index 000000000..72c6800d5 --- /dev/null +++ b/src/common/combinator.h @@ -0,0 +1,96 @@ +// Copyright (c) 2018, The Monero Project +// +// All rights reserved. +// +// Redistribution and use in source and binary forms, with or without modification, are +// permitted provided that the following conditions are met: +// +// 1. Redistributions of source code must retain the above copyright notice, this list of +// conditions and the following disclaimer. +// +// 2. Redistributions in binary form must reproduce the above copyright notice, this list +// of conditions and the following disclaimer in the documentation and/or other +// materials provided with the distribution. +// +// 3. Neither the name of the copyright holder nor the names of its contributors may be +// used to endorse or promote products derived from this software without specific +// prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY +// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF +// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL +// THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, +// STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF +// THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +// +// Parts of this file are originally copyright (c) 2012-2013 The Cryptonote developers + +#pragma once + +#include +#include + +namespace tools { + +uint64_t combinations_count(uint32_t k, uint32_t n); + +template +class Combinator { +public: + Combinator(const std::vector& v) : origin(v) { } + + std::vector> combine(size_t k); + +private: + void doCombine(size_t from, size_t k); + + std::vector origin; + std::vector> combinations; + std::vector current; +}; + +template +std::vector> Combinator::combine(size_t k) +{ + if (k > origin.size()) + { + throw std::runtime_error("k must be smaller than elements number"); + } + + if (k == 0) + { + throw std::runtime_error("k must be greater than zero"); + } + + combinations.clear(); + doCombine(0, k); + return combinations; +} + +template +void Combinator::doCombine(size_t from, size_t k) +{ + current.push_back(0); + + for (size_t i = from; i <= origin.size() - k; ++i) + { + current.back() = i; + + if (k > 1) { + doCombine(i + 1, k - 1); + } else { + std::vector comb; + for (auto ind: current) { + comb.push_back(origin[ind]); + } + combinations.push_back(comb); + } + } + + current.pop_back(); +} + +} //namespace tools -- cgit v1.2.3