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.
Comments
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.