I think you're misunderstanding Red's contention here.

If I understand correctly, it's not that proof of work is unnecessary if you want to reach consensus on transaction order without trusted bookkeepers.

Rather, it's that having trusted bookkeepers isn't so bad.