The first budget black hole was a mere $540 million. That was in 1987 dollars, which is around $1.5 billion these days. It was in John Howard's tax policy, assembled by his shadow treasurer Jim Carlton and launched during the 1987 election. Paul Keating seized on it and tore Howard apart, because it really was a black hole -- Howard admitted it was an error by Carlton. His campaign never recovered.
Ever since, governments in election campaigns have been trying to replicate Keating's 1987 attack, and failing. Keating himself tried it again the following election and failed -- though it didn't stop him trying every election after that. It has become yet another pointless ritual of politics, like governments issuing demands about what opposition leaders "must do" the afternoon before a budget reply speech. The closest any government got was the Howard government after the 1996 election, when it confected the claim of an $8 billion "Beazley black hole" about the budget Labor had left the Coalition. It's true that the Keating government's budget forecasts were decidedly optimistic -- but both sides were aware of that and it suited both Howard and Keating in the lead-up to the election to ignore the fiscal reality.