Overview of 'colored bitcoin' concept and useful links are here: https://bitcointalksearch.org/topic/chromawallet-colored-coins-issue-and-trade-private-currenciesstocksbonds-106373
We introduce certain "color" of bitcoin (i.e. a label) by associating it with a certain transaction (or transaction output). I.e. transaction with hash X would be a genesis transaction for color Y. I assume that this information will be present in configuration files of client software in case use is interested in distinguishing color Y.
Then to check whether a transaction or transaction output is of color Y we need to find whether we can trace it back to the genesis transaction.
Coloring whole transactions is easy: transaction is of color Y if all of its inputs come from transactions of color Y. (With exception of genesis transaction.)
(Coins of color Y will turn into ordinary, uncolored bitcoins if they are mixed with anything but color Y. So essentially these coins are 'lost' w.r.t coloring.)
I've already implemented a proof of concept which implements this very simply coloring scheme. But it's not cool.
One thing, we do not want to pay transaction fees with colored bitcoins, so we need to allow mixing colored and noncolored bitcoins within one transaction. Simplest solution is to assume that all non-colored ones are spent as a fee and amount of colored ones is preserved.
But to make a decentralized exchange based on colored bitcoins we need to be able to have coins of different colors within one transaction without mixing them. I.e. we need an unambiguous coloring scheme which would preserve amounts of colored coins.
This is an open question. I have a number of ideas, though.
