color kernel design considerations

[Alex Mizrahi]

We can classify parametrized color kernels (informally called 'coloring schemes') according to several different aspects:

I. How quantities (colorvalues) are encoded:

1. Using 'satoshi' value of outputs (svalue), particularly:

  a) directly proportional, i.e. just `svalue` (used in simple order-based coloring)

  b) `svalue - padding` (POBC)

  c) `svalue * q` where q is calculated according to some rule for each transaction

  d) `(svalue - padding) * q`

  e) more complex rules involving svalue

2. Colorvalues are not related to satoshi values of outputs, they can be encoded as data attached to a transaction, for example, in OP_RETURN output

II. How colored coin target outputs are chosen:

1. Order-based coloring matches inputs and outputs according to their order.

2. Outputs have special 'tags' which either specify their color or related inputs.

3. Inputs specify which outputs they have as targets.

4. Target outputs are specified in a separate piece of data (OP_RETURN)

Vitalik Buterin outlined criteria for evaluation of color kernels: simplicity, backward scanning, non-restrictiveness, atomic tradeability, efficiency, space efficiency.

It is pretty much impossible to go through all possible coloring schemes, so it's better to describe requirements and construct ones which fit them:

1. Colorvalue encoding: Since "anti-dust rules" are in effect, if we use svalue, we need padding for efficient encoding, and it should be updateable since Bitcoin price changes a lot.

    Alternatively, we can use scheme which doesn't use svalues to encode colorvalues.

2. Using output scripts for tagging or colorvalue encoding creates a number of problems: 1) use of non-standard scripts is discouraged; 2) space efficiency suffers; 3) creates compatibility problems with advanced scripts. So we should avoid it if possible.

Requirement 1 creates problems for schemes based on order-based coloring: in theory, they can be used with variable padding and q factor, but backward scan becomes complex.

Requirement 2 rules out output tagging.

Thus we are left with two options:

1. target outputs are encoded in input's nSequence field (32 bits)

2. target outputs are encoded in a separate piece of data (OP_RETURN)

Both options are viable, but the first option has better space efficiency (but, worse satoshi-efficiency) and doesn't require OP_RETURN, and thus can be used right now.

Also it might be better for 'simplicity' reason, although that is arguable.

Let's consider this option in more detail: each input has a 32-bit field called nSequence, 32-bit integer used for transaction replacement semantics.

This replacement semantics is disabled  now and thus this field is unused, any value can be used there.

We can use these 32-bits to define which outputs colored coins from certain input go to, and, possibly, padding and q parameters.

It was first described by Peter Todd, in his version 32 bits are used as a bit field to specify outputs certain input is connected to. In Peter's version q is of form 2^n and can be found by according to a law of conservation.

Unfortunately, Peter's version restricts us to 32 colored outputs per transaction, and lack of padding means that efficiency can be bad, despite 2^n factor.

In the next message I'll describe a different version which fixes these issues.

However, I'd like to see comments on coloring schemes in general: Did I miss something in my analysis?

I haven't considered the other viable option -- encoding everything in data, i.e. OP_RETURN outputs -- in detail.

It can excel in all aspects except space efficiency, and I'm not sure if we are allowed to use more than one OP_RETURN output per transaction, which would make it very restrictive.

If we aren't restricted in this way, we could try to achieve relatively good space efficiency through various optimization tricks, like bit-level encoding, compression etc.

It is an interesting topic, perhaps somebody wants to discuss it in more detail, or even try to construct such encoding scheme.

NGCCC can be a good platform for experiments as it allows one to develop a color kernel in isolation and simply plug it in.

[Alex Mizrahi]

Two additional design considerations I did not mention:

I. Ability to create partial colored transactions.

Currently p2ptrade requires at least 3 steps (note that ChromaWallet's p2ptrade uses 4 steps):

1. Alice posts her offer which includes txins she has. 

2. Bob posts a transaction which has both his and Alice's txins, with Bob's txins signed

3. Alice signs her txins, thus making a complete transaction, which is then  published on the Bitcoin network

This means that parties need a two-way communication channel to be able to make a full transaction, which is inconvenient in several ways: both parties need to be online, it is prone to DoS and spam attacks, etc.

2-step p2ptrade process could look like that:

1. Alice post her offer in form of a partial transaction which has her txins and txouts. It is already signed by Alice.

2. Bob completes the transaction by adding his txins/txouts and signs it. Now he can publish a complete transaction on the Bitcoin network.

This opens many possibilities such as offline trading: Alice can shut down her computer after she posted a partial transaction, Bob can complete it without her involvement.

Sadly, it doesn't seem to be possible as Alice needs to be able to specify a condition like "I pay you X coins of color A if you pay me Y coins of color B" in her partial transaction, but Bitcoin doesn't enforce conditions like that, so it cannot work.

Except in case when Alice wants to sell her colored coins for Bitcoin. In that case colored coin validity is no longer a question (Alice knows that her inputs/outputs are valid), Alice just needs to create a transaction which lacks certain amount of bitcoins.

Then Bob completes the transaction by adding txins which adds this amount of bitcoins, and now he has a complete transaction which suits both Alice and Bob.

However, this seems to be impossible with classic order-based coloring, but it might be possible in with other coloring schemes.

E.g. suppose a scheme where outputs are tagged is being used.

In that case Alice creates a transaction with one input and one output:

input_0: 1 colored coin from Alice

output_0: 1 bitcoin to Alice

Bob sees Alice's transaction and adds:

input_1: 1 bitcoin from Bob

output_1: 1 colored coin to Bob (has color tag)

Alice can sign her inputs with flags SIGHASH_ANYONECANPAY | SIGHASH_SINGLE which would allow Bob to add txins/txouts without invalidating her signature. It doesn't matter what Bob adds: transaction is valid only if Alice is paid 1 bitcoin.

II. Peer to peer coin mixing, aka CoinJoin: 

Peter Todd wrote that the only coloring scheme which is compatible with CoinJoin is one which specifies target outputs in input nSequence field: https://bitcointalk.org/index.php?topic=106373.msg4190061#msg4190061

I disagree with him: it doesn't really matter if CoinJoin is colored coin-aware, and it needs to be colored coin-aware:

https://bitcointalk.org/index.php?topic=106373.msg4209433#msg4209433

But, perhaps, there is some difference, and we should take this CoinJoin-compatibility into account.

[Yoni Johnathan Assia]

It seems that :

2. target outputs are encoded in a separate piece of data (OP_RETURN)

Is the approach the bitcoin devs are taking smart property, I think it makes sense to plan on it as 0.9 is coming out soon.

Can you explain why nSeq is better in terms of space efficiency ? The OP_Return has 80 bytes allocated in any case.

--
You received this message because you are subscribed to the Google Groups "Colored coins (BitcoinX)" group.
To unsubscribe from this group and stop receiving emails from it, 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]

2. target outputs are encoded in a separate piece of data (OP_RETURN)

Is the approach the bitcoin devs are taking smart property, I think it makes sense to plan on it as 0.9 is coming out soon.

No, it's just what they recommend in case one needs to add data to a transaction, instead of other, more wasteful approaches.

Nobody says we have to use it to implement smart property.

Can you explain why nSeq is better in terms of space efficiency ?

It doesn't require any extra bytes because nSequence is present in each input no matter whether we use it or not.

0 bytes is less than non-zero bytes. 

The OP_Return has 80 bytes allocated in any case.

Yes, up to 80 bytes, it isn't enough for longer transactions.

Say, if we need 16 bytes per output, it would limit us to 5 colored outputs... Not cool.

Of course, we could compress it into fewer bytes, or use multiple OP_RETURN outputs per transaction if that is allowed.

[Flavien]

Regarding I:

I'm not a fan of non-linear options (padding). Once a color is defined, there is no way to change the padding later. If the price of BTC goes up a lot, coins of that color become prohibitively expensive to exchange because of the padding.

If you want a future-proof solution, you can't use padding.

If you want a large amount of very granular units, it's going to be expensive to issue. That's how the real world works. If the government wants to mint 1 trillion dollars in 1 cent coins, that's going to take a lot of copper. If you want to issue colored coins on a budget, you either issue fewer of them, or make them less granular.

 

Padding is unnatural and introduced unnecessary complexity.

 

Regarding II:

There is another option you didn't mention. Have a marker OP_RETURN output, which indicates this is a colored transaction (With a constant value in it - just a few bytes), and use order based coloring.

Backwards scanning then becomes trivial, because you can stop the backwards scanning whenever you hit a non-marked transaction, since you know those outputs are uncolored.

Using nSequence is imperfect because this field could one day become used.

[Alex Mizrahi]

I'm not a fan of non-linear options (padding).

It's the only way to achieve high 'satoshi-efficiency'.

 

Once a color is defined, there is no way to change the padding later.

Wrong. It can be specified on per-transaction level.

ITOG coloring lets one to choose padding for each output group independently.

 

If the price of BTC goes up a lot, coins of that color become prohibitively expensive to exchange because of the padding.

Yes, that's why variable padding is important.

 

That's how the real world works.

I understand that linear relationship makes account simpler, but it is already prohibitively expensive.

We are working with digital assets, so divisibility shouldn't be a problem. If it is a problem, then our system is flawed.

 

There is another option you didn't mention. Have a marker OP_RETURN output, which indicates this is a colored transaction (With a constant value in it - just a few bytes), and use order based coloring.

Backwards scanning then becomes trivial, because you can stop the backwards scanning whenever you hit a non-marked transaction, since you know those outputs are uncolored.

I didn't mention it because it doesn't satisfy requirements: currently we have to use about 10000 satoshi per unit, it is prohibitively expensive. 

 

Using nSequence is imperfect because this field could one day become used.

It is already associated with certain semantics, and we know that it won't bother us even if it will be enabled again.

[Flavien]

It's the only way to achieve high 'satoshi-efficiency'.

 

Correct, and I am challenging the assumption that satoshi-efficiency should be a goal.

 

Satoshi-efficiency is Bitcoin's problem, not colored coin's problem. Today the dust rule is a temporary measure that improves scalability at the cost of that efficiency, Bitcoin devs put it in place and it's now Bitcoin devs' job to find a more long-term solution. A natural improvement would be to deincentivize small outputs through fees, without outright banning them, and let the free market do its job.

 

We shouldn't devise a complex scheme to work around a problem that may no longer be here in a year's time.

 

Also, padding is supposed to facilitate transactions with small amounts, yet if you want to send 1 colored satoshi, with padding, you still have to pay a padding of 10,000 uncolored satoshis, which defeats the purpose.

 

I didn't mention it because it doesn't satisfy requirements: currently we have to use about 10000 satoshi per unit, it is prohibitively expensive. 

 

Not sure what you're talking about, this is independent from the padding/no-padding satoshi-efficiency question.

 

It is already associated with certain semantics, and we know that it won't bother us even if it will be enabled again.

 

Well with the option I proposed (and that you didn't read it seems), you can achieve the same as nSequence-based coloring without having to take a dependency on the nSequence field.

[Gideon Greenspan]

I am trying to understand why there is any debate about using the OP_RETURN <=80 bytes for colored transactions. The purpose of these bytes is to allow extra data to be attached to bitcoin transactions, and this is exactly what colored coins need. Once bitcoin 0.9 forms the majority of the network I think there is likely to be a big race to find the best applications for this extra information. To find X which completes: X is to bitcoin as the web is to the Internet. Why not X = colored coins?

And if we use these 80 bytes, why not a simple scheme for moving colors from inputs to outputs *explicitly*? The 80 bytes can contain a list of color transfers accompanying the transaction, where each color transfer consists of:

a) A reference for which color. This can be (1) a URL to a color specification or (2) a block number + transaction index for the genesis transaction in the blockchain. (1) is inefficient space-wise but can be used immediately after the color is generated, (2) is very efficient space-wise.

b) The quantity of color (in integer satoshis) being transferred. If this is more than is truly available, assume that all of the available color is transferred across.

c) The input from which the color is being taken.

d) The output to which that color is being assigned.

We can pack in the bits for this efficiently, with an extra meta field stating how many bits are used for each aspect of the transfer. For the vast majority of color transactions, (a) will need less than 48 bits under the efficient scheme, (b) 16 bits, (c) 4 bits and (d) 4 bits. Total: 72 bits or 9 bytes. Plus (say) one byte of meta field. So 8 color transfers can be specified within the 80 byte limit. From a purist perspective we might want to transfer an infinite number of colors per transaction. But in reality I think 8 is more than enough for any normal application, including complex swaps and trades. If someone really needs to so more than 8, they can use multiple transactions.

Forward- or back-tracking is also simple with this scheme, since every single transaction explicitly states whether it transfers color across.

Are there reasons I am missing for why we can't use such a simple scheme?

Gideon

[Flavien]

While Alex is set on the idea that any metadata in the blockchain is evil, I think many people agree that it is beneficial.

 

I have a few comments on what you are suggesting:

 

This can be (1) a URL to a color specification

 

Metadata such as URL belongs to a higher level protocol (built on top of colored coins). While you want to use an URL, someone else may want to use an email, a hash or a company registration number. While the core color coin protocol should allow for embedding metadata, it should not mandate what that metadata is. Higher level protocols can be built on top of the core color coin protocol to give particular meanings to the metadata.

 

or (2) a block number + transaction index for the genesis transaction in the blockchain.

 

I don't think that helps, since any trustless node has to backtrack to the issuing transaction anyway to verify that the output is really of the color that the transaction is claiming.

 

b) The quantity of color (in integer satoshis) being transferred. If this is more than is truly available, assume that all of the available color is transferred across.

c) The input from which the color is being taken.

d) The output to which that color is being assigned.

 

Forward- or back-tracking is also simple with this scheme, since every single transaction explicitly states whether it transfers color across. 

 

The goal of what you are suggesting is facilitating the backtracking, and I think using metadata to help backtracking is indeed the right thing to do. But none of this is actually necessary. All we need to just have a particular identifiable OP_RETURN output in the transaction, and then use order-based coloring. Order based coloring already tells you which input goes to which output. The marker output is here to tell you this is a color transaction, without it, all outputs are uncolored, and backtracking can be halted.

 

The assumption I use to make that simplification is that each output is single colored and fully colored.

 

The benefit here is that we can have as many inputs and outputs and colors as we want because the metadata is constant size, and also that we don't take dependency on the nSequence field, which is used for something else.

[Gideon Greenspan]

This can be (1) a URL to a color specification

 

Metadata such as URL belongs to a higher level protocol (built on top of colored coins). While you want to use an URL, someone else may want to use an email, a hash or a company registration number. While the core color coin protocol should allow for embedding metadata, it should not mandate what that metadata is. Higher level protocols can be built on top of the core color coin protocol to give particular meanings to the metadata.

OK. I think there is good reason to use URLs with standardized contents for those URLs. But it can indeed be a higher level specification.

 

or (2) a block number + transaction index for the genesis transaction in the blockchain.

 

I don't think that helps, since any trustless node has to backtrack to the issuing transaction anyway to verify that the output is really of the color that the transaction is claiming.

Its only purpose saving space in the metadata - i.e. a way to refer to the original color spec without including it in full.

   

The assumption I use to make that simplification is that each output is single colored and fully colored.

There are reasons I posted in another thread here why I think this is a bad idea. I am thinking of all the ways that building a colored coin protocol on top of the bitcoin protocol can go wrong. I think any scheme has to fulfill these criteria:

* No valid bitcoin transaction loses colors ("whoops, I pressed return, and deleted my shares in company X"). This means that it must be possible to combine colors together in an output and also have partially colored outputs, since the undelying bitcoin is fungible in this way.

* All color transfers are explicitly indicated in a transaction. Otherwise if my colored coin client forgets about one of the colors, or if I use my old bitcoin client by mistake, I can accidentally lose my house when all I really meant to do was transfer 0.001 BTC. In a situation where my wallet is empty of bitcoin but still holds some coloring, I can recover that coloring by sending some plain bitcoin back in first.

I understand there is a downside in terms of limiting the number of color transfers per transaction. But from a product perspective I think that is a small price to pay for the safety of not accidentally deleting or transferring my color away. I guess this is the core way in which I seem to be in disagreement with the colored coins protocol as it currently stands.

Gideon

[Flavien]

* No valid bitcoin transaction loses colors

 

It is a useful characteristic to have, but I think the cost in terms of complexity (backtracking) and storage are high. A full client would have to store a potentially large list of colors for every output. This does not scale well.

 

Also, when you think about normal bitcoins, it is already possible to blackhole your coins by mistake: "whoops I just sent my retirement savings to an OP_RETURN output". Clients usually protect you from this though. This would be no different with colored coins.

 

if my colored coin client forgets about one of the colors

 

You client should never forget about any color. The same way it knows the value of every unspent output in the blockchain, it should know the color of every unspent output in the blockchain. Of course, this is only feasible if outputs are single colored.

 

Anyway both approaches are valid, but my opinion is that simplicity and scalability outweighs safety. Safety is something that can easily be built into tooling.

[Gideon Greenspan]

* No valid bitcoin transaction loses colors

 

It is a useful characteristic to have, but I think the cost in terms of complexity (backtracking) and storage are high. A full client would have to store a potentially large list of colors for every output. This does not scale well.

I'm afraid I don't see the issue. My client will only track those colors I'm interested in. If someone sends me a color I really don't care about ("bob's babysitting tokens") I can choose to stop tracking it in my client. But there's no reason for anyone to do that under my scheme, since all color transfers are deliberate and explicit in the transaction. Why wouldn't someone I don't know send me a color I don't care about? One could in theory imagine a problem with color spam, but since it costs a meaningful amount of bitcoin to send color (or at least, it will once transactions with no fees can't compete for space in blocks).

 

Also, when you think about normal bitcoins, it is already possible to blackhole your coins by mistake: "whoops I just sent my retirement savings to an OP_RETURN output". Clients usually protect you from this though. This would be no different with colored coins.

OK, let me be more specific about the criterion I think we should aim for:

* There should be no way in which to accidentally lose coloring which isn't also a way to accidentally lose bitcoin. The bitcoin protocol is proven as usable with relatively little accidental loss. So the same level of risk should apply for coloring. It is possible for me to have multiple bitcoin wallets which share private keys. In fact, this is one of the great features of bitcoin. If one of my wallets is color-aware and one is not, I think it is essential that transactions from my non-color-aware wallet cannot accidentally transfer coloring.

 

if my colored coin client forgets about one of the colors

 

You client should never forget about any color. The same way it knows the value of every unspent output in the blockchain, it should know the color of every unspent output in the blockchain. Of course, this is only feasible if outputs are single colored.

I am thinking about a gradual transition from current wallets to color-aware wallets in the marketplace. I think this transition needs to be same (see comment above).

Gideon

[Tamas Blummer]

Given the great choice of options to ride the block chain with colors, it appears to me that the first commercially successful use of colors will simply define the rules.

[Alex Mizrahi]

> Given the great choice of options to ride the block chain with colors, it
> appears to me that the first commercially successful use of colors will
> simply define the rules.

OP_RETURN won't be practically available for a month or so, I'm
implementing ITOG now.
Although we'll probably add something OP_RETURN-based as an option later.

nSequence can become useful only after fundamental changes to Bitcoin
protocol: it needs a separate consensus layer besides proof-of-work.
Otherwise transaction replacement rules cannot be relied upon: miners
are free to use different rules, say, prefer transactions which pay
higher fees.

But in an unlikely event that transaction replacement rules will be
re-enabled and nSequence will be used together with nLockTime, we can
offer upgrade to a different coloring scheme:
colored coin give us an ability to do relatively painless rule
upgrade: old clients which didn't update coloring scheme will see
transfer to new scheme as destruction of coins.
Thus it doesn't result in a fork.