How many external interrupts has attiny85?
There's INT0, and then there's PCINT[0:5].  INT0 gets its own interrupt routine, and the PCINT has one routine for all the pins configured to be used by the interrupt.  That means that one of the first thing the interrupt routine needs to do is figure out which pin(s) actually changed to trigger the interrupt.  Should actually be more convenient to use this way for your encoder, as you really want any encoder change to trigger the same interrupt routine.

I have no idea if all this is accessibile through the arduino platform, or if you need to program the controller yourself (as I'm not an Arduino user).