bits of proof with colored coins

[Tamas Blummer]

Website launched, I am adding documentation and background info: http://bitsofproof.com

[Yoni Johnathan Assia]

Will this support colored coins format from the start ?
I think that's an amazing differentiator.

On Apr 6, 2013 11:40 AM, "Tamas Blummer" <tamas....@gmail.com> wrote:

Website launched, I am adding documentation and background info: http://bitsofproof.com

--
You received this message because you are subscribed to the Google Groups "Colored bitcoin - BitcoinX" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoinX+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Amos Meiri]

Think we should tell a simple story of how it works (like the one with the theater tickets you told Adi...).
Let me know if i can help with anything

[Alex Mizrahi]

Neither color definition format nor coloring algorithm you implemented is compatible with what is described here:

https://github.com/bitcoinx/colored-coin-tools/blob/master/colors.md

and is implemented in ArmoryX and other colored coin clients.

So for now bitsofproof implementation is considered incompatible and, likely, broken. (I'm not 100% sure it is broken, but chances are it is vulnerable to attacks which official order-based coloring algorithm is secure against. We had a lot of discussion on this...)

This is sad. I want different colored coin clients to be able to interoperate freely. But to do this, we need to implement spec exactly as written. Just like with Bitcoin protocol, if client doesn't implement spec exactly, bad things can happen.

Starting with a minimal protocol is not an argument. This makes about as much sense as implementing a Bitcoin client which supports transactions only with two outputs. "Minimal protocol" will bite you in future, and it is just easier to implement a real thing and not face various incompatibility issues in future. (And in this case "incompatibility issues" means that somebody might lose very valuable shares of some company.)

We had a lengthy design phase, and protocol is exactly what is enough to support anticipated uses.

Of course, it is not cast in stone, and some parts are missing.

Perhaps something needs to be changed or clarified.

But we need to do this together, with proper discussion and so on... 

[Alex Mizrahi]

One particular problem with coloring algorithm implemented in bitsofproof is that it doesn't allow merging multiple inputs into one output; only splitting is allowed. But I suspect that there is like a dozen of subtle bugs...

[Amos Meiri]

Alex i got your point...

Tamas, Alex what do you say about setting a conference with both of you to discuss those important inputs ?

[Tamas Blummer]

That would be a bug, but I do not think so. Even if your suspicions come true that there are bugs, that applies to any new software and if stated like you do, then that is called FUD.

[Alex Mizrahi]

Let's start over... Were you trying to implement algorithms described here: https://github.com/bitcoinx/colored-coin-tools ?

Well, it's pretty much completely broken.

No, it isn't called FUD when it is obvious that it is broken and anybody can check this.

I just do not want to waste my time on this because reference implementation is available in multiple languages and it is trivial to compare:

https://github.com/bitcoinx/colored-coin-tools/blob/master/color.cpp (no zero-valued output support)

https://github.com/bitcoinx/colored-coin-tools/blob/master/color.js

https://github.com/bitcoinx/BitcoinArmory/blob/color/colortools.py

and there is an interactive demo:

http://killerstorm.xen.prgmr.com/alex/color.html

Your algorithm does not do merging:

Inputs:

1 RED

1 RED

Outputs (correct)

2 RED

Outputs (incorrect)

2 Uncolored

And it computes incorrect color when there is a band of uncolored coins:

Inputs

1 RED

1 Uncolored

1 RED

Outputs (correct)

1 RED

1 Uncolored

1 RED

Outputs (incorrect)

1 RED

1 RED

1 Uncolored

But again, fixing bugs is futile, you need to implement it exactly as reference implementation does.

We spent a lot of time on validation, analysis and code review. Each line of it is there for a reason.

(It's worth noting that coloring scheme is not an artifact of a particular algorithm. 

There is a completely different algorithm which implements same coloring scheme:

https://github.com/vbuterin/BitcoinArmory/blob/color/gettxcolor.py

)

[Tamas Blummer]

I would say, your style is completely broken. My code, since fresh has bugs and might be in disagreement with yours.

I am glad if you pinpoint bugs, so I fix it. A bug is however not defined by disagreement with your implementation,

we have enough of that shit in this community.

We need test vectors not sacred implementations. I will create test vectors and you might have some. Hopefully we come

up with a suite that proves that an implementation is compliant and I promise you to run that with every pull of bits of proof.

[Alex Mizrahi]

I would say, your style is completely broken.

Wat?

if you have problems understanding C++, there is cleaner code in Python, it reads like pseudo-code:

https://github.com/killerstorm/BitcoinArmory/blob/color/colortools.py#L126

 

My code, since fresh has bugs and might be in disagreement with yours.

 

I am glad if you pinpoint bugs, so I fix it. A bug is however not defined by disagreement with your implementation,

we have enough of that shit in this community.

Bug is defined by disagreement with specification, of course. But since my implementation is well-analyzed it is pretty much the same thing.

 

 

We need test vectors not sacred implementations.

There is no sacred implementation.

 There are two coloring ALGORITHMS which implement same order-based coloring rules.

One algorithm implements the specification exactly as written, i.e. it finds inputs matching the output by checking for intersection.

Another algorithm does coloring without storing intermediate results. There is no formal proof that it is equivalent, but it was reviewed, analyzed and tested.

You're trying to invent your own algorithm, but why?

You don't invent a new sorting algorithm when you need to implement a sort, do you?

(I hope you understand the difference between an algorithm and implementation of an algorithm.)

If you're concerned about second algorithm's validity, perhaps I can make a proof that it computes results correctly according to the specification.

 

I will create test vectors and you might have some. Hopefully we come

up with a suite that proves that an implementation is compliant and I promise you to run that with every pull of bits of proof.

Here are test vectors together with rationale for these particular coloring rules and algorithm:

https://bitcointalk.org/index.php?topic=106449.msg1169974#msg1169974

It spans several messages, the last relevant message is one which mentions C++ proof-of-concept.

(In the first message algorithm isn't fully fleshed out.)

There is an updated algorithm which works with zero-valued outputs too, but let's get at least the basic one right, for the start...

[Alex Mizrahi]

There is a variation of second algorithm which might be easier to follow: fuse consecutive inputs with same color together.

Then you don't need state-machine-like logic in a loop which eats inputs: if there is enough value left to cover an output then this output is colored. If it is not enough then you have an output of mixed color.

E.g.

if (current_value >= output[i].value) {

   output[i].color = current_color;

   current_value -= output[i].value;

} else {

   output[i].color = UNCOLORED;

   ...input-eating loop goes here

}

[Jorge Timón]

I agree specifying some test cases is the way to go to advance in
standardizing the coloring rules.
Maybe that's were the focus should be now that there are several implementations
But, please, don't fight like this. It doesn't help to make the
different implementations inter-operable, which is the goal the way I
see it.

> --
> You received this message because you are subscribed to the Google Groups
> "Colored bitcoin - BitcoinX" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to bitcoinX+u...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>

--
Jorge Timón

http://freico.in/

[Alex Mizrahi]

I agree specifying some test cases is the way to go to advance in
standardizing the coloring rules.

We already have a document which specifies the rules.

Test cases can help implementors to detect problems, but they are not in any way a replacement for specification.

Tests cannot test everything.

There is no disagreement over coloring rules, as far as I know, and I'm not some crazy dude who has monopoly on implementation.

Vitalik Buterin implemented a coloring algorithm directly based on the specification, without any inputs from me.

Lior Hakim almost implemented it... There were some flaws in his implementation, but I think he was on the right track. (Lior also made a document on coloring implementation, but I don't remember whether it has an independent description of coloring algorithm.)

Meni Rosenfeld reviewed this specification and made his own description of the algorithm in his paper.

Benjamin Linder reviewed my algorithm w.r.t. its conformance to earlier formulation of rules.

I don't think it is a "fight", I'm simply stating facts...

Bug is one thing, incompatibility is another.

Coloring algorithm is a trivial issue, by the way, there is much bigger problem...

[Tamas Blummer]

There is likely no disagreement on the rules, we will clarify in a conference this week.

I was just pissed by tone how bits of proof implementation was dismissed. The implementation of the coloring rules

is a small fraction of the work I put into this and more than likely it can be fixed if it was not in alignment with 

expectations.

[Alex Mizrahi]

There is likely no disagreement on the rules, we will clarify in a conference this week.

I was just pissed by tone how bits of proof implementation was dismissed.

OK, I apologize if it looked this way...

It just did not look like it is trying to implement same coloring rules...

(I know what rules it implements simply by looking through the code. For me it is pretty much obvious, training for programming competitions helps here a lot.)

 

The implementation of the coloring rules

is a small fraction of the work I put into this and more than likely it can be fixed if it was not in alignment with 

expectations.

I understand that, this is a fairly trivial issue.

Much bigger issue is a lack of support for color definitions supported by ArmoryX, and lack of support for anticipated use cases.

And there is also a meta-issue: lack of proper communication on your side.

Basically, I expected you to announce what are you trying to implement so we can discuss and review this before you do.

What I see instead is just code... I can look through the code, of course, but it's much harder to fix it after you have already implemented it.

Some time ago I wrote three pages of text describing possible approaches towards server-side colored coin implementation.

I didn't write it because I had too much free time at hands, it was largely addressed to you, so you can use it for bitsofproof implementation.

Which approach are you using?

Forward scan is pretty much trivial, but what's about finding colors of outputs of transactions in previous blocks?

Please understand me correctly, I'm not a boss here and I cannot force anyone to report to me. I do not even want to encourage that, I'd rather let people to work in a manner which is comfortable for them. But there are three options:

1. Person communicates like I mentioned above, then I'll try to make sure that everything is correct.

2. Person writes a largely correct implementation on his own. Then I'll try to review it and see how we can fix whatever issues are there. This is how it worked with bitpaint.py.

3. If implementation is too divergent, I simply state is as a fact. I cannot enforce compatibility, I can simply note which implementations are compatible and which are not.

I think you're underestimating how complex and fragile colored coins are. We can create an ecosystem only through tight cooperation.

Coding something on your own for weeks isn't called "tight cooperation".

Even when I was a sole implementor and there were no specifications of any sort, I always announced what I'm going to do before I implemented it, and I discussed it with everybody who wanted to discuss.

For example, I did not implement the coloring algorithm right in ArmoryX. I first described it on forum, then made a small C++ program, then an interactive web demo, and only then I got to ArmoryX. 

Then when I started implementing ArmoryX, there were several open questions, and I discussed them before jumping straight to coding.

[Jorge Timón]

I know the rules are specified, i meant standardizing the different "non-official rules" that each implementation may have by making them comply with the same set of "standard tests". Does this make more sense to you?
It can be a simple set of tests that make sure you comply with the specification and grow when more edge cases appear or when the specifications change to support new features or because we realize we missed something (I'm not saying it is the case, just trying to imagine possible reasons to extend these "standard tests").

--

[Alex Mizrahi]

I know the rules are specified, i meant standardizing the different "non-official rules" that each implementation may have by making them comply with the same set of "standard tests". Does this make more sense to you?

No, I'm not aware of any "non-official rules".

Did you mean "bugs"?

 

It can be a simple set of tests that make sure you comply with the specification and grow when more edge cases appear or when the specifications change to support new features or because we realize we missed something (I'm not saying it is the case, just trying to imagine possible reasons to extend these "standard tests").

Sure, test set is a good thing.

[Jorge Timón]

I mean subtle differences between the algorithms (maybe trying to support more features or just implementation differences) that don't break the general rules and therefore aren't necessarilly bugs.
Anyway, whatever the reasons, designing those tests can only be a good thing and I'm glad we can all agree on that.
As you said before, they're not a substitute of the specificaions but rather a complement.

--

[Yoni Johnathan Assia]

Defining these test is a great idea ! The actual standard can be defined as test driven development and simlly define thos set of test, and have automatic scripts to test differemt implementations.

Can someone help write thise tests ?
Thanks,
Yoni

[Tamas Blummer]

I am guilty of sparse communication Alex. 

This is not intentional, but times are crazy busy for me now as I am setting up my company.

I focused on getting the framework around coloring ready, that is color aware wallet and

API to the server. The coloring of outputs itself although a central piece is a small amount

of code that will be aligned to test vectors we agree on.

Call bits of proof incompatible and broken. I would prefer "in development".

[Albert Hendriks]

Guys, I hate to interfere but I will (although I'm new). I'm currently forming an opinion on this matter between Tamas and Alex. I will thoroughly test and investigate my opinion before disclosing anything about it. This may take a couple of days. The reason I'm posting this announcement is that I think it would be good for the project to wait for my opinion before continuing too much or even before making up. I'm working fulltime on this now. I'll try to hurry up.

Albert

[Albert Hendriks]

Sooner than expected, here's my opinion. As I said before I feel a bit like I'm intruding, but I think this is an opinion that matters for the project, even though it's from a new member.

What's my knowledge about this?

I'm a software developer at a high frequency trading firm. I'm specialized at Java code reviews.

I don't know exactly how sha works yet, nor do I know the details of the bitcoin protocol yet, nor the details of the coloring algorithm. I have some experience with open source projects (Symfony, Drupal).

What's the issue?

Tamas has worked hard to get something working. Any normal project would be very happy with such commitment. The code is of good quality and instead it is trashed after a small review.

But for this project you need a high-quality standard (because of the cost of a bug and because the code will be inspected millions of times when things get rolling). This means we need a different process. Every single java statement will need discussion before it ends up in a Java file. Of course we'll need tests as well, but that's just a side thing.

Conclusion?

Alex is right on every aspect, except for subtility. It's all about the process.

Recommendations?

We start from scratch with the code. Alex should get the free hand from above and we should listen to him. Tamas will coach me how to get started to learn the protocols.

That's my mouth; where's my money?

I'm planning to invest at least 2 months in this project starting today. I've got only one small other project running. In addition, if my advice is followed upon exactly AND everybody stays onboard, I'll invest 3 BTC to this project today. I see it as a commerical investment, and I will want a share of the proceedings. (Or if I decide to quit the project, I'll want the 3 BTC back once the proceedings are there). I know this doesn't sound like a lot, but please beware that I only found out about bitcoins very recently and this is a huge portion of the bitcoins I own.

Please tell me what you think. Are you going for my advice or should I just get lost?

[Alex Mizrahi]

Tamas has worked hard to get something working. Any normal project would be very happy with such commitment. The code is of good quality and instead it is trashed after a small review.

 

Alex is right on every aspect, except for subtility. It's all about the process.

I guess I need to explain...

I simply asked for better cooperation, and used coloring incompatibility simply as an example of why lack of cooperation is bad.

I guess I didn't take into account that people don't like when somebody says their code is broken :)

I didn't try to be more subtle because I already asked about cooperation on March 24.

Tamas have chosen to develop his own color definition standard instead of improving mine.

it is very well possible that his color definitions are better, but we cannot switch to a different format each time somebody wishes so.

We need to discuss what's wrong with old format and how new one fixes it.

THE main problem with color definitions is handling of updates and additional issues.

We also seem to differ in how we see the PURPOSE of coloring server.

For me coloring server is just a TOOL which one might choose to use. E.g. if I want to trade coloring coins I will launch bitsofproof server, import color definitions and run client. Or I can use a different client, say, ArmoryX.

But it looks like Tamas sees coloring server as a service, as implied here:

"The server also signs the terms with an "underwriter" key to disallow the issuer to emit alternate terms for the same output."

This isn't how it should work... Well, of course color definition can be signed by multiple parties.

Say, by issuer, insurer and operator of exchange it is listed on.

But exchange operator =/= server.

[Alex Mizrahi]

OK, I guess I need to bring back discussion about color definitions...

We stopped it because nobody really cared... But now we kinda need to settle on something.

[J.R. Willett]

Welcome Albert!

Thanks for your comments and commitment to this project. I am hopeful that colored bitcoins are paving the way for trade in stable distributed currencies. Like you, I personally would love to invest in the concept being successful, but at this point it is not clear what one would invest in other than just buying bitcoins. Like you, I am also a software developer by trade with a strong understanding of trading and market economics.

Colored coins simply make bitcoins more valuable. If Alex decides to use an alt-coin (which I think is a bad idea, personally), the benefit will go to that alt-coin until developers do something similar for bitcoin. Your two months of promised work would be much appreciated, but I don't see any way it could make you money except via the bounties currently on offer for development milestones.

Personally, I am waiting for an investment opportunity which offers the kind of blue-sky moonshot that bitcoin is, where my investment gains value in proportion to the success of the protocol. I think those opportunities will come eventually, probably once colored coins have taken hold and people recognize their benefits and weaknesses. I wrote a paper about one such moonshot, but I am sure there are many other ways to go about it.

Are you going to the bitcoin conference in San Jose? I will be there, and Yoni (CEO of eToro who is backing development on colored coins) will be there as well. I'll be participating in a panel discussion about "the future of bitcoin" where I expect there will be a lot of discussion of ideas like this.

Again, welcome. I'm sure your contributions to the code will be very valuable.

-J.R. Willett

--

[Albert Hendriks]

Hi JR,

Thanks for your enthusiasm :). I'm not expecting that two months of work will bring me any coins. The point is that from the 1st of July on I won't have an income anymore, which means I'll need to find a job before then. This means that under normal circumstances I won't have time from then on anymore, because of that job. I must admit that I agree with your investment visions. This coloring protocol will be the basis and the basis won't make the money. Something on top of that will (like a fee-receiving service). This still might be a good way to get started. Can you point me to your paper (just curious)?

I'd go to the San Jose conference, but unfortunately I can't afford.

Alex, I'd love to respond but at this point I need more knowledge. My previous opinion was just about the process, but to have an opinion about the coloring algorithm I need to learn about the bitcoin protocol, which I'm going to do now.

Cheers,

Albert

[Alex Mizrahi]

Alex, I'd love to respond but at this point I need more knowledge. My previous opinion was just about the process, but to have an opinion about the coloring algorithm I need to learn about the bitcoin protocol, which I'm going to do now.

Well, I'll try to make a summary about color definitions, since previous discussion was scattered over many messages.

Color definition =/= coloring algorithm, by the way.

[Albert Hendriks]

Alex, I'm not good with terminology and definitions. But I do understand that you give a way to DEFINE coloring, and that that description should not be taken as an implementation prescription at all. (I'm deliberately avoiding the word "algorithm" here, everybody seems to have his own definition of it.)

I have looked at your js code. We have to be careful with the MIXED value, because it's not defined in your document. My suggestion would be to declare the transaction illegal instead (when now a MIXED would be encountered). An alternative would be to uncolor the satoshi, which is something we don't really want to happen either.

My suggestion would lead to easier implementations because the colors would be aligned in legal transactions, but that's not the reason why I suggest this (the reason is proper definition).

The last alternative I see is to really have a linear combination of colors in one output. But that would lead to improper definition of colors when that output becomes an input in a new transaction. Of course it depends on the practical implications whether we can/should use this alternative. If I understand everything about the bitcoin protocol right, it would make sense to me to always have a separate wallet for each color (I think?) at client's responsibility, which would render this last alternative unnecessary.

[Albert Hendriks]

I realize only now that I don't understand your definition of coloring yet. I would understand it if every satoshi would have a color, which would be equal to some bitcoin address of a miner. If not: how would you assign colors retrospectively (I think the constraints/definitions would get complicated if that weren't possible)?

[J.R. Willett]

The paper: https://sites.google.com/site/2ndbtcwpaper/2ndBitcoinWhitepaper.pdf

I'm hoping to revise it before the conference in May.

[Alex Mizrahi]

But for this project you need a high-quality standard (because of the cost of a bug and because the code will be inspected millions of times when things get rolling). This means we need a different process. Every single java statement will need discussion before it ends up in a Java file. Of course we'll need tests as well, but that's just a side thing.

Yes, we need at least one high-quality, reference implementation (which might be used by market makers, for example), and we need to be aware of every decision we make.

I.e. ideally nothing should be left as an "artifact of an implementation".

Sadly  ArmoryX can't be used for this purpose: even if I document every line of my code, there is a ton of C++/Python code which isn't very reliable, it literally crashes from time to time.

So that's kinda futile...

I'm not a big fan of Java myself, but it seems to be better than alternatives in this case...

 

We start from scratch with the code.

I doubt it's necessary, can't we just review existing code? If we are going to proceed with bitsofproof, that is.

For the sake completeness, we could start from scratch with something like MultiBit.

What's better depends on how we're going to use it, I think...

 

I'm planning to invest at least 2 months in this project starting today.

That would be great!

We found a lot of people interested in colored coins, but they can only spend a couple of hours per week on this project, and it is really hard to do development this way, since there are dependencies between different components, and it basically takes forever.

 

I've got only one small other project running. In addition, if my advice is followed upon exactly AND everybody stays onboard, I'll invest 3 BTC to this project today. I see it as a commerical investment, and I will want a share of the proceedings. (Or if I decide to quit the project, I'll want the 3 BTC back once the proceedings are there). I know this doesn't sound like a lot, but please beware that I only found out about bitcoins very recently and this is a huge portion of the bitcoins I own.

Proceedings?

Well, that's a hard part... We are developing an open source technology, and anybody will be able to use and possibly get profits... But we can't force them to share, of course, that would kind undermine openness of the technology.

So, basically, funding of development is limited to donations, possibly consultancy fees etc.

Unless you want to implement (and, maybe, run) some sort of commercial solution. Say, for high-frequency trading. But open source should come first, since openness is the selling point.

Of course, it is possible that some traders will want to share their profits with developers. But it's up to them entirely. So I don't think there is a way to invest into this project in general.

[Albert Hendriks]

I do see your point about open source and I fully agree. It's true that this won't generate coins directly, although it's a magic project. It needs to be done, but especially after two months I might get de-motivated and hop off to a spinoff project (if any). But let's check where this will lead first.

I'll keep my 3 coins then I suppose.

Could you comment on the questions I asked about coloring in my previous post? Is the criticism justified?

[Albert Hendriks]

By the way, I was also in a discussion with someone who wants to develop a standalone plugin we might use:

https://bitcointalk.org/index.php?topic=173220.msg1804949#msg1804949

[Alex Mizrahi]

Alex, I'm not good with terminology and definitions.

We use weird terms sometimes...

"Color definition" is a document which describes issuance of particular color. I.e. its genesis, name, meaning etc.

 

But I do understand that you give a way to DEFINE coloring, and that that description should not be taken as an implementation prescription at all. (I'm deliberately avoiding the word "algorithm" here, everybody seems to have his own definition of it.)

OK, I think we usually call this coloring scheme or something like that.

 

I have looked at your js code. We have to be careful with the MIXED value, because it's not defined in your document. My suggestion would be to declare the transaction illegal instead (when now a MIXED would be encountered). An alternative would be to uncolor the satoshi, which is something we don't really want to happen either.

Mixed outputs should be considered the same uncolored by clients. Separate MIXED state is there just for display and diagnostic purposes.

It's done this way for a reason, I'll dig up a discussion for you.

As for declaring transaction illegal, well, we can't do that since it is already included into blockchain and we cannot ignore it since its outputs can be used in other transactions. So we need to know colors of its outputs.

We could uncolor all outputs of such transaction, but it's undesirable for several reasons.

So we do minimum amount of damage, uncoloring only mixed outputs.

 

The last alternative I see is to really have a linear combination of colors in one output. But that would lead to improper definition of colors when that output becomes an input in a new transaction. Of course it depends on the practical implications whether we can/should use this alternative. If I understand everything about the bitcoin protocol right, it would make sense to me to always have a separate wallet for each color (I think?) at client's responsibility, which would render this last alternative unnecessary.

Yes, we can assume that mixing is either a fuck up or a deliberate destruction. In either case it is easier to assume that color of coins was lost.

If it was an accident, issuer can repair the damage.

[Albert Hendriks]

Ah, that clarifies everything for me, thx. I have to go now, trying to be back within two hours.

--

[Albert Hendriks]

I read somewhere the idea of ordering inputs by color. That's technically wrong (even when colorless coins are at the bottom).

I think that the coloring scheme/algorithm/something suggested (https://github.com/bitcoinx/colored-coin-tools/blob/master/colors.md) is sound. I don't agree with it yet though. Usually that means there's something I don't understand yet. However I will phrase my misconception in a way that suggests a better coloring mechanism would be possible.

It can be made mathematically much more beautiful and easier to implement. We don't need "color definitions". With an easy adjustment, a satoshi could have multiple colors (but not a linear combination; each color is yes or no). Every output is a genesis. Most of them are irrelevant. The only thing you want to know is: "is my wallet of color x"? It works almost the same as Alex's article except that you would now need to backtrack instead of doing it bottom-up. For example, I hereby declare that wallet 1DE8pQWtX5vL59BRA1bVNSj4wpaGx6gNr5 is an interesting genesis (let's call it the color "pink"). If you want to know if your wallet has color pink, you would use Alex's method to figure out which are the belonging inputs of your wallet and recursively check if they all come from my wallet. Mixing would remove the color pink, but when backtracking another color you might not get mixing.

Obviously at some point we will want color definitions. As in: what can I do with pink satoshi? But I don't see why we would need to specify that at this point. We don't need a format for it yet: we can trade although it's not user friendly.

Note that I'm confusing the terms "wallet" and "transaction output". This is because I don't know the exact difference. I suppose a wallet contains a set of transaction outputs?

Now I'm beginning to understand why we need to adjust some wallets source code. I was hoping we could make a "proxy" on top of a wallet, but that might be impossible as a general wallet would mix the colors. So I agree that the question is now, what are we going to use as basis? We can't make it general for any wallet. The options you mention are bitsofproof, armoryX and MultiBit.

I will now delve further into the bitcoin protocol to figure out if two parties can make a trade where they cannot fool each other and if wallets would almost support something like that (i.e. coins going into 2 directions).

[Alex Mizrahi]

It can be made mathematically much more beautiful and easier to implement. We don't need "color definitions". With an easy adjustment, a satoshi could have multiple colors (but not a linear combination; each color is yes or no). Every output is a genesis. Most of them are irrelevant. The only thing you want to know is: "is my wallet of color x"? It works almost the same as Alex's article except that you would now need to backtrack instead of doing it bottom-up.

You can go either way, it is symmetric.

ArmoryX finds all colored tx outputs by scanning blockchain forward.

JS-based thin block explorer goes backwards, from output it wants to check down to coinbase or genesis tx output.

Here's a backward scan implementation:

https://github.com/vbuterin/BitcoinArmory/blob/color/gettxcolor.py

Obviously at some point we will want color definitions. As in: what can I do with pink satoshi? But I don't see why we would need to specify that at this point. We don't need a format for it yet: we can trade although it's not user friendly.

Color definitions are necessary because people want to be able to issue more coins of same color...

Otherwise, yes, it is a matter of user interface.

 

Note that I'm confusing the terms "wallet" and "transaction output". This is because I don't know the exact difference. I suppose a wallet contains a set of transaction outputs?

No, wallet normally contains one's keypairs.

Client can then find transaction outputs corresponding to these keypairs by scanning blockchain.

Some wallets also keep relevant transactions just to avoid rescan each time.

 

Now I'm beginning to understand why we need to adjust some wallets source code. I was hoping we could make a "proxy" on top of a wallet, but that might be impossible as a general wallet would mix the colors.

Yes. I think it's easier to modify a wallet source code...

There is usually some piece of code which goes through all transaction outputs which belong to user and calculates sum, for example.

We just need to filter them by color, it isn't hard to add this modification.

 

So I agree that the question is now, what are we going to use as basis? We can't make it general for any wallet. The options you mention are bitsofproof, armoryX and MultiBit.

Just for the sake of completeness, there is also bitcoind and Electrum client/server.

 

I will now delve further into the bitcoin protocol to figure out if two parties can make a trade where they cannot fool each other and if wallets would almost support something like that (i.e. coins going into 2 directions).

Yes, and we already figured that out. We call such transactions 'atomic coin swapping', 

and ArmoryX implements so-called p2ptrade protocol to do atomic coin swapping on colored coins of your choice.

There is literally a GUI for this: http://i.imgur.com/qPaXcpS.png

Basically you select what coins you want to trade, quantity, price. And it executes a trade in about a dozen of seconds if there is a matching order. (Otherwise it posts order so others can match it.)

Here's code, it does everything:

 * state maintenance (orderbook, state of trade)

 * construction of atomic coin swap transactions

 * verification of such transactions

 * networking

Just 500 lines of code:

https://github.com/bitcoinx/BitcoinArmory/blob/color/p2ptrade.py

[Albert Hendriks]

>Here's a backward scan implementation:

>https://github.com/vbuterin/BitcoinArmory/blob/color/gettxcolor.py

Obviously at some point we will want color definitions. As in: what can I do with pink satoshi? But I don't see why we would need to specify that at this point. We don't need a format for it yet: we can trade although it's not user friendly.

>Color definitions are necessary because people want to be able to issue more coins of same color...

>Otherwise, yes, it is a matter of user interface.

I think I'm going to stick with my point here. Your backward scan implementation is not what I mean: it returns the color. The backward scan I'm talking about would check if a coin has a given color x (true or false). It could return true for more than one color. The color definition makes things unnecessarily complicated. We will need it in the end, but in your setup we would need it for the protocol to work properly. It's like the http protocol requiring nameservers to function. If someone wants to issue more coins of a certain color (and didn't create and store extra in the first place), he should just issue another color and provide a 1->1 service instead. In short: every output is a genesis. It will make life much easier.

[Tamas Blummer]

Alex,

Yes, I see coloring server as a service. 

Color coding coins is a basic idea that will have different uses. Probably the most advanced is in a p2p exchange, that I am not targeting in the first step.

Coloring rules is the basic idea where all uses start from, therefore I seek to achieve a compliance there. 

Above that rule set however we are in unchartered water that need to be explored with real world uses rather than theory.

I choose to explore that territory by creating applications and check their acceptance. Should they find adoption, then they are worth of calling them standard, not before. 

Your countless emails and self referencing documents are not binding to my creativity for the same reason: they have no proven uses yet.

[Alex Mizrahi]

>Color definitions are necessary because people want to be able to issue more coins of same color...

>Otherwise, yes, it is a matter of user interface.

 

I think I'm going to stick with my point here. Your backward scan implementation is not what I mean: it returns the color. The backward scan I'm talking about would check if a coin has a given color x (true or false). It could return true for more than one color.

Well, you can run it for each color definition separately, then it also returns true or false, basically.

As I understand, you just want to restrict color to one transaction output.

This changes... approximately nothing.

By the way, to identify transaction output you needs its hash and output index, like this:

   {

    "outindex": 0, 

    "txhash": "b68525e1d5c1ea91b77918721f40d1390fd531bc53ae13ea9ad7ceab79d05378"

   }

Well, almost... Transactions with same hash are actually possible, so you might be better off with block number and index within block

 

The color definition makes things unnecessarily complicated.

I really do not see the difference... You can describe color in 36 bytes, but is it a problem to use 100 bytes?

Coloring algorithm is the same...

 

We will need it in the end, but in your setup we would need it for the protocol to work properly.

Not really...

 

It's like the http protocol requiring nameservers to function.

No, it doesn't.

Suppose you know only txhash and outindex. You can create color definition on your own and give it to your color-aware client.

Or perhaps there is a dialog in your client which lets you enter txhash and outindex, same way as browsers allow to type IP addresses.

It is true that color definition is just a convenience feature. When I implemented ArmoryX I wanted to demonstrate how colored coins can be used, i.e. one might use, say, USD-coins without referring to them as b68525e1d5c1ea91b77918721f40d1390fd531bc53ae13ea9ad7ceab79d05378:0.

Actually the main problem I see with bitsofproof is that it requires color to have terms, signature and pubkey:

https://github.com/bitsofproof/supernode/blob/master/server/src/main/java/com/bitsofproof/supernode/model/StoredColor.java

If someone wants to issue more coins of a certain color (and didn't create and store extra in the first place), he should just issue another color and provide a 1->1 service instead. In short: every output is a genesis. It will make life much easier.

I agree, but pretty much everybody wants to be able to  "issue more coins of same color".

So I want to have this feature. It doesn't make implementation any more complicated. 

[Tamas Blummer]

Well, almost... Transactions with same hash are actually possible, so you might be better off with block number and index within block

Wrong. See https://en.bitcoin.it/wiki/BIP_0030 (BIP30)

Transaction hashes are unique on the trunk.

 

Actually the main problem I see with bitsofproof is that it requires color to have terms, signature and pubkey:

https://github.com/bitsofproof/supernode/blob/master/server/src/main/java/com/bitsofproof/supernode/model/StoredColor.java

A color without terms is meaningless in my opinion. 

[Alex Mizrahi]

Your countless emails and self referencing documents are not binding to my creativity for the same reason:

Look, I don't want to limit your creativity in any way.

I think Albert have nailed it with HTTP and DNS analogy:  protocols should work in a layered fashion, then particular application can pick a particular set of protocols.

If you have Color which _requires_ signatures and whatnot, you're essentially mixing low-level coloring with high-level application logic.

This just makes supernode less useful.

I simply wish it had a general purpose layer which many applications could use.

If that's not your intention, that's OK, but I think you should be up-front about it to avoid confusion.

 

they have no proven uses yet.

People inquire me about p2ptrade all the time, the only reason it is that I don't think that software is ready yet.

[Alex Mizrahi]

Well, almost... Transactions with same hash are actually possible, so you might be better off with block number and index within block

Wrong. See https://en.bitcoin.it/wiki/BIP_0030 (BIP30)

Transaction hashes are unique on the trunk.

• Blocks are not allowed to contain a transaction whose identifier matches that of an earlier, not-fully-spent transaction in the same chain.

This means that once transaction is fully spent, transaction with same hash can appear in blockchain again.

So, txhash and blocknumber identify the transaction, I think.

 

A color without terms is meaningless in my opinion.

It is, but I believe tools should allow people to work with low-level stuff if they wish so. 

[Jorge Timón]

On 4/12/13, Alex Mizrahi <alex.m...@gmail.com> wrote:
>> Well, almost... Transactions with same hash are actually possible, so you
>>> might be better off with block number and index within block
>>>
>>>
>> Wrong. See https://en.bitcoin.it/wiki/BIP_0030 (BIP30)
>> Transaction hashes are unique on the trunk.
>>
>
>

> - Blocks are not allowed to contain a transaction whose identifier
> matches that of an earlier, *not-fully-spent* transaction in the same

> chain.
>
>
> This means that once transaction is fully spent, transaction with same hash
> can appear in blockchain again.
> So, txhash and blocknumber identify the transaction, I think.

I like txhash and blocknumber more than blocknumber + tx index.

>> A color without terms is meaningless in my opinion.

The terms doesn't have to be in the protocol, they can be defined on
an upper layer.
They can even be defined orally. For example, IOUs between friends
(see ripple or villages.cc, for example, or just any LETS-like local
currency), don't need any formality.

Putting more things than needed in the lowest level will just complicate things.
I like color definitions as they are: with a pretty informal and open
format that can be extended on upper layers.

[Tamas Blummer]

It is would be technically to create identical hash for coinbase but disallowed since BIP30.

It is impossible (astronomically low probability) to create ordinary spending transaction with the same hash.

The reason is, that an ordinary transaction contains its source reference, that can not be the same for two transactions since that would be a double spend. 

[Tamas Blummer]

The reason terms (actually hash of the term) is in the color definition to allow

two issues of the same color to be fungible. The name of the color is actually

the hash of the terms.

[Alex Mizrahi]

The thing is that you can create two chains of identical transactions out of coinbases with identical hashes.

So you cannot prevent this by disallowing using coinbase for colored coin issuance.

Of course, one who will try to pull it of is definitely malicious.

--

[Tamas Blummer]

Coinbases of identical hashes are disallowed since BIP30 introduced and implemented, therefore

this is not a possible scenario.

[Albert Hendriks]

I'm still on the path of restricting color to one output. Of course people will want to issue more coins of the same color, but it's just that they don't know what they think they want. They don't want red or brown coins, they want a share in Microsoft and issue more shares of Microsoft by issuing... another color. I don't see the point. They can just setup a 1->1 service and if that's down, arbitrage will solve any issues. It's easy and you don't need "name-servers" or a protocol between to parties who want to trade, to agree on upon the genesis set. It will work decentralized because of arbitrage even if all reference servers are down, without the need of extra protocols. And as for traders, this will be arbitrage heaven.

After writing the above, synthesis is now coming up.

I think we have a different view on what is a color wrt a certain aspect. You see a color as something that's an asset group, whereas I see it as something that should exist naturally. We can decouple this!

I'd like to name my color "colorSingle". It's the colors that exist naturally by having single-genesis. There can never be misconception about what colorSingles a certain output is. Let's call your color "colorAsset". a colorAsset is simply a set of colorSingle.

Yes I know, there's a subtle difference between your definition of a color and colorAsset. Would you give in a little bit here for the sake of decoupling? This is the example:

colorSingleRed = "red"

colorSingleBrown = "brown"

colorAssetMicrosoft = {colorSingleBrown, colorSingleRed}

transaction1:

in1: colorSingleBrown

in2: colorSingleRed

out1: colorSingleBrown+colorSingleRed

transaction2:

in1: colorSingleBrown

in2: colorSingleRed

out1: colorSingleRed

out2: colorSingleBrown

In transaction1 in my setup, your microsoft shares would be lost as it's something mixed (colorSingle of transaction1.out1 is not "red" because it's mixed and neither is it "brown") (in your setup they would not be lost). We agree that in transaction2 they are kept, which is the format we should use.

That colorSingleRed is part of colorAssetMicrosoft is based on some kind of trust. That trust could be based on some protocol which ensures that only microsoft can add a colorSingle to colorAssetsMicrosoft. But the trust could also be based on abritrage opportunities. The challenge for us should be to leave that in the middle. I now agree that we should somehow in the wallet show items of colorAssetMicrosoft as belonging together.

[Albert Hendriks]

Proposal

What we would like to have

- colored payments

- colored automic swaps

- the ability to define the coloring

- the possibility for a wallet to know the colors (based on the coloring)

Scope 

- let's set it up in a way that allows for colored atomic swaps later on while removing that from scope for now.

- the coloring will be defined in a config file. It's not time to define a protocol for that yet.

- we want full colored payment functionality. For this it is required that both the sending and receiving party have configured the involved colors, or the colors will be lost.

Why this scope

I don't like the example I saw of colored atomic swaps. The whole protocol contains the process of broadcasting an offer etc, which is too specific and should be done by custom implementations. In most cases, a gui decides to initiate a trade. This gui/decision should be decoupled from the wallet. We don't care how people decide or communicate to do a swap. When we have decoupled the decision maker (which will run on the same device as the wallet) it should provide the remote transaction details to the wallet. We don't care how the decision maker gets that data. First we will provide an interface for the decision maker to the wallet (for atomic swaps). But that will also be done later. Once we have an interface for atomic swaps and colored payments are possible, there will be much interest from other people to implement decision makers that interface to the wallet on one side and to some new protocol on the other side.

Electrum

Electrum looks interesting. We have the client that's basically the wallet+gui and the server that's basically an adapter between the client and bitcoind. If I'm right, clients need to trust the server already. If not, the server can also run on the same device as the client. Which might be a good idea if we go for the first of the following options:

- we might not need to adapt the server (only the client).

  + adv: we don't need to adapt the server

  + adv: we don't need to adapt the protocol between server and client

  + disadv: lots of communication between server and client

  + disadv: we'll need to analyze blockchain on client (not sure if it's done there already)

- we can still choose to adapt the server

  + adv/disadv vice versa.

[Alex Mizrahi]

I think we have a different view on what is a color wrt a certain aspect. You see a color as something that's an asset group, whereas I see it as something that should exist naturally. We can decouple this!

I'd like to name my color "colorSingle". It's the colors that exist naturally by having single-genesis. There can never be misconception about what colorSingles a certain output is. Let's call your color "colorAsset". a colorAsset is simply a set of colorSingle.

Yes I know, there's a subtle difference between your definition of a color and colorAsset. Would you give in a little bit here for the sake of decoupling? This is the example:

OK, I like this idea, but I need to think a bit more about it...

Basically, the trade-off is that transactions might be bigger because we cannot merge outputs.

But, on the other hand, we have less problems with mixing colors, additional issues and color overlap.

Of course, we should prefer reliability and simplicity over efficiency (which might not be even a problem).

 

transaction2:

in1: colorSingleBrown

in2: colorSingleRed

out1: colorSingleRed

out2: colorSingleBrown

Did you reverse order intentionally or is it a typo?

 

[Yoni Johnathan Assia]

I believe The concept of colorSingle and ColorAsset can also be used in the future for multiple issuers, I.e :

ColorSingle a specific genesis transaction USDCoin, by one issuer

ColorSingle another txn by the same issuer

ColorSingle another txn by a 2nd issuer

In this case, there can be colorAsset, one that is only based on the colorSingle of the first issuer, and the 2nd that also includes the color single of the 2nd issuer.

In order for 2 parties to transact, they can only trade coins of txn that are included in the color definition they "accept".

This sort of creates for colored coins the ability to work like ripple in a decentralized way, for every asset you "trust" specific set of issuers. 

I believe this is something that color coins should support, as having multiple issuers significantly makes the p2p exchange more liquid and more decentralized.

--

[Alex Mizrahi]

This sort of creates for colored coins the ability to work like ripple in a decentralized way, for every asset you "trust" specific set of issuers. 

I believe this is something that color coins should support, as having multiple issuers significantly makes the p2p exchange more liquid and more decentralized.

Yes, this is something we wanted to have anyway.

Albert found a way to simplify protocol to support it from start, which is really great!

[Yoni Johnathan Assia]

This is amazing ! We can have a decentrelized exchange with decentrelized issuers as well, this means we can create real alts based on colored coins.

--

[Albert Hendriks]

> Did you reverse order intentionally or is it a typo?

Whoops, the order order is wrong indeed.

--

[Jorge Timón]

I like the concept of custom user asset definitions. The inflatable
asset issuer can always sign the new SingleColor with the same key and
broadcast that outside the chain. This seems more elegant for pruning,
so I'll stop to defend the issuer public Key definition format.
You can't really make fungible open binding orders without changing
bitcoin anyway, since you need to explicitly specify the output you
will receive your part from before signing.
The best you can do regardless of the color definition format is to
sign the same order for all the possible outputs that could fill it.
Only one of them can make it because the others can't double-spend
your input.

Ripple is just about transitive transaction with multiple assets
involved in the same atomic transactions, so we support that from the
beginning with the specifications we have.

Alice only needs to send 1 AAA to Bob, and Bob 1 BBB, to Carol, who
accepts BBBs as payment because she trust Bob and that's it.
The trust part can be easily implemented an upper layer, the custom
Asset definition could be one way to simulate it. What you can't do is
ripple open orders though.

I hope that the needed changes can be added at some point to the core
chain protocol after more people understand the potential of this
technology.

--
Jorge Timón

http://freico.in/

[Tamas Blummer]

I created a stand-alone (means no extra classes referred) java implementation of the coloring algorithm here:

https://github.com/bitsofproof/supernode/blob/master/api/src/main/java/com/bitsofproof/supernode/api/ColorRules.java

and test cases, in portable JSON format here:

https://github.com/bitsofproof/supernode/blob/master/api/src/test/resources/colorRules.json

I think this test format is suitable to document cases an implementation has to pass and reject. The unit test that is executed with every bits of proof build is here:

https://github.com/bitsofproof/supernode/blob/master/api/src/test/java/com/bitsofproof/supernode/api/ColorRulesTest.java

The class ColorRules is now used inside the bits of proof kernel to derive colors from inputs to outputs of a transaction. 

I believe that I addressed incompatibilities or bugs previously spotted by Alex definition. Let me please know if not.

[Alex Mizrahi]

I believe that I addressed incompatibilities or bugs previously spotted by Alex definition. Let me please know if not.

Sorry, i guess my spec was a bit confusing...

Formal definition of order-based coloring scheme is in sections "Recursive color tracking" and "Order-based coloring"

https://github.com/bitcoinx/colored-coin-tools/blob/master/colors.md#recursive-color-tracking

Formally: In a single transaction, transaction output is of color X when all matching inputs are of color X. Input is of color X if output it spends is of color X.

Input i matches output j when segmentsPS(input[i]), PS(input[i])+input[i].value] and[PS(output[j]), PS(output[j])+output[j].value] overlap.

Note that it is defined in such a way that color of one transaction output can be identified independently, it is NOT affected by coloring of other outputs in same transaction.

Basically you just need to find matching inputs and check whether they are of a same color. It doesn't matter whether coloring of other outputs is good or bad.

This means that when you're identifying colors of outputs you MUST NOT try to validate coloring.

There is a reason why it should work this way: client (or server) should not assume that it has information about all colors. So what appears as uncolored to it might appear as colored to other client. 

I mentioned it in the very first description of order-based coloring;

https://bitcointalk.org/index.php?topic=106449.msg1169974#msg1169974

----

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.

----

You might ask "What's about 'Rules for well-formed colored coin transactions' then?"

https://github.com/bitcoinx/colored-coin-tools/blob/master/colors.md#rules-for-well-formed-colored-coin-transactions

The thing is, this section is basically a recommendation on how to create colored coin transaction, not rules on how to identify colors!

Rules listed above allow one to preserve color labels even if some of parties involved have only partial information about colors involved. It is recommened for colored coin software to follow these rules, although it is not strictly necessary:

If you implement a p2p trade client you might want to check transaction against these rules to make sure that it looks good. But you aren't supposed to apply them to transactions which already exist in blockchain, as you cannot remove transactions from blockchain.

I hope you don't blame me too much for this confusion, after all I left hints like "formally" and "recommended"/"not strictly necessary".

[Tamas Blummer]

Thanks for the clarification Alex.

I focus at server trusting client at the moment, therefore a different knowledge of colors is not a concern.

It however becomes one if colors are issued on distinct servers, that are merged at a later point.

I will review the code with this in mind later.

Tamas

[Alex Mizrahi]

I focus at server trusting client at the moment, therefore a different knowledge of colors is not a concern.

It isn't related to trust between client and server.

Even if colored coins are issued on your server, they might be used in transactions made by other clients, so it is important that everybody uses same coloring...

Consider this example:

1. Colored coins, say, "XYZ tickets", were issued on your server.

2. User who uses client which works with your server obtained them.

3. He then sends these "XYZ tickets" to an address which belongs to a different user, which might be using a different client software, let's say ArmoryX.

4. ArmoryX implements p2ptrade, and so these "XYZ tickets" might be used in atomic coin swap transactions.... Say, they can be swapped for some GOLDcoins. 

5. After several such trades, "XYZ tickets" come back to a user who uses client working with your server.

6. But now to be able to identify "XYZ tickets" your server needs to be able to "parse" these atomic coin swaps which involved colors your server did not know about. GOLDcoins appear to your server as if they were uncolored coins. But it should not affect its ability to "parse: transactions.

E.g. suppose atomic coin swap which involved XYZ tickets and GOLDcoins had three color bands in this order:

1. GOLDcoins

2. XYZ tickets

3. uncolored Bitcoins

Since your server is not aware of GOLDcoins, it will appear as 

1. uncolored Bitcoins

2. XYZ tickets

3. uncolored Bitcoins

This shouldn't be a problem because all we care about is size of bands.

It is also possible that somebody will create a transaction where outputs of same color won't be adjacent.

We initially thought that it is unnecessary, but now as we have a formal definition of coloring, and as we have p2ptrade protocol, there is no reason to "ban" such transactions. And in fact they can be useful...

Thus some client might create a weird transaction like:

1. GOLDcoins

2. XYZ tickets

3. USDcoins

4. XYZ tickets

5. uncolored coins

(Why? I don't know. Maybe they are mixing coins. Maybe they are doing some multi-party trade.)

For your server it might appear as

1. uncolored

2. XYZ tickets

3. uncolored (or, maybe, USDcoins if you have definition of USDcoins)

4. XYZ tickets

5. uncolored

Again, there is no reason to not process this transaction correctly w.r.t. XYZ tickets.