Paper on marker addresses (aka green addresses)

[jav]

Paper

I have summarized the ideas around green addresses (I decided to call them marker addresses going forward) in a paper which got accepted and will be presented at a Bitcoin workshop & tutorial organized by Professor Clemens Cap of the University of Rostock. The workshop will take place on September 20th.

  Paper: http://www.bitcoinmonitor.com/static/paper/marker-addresses.pdf
  Workshop website: http://bitcoin.uni-rostock.de/index.php?site=callforpapers_en

Marker/Green addresses are a proposal for a simple method of allowing a Bitcoin sender to identify herself to a recipient, to be used in cases where two parties have a trust relationship and want to recognize each other's transactions for special treatment (usually instant confirmation). They have been discussed before on this forum primarily in these two threads:

  https://bitcointalk.org/index.php?topic=32818.0
  https://bitcointalk.org/index.php?topic=48170

Implementation: Receiving

Since finishing the paper, I have been working some more on the implementation side of things (based on bitcoind git tag v0.6.3). For the receiving side (recognizing marker addresses on incoming transactions) I have implemented an "getorigins" RPC call:

  https://github.com/javgh/bitcoin/tree/bw-getorigins
  ( diff to v0.6.3: https://github.com/javgh/bitcoin/compare/bw-master...bw-getorigins )

If you give getorigins a txid, it will (if the transaction has a suitable structure) display the addresses from where the coins came. For example for this transaction from Mt.Gox, where the green address feature was enabled, it returns this:

Code:

./bitcoind getorigins 162d25037687be593e1be27bf79583afa5141c7fcd168e068501f162d2016c9a

{
    "confirmations" : 39,
    "blockhash" : "00000000000003cb80e379d5fae8e19c2594d35881ec21ff54847d99e6894671",
    "blockindex" : 110,
    "txid" : "162d25037687be593e1be27bf79583afa5141c7fcd168e068501f162d2016c9a",
    "time" : 1344887758,
    "origins" : [
        "1LNWw6yCxkUmkhArb2Nf2MPw6vG7u5WG7q"
    ]
}

You would then check if a known green/marker address appears somewhere in the list. Here we see 1LNWw6yCxkUmkhArb2Nf2MPw6vG7u5WG7q, which is the green address currently used by Mt.Gox. In the case of Mt.Gox the whole transaction is funded from that address, but the way the paper describes the technique it might just be one of the addresses appearing in the list.

Implementation: Sending

The sending part is still a little bit hacky. My code has a marker address hardcoded and expects that the local wallet has the necessary keys for it. It will then

• Always try to add a single 0.01 BTC from that address to any outgoing transaction and an additional output sending it back. If this is not possible, the transaction creation will fail. It will resort to using marker coins with zero confirmations, if no others are available.
• Mark those incoming transactions to the marker address as change, so that they do not appear in "listtransactions".
• Prevent marker coins (coins at the marker address) from being used in any other way for a transaction, so that the marker address does not get depleted.  
• Add an extra option to "getbalance", which shows the actual available balance after subtracting marker coins.

  https://github.com/javgh/bitcoin/tree/bw-markeraddress
  (diff to v0.6.3: https://github.com/javgh/bitcoin/compare/bw-master...bw-markeraddress

The transaction http://blockchain.info/tx-index/15610835/5fcc25b576547aafddc1fed22d27259478d6c000540cb458df44c629eb10bd0b?show_adv=true is an example for a marker transaction created in this way. In this case the marker address is 1MAbwuYp8CPChJ1ua25tnEKXkfXTVqEoyg.

Future work

I am working on a new Bitcoin project which will also make use of marker addresses. I hope some nice demonstrations will come out of that, but that's still a couple of months off.

Comments, questions and other feedback is appreciated! :-)

[gmaxwell]

I am working on a new Bitcoin project which will also make use of marker addresses. I hope some nice demonstrations will come out of that, but that's still a couple of months off.
Comments, questions and other feedback is appreciated! :-)

Thats unfortunate, because they're really a bad idea.

There are multiple problems with marker addresses but foremost among them is that they're incompatible with Bitcoin's privacy model and their use harms the privacy of not only the people who use them but also people who transact with people who use them (and so on, transitively with decaying harm). They also encourage poor key management practices (e.g. constantly assigning funds to a long term online key which is potentially subject to theft), and an additional burden on the public network to convey store additional information that is only interesting to a single pair of parties.

We added the signmessage feature in order to have detached, private, identification authentication available. Rather than in-band marking a party can trivially sign a transaction ID with an address reserved for that purpose and then pass it over whatever mechanism they like (including appending the signature to the normal transaction ID they display).   This avoids all of the concerns above related to marker addresses.

[davout]

I think it's great.

There are multiple problems with marker addresses but foremost among them is that they're incompatible with Bitcoin's privacy model and their use harms the privacy of not only the people who use them but also people who transact with people who use them (and so on, transitively with decaying harm).

There is no such thing as a "bitcoin privacy model". There are steps one can take to improve the anonymous properties of Bitcoin. The green address system is opt-in.

They also encourage poor key management practices (e.g. constantly assigning funds to a long term online key which is potentially subject to theft),

That somewhat goes with the "instant transfer" feature, I don't think you can really have this without leaving some key online at some point. You could still mitigate that risk by using a multiple signature address as marker address.

and an additional burden on the public network to convey store additional information that is only interesting to a single pair of parties.

"conveying information that is only interesting to a single pair of parties" is pretty much what Bitcoin already does. At the end of the day it's the market that will decide what's a fair price for this additional bit of information. It seems logical that instant transactions between green-address aware parties might cost a little more.

We added the signmessage feature in order to have detached, private, identification authentication available. Rather than in-band marking a party can trivially sign a transaction ID with an address reserved for that purpose and then pass it over whatever mechanism they like (including appending the signature to the normal transaction ID they display).   This avoids all of the concerns above related to marker addresses.

You just need blockexplorer or a similar tool to validate a green address transfer which is much simpler than validating a detached signature.

[Pieter Wuille]

What this does in essence, is using the block chain as a communication channel for private information. That may seem to be an easy solution right now, because of how the current Bitcoin infrastructure operates, but it has so many disadvantages (like gmaxwell already described).

The root of the problem - in my opinion - is the fact that the only widely-supported way of doing a bitcoin transaction, is in fact already by using the block chain as a communication channel. Satoshi originally envisioned that transactions would be done using a pay-to-IP-address protocol, and not via pay-via-blockchain-to-public-key-hash (what we do now). In many ways, pay-to-IP is far superior, however:

• It sends the transaction directly to the one who needs it, instead of forcing him to scan the entire blockchain for things that look like a payment to him.
• It moves the responsability for getting the transaction accepted to the only one who cares about that.
• It allows adding comments, order id's, or whatever message you like to the transactions (including proof that it comes from a trusted party), completely private, and without bloating a very expensive distributed database (the block chain).

Over time, however, pay-to-IP had many shortcomings, and became obsolete, and eventually disabled.

I think it is time we introduce a new way for doing direct payments, with the advantages of pay-to-IP, but properly authenticated and secured. I don't think the solution is tagging the Bitcoin transaction itself (which only requires data necessary for the world to validate it) with data that decreases the privacy of the entire system.

[gmaxwell]

There is no such thing as a "bitcoin privacy model".

There absolutely is, http://bitcoin.org/bitcoin.pdf  Section 10.

The green address system is opt-in.

Only partially. The sender can opt-in. The receiver gets it if sender chose, if they like it or not. Further downstream users— who's identity is now more disclosed by association with a named entity in the block-chain— don't really get a say at all.  The hundreds of thousands of other uninterested nodes will waste cpu cycles validating these signatures (and the pointless transactions required to create the inputs) and storage recording them, even those these transactions do not serve to further their interests in the way that general blockchain validation does.  They could, of course, filter out the ones that they're aware of, but unless they all do it they'll be forced to validate them when they are mined or risk their security.

There are many sources of cost here and most of them are externalized.

They also encourage poor key management practices (e.g. constantly assigning funds to a long term online key which is potentially subject to theft),

That somewhat goes with the "instant transfer" feature, I don't think you can really have this without leaving some key online at some point. You could still mitigate that risk by using a multiple signature address as marker address.

It doesn't.  A transaction requires only the keys being online that sign for the particular input coins.  Prudent key management would have those keys used only once.   A marker address is a long term key.  In-band marker address usage requires constantly assigning funds do a long term key.  It's a bad practice and increases the exposure to theft, if only marginally.

"conveying information that is only interesting to a single pair of parties" is pretty much what Bitcoin already does. At the end of the day it's the market that will decide what's a fair price for this additional bit of information. It seems logical that instant transactions between green-address aware parties might cost a little more.

Bitcoin has gone to rather extraordinary lengths to avoid including any more data than strictly necessary in the globally and eternally visible flooded blockchain. The only data included is the minimum required to have the system be fully decentralized, secure, and inflation proof. This information is in the interest of all bitcoin users: we want to protect you from double spends because we want to prevent inflation in order to make Bitcoin useful.  If it were believed to be viable to include a memo field in transactions there would be one; it isn't like the usefulness of them is a surprise (the old IP transactions had a memo field, in fact, but they never showed up in the public network.)

There is no mechanism available to directly compensate most of the parties that undertake the costs created by a third party's use of in-band marker addresses.

You just need blockexplorer or a similar tool to validate a green address transfer which is much simpler than validating a detached signature.

There is no reason that other schemes can't be made just as easy— or even easier, since they have a chance of being integrated. Validating a detached signature using blockexplorer could be as simple as following a link.  E.g. With a simple bit of JS,  http://blockexplorer.com/tx/eb620fe4cdc24afbd2ded229577c64fbb099a39e80bcc15750b84c04b7878d90#G7mlJ2Db1W68LQPkqNt0UAyEE9xNI4KVMxy/GSwI/TU8GH2rUzs7jKFr9yq6M43zsKUHlqIF9HQ1pypvWpuUg8E=   could display  "This transaction is certified against reversal by 1GMaxweLLbo8mdXvnnC19Wt2wigiYUKgEB"

Of course, as Pieter points out— payment protocols are even more powerful. There are a lot of superior options.

My concern is that things like inband-marker addresses discourage the implementation of better solutions which have fewer compromises simply because it has a lower startup cost.  As a community we need to resist that kind of lazyness if we're to keep our system healthy.

Edit: With some code from Joric, I setup exactly the validation I described above. The signature checking is all client side, so the normal operaiton of the site doesn't even cause them to learn the relevant marker addresses being checked unless they go out of their way to inject monitoring code.

[pc]

Without commenting on the usefulness of marker addresses versus other methods of transmitting sender information…

Does your sending code make sure that its inputs are very confirmed before it "signs" the transaction with its marker address?

[davout]

There is no such thing as a "bitcoin privacy model".

There absolutely is, http://bitcoin.org/bitcoin.pdf  Section 10.

The green address system is opt-in.

Only partially. The sender can opt-in. The receiver gets it if sender chose, if they like it or not. Further downstream users— who's identity is now more disclosed by association with a named entity in the block-chain— don't really get a say at all.  The hundreds of thousands of other uninterested nodes will waste cpu cycles validating these signatures (and the pointless transactions required to create the inputs) and storage recording them, even those these transactions do not serve to further their interests in the way that general blockchain validation does.  They could, of course, filter out the ones that they're aware of, but unless they all do it they'll be forced to validate them when they are mined or risk their security.

There are many sources of cost here and most of them are externalized.

[...]

My concern is that things like inband-marker addresses discourage the implementation of better solutions which have fewer compromises simply because it has a lower startup cost.  As a community we need to resist that kind of lazyness if we're to keep our system healthy.

Edit: With some code from Joric, I setup exactly the validation I described above. The signature checking is all client side, so the normal operaiton of the site doesn't even cause them to learn the relevant marker addresses being checked unless they go out of their way to inject monitoring code.

You make good points but regardless, it will happen if there is a use for it, if it fits in the existing protocol, if it's easy to implement (applying a patch to the source counts as easy), and if it's cost-effective. Some other options are superior, but this one would be good enough for lots of folks.

Looks fairly easy to implement, and maybe miners will see an opportunity to charge higher fees. Might not be good for the performance of subsequent tx validations, but that's irrelevant since miners have no economic incentive, that I know of, to facilitate tx validation for other peers.

Of course, built-in out-of-band authentication would be neat

[pc]

If miners are going to charge for it anyway, then one might as well use transactions of 0 BTC instead of 0.01 BTC for the marker address input/output. The only reason to have it be 0.01 is that it avoids the too-small-transaction fee on a transaction that would otherwise be free.

[jav]

Thanks for your criticism. One clarification regarding the problem of "constantly assigning funds to a long term online key which is potentially subject to theft": This reads like it might talk about the original technique? In this current proposal the marker address only holds a number of 0.01 BTC coins.

But in general I totally see the problematic parts regarding privacy and increased store requirements - I even said as much in the paper. So I am all for specifying a proper out-of-band payment mechanism with all the bells and whistles one would like.

But this is how I see it: Personally I think a decent solution for some type of instant transactions would open up the possibility for a whole new set of applications. On the other hand my impression is, that many people would disagree with this assessment and argue instead, that standard unconfirmed transactions are already good enough for anything one might want to do.

Because of this, I fear that the development of a out-of-band payment mechanism focused on instant payments will proceed very slowly and have a hard time achieving enough participants.

That's why I propose this as a stop-gap solution. It will hopefully prove that something like this is necessary and also make it clear in which situations it is typically used. With this information that a) there is a real need and b) a good understanding of the requirements, one can then go on and define a suitable out-of-band payment mechanism.

Is there a risk that we are stuck with this forever? I don't know, I don't find that very likely. It's too much of a hack that one wouldn't jump at upgrading to something more elegant, in my opinion. So I am sorry to hear if some people consider it actively harmful, but at the moment I plan on continuing to push this. But I'm looking forward to participate and switch to any other better solution that is emerging.

Does your sending code make sure that its inputs are very confirmed before it "signs" the transaction with its marker address?

It uses the standard algorithm that bitcoind uses to select coins. So it might select coins with as few as one confirmation, if I remember correctly. It would be possible to adjust that, if one wants to be extra careful.

[pc]

Does your sending code make sure that its inputs are very confirmed before it "signs" the transaction with its marker address?

It uses the standard algorithm that bitcoind uses to select coins. So it might select coins with as few as one confirmation, if I remember correctly. It would be possible to adjust that, if one wants to be extra careful.

The concern is that if the trusted service used its marker address on a transaction, but one of the inputs to that transaction became invalid (because somebody did a double-spend on its transaction to the service), then the transaction becomes invalid and the service may no longer be trusted. It somewhat depends on whether somebody relying on the marker address is a contract of "I promise that this transaction will stay valid" or "I promise that if this transaction becomes invalid, I will issue another transaction in its place so that the same money gets transferred."