padded order-based coloring

[Alex Mizrahi]

There are (at least) two problems with order-based coloring:

1. One needs to use many satoshis per unit to comply with anti-dust rules, which means that issuance of colored coins can be expensive.

2. Thin client which uses backward scan needs to scan many transactions to prove that output is uncolored.

Thus I propose a different scheme, 'padded order-based coloring' to be used instead.

Simple 'order-based coloring' will be considered 

As far as I know, we do not have any 'real' colored coins now, so we can simply forget about old 'order-based coloring'.

Here's a draft of the spec: 

https://github.com/bitcoinx/colored-coin-tools/wiki/colored_coins_intro#padded-order-based-coloring

This scheme was first proposed by Jeremy Spilman back in Spring, but it was a tad problematic under model we were using back then.

However, one genesis txout per color model allows us to use strict validation rules, and that makes padded order-based coloring straightforward.

I also considered a variation of it which was described by Piotr Kopeć, but I believe that extra complexity is unnecessary.

[Meni Rosenfeld]

There's something I don't understand. It looks like the analysis assumes only one color is represented in the tx, but if the tx is an atomic trade of several colors with different padding parameters, won't this mess up the allocation of intervals?

[Alex Mizrahi]

There's something I don't understand. It looks like the analysis assumes only one color is represented in the tx, but if the tx is an atomic trade of several colors with different padding parameters, won't this mess up the allocation of intervals?

Yes, colors are compatible with each other in this sense only if they have same padding parameter.

I expect that we can pick something reasonable (say, 10000) and make that the de-facto standard for everybody to use.

With padding being 10000 satoshi, at most 21 * 10^6 * 10^8 / 10 ^4 = 21 * 10 ^10 transaction outputs can exist. I think that's reasonable: 

 * it's neither too low (something like 30 transaction outputs for each person living now on Earth)

 * nor too high (if we assume that we need to keep 100 bytes per UTXO, whole UTXO set requires 210 TB at most)

However, it is possible to use colors with different padding parameters within one transaction: you have to send the exact amount, without change. That is, you first need to create an UTXO with the exact value you want to send, and use that UTXO as an input to atomic trade transaction.

This has slightly higher space overhead, so I'm not going to implement it, but it is theoretically possible.

[Meni Rosenfeld]

Eventually 10K satoshi will be worth something, and this could problems similar to those we discussed earlier.

Suppose a stock is divisible enough that 1 satoshi-share isn't worth much. I want to buy 1 share. The seller can't send me a share, he can send a coin that represents a share but can also be melted for 10K plain satoshis. So it's worth more than a share and I'll have to pay accordingly. And it's hard to figure out how much exactly, as it's either/or, so the value depends on the probability distribution of the share worth.

And it doesn't scale linearly. If I buy X shares then I get a coin which is either X shares or 10K plain satoshis - it's not worth X times as much as 1 share, and it's not even some linear function a+bX since it depends on the specific shape of the share value distribution. In these conditions you can't have an efficient market.

A proper way to handle multiple padding parameters (I'm not sure I follow your last suggestion) could mitigate this, as we could reduce the parameters to keep the metal value negligible. (There's still a problem with old colors).

All in all I liked the idea of padding at first but now I think it's just worse than a lower bound on amount of satoshi-shares that can be transferred, as then the value is at least linear.

--
You received this message because you are subscribed to a topic in the Google Groups "Colored coins (BitcoinX)" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/bitcoinX/-13VWOrkncA/unsubscribe.
To unsubscribe from this group and all its topics, send an email to bitcoinX+u...@googlegroups.com.
To post to this group, send email to bitc...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Alex Mizrahi]

Suppose a stock is divisible enough that 1 satoshi-share isn't worth much. I want to buy 1 share. The seller can't send me a share, he can send a coin that represents a share but can also be melted for 10K plain satoshis. So it's worth more than a share and I'll have to pay accordingly. And it's hard to figure out how much exactly, as it's either/or, so the value depends on the probability distribution of the share worth.

I think you're approaching this from the wrong end:  

 the value of padding shouldn't be considered a part of the value of shares.

It is more like the protocol requires you to lock a certain amount of bitcoins in a transaction output which holds shares. It is more like a security deposit in terms of accounting.

Suppose I want to buy 10 shares, with price of 10^5 satoshi each.

I also need to pay

 * 10^4 satoshi for padding 

 * 10^4 satoshi as a transaction fees.

 * 100 satoshi for share encoding

So I send a total of 

    10^7 + 2 * 10^4 + 100 satoshi = 10020100 satoshi.

Seller gets 10010100 satoshi.

I receive a colored output with 10100 satoshi in it.

The value of this output is 10100 satoshi + value of shares it represents.

Obviously, it is possible to design wallet software which will take this into account.

it might show total holding as:

    100 shares of Foo

    0.00010100 bitcoins locked to represent shares

    0.1234 bitcoins spendable

It isn't particularly weird because bitcoins might be locked for many different reasons.

Essentially, protocol forces me to buy a bit of bitcoins while I hold shares which are represented as colored coins, but i can sell those bitcoins when I'll sell shares.

I believe it is actually a good thing. 

A proper way to handle multiple padding parameters (I'm not sure I follow your last suggestion)

Well, suppose we are going to exchange 37 of Foo for 42 of Bar. Foo's padding parameter is 10000 and Bar's padding parameter is 1000.

We can make a transaction like this:

Inputs: [10037, 1042, 10000]

Outputs: [10037, 1042]

Both Foo and Bar are transferred correctly.

In order to make this transaction, owner of Foo has to create the output which has the exact amount first. Suppose he has an output with 77 foo, then he will create a transaction like this:

Inputs: [10077, 20000]

Outputs: [10037, 10040]

Owner of Bar will likely do the same.

So usually we need three transaction to do this trade, but total size of these transactions isn't 3x more than size of a normal trade transaction, because trade transaction doesn't have change outputs.

 

could mitigate this, as we could reduce the parameters to keep the metal value negligible. (There's still a problem with old colors).

I believe that a perfect asset management/decentralized exchange system cannot be constructed now.

Bitcoin comes with many limitations. For example, currently no more than 7 transactions can be confirmed per second.

So instead of trying to design a perfect system, we should design an upgradeable system, that is one which provides an easy path to migrate to something else in future.

So POBC only needs to be usable right now, we don't need to make it very future-proof.

And currently POBC has much fewer problems than OBC.

[Meni Rosenfeld]

Ok, I guess you have a point since colored outputs can be merged with excess padding ejected.

[Stefaan Ghysels]

Hey all,

I'm implementing the padded order based color definition. I'd like to know if all of the following examples are possible:

padding = 10000 (in all examples)

Example 1

input = [10001, 10005, 10001]

in_color = [None, "gold", None]

output = [10001,10003,10002,10001]

out_color = [None, "gold", "gold", None]

fee = 10000

Example 2

input = [10001,10003,10002,10001]

in_color = [None, 3x"gold", 2x"gold", None]

output = [10001,10005,30001]

out_color = [None, 5x"gold", None]

fee = 10000

• Does the last input always have be colorless? I think it would help a lot in order to fix tx fee and padding when more inputs than outputs.
• Can you combine one color together like I did here?

Example 3

input = [10001,10003,10002,10001]

in_color = [None, "gold", "soap", None]

output = [10001,10005,30001]

out_color = [None, None, None]

fee = 10000

• Does this mixing automatically create a new color? Or should this kind of tx get flagged as a genesis?
  out_color = [None, "Golden Soap", None]
• Or do the units get destroyed = never available again?
• Or should we mark this as an invalid color tx, so that the colors don't leave the input addresses.
• Does this new color scale? Example 
• from 3 gold + 2 soap = 5 golden soap.
• to 30 gold + 20 soap = 50 golden soap?

Op maandag 7 oktober 2013 02:31:59 UTC+2 schreef Alex Mizrahi:

[Alex Mizrahi]

I'm implementing the padded order based color definition. I'd like to know if all of the following examples are possible:

padding = 10000 (in all examples)

Example 1

input = [10001, 10005, 10001]

in_color = [None, "gold", None]

output = [10001,10003,10002,10001]

out_color = [None, "gold", "gold", None]

fee = 10000

No: it isn't a valid Bitcoin transaction, as sum of inputs needs to be >= sum of outputs.

If there were 50001 satoshi in the third input, the it is possible: 5 gold were split into 3 gold and 2 gold.

 

Example 2

input = [10001,10003,10002,10001]

in_color = [None, 3x"gold", 2x"gold", None]

output = [10001,10005,30001]

out_color = [None, 5x"gold", None]

fee = 10000

This one is valid.

 

• Does the last input always have be colorless?

No.

 

• I think it would help a lot in order to fix tx fee and padding when more inputs than outputs.

I don't see how it helps.

 

• Can you combine one color together like I did here?

Sure.

 

Example 3

input = [10001,10003,10002,10001]

in_color = [None, "gold", "soap", None]

output = [10001,10005,30001]

out_color = [None, None, None]

fee = 10000

This is impossible because color kernel is aware only of its own colorvalues.

If transaction has both "gold" and "soap" inputs, then client might first run gold color kernel:

in_color = [None, 3 "gold", None, None]

out_color = [None, None, None]

and then it might run "soap" color kernel:

in_color = [None,  None,  2 soap, None]

out_color = [None, None, None]

I say "might" because client considers has a list of colors which are possible for a particular address.

Suppose that the second output has an address which client associates with 'gold'.

It will run only gold color kernel to check whether it received gold.

But even if it is aware of soap, it doesn't need to run soap color kernel.

This is possible because each color is completely independent of all other colors.

It is actually possible that one output is both gold and soap. (In case with POBC, it is possible only if soap genesis txout has gold colorvalue, or if gold genesis had soap colorvalue.)

But if address is tagged as gold, it will simply ignore soap colorvalue.

  

• Or do the units get destroyed = never available again?

Yes, they are destroyed.

 

• Or should we mark this as an invalid color tx, so that the colors don't leave the input addresses.

Well, on this low level we just know that output has no colorvalues.

If this check is done before transaction is sent, client should do abort the process and display an error.

If it is already in blockchain, then we should assume that units were destroyed.

Basically, there is no difference between "units were destroyed" and "units never left the input address" on the low level, as it only knows that output is uncolored.

Higher levels can interpret this situation in different ways.

Say, an issuer might choose to send replacement colored coins if they were destroyed due to a bug in software.

[Stefaan Ghysels]

Darn, I messed up all TX fees. They should be in the inputs of course. Update with correct numbers:

Why doesn't google allow to edit posts -.-

padding = 10000 (in all examples)

Example 1

input = [10001, 10005, 30001]     

in_color = [None, "gold", None]

output = [10001,10003,10002,10001]

out_color = [None, "gold", "gold", None]

fee = 50007 - 40007 = 10000

Example 2

input = [10001,10003,10002,10001]

in_color = [None, 3x"gold", 2x"gold", None]

output = [10001,10005,10001]

out_color = [None, 5x"gold", None]

fee = 40007 - 30007 = 10000

Example 3

input = [10001,10003,10002,10001]

in_color = [None, "gold", "soap", None]

output = [10001,10005,10001]

out_color = [None, None, None]

fee = 40007 - 30007 = 10000

• 3 gold & 2 soap coins are destroyed in this transaction.
  
• This is how this transaction will be evaluated if it is seen in the blockchain.
  
• Your colored coin client should not allow this / clearly warn the user of the result.

This is currently in run_kernel of colordef.py:

if colored:
    colored = (in_colorstates[inp_index] != None)
...
if colored:
    out_colorstates.append((o.value, ''))
else:
    out_colorstates.append(None)

Where do you determine output color?

[Meni Rosenfeld]

As for editing posts - While Google has a nice forum-like interface for viewing posts, the interface with the Group is via emails. You can't edit already sent emails.

[Alex Mizrahi]

• This is how this transaction will be evaluated if it is seen in the blockchain.
  

Not just a blockchain... Colorvalues are defined as soon as transaction is concrete and all transactions it depends on are known. 

• Your colored coin client should not allow this / clearly warn the user of the result.

Yes.

 

Where do you determine output color?

ColorDefinition object implements a color kernel for one specific color, that is, it returns colorvalues for that color.

Then there is a ColorDataStore which records colorvalues for transactions we have scanned so far. Conceptually it should record tuples

 (color, txout, colorvalue)

Physically information is stored in SQLite database in form of tuples

 (color_id, txhash, outindex, value, label)

Label will allow us to implement non-scalar colorvalue types in future.

ColorDataBuilder objects are responsible for maintaining ColorDataStore. That is, they detect transactions which involve non-null colorvalues, run color kernel and store information into ColorDataStore.

For example, suppose there is a ColorDataBuilder for color 'gold'. 

Application makes a request: "Please make sure that all txouts of transactions in block B which have non-null 'gold' colorvalues are identified and stored in ColorDataStore".

To satisfy this request, ColorDataBuilder identifies all blocks which need to be scanned, then scans blocks one by one:

For each transaction in a block it checks whether transaction has any input with non-null 'gold' colorvalue, or whether transaction is 'special' (that is, is a genesis of gold).

For each such 'interesting' transaction it runs color_kernel via ColorDefinition.run_kernel.

Kernel gives it gold colorvalues for outputs, and it stores all non-null colorvalues in the store.

After this process was done for a block, application is able to get 'gold' colorvalue for each txout in this block.

E.g. suppose wallet detected a new unspent transaction output. It wants to know color of those coins. So it will first make sure that block was scanned by all relevant colorbuilders, and then will fetch all records for that transaction output from ColorDataStore.

If no records are returned then UTXO is uncolored (for our purposes).

If there is one record, then it is of that color identified by a record.

If there is more than one record... Well, it is possible if colors "overlap".

To avoid unpleasant situations like that (e.g. txout is both 'gold' and 'soap', and wallet doesn't know what is more valuable and how to treat it), wallet associates a set of colors with particular address.

So, basically, it just checks "is it gold?"/"what's it gold value?"

If it has no gold value then we just assume that this txout is uncolored.

OK, so in coloredcoinlib this mechanism is implemented via a number of classes:

https://github.com/bitcoinx/ngcccbase/blob/master/coloredcoinlib/colordata.py#L7

ThickColorData.get_colorstates(self, color_id_set, txhash, outindex)

returns colorvalues for particular txout for a set of colors.

Automatically makes sure that information is consistent.

So application just calls this method and it does the rest.

https://github.com/bitcoinx/ngcccbase/blob/master/coloredcoinlib/builder.py#L24

ColorDataBuilderManager.ensure_scanned_upto(self, color_id_set, block_height):

Makes sure that blockchain is scanned properly for a certain set of colors.

Automatically creates builders as necessary.

https://github.com/bitcoinx/ngcccbase/blob/master/coloredcoinlib/builder.py#L39

BasicColorDataBuilder.scan_tx(self, tx)

This function is called for each transaction of interest, it checks if there are non-null input colorvalues, runs color kernel if necessary and stores data in ColorDataStore

FullScanColorDataBuilder

makes sure that we scanned all blocks in question

https://github.com/bitcoinx/ngcccbase/blob/master/coloredcoinlib/store.py#L35

ColorDataStore

Note that we're going to refactor ColorDataBuilder, but idea stays the same.

Also, we're going to implement more efficient builders which won't need to scan whole blocks.

So let's go back to this:

ColorDefinition object implements a color kernel for one specific color, that is, it returns colorvalues for that color.

This allows us to decouple color kernel implementation from block scanning/traversal strategies.