colored bitcoin tech discussion

[killerstorm]

Overview of 'colored bitcoin' concept and useful links are here: https://bitcointalk.org/index.php?topic=106373.0

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.

[hashman]

Interesting   If you don't like the blue ones send them my way.  Another possible metric of interest would be date of birth. 

If I have 1 bitcoin that was entirely created on Jan 25, 2009, it's DOB would be Jan 25, 2009.

More common of course would be that fractions of my coin are from different coinbase transactions.  In that case you would do a weighted average of each of the days involved, weighted by amount of coin.   

Some interesting statistics could develop from this analysis, such as DOB variance of transacted coins, etc. 

This kind of thing is interesting and could be useful but of course in the end one old blue coin is worth the same as a young red one. 

[killerstorm]

Are you joking, or your seriously do not understand the concept? (I hope you've read message I've referenced.)

Here's an example:

Let's say I'm an owner of a company XYZ and I want to sell its shares. I can sell those shares on GLBSE, then ownership of company is represented by some records in GLBSE's database. In this case I declare that whatever information GLBSE stores is legit.

OR I can declare that legal owners of company are ones who own bitcoins which can be traced to a 1 BTC transaction I've made, and each mBTC one owns represents a share equal to 1/1000 of a company.

Then I'll sell mBTCs derived from that transaction for a price way above 1 mBTC.

So, well, what's the difference between first approach and second approach? In second case we have company ownership which is totally transparent, secure and verifiable.

In same way one can introduce a private currency, i.e. one which is pegged to USD, for example. (It can work like Liberty Reserve, but better.)

[hashman]

Ah, no I hadn't understood.  Thanks.

That's a good idea.  I'll try to reiterate to see if I got it right. 

I could say that one bitcoin, history unimportant, represents interest in my private business venture.  One could then send out .01 from this input to different outputs for each of 100 shareholders.  Shareholders can verify their shares are legit by showing they own a piece of coin tracing back to this original coin. 

Nice idea, kind of like marked bills but with the advantages of bitcoin.  Just don't forget and go spend it at satoshi dice  

[killerstorm]

Shareholders can verify their shares are legit by showing they own a piece of coin tracing back to this original coin. 

Nice idea, kind of like marked bills but with the advantages of bitcoin.  Just don't forget and go spend it at satoshi dice  

Right. The client mod I'm developing would kinda 'lock' colored coins one owns making them unavailable for spending. To spend them one needs to switch to that color. But if company goes bankrupt, sending those coins to satoshi dice might be a right choice

[killerstorm]

I've identified following general approaches which can be used for coloring of transaction outputs:

1. Based on law of conservation, i.e. color mapping is valid when it preserves amounts of coins participating in transaction.
2. Based on ordering, i.e. color depends on ordering of outputs within a transaction.
3. Based on meta-info included in transaction. Say, colored outputs might have special meta-info embedded in script (e.g. OP_DROP message).

Law of conservation can work in some cases, e.g. if input is 3 red and 7 blue coins, and outputs are 7 X and 3 Y, then X = blue and Y = red.
However, there is potential ambiguity: if we have 5 red and 5 blue, we won't know how to color outputs.
Also, coloring might require exponential time.

There are possible workarounds, but I think none of them are practical except a combination of conservation law with ordering. (See below.)

Inclusion of meta-info obviously solves all ambiguities, but it might be problematic to implement and it adds bloat to the blockchain.

So here's how ordering-based approach can work. Basic idea is that we know order of colors in inputs, and we assume that outputs go in same order. (I.e. client software must create transactions involving colored bitcoins in this way). Let's start with a simple example:

Inputs: [1 red, 1 blue, 1 green]
Outputs: [1 X, 1 Y, 1 Z].

Obviously, X = red, Y = blue, Z = green.

Now a bit more complex example, where number of inputs and outputs do not match:

Inputs: [1 red, 1 red, 1 blue, 1 green]
Outputs: [2 X, 1 Y, 1 Z]

Again fairly obvious, two red inputs will be grouped together. Same works with situation reversed:

Inputs: [2 red, 1 blue, 1 green]
Outputs: [1 X, 1 Y, 1 Z, 1 W]

Inputs define ordering R->G->B. First output must be R, but we have 1 red coin left. So second output is red too, and the rest is trivial.

At this point we see a general algorithm: first go through inputs to find order of colors and compute total amount for each color.

Then we go through outputs in order having two state variables: current color and amount of coins of this color left. For each output we declare that it is of 'current color' and reduce amount of coins left by that output's amount. When amount goes to zero we go to next color. If we ever have negative amount, coloring is erroneous and we assume that all outputs are uncolored. (I.e. owner does not care about colors anymore.)

Fairly simple.

What's about uncolored coins? We want to pay fees with uncolored coins. To do that, we should include them in the end of transaction.

In case fee is paid, we will end up with positive amount left in the end, but this is not a problem because we have no more outputs to color and it won't confuse our algorithm. (Also, one can pay a fee with a colored coin: that color should just come last.)

Example:

Inputs: [1 red, 1 blue, 1 uncolored]
Outputs: [1 red, 1 blue, 0.95 uncolored]

Finally, suppose that we don't know about certain colors, i.e. we see those colors as uncolored. Is that a problem? No. Example:

Inputs: [1 uncolored, 1 uncolored, 1 red]
Outputs: [1 X, 1 Y, 1 Z]

X and Y will be uncolored, Z is red. We don't know whether X and Y are of same color or not, but we only care about red, and we can figure out red.

Note, however, that if client received coins of colors he is not aware of, he can get them all mixed up and thus spoiled. But then it's his own problem since he only removes potential value from himself.

[killerstorm]

I've found a couple of corner cases which make this rule problematic:

If we ever have negative amount, coloring is erroneous and we assume that all outputs are uncolored. (I.e. owner does not care about colors anymore.)

For example, suppose person only knows (and cares) about red coins, but he accidentally receives blue and green coins. (I.e. other clients are aware of this colors. Maybe they are not valuable.)

This person's client might construct a transaction like this (his client software thinks that green and blue are uncolored, so they go in the end):

Inputs: [1 red, 1 green, 1 blue]
Outputs: [1 X, 2 Y]

If clients who are aware of green and blue will simply find whole transaction erroneous and assume that all outputs are uncolored, person will lose red coins.

To avoid this unpleasant situation, we should replace it with a following rule:

If we ever have negative amount, we fuse all remaining inputs together and assume that this and all remaining outputs are uncolored.

With this rule, person can only accidentally uncolor coins he thought are uncolored anyway, but he will never lose coins which he thinks are colored because they go before all uncolored coins.

Note that more complex rule which preserves as much colored coins as possible can be constructed, but I'm not sure it's necessary. Basically, we need to recover from erroneous situation. E.g.

Inputs: [1 red, 1 green, 3 blue]
Outputs: [1 red, 2 X, 2 Y]

X will be uncolored since coins are mixed, but Y will be blue.

Change to rule is rather simple: if we encounter a negative amount, we switch to next color and increase amount left by this color's amount. We will mark only output which brought amount to negative as uncolored, i.e. only an output which spans several colors.

Another corner case is client unaware of green and blue coins creating a txn with non-adjacent colors, e.g.:

Inputs: [1 red, 1 green, 1 blue, 1 green]
Outputs [1 X, 1 Y, 1 Z, 1 W]

In this case simplest resolution is to assume that inputs are uncolored from the point where we've got a duplicated color. So in this example W is uncolored.

Again, there is an alternative rule which would preserve as much colors as possible (it will sum up only adjacent colors), but I'm not sure it's necessary since clearly such transactions are a result of misunderstanding.

Now I think all possible cases are covered.

[Jutarul]

I played around with the necessary rule sets to deduce the output color from the inputs colors.

A transaction conforming to colored bitcoins has to meet the following requirements:
1) always list colored inputs and outputs before any uncolored inputs and outputs
2) inputs with the same color have to be consecutive
3) the order of the color has to be the same in inputs and outputs
4) the coin value per color has to be preserved (same in input and output)
5) any mining fee has to be paid from uncolored bitcoins, which are listed last

If a transaction follows these conventions then the client can perform -what I call - "incomplete color validation":
A client will be able to correctly calculate the color of outputs, independent of the degree of color knowledge and the position of the color.

If a transaction does not meet these requirements it makes it generally impossible to correctly compute the output color assignment. (there are some exceptions).

I created some proof-of-concept code as a python script: (validate.py)
http://ubuntuone.com/2XbRs0kFL8A2v65QCq4KLY

and some artificial input transactions: (transactions.yaml)
http://ubuntuone.com/0nGM4g7uGDbkdhY2LAnkrQ

command line: python validate.py transactions.yaml

The code contains a validate function which is able to compute the output colors by exploiting the above rules.
The script also does some random color deletions which I used to test the stability of the procedure to a varying degree of color information.

So far it looks good. I guess we can settle on the above rule set and focus on tracing colors through the block chain.

[bitcon]

I call black. sorry, black is already taken- please choose a new coin color

[jgarzik]

JFYI, copying from another thread so everyone stays on the same page...

pybond will also be a colored coin implementation, with a subset of colored coins being distributed bonds.  Have a lot of networking boilerplate to write first; the basic design is simply following "rules for colored coins" and "atomic coin swapping" though.

P.S. My name for colored coins is "smartcoins."  Sexier, more marketing friendly name ;p

Other thread references:

Rules for colored coins - https://bitcointalk.org/index.php?topic=106449.msg1203918#msg1203918
Smart property - https://bitcointalk.org/index.php?topic=41550.0
Distributed bonds - https://bitcointalk.org/index.php?topic=92421.0
Atomic coin swapping - https://bitcointalk.org/index.php?topic=112007.0

On the wiki:

https://en.bitcoin.it/wiki/Smart_Property
https://en.bitcoin.it/wiki/Contracts

[ShireSilver]

I'm still not getting how this is better than an alt-chain with merged mining (like namecoin)? I'm admittedly not an expert on how the blockchain, alt-chains, and merged mining work; but that approach sounds more flexible and with fewer possibilities of screwing up the bitcoin blockchain. It also doesn't need all the bitcoin clients to be changed to account for handling colored coins.

Also, what if you want more colored coins than can be derived from one origin block? That is, how do you make more than 50btc worth of one color?

[Jutarul]

I'm still not getting how this is better than an alt-chain with merged mining (like namecoin)?

The benefit is that you use existing infrastructure to implement higher order functionality. The cryptocurrency provides network security and irreversibility, while a protocol on top of bitcoin implements contract or assignment logic.
It's like TCP and HTTP. TCP takes care of the network and handles the communication on the IP layer, while HTTP takes care of creating content which can be displayed...

Also, what if you want more colored coins than can be derived from one origin block? That is, how do you make more than 50btc worth of one color?

There are some ideas floating around on how to create either inflatable or non-inflatable "colors". Since the color protocol definition (or smart coin, or whatever you want to call it) is just meta-information, it basically depends on convention. E.g. if color is associated with all outputs which come from a specific BTC address you have an inflatable color. If color is associated with a specific output in a transaction incorporated into the blockchain at some point, you have a non-inflatable color.

It's thus knowledge build into the client software... not into bitcoin!

ADDENDUM: I should add that the concept of coloring is universal to cryptocurrency. Thus color could be denoted in BTC, LTC, PPC or whatever your favorite is... (however it is scoped to the particular blockchain)

[Peter Todd]

JFYI, copying from another thread so everyone stays on the same page...

pybond will also be a colored coin implementation, with a subset of colored coins being distributed bonds.  Have a lot of networking boilerplate to write first; the basic design is simply following "rules for colored coins" and "atomic coin swapping" though.

P.S. My name for colored coins is "smartcoins."  Sexier, more marketing friendly name ;p

"tinted coins"?

"tainted coins" is most accurate... if right out.

[killerstorm]

I'm still not getting how this is better than an alt-chain with merged mining (like namecoin)?

This would allow one to create a private currency/asset token with a few clicks in client software. Once you've issued these 'colored coin' tokens no maintenance is necessary.

There is no reason why we cannot carry millions or even billions of different kinds of tokens within one blockchain. When people do not transact, there is no information being sent or processed.

Merged mining is a different beast, there is a lot of friction.

I'm admittedly not an expert on how the blockchain, alt-chains, and merged mining work; but that approach sounds more flexible and with fewer possibilities of screwing up the bitcoin blockchain.

On the contrary: colored bicoins are bitcoins, transactions with them are indistinguishable from normal bitcoin transactions. There is no way it can screw the bitcoin blockchain.

OTOH merged mining has to embed its meta-info into blocks... It's literally about screwing with blockchain.

Also I'd say colored coins are more flexible... Although that depends on how you define flexibility.

It also doesn't need all the bitcoin clients to be changed to account for handling colored coins.

We do not need to change all clients. If you care about colored coins you need a special client which recognizes them. Otherwise you would see them as normal bitcoins.

Also, what if you want more colored coins than can be derived from one origin block? That is, how do you make more than 50btc worth of one color?

They are not derived from a block, they are derived from genesis transactions. Basically, you just need to notify people that coins you currently have are of a certain color.

[killerstorm]

P.S. My name for colored coins is "smartcoins."  Sexier, more marketing friendly name ;p

"tinted coins"?

"tainted coins" is most accurate... if right out.

Tainted coins is a different thing. Taint is supposed to be contagious: if tainted coin is mixed with non-tainted, the result is tainted.

If colored coin is mixed with uncolored, the result is uncolored.

I agree that "smartcoins" sounds much better, but term "colored coins" sort of makes sense during development: we can talk about coin's color, coloring algorithms etc. Term "color" isn't used for anything else, as far as I can tell, so it is unambiguous.

[killerstorm]

I created some proof-of-concept code as a python script: (validate.py)

Let's go back to discussion of coloring algorithms... Jutarul's implementation does not cover case I mentioned in second message, i.e. when sender has partial information, but receiver who does validation has complete. In that case validation fails, so sender loses coins he had even though they were used correctly.

I've implemented an algorithm which is both simpler and covers all cases I can imagine: it colors all coins which can be reliably colored, marking the rest as "uncolored".

Here's C++ proof-of-concept implementation: https://gist.github.com/3793725

Run an example embedded in code:

Code:

$ g++ -o color_demo colors.cpp
$ ./color_demo
inputs:
Color: 1 amount: 1
Color: 1 amount: 2
Color: 2 amount: 1
Color: 0 amount: 4
Outputs:
Color: -2 amount: 3
Color: -2 amount: 1
Color: -2 amount: 3
Coloring log:
State: color:-2, amount:0
Eating (c:1,a:1) to match (c:-2,a:3) 
State: color:1, amount:1
Eating (c:1,a:2) to match (c:-2,a:3) 
State: color:1, amount:0
Eating (c:2,a:1) to match (c:-2,a:1) 
State: color:2, amount:0
Eating (c:0,a:4) to match (c:-2,a:3) 
Outputs colored:
Color: 1 amount: 3
Color: 2 amount: 1
Color: 0 amount: 3

Run with your own inputs/outputs:

Code:

$ ./color_demo 1 <colors.txt

Sample colors.txt is included.

Now a bit of discussion:
We assume that colors of inputs and colors of outputs go in same order.
Algorithm tries to recover from situations with partial information as much as possible without backtracking.

The reason we do not do backtracking is that it is computationally expensive and totally unnecessary.
The reason we don't do it in a more strict way is that
1) there is no way partially recovery might hurt one; conservation rule isn't violated;
2) it might save somebody's ass, though
3) extra checks are unnecessary.

So we go through inputs and outputs in order, matching them.
We go through outputs one by one to find their colors.
While we do that, we go through inputs to match amounts of outputs, essentially eating enough inputs to cover sum of outputs so far.
We track color of inputs we have eaten. If we need  inputs of different colors to match ouput, that output gets assigned mixed" color, which is semantically same as uncolored.

Here is pseudo-code derived from actual C++ code, it lacks type information and has extra comments: https://gist.github.com/3793879

[killerstorm]

A viable alternative to order-based coloring is embedding meta-info into a scriptPubKey.
The most straightforward way to do this is OP_DROP message, but there is a rather elegant approach which uses already standard multisig transactions:

For each color issuer will create a keypair, and BOTH private and public key will be revealed in color definition.

Transactions with this color should have scriptPubKey which is 2-of-2 multisig with first pubkeyhash being pubkeyhash of color's keypair.

Thus to spend a colored coin one needs to sign transaction using color's private key.

Thus it is only possible to spend a colored coin when you've got its definition which includes private key.

This effectively prevents accidents when user would receive a colored coin by a color-unaware client, or before color definition is loaded. User won't be able to use (or even see?) this coin until he uses software which can handle it.

I think it's a cool feature, but still order-based weak coloring algorithm (OBWC) is superior because it doesn't limit what scriptPubKey one can use, so it's compatible with pretty much everything imaginable.

So I think it's better to use OBWC as a base and use multisig color tagging (MCT) as an additional safety measure.

There are, however, different opinions. Jutarul proposed to use color tagging without OBWC. I guess he'll tell us his part of the story...

Anyway, it looks like having multiple coloring algos would be a major PITA (I can show an example if somebody wants), so it's important to settle on some base algo. For example, we can adopt OBWC, all alternatives should be OBWC-compatible.

[misterbigg]

Let's say I'm an owner of a company XYZ and I want to sell its shares. I can sell those shares on GLBSE, then ownership of company is represented by some records in GLBSE's database. In this case I declare that whatever information GLBSE stores is legit.

When colored coins come up I always hear the example of shares / stock. But when it comes to securities, determining ownership and decentralizing the exchange is simply not an interesting problem, compared to the bigger problem of ensuring that the issuing company is trustworthy (which is more of a social problem rather than a technological one).

[jgarzik]

On the contrary: colored bicoins are bitcoins, transactions with them are indistinguishable from normal bitcoin transactions. There is no way it can screw the bitcoin blockchain.

OTOH merged mining has to embed its meta-info into blocks... It's literally about screwing with blockchain.

Not sure "screwing with the blockchain" is accurate or fair.

Merged mining is preferable to colored coins, because you do not bloat the blockchain with person-to-person property transfers.

However, colored coins offer the unique advantage of being automatically swapped for bitcoin payment.

It is a trade-off.  Merged mining is far more scalable, and many discussions about creating a "data chain" for timestamping have been discussed.

[jgarzik]

A viable alternative to order-based coloring is embedding meta-info into a scriptPubKey.
The most straightforward way to do this is OP_DROP message, but there is a rather elegant approach which uses already standard multisig transactions:

No, that is the opposite of elegant:  it adds blockchain bloat that is difficult to recognize or avoid or prune.