>> (p.1)
    Author Topic: order-based coin coloring  (Read 3178 times)

    • killerstorm (OP)
    Legendary
    *
    Offline Offline

    Activity: 1022
    Merit: 1033



    View Profile
    October 01, 2012, 08:20:33 AM
    Last edit: October 13, 2012, 02:19:57 PM by killerstorm
     #1
    Previous discussion: https://bt.irlbtc.com/view/106449.0 got a bit cluttered, so I'm starting a new thread specifically about coloring algorithm.

    Introduction into coin coloring schemes: https://bt.irlbtc.com/view/106449.msg1169974#msg1169974
    A summary by Jutarul: https://bt.irlbtc.com/view/106449.msg1203918#msg1203918
    Atomic coin swapping - https://bt.irlbtc.com/view/112007.0

    A C++ implementation of order-based coloring algorithm: https://bt.irlbtc.com/view/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://bt.irlbtc.com/view/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.
    Chromia: a better dapp platform

  • killerstorm (OP)
    Legendary
    *
    Offline Offline

    Activity: 1022
    Merit: 1033



    View Profile
    October 01, 2012, 08:47:39 AM
     #2
    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://bt.irlbtc.com/view/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.
    Chromia: a better dapp platform

  • killerstorm (OP)
    Legendary
    *
    Offline Offline

    Activity: 1022
    Merit: 1033



    View Profile
    October 01, 2012, 08:48:21 AM
     #3
    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.
    Chromia: a better dapp platform

  • jgarzik
    Legendary
    *
    qt
    Offline Offline

    Activity: 1596
    Merit: 1142


    View Profile
    October 01, 2012, 06:11:48 PM
     #4
    Quote from: killerstorm on October 01, 2012, 08:47:39 AM
    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://bt.irlbtc.com/view/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.
    Jeff Garzik, Bloq CEO, former bitcoin core dev team; opinions are my own.
    Visit bloq.com metronome.io
    Donations tip jar: 1BrufViLKnSWtuWGkryPsKsxonV2NQ7Tcj

  • killerstorm (OP)
    Legendary
    *
    Offline Offline

    Activity: 1022
    Merit: 1033



    View Profile
    October 01, 2012, 06:17:52 PM
     #5
    Quote from: jgarzik on October 01, 2012, 06:11:48 PM
    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?
    Chromia: a better dapp platform

  • killerstorm (OP)
    Legendary
    *
    Offline Offline

    Activity: 1022
    Merit: 1033



    View Profile
    October 01, 2012, 06:25:27 PM
     #6
    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 Smiley
    Chromia: a better dapp platform

  • jgarzik
    Legendary
    *
    qt
    Offline Offline

    Activity: 1596
    Merit: 1142


    View Profile
    October 01, 2012, 06:25:45 PM
     #7
    Quote from: killerstorm on October 01, 2012, 06:17:52 PM
    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.
    Jeff Garzik, Bloq CEO, former bitcoin core dev team; opinions are my own.
    Visit bloq.com metronome.io
    Donations tip jar: 1BrufViLKnSWtuWGkryPsKsxonV2NQ7Tcj

  • Meni Rosenfeld
    Donator
    Legendary
    *
    expert
    Offline Offline

    Activity: 2058
    Merit: 1056



    View Profile WWW
    October 01, 2012, 06:52:42 PM
     #8
    Quote from: killerstorm on October 01, 2012, 06:25:27 PM
    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 Smiley
    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.

    Quote from: jgarzik on October 01, 2012, 06:25:45 PM
    Quote from: killerstorm on October 01, 2012, 06:17:52 PM
    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.
    1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
    Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
    Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond

  • killerstorm (OP)
    Legendary
    *
    Offline Offline

    Activity: 1022
    Merit: 1033



    View Profile
    October 01, 2012, 07:17:24 PM
     #9
    Quote from: Meni Rosenfeld on October 01, 2012, 06:52:42 PM
    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?

    Quote from: Meni Rosenfeld on October 01, 2012, 06:52:42 PM
    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.
    Chromia: a better dapp platform

  • Meni Rosenfeld
    Donator
    Legendary
    *
    expert
    Offline Offline

    Activity: 2058
    Merit: 1056



    View Profile WWW
    October 01, 2012, 08:29:50 PM
     #10
    Quote from: killerstorm on October 01, 2012, 07:17:24 PM
    Quote from: Meni Rosenfeld on October 01, 2012, 06:52:42 PM
    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.
    1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
    Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
    Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond

  • jgarzik
    Legendary
    *
    qt
    Offline Offline

    Activity: 1596
    Merit: 1142


    View Profile
    October 01, 2012, 09:04:11 PM
     #11
    Quote from: Meni Rosenfeld on October 01, 2012, 08:29:50 PM
    Quote from: killerstorm on October 01, 2012, 07:17:24 PM
    Quote from: Meni Rosenfeld on October 01, 2012, 06:52:42 PM
    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).
    Jeff Garzik, Bloq CEO, former bitcoin core dev team; opinions are my own.
    Visit bloq.com metronome.io
    Donations tip jar: 1BrufViLKnSWtuWGkryPsKsxonV2NQ7Tcj

  • coloredcoin
    Full Member
    ***
    Offline Offline

    Activity: 199
    Merit: 101


    View Profile
    February 18, 2014, 07:04:20 AM
     #12
    SHOULD CONTINUE.

  • maaku
    Legendary
    *
    expert
    Offline Offline

    Activity: 905
    Merit: 1014


    View Profile
    February 18, 2014, 08:14:40 AM
     #13
    Quote from: coloredcoin on February 18, 2014, 07:04:20 AM
    SHOULD CONTINUE.

    https://bt.irlbtc.com/view/106373.0
    I'm an independent developer working on bitcoin-core, making my living off community donations.
    If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
    Pages: [1]
      Print  
Page 1
Viewing Page: 1

IRLBTC™ © 2025 IRLBTC.com