order-based coin coloring

[killerstorm]

Previous discussion: https://bitcointalk.org/index.php?topic=106449.0 got a bit cluttered, so I'm starting a new thread specifically about coloring algorithm.

Introduction into coin coloring schemes: https://bitcointalk.org/index.php?topic=106449.msg1169974#msg1169974
A summary by Jutarul: https://bitcointalk.org/index.php?topic=106449.msg1203918#msg1203918
Atomic coin swapping - https://bitcointalk.org/index.php?topic=112007.0

A C++ implementation of order-based coloring algorithm: https://bitcointalk.org/index.php?topic=106449.msg1230732#msg1230732

It's important to make distinction between coloring algorithm and coloring validation.

Coloring algorithm's output is colors for each transaction output in a transaction. (We assume that it's being fed with transactions which are already in blockchain so saying that they are "broken" is not an option.) It is not allowed to fail as long as its input is a valid transaction. If colors cannot be determined for some outputs (or for all outputs) it simply should say that they are uncolored. (I use separate COLOR_MIXED color, but it's semantically same as uncolored.)

A good coloring algorithm should be "forgiving": if colors can be determined for some outputs but other outputs are not correctly organized, it should correctly color outputs which can be reliably identified.

The reason for this is that we need to work in a situation with incomplete information. Particularly we should take into account situations where transaction receiver does not know about some colors transaction creator was aware of. Also it's possible that transaction creator does not know colors of some outputs he is using in his transaction, but transaction receiver has this knowledge.

Examples are here: https://bitcointalk.org/index.php?topic=106449.msg1170082#msg1170082

A transaction coloring validator is a different thing. It will be ran when transaction is being made or signed. It might be used to check for defects in transaction-making algorithms. We can be much more strict in a transaction coloring validator.

[1714827342]

1714827342

[1714827342]

1714827342

[killerstorm]

I've found a problem: it turns out that zero-valued outputs are possible in Bitcoin. Moreover, Mike Hearn wants to use them to represent bonds in a manner similar to colored coins:
https://bitcointalk.org/index.php?topic=92421.0 (search for "zero-valued")
So apparently we don't need even a single satoshi per colored coin, 0 works too. Although in that case it isn't subdivisible.

But I guess we should support zero-valued outputs in order-based coloring algorithm... Just in case. Unfortunately, as is it fails miserably since zero-valued outputs do not follow conservation rules (i.e. you can insert any amount of them in any place). Zero-valued inputs will be simply ignored and zero-valued outputs will get adjacent colors.

So I've amended algorithm specifically for zero-valued outputs: one such output will eat one zero-valued input, if possible. In this case it gets input's color. So you can't get more zero-valued colored outputs than you had zero-valued colored inputs.
If matching zero-valued inputs and outputs in order is not possible, they are assigned COLOR_MIXED.

[killerstorm]

I've implemented interactive coloring demo in JavaScript: http://killerstorm.xen.prgmr.com/alex/color.html
To try it, select colors and values of inputs, e.g.
Red 1
Blue 1
Uncolored 1

Then fill amounts of outputs, but do not fill colors, e.g.
1
1
1

Then press button "compute", it will fill colors of outputs. If sum(outputs)>sum(inputs) it is reported in alert and outputs are not filled.

There is a list of possible errors/warnings in bottom of screen. If it says "false" that means it's OK, if it says "true" that means that there is error/warning.

Whether these errors/warnings matter depends on application.

Here is code: https://gist.github.com/3807220 (below HTML)

Unfortunately validation code cluttered algo code so it's hard to follow it, but actually changes to handle zero-valued inputs/outputs were minimal.

I think it's probably better to have coloring and validation code separate, i.e. do coloring first and then run validation checks on it.
So I don't recommend reading code in this version, it's ugly.

[jgarzik]

I've found a problem: it turns out that zero-valued outputs are possible in Bitcoin. Moreover, Mike Hearn wants to use them to represent bonds in a manner similar to colored coins:
https://bitcointalk.org/index.php?topic=92421.0 (search for "zero-valued")
So apparently we don't need even a single satoshi per colored coin, 0 works too. Although in that case it isn't subdivisible.

I disagree with Mike, here, and am avoiding zero-value outputs in pybond.  Here's why:

• The reference client does not consider zero-valued outputs standard.  Failing the is-standard check implies the transaction will not be relayed by many.  Miners may also avoid the transaction for the same reason.
• nValue may be employed to efficiently hold multiple smartcoins, in a single output.  For example, nValue==3 may imply you are holding 3 of the same type of smartcoin (bond).
• 1-satoshi outputs have an obvious cost.  The fee requirement for relaying "dust spam" also adds to the cost.  This economic signalling encourages conservation and reduces blockchain spam.

[killerstorm]

I disagree with Mike, here, and am avoiding zero-value outputs in pybond.  Here's why:

• The reference client does not consider zero-valued outputs standard.  Failing the is-standard check implies the transaction will not be relayed by many.  Miners may also avoid the transaction for the same reason.
• nValue may be employed to efficiently hold multiple smartcoins, in a single output.  For example, nValue==3 may imply you are holding 3 of the same type of smartcoin (bond).
• 1-satoshi outputs have an obvious cost.  The fee requirement for relaying "dust spam" also adds to the cost.  This economic signalling encourages conservation and reduces blockchain spam.

Yep, I'm aware of your opinion and I totally agree with you.

But still, we have to support them in coloring algorithm, right?

[killerstorm]

There is also a theoretic reason to ban zero-valued outputs on protocol level: If all outputs are at least 1 satoshi, we have a theoretic limit on number of unspent transaction outputs, thus pruned blockchain representation has finite size.

But if zero-valued outputs are allowed blockchain is potentially infinite.

It's easier to work with object of a finite size, I think. We'll have less worries about blockchain centuries from now

[jgarzik]

But still, we have to support them in coloring algorithm, right?

I don't see much point.  I'm just calling nValue==0 invalid and moving on.

[Meni Rosenfeld]

There is also a theoretic reason to ban zero-valued outputs on protocol level: If all outputs are at least 1 satoshi, we have a theoretic limit on number of unspent transaction outputs, thus pruned blockchain representation has finite size.

But if zero-valued outputs are allowed blockchain is potentially infinite.

It's easier to work with object of a finite size, I think. We'll have less worries about blockchain centuries from now

0-value output should be considered already spent for the purposes of pruning. A more general framework for controlling the blockchain size is output upkeep costs.

But still, we have to support them in coloring algorithm, right?

I don't see much point.  I'm just calling nValue==0 invalid and moving on.

Right, we're defining the rules for what makes a colored transaction valid. We can decide that a tx with 0-value outputs is invalid; whether some Bitcoin node will accept it is a valid Bitcoin transaction (uncoloring the coins) is not your concern.

[killerstorm]

0-value output should be considered already spent for the purposes of pruning.

Then how zero-valued input will be connected to zero-valued output?

Or am I missing something and there are no zero-valued inputs?

Right, we're defining the rules for what makes a colored transaction valid. We can decide that a tx with 0-value outputs is invalid; whether some Bitcoin node will accept it is a valid Bitcoin transaction (uncoloring the coins) is not your concern.

Suppose that 5 years from now smartcoins based on zero-valued outputs become a thing and somebody implements a client which handles them. Then somebody might want to do an atomic swap of "normal" colored coin and zero-valued one.

But this would uncolor this "normal" colored coin in view of older clients which are based on coloring algo which sees zero-valued outputs as invalid.

I'd rather add 3 lines of code to implement some sensible reaction then deal with this mess later.

[Meni Rosenfeld]

0-value output should be considered already spent for the purposes of pruning.

Then how zero-valued input will be connected to zero-valued output?

Or am I missing something and there are no zero-valued inputs?

Pruning isn't immediate, some cooldown period will be given after an output is spent before it can be pruned. So a 0 output can be used as a 0 input before it is pruned.

I don't know how well this fits with the contemporary implementation.

[jgarzik]

0-value output should be considered already spent for the purposes of pruning.

Then how zero-valued input will be connected to zero-valued output?

Or am I missing something and there are no zero-valued inputs?

Pruning isn't immediate, some cooldown period will be given after an output is spent before it can be pruned. So a 0 output can be used as a 0 input before it is pruned.

I don't know how well this fits with the contemporary implementation.

ultraprune looks at the set of unspent outputs, zero value or not.

There are some proposals to create certain transactions obviously impossible-to-spend, and therefore obviously pruneable immediately (or after some length of time).

[coloredcoin]

SHOULD CONTINUE.

[maaku]

SHOULD CONTINUE.

https://bitcointalk.org/index.php?topic=106373.0