Contributing to Bitcoin Core: Coin selection, patience, and getting started

Ben Woosley, a.k.a. Empact, has been a contributor to Bitcoin Core since 2018, and a member of the Unchained Capital engineering team since 2021.

In the spirit of open source development, what follows is a story of one Bitcoin Core contribution of mine, how it came to be, from its beginnings in 2018, to finally being merged in 2022. Along the way, I hope you’ll learn a bit about the practicalities and vagaries of contributing to Bitcoin Core, and software development generally—ultimately, to help you toward the inclusion of an improvement or contribution of your own.

Contributing to Core: The need for code review

There are two main avenues for contributing to the Bitcoin Core development process:

1. reviewing the pull requests that are open for consideration, and
2. proposing changes to improve the codebase, i.e. opening pull requests of your own.

At the moment I’m writing this, there are some 400 pull requests open, each providing a perspective on how Core might be improved. This is an indication that the desire to contribute code is relatively abundant, but the time and attention to review is more limited. So of these two avenues above, this Core contributor among others will tell you that Bitcoin Core’s most significant, abiding, and serious need, is for more qualified attention and review of pull requests.

In choosing the path of code review, the task is not necessarily to pass judgment on a PR, that it be right or wrong for inclusion in the codebase. You can instead adopt an adversarial or optimizing perspective, and look for any issue with, or opportunity for improvement of, the code put forward. In doing so, you can help make each PR as good as it can be, and leave the judgments to others. You can help every pull request be the best possible version of itself.

A recent contribution

The pull request I’ll describe today, #13226, took the path of code review. In reviewing pull requests, I came across #13167, which proposed several optimizations to SelectCoinsBnB, Core’s implementation of Murch’s branch and bound coin selection algorithm, originally developed for his Master’s Thesis.

The proposed changes were motivated by performance improvement, and I found there were some interesting ideas therein. But there’s often a natural tension in development, between the efficient piece of code, and the most succinct and expressive. In this case I was uneasy with the proposed trade-offs—I found the new code to be somewhat less legible. The importance of readability is particularly elevated in a complex, highly secure system like Bitcoin Core, where readability supports the ability of reviewers to identify issues and make improvements.

Secondly, one of the optimizations was to look up values without bounds-checking, which may be unnecessary in the code as written, but code under development is a continuously changing system, so it’s sometimes beneficial to take the so-called “belt-and-suspenders” approach of redundant protections, so as not to be caught with your pants down. When and where this is appropriate is a matter of subjective and contextual analysis, but I was wary of applying it in this case.

In reviewing, I was inquiring into my wariness, and asking myself whether the change represented an improvement on balance. In doing so, I was looking into the code under consideration, to make sense of the interactions, whereby I noticed a fourth opportunity to optimize the code—one which would leave the checks in place and simplify it in the process, thus removing the tension that I was feeling between these two considerations.

Specifically, I found it interesting that the curr_selection and best_selection, the core accounting objects of the search, were represented as an array of booleans, which were to hold true for UTXOs to be included, and false for those to be excluded. This meant that information was recorded for every UTXO under consideration, even those which are bound to be excluded—rather than positively say: do the following, the objects said included these, and also don’t include the inverse of these.

In context, this particularly seemed incongruous: In the common case of coin selection, optimizations tend toward minimizing the number of UTXOs selected from a possibly large number of UTXOs—and that is just considering the ultimately selected set. In a search algorithm like Branch and Bound, many combinations of UTXOs are considered, and every one of these combinations can repeatedly consider and pass over many UTXOs in order to produce the result.

So, by defining these objects in a way that spoke only in positive terms, we could avoid unnecessary accounting of the passed over UTXOs, and at the same time simplify the codebase by eliminating the negative paths. I went about implementing this, and found that it improved performance significantly.

Suggesting improvements to pull requests

The most common way to offer up an improvement to a pull request is to comment with your suggestion, but there are some cases where possibility rises above the realm of a comment. For example, if the change you have in mind is significant, it may be more difficult to articulate in full than it is to implement it in code.

Thanks to the decentralized nature of Git, it’s extremely easy to offer up feedback in the form of publishing a branch that builds upon the pull request branch. This enables the author of the pull request to consider your suggestions, and if they approve, to cherry-pick them into their branch and thus into the pull request. I’ve used this approach to good effect in Bitcoin Core, and it nicely comports with the tools and philosophy of open source development.

In this case, however, I was putting forward an entirely different approach, which was independent of the original pull request, so it made sense for it to be an independent pull request. So I opened a pull request with the note: “This is prompted by #13167 and presented as a friendly alternative to it.” to help reviewers understand the context of the PR.

Getting your contribution across the finish line

One of the interesting, some might say notorious, aspects of Bitcoin Core development is that it can be difficult to know what is likely to be merged, or when. Pull request inclusion depends on the independent and subjective analysis of the many reviewers and few maintainers of the Bitcoin Core codebase. Whether something gets attention, and when, is one of the vagaries of Core development.

Participate in meetings and request review

There are a few ways to make a pull request more attractive to review—the most notable and explicit is by participating in the Core Development meetings, and putting forward your pull request for the High-priority for review list. This will naturally draw more attention, and increase the amount of feedback you receive.

Another is to ask for review explicitly from people who have a particular interest in the code in question. In my case, the most relevant figure was Murch, given the role he played in articulating and implementing the algorithm in question. You can do this directly from the “Reviewers” sidebar of your pull request, or through some other medium.

Maintaining a pull request under review

In addition to responding to review, an important duty of anyone submitting a PR is to keep it in a state that is ready to merge, with a green test suite, and without any conflicts with the base branch. On the latter point, any other merge could introduce a conflict, so the need to rebase a PR could come up at any time. Just know that merging and reviewing are less likely to occur when a PR is in an unready state.

Be patient

One of the reasons my pull request took 4 years to be merged is that, after one year of review and refinement (and some silence), I became pessimistic about its inclusion, and decided to close the PR. It sat closed for two years, until I met with Murch at a conference and we got to talking about it as a possibility. He encouraged me to put it forward and so I did.

The lesson for me, and for you, is not to assume that something is unwanted simply because it hasn’t garnered attention, sometimes you will have to bring it to the attention of others in order to get the feedback you desire.

From the time of re-opening the PR, it took an additional year of review and refinement before finally being merged. While this is a while, it’s a matter of multiple rounds of people finding time to review the PR, and its author accommodating the feedback.

Get started

I hope this brief story gave you a bit better understanding of the work that goes into Bitcoin Core, and how you might participate in it yourself. This was far from the easiest pull request of my Core contribution experience—and though the amount of time required to merge was more than expected, the effort I put in over the timespan was modest.

To any developer with an interest in improving or protecting Bitcoin Core: first and foremost, review the outstanding pull requests of others. Bitcoin Core depends on robust review to prevent accidental or intentional corruption of the codebase. While it can be difficult to know what is likely to be merged or when, participation, maintenance, and patience will help your work be noticed, reviewed, and eventually included.