Skip to content

Conversation

@hebasto
Copy link
Member

@hebasto hebasto commented Apr 25, 2025

This PR accommodates the deep recursion in the FindChallenges() function used in test/miniscript_tests.cpp.

Fixes #32341 (comment).

CI log: https://github.com/hebasto/bitcoin/actions/runs/14664806617/job/41156972137

This change accommodates the deep recursion in the `FindChallenges()`
function used in `test/miniscript_tests.cpp`.
@DrahtBot
Copy link
Contributor

DrahtBot commented Apr 25, 2025

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/32349.

Reviews

See the guideline for information on the review process.
A summary of reviews will appear here.

Conflicts

No conflicts as of last run.

target_link_options(core_interface INTERFACE
# Increase stack size to accommodate the deep recursion
# in the FindChallenges() function used in miniscript_tests.
$<$<CONFIG:Debug>:/STACK:2097152>
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Where does this reserve value come from?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Determined empirically—this value was found to be sufficient during testing.

@l0rinc
Copy link
Contributor

l0rinc commented Apr 25, 2025

I'm not against increasing the Windows stack depth, but the underlying problem may be that we're ignoring warnings such as misc-no-recursion, even when the fix is quite simple.

FindChallenges looks like a simple depth-first search, which should be straightforward to rewrite as an iterative walk:

diff --git a/src/test/miniscript_tests.cpp b/src/test/miniscript_tests.cpp
index f253562a2f..14ac44e2c6 100644
--- a/src/test/miniscript_tests.cpp
+++ b/src/test/miniscript_tests.cpp
@@ -323,6 +323,35 @@ std::set<Challenge> FindChallenges(const NodeRef& ref) {
     return chal;
 }
 
+std::set<Challenge> FindChallenges_no_recursion(const NodeRef& root)
+{
+    std::set<Challenge> chal;
+    std::vector<const Node*> stack;
+    stack.push_back(root.get());
+
+    while (!stack.empty()) {
+        const Node* ref{stack.back()};
+        stack.pop_back();
+
+        for (const auto& key : ref->keys) {
+            chal.emplace(ChallengeType::PK, ChallengeNumber(key));
+        }
+        switch (ref->fragment) {
+        case Fragment::OLDER: chal.emplace(ChallengeType::OLDER, ref->k); break;
+        case Fragment::AFTER: chal.emplace(ChallengeType::AFTER, ref->k); break;
+        case Fragment::SHA256: chal.emplace(ChallengeType::SHA256, ChallengeNumber(ref->data)); break;
+        case Fragment::RIPEMD160: chal.emplace(ChallengeType::RIPEMD160, ChallengeNumber(ref->data)); break;
+        case Fragment::HASH256: chal.emplace(ChallengeType::HASH256, ChallengeNumber(ref->data)); break;
+        case Fragment::HASH160: chal.emplace(ChallengeType::HASH160, ChallengeNumber(ref->data)); break;
+        default: break;
+        }
+        for (const auto& sub : ref->subs) {
+            stack.push_back(sub.get());
+        }
+    }
+    return chal;
+}
+
 //! The spk for this script under the given context. If it's a Taproot output also record the spend data.
 CScript ScriptPubKey(miniscript::MiniscriptContext ctx, const CScript& script, TaprootBuilder& builder)
 {
@@ -348,6 +377,8 @@ struct MiniScriptTest : BasicTestingSetup {
 void TestSatisfy(const KeyConverter& converter, const std::string& testcase, const NodeRef& node) {
     auto script = node->ToScript(converter);
     auto challenges = FindChallenges(node); // Find all challenges in the generated miniscript.
+    auto challenges_no_recursion = FindChallenges_no_recursion(node); // Find all challenges in the generated miniscript.
+    BOOST_CHECK(std::vector{challenges} == std::vector{challenges_no_recursion});
     std::vector<Challenge> challist(challenges.begin(), challenges.end());
     for (int iter = 0; iter < 3; ++iter) {
         std::shuffle(challist.begin(), challist.end(), m_rng);

@hebasto
Copy link
Member Author

hebasto commented Apr 25, 2025

I'm not against increasing the Windows stack depth, but the underlying problem may be that we're ignoring warnings such as misc-no-recursion, even when the fix is quite simple.

FindChallenges looks like a simple depth-first search, which should be straightforward to rewrite as an iterative walk:

diff --git a/src/test/miniscript_tests.cpp b/src/test/miniscript_tests.cpp
index f253562a2f..14ac44e2c6 100644
--- a/src/test/miniscript_tests.cpp
+++ b/src/test/miniscript_tests.cpp
@@ -323,6 +323,35 @@ std::set<Challenge> FindChallenges(const NodeRef& ref) {
     return chal;
 }
 
+std::set<Challenge> FindChallenges_no_recursion(const NodeRef& root)
+{
+    std::set<Challenge> chal;
+    std::vector<const Node*> stack;
+    stack.push_back(root.get());
+
+    while (!stack.empty()) {
+        const Node* ref{stack.back()};
+        stack.pop_back();
+
+        for (const auto& key : ref->keys) {
+            chal.emplace(ChallengeType::PK, ChallengeNumber(key));
+        }
+        switch (ref->fragment) {
+        case Fragment::OLDER: chal.emplace(ChallengeType::OLDER, ref->k); break;
+        case Fragment::AFTER: chal.emplace(ChallengeType::AFTER, ref->k); break;
+        case Fragment::SHA256: chal.emplace(ChallengeType::SHA256, ChallengeNumber(ref->data)); break;
+        case Fragment::RIPEMD160: chal.emplace(ChallengeType::RIPEMD160, ChallengeNumber(ref->data)); break;
+        case Fragment::HASH256: chal.emplace(ChallengeType::HASH256, ChallengeNumber(ref->data)); break;
+        case Fragment::HASH160: chal.emplace(ChallengeType::HASH160, ChallengeNumber(ref->data)); break;
+        default: break;
+        }
+        for (const auto& sub : ref->subs) {
+            stack.push_back(sub.get());
+        }
+    }
+    return chal;
+}
+
 //! The spk for this script under the given context. If it's a Taproot output also record the spend data.
 CScript ScriptPubKey(miniscript::MiniscriptContext ctx, const CScript& script, TaprootBuilder& builder)
 {
@@ -348,6 +377,8 @@ struct MiniScriptTest : BasicTestingSetup {
 void TestSatisfy(const KeyConverter& converter, const std::string& testcase, const NodeRef& node) {
     auto script = node->ToScript(converter);
     auto challenges = FindChallenges(node); // Find all challenges in the generated miniscript.
+    auto challenges_no_recursion = FindChallenges_no_recursion(node); // Find all challenges in the generated miniscript.
+    BOOST_CHECK(std::vector{challenges} == std::vector{challenges_no_recursion});
     std::vector<Challenge> challist(challenges.begin(), challenges.end());
     for (int iter = 0; iter < 3; ++iter) {
         std::shuffle(challist.begin(), challist.end(), m_rng);

cc @sipa @darosior

@darosior
Copy link
Member

That sounds sensible, can you open a PR with this patch and tag me?

@l0rinc
Copy link
Contributor

l0rinc commented Apr 25, 2025

Opened #32351 as an alternative fix, cc: @darosior

@hebasto
Copy link
Member Author

hebasto commented Apr 27, 2025

Closing in favour of #32351.

@hebasto hebasto closed this Apr 27, 2025
l0rinc added a commit to l0rinc/bitcoin that referenced this pull request Apr 28, 2025
The original recursive `FindChallenges` explores the Miniscript node tree using depth-first search. Specifically, it performs a pre-order traversal (processing the node's data, then recursively visiting children from left-to-right). This recursion uses the call stack, which can lead to stack overflows on platforms with limited stack space, particularly noticeable in Windows debug builds.

This change replaces the recursive implementation with an iterative version using an explicit stack. The iterative version also performs a depth-first search and processes the node's data before exploring children (preserving pre-order characteristics), although the children are explored in right-to-left order due to the LIFO nature of the explicit stack.
Critically, both versions collect challenges into a `std::set`, which automatically deduplicates and sorts elements. This ensures that not only the final result, but the actual state of the set at any equivalent point in traversal remains identical, despite the difference in insertion order.

This iterative approach is an alternative to increasing the default stack size (as proposed in bitcoin#32349) and directly addresses the stack overflow issue reported in bitcoin#32341 by avoiding deep recursion.

The change is done in two commits:
* add a new iterative `FindChallenges` method and rename the old method to `*_recursive` (to simplify removal in the next commit), asserting that its result matches the original;
* Remove the original recursive implementation.

This approach avoids needing to suppress `misc-no-recursion` warnings and provides a portable, low-risk fix.

Using a `std::set` is necessary for deduplication, matching the original function's behavior. An experiment using an `std::vector` showed duplicate challenges being added, confirming the need for the set:
Example failure with vector:
  Recursive (set):
    (6, 9070746)
    (6, 19532513)
    (6, 3343376967)
  Iterative (vector attempt):
    (6, 19532513)
    (6, 9070746)
    (6, 3343376967)
    (6, 9070746) // Duplicate

Co-authored-by: Hennadii Stepanov <32963518+hebasto@users.noreply.github.com>
achow101 added a commit that referenced this pull request Apr 29, 2025
…al iteration

7e8ef95 refactor: Fix Sonar rule `cpp:S4998` - avoid unique_ptr const& as parameter (Lőrinc)
e400ac5 refactor: simplify repeated comparisons in `FindChallenges` (Lőrinc)
f670836 test: remove old recursive `FindChallenges_recursive` implementation (Lőrinc)
b80d0bd test: avoid stack overflow in `FindChallenges` via manual iteration (Lőrinc)

Pull request description:

  `FindChallenges` explores the `Miniscript` node tree by going deep into the first child's subtree, then the second, and so on - effectively performing a pre-order Traversal (Depth-First Search) recursively, using the call stack which can result in stack overflows on Windows debug builds.

  This change replaces the recursive implementation with an iterative version using an explicit stack. The new implementation also performs a pre-order depth-first traversal, though it processes children in right-to-left order (rather than left-to-right) due to the LIFO nature of the stack. Since both versions store results in a `std::set`, which automatically sorts and deduplicates elements, the exact traversal order doesn't affect the final result.

  It is an alternative to increasing the Windows stack size, as proposed in #32349, and addresses the issue raised in #32341 by avoiding deep recursion altogether.

  The change is done in two commits:
  * add a new iterative `FindChallenges` method and rename the old method to `*_recursive` (to simplify the next commit where we remove it), asserting that its result matches the original;
  * remove the original recursive implementation.

  This approach avoids ignoring the `misc-no-recursion` warning as well.

  I tried modifying the new method to store results in a vector instead, but it demonstrated that the deduplication provided by `std::set` was necessary. One example showing the need for deduplication:

  Recursive (using set):
  ```
    (6, 9070746)
    (6, 19532513)
    (6, 3343376967)
  ```
  Iterative (using vector attempt):
  ```
    (6, 19532513)
    (6, 9070746)
    (6, 3343376967)
    (6, 9070746)  // Duplicate entry
  ```

  The performance of the test is the same as before, with the recursive method.

  Fixes #32341

ACKs for top commit:
  achow101:
    ACK 7e8ef95
  sipa:
    utACK 7e8ef95
  hodlinator:
    re-ACK 7e8ef95

Tree-SHA512: 9e52eff82a7d76f5d37e3b74c508f08e5fced5386dad504bed111b27ed2b529008a6dd12a5116f009609a94c7ee7ebe3e80a759dda55dd1cb3ae52078f65ec71
luke-jr pushed a commit to luke-jr/bitcoin that referenced this pull request Jun 6, 2025
The original recursive `FindChallenges` explores the Miniscript node tree using depth-first search. Specifically, it performs a pre-order traversal (processing the node's data, then recursively visiting children from left-to-right). This recursion uses the call stack, which can lead to stack overflows on platforms with limited stack space, particularly noticeable in Windows debug builds.

This change replaces the recursive implementation with an iterative version using an explicit stack. The iterative version also performs a depth-first search and processes the node's data before exploring children (preserving pre-order characteristics), although the children are explored in right-to-left order due to the LIFO nature of the explicit stack.
Critically, both versions collect challenges into a `std::set`, which automatically deduplicates and sorts elements. This ensures that not only the final result, but the actual state of the set at any equivalent point in traversal remains identical, despite the difference in insertion order.

This iterative approach is an alternative to increasing the default stack size (as proposed in bitcoin#32349) and directly addresses the stack overflow issue reported in bitcoin#32341 by avoiding deep recursion.

The change is done in two commits:
* add a new iterative `FindChallenges` method and rename the old method to `*_recursive` (to simplify removal in the next commit), asserting that its result matches the original;
* Remove the original recursive implementation.

This approach avoids needing to suppress `misc-no-recursion` warnings and provides a portable, low-risk fix.

Using a `std::set` is necessary for deduplication, matching the original function's behavior. An experiment using an `std::vector` showed duplicate challenges being added, confirming the need for the set:
Example failure with vector:
  Recursive (set):
    (6, 9070746)
    (6, 19532513)
    (6, 3343376967)
  Iterative (vector attempt):
    (6, 19532513)
    (6, 9070746)
    (6, 3343376967)
    (6, 9070746) // Duplicate

Co-authored-by: Hennadii Stepanov <32963518+hebasto@users.noreply.github.com>

Github-Pull: bitcoin#32351
Rebased-From: b80d0bd
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

ctest -C Debug fails on vs2022 (miniscript_tests (SEGFAULT))

5 participants