It doesn't seem like hashing the data fields reduces the problem to finding collisions. Say I hash 2 values. I can distribute these and say H1 corresponds to a '1', and H2 corresponds to '0'. Now, I can store 1 bit of arbitrary data per transaction. Of course, I can increase the amount of data per transaction by exponentially increasing my initial work (and the size of the lookup table). But given that transactions are cheep, I would not need to compute the complete rainbow table to make this practical, and you only need to do the hashing once.