Since no one more knowledgeable has come along, I'll go ahead and put together an answer.
Based on the recipe, it looks like you're actually intended to make your own black bean sauce using fermented black beans, or douchi. It seems that Chinese douchi are made and known as "hamanatto" in Japan as well. Searching online, there are retailers that you could purchase Japanese dried hamanatto from, but I have not done so myself. It looks like that would be the best direct substitute for douchi.
As a substitution for the resulting black bean sauce, I would personally recommend Korean chunjang. Chunjang, which also translates to black bean paste, is the major flavoring component in Jjajang sauce in Korea, and you can even find Jjajang (or "chajang") sauce premade.
I have Lee Kum Kee brand Chinese black bean sauce on hand as well as Assi brand Korean chunjang, so my mother and I did a small taste test (and included some other bean sauces, like doubanjiang, akamiso, and some zhajiang I prepared a while back.) We agreed that we of the options we had on hand, Korean chunjang would be the best substitution for a Mongolian beef recipe we love that also calls for Chinese black bean sauce if we ran out.
The black bean sauces were both predominantly salty, with some pleasant bitterness to them and a little sweetness. The Lee Kum Kee reminded me a little of bitter chocolate, but it was very mild. The chunjang on the other hand was much more aggressive all around, which makes sense since it's a paste rather than a prepared sauce. The bitterness and sweetness were both stronger, and it also had more acidity. It was also saltier, being more concentrated, but the other flavors seemed stronger proportionately. I might describe it as a little smoky, rather than chocolatey, which makes sense if black caramel color is added. But other than the acidity we both detected in the chunjang, the flavors were very similar. Both are complex flavors and can't be fully described, but while certainly different, I think chunjang would work well in a pinch, potentially with some extra salt, to taste.
My only other suggestion would be to look into fermenting your own douchi. You can buy black soy beans online, and you should also be able to purchase an aspergillus starter. It seems the basic process is to inoculate the steamed black soybeans with the aspergillus spores to create koji. After a week, the koji is washed (to remove bitterness), then dried and combined with salt (I saw references to a 15% brine as well as 15% salt by weight.) and then aged for several weeks or months. Again, I have not done this myself, and would recommend doing significantly more research before attempting. But based on what I've read it should be quite doable.