The anatto reference is very interesting, but from the details I found on Wikipedia, I doubt that there was any in the Brazilian sauce. It wasn't spicy as such, except maybe a hint of chili which might have actually been green peppers (aka bell peppers?).
But there there might very well be some anatto in that secret Protuguese prego sauce, which is very spicy. Or maybe Larry's Dend Oil. I must try and find these somewhere.
I'm not certain at all that there were carrots in the Brazilian paste .. but in taste it was very much like an intensely rich vegetable stock with a very healthy dose of garlic. In this paste, there was no oil. And it lasted for ages in the fridge .. it was still in perfect shape when we finished it more than 6 months later!
The intense flavour and longevity of it suggested to me that fermentation might have been part of the process, but my flatmate couldn't confirm this. I tried to duplicate it by blending as finely as possible some garlic, celery, carrots, and salt. But it was nowhere close to the original! Even when it "fermented"