300 BTC Coding Contest: Distributed Exchange (MasterCoin Developer Thread)

[HammerFist]

Like a real man, he only wants MasterCoins for his contest winnings

Atta boy! 

[1713991999]

1713991999

[1713991999]

1713991999

[dacoinminster]

Our first blog article giving you the latest updates and news in now available online!

Great article! Weekly updates will be a really helpful way to keep track of all things Mastercoin – thanks a lot for this.

I apologize that this thread does not yet reflect the new coding contest. I plan to change the OP and thread title to reflect whatever we are currently working on, and I'd like this to become the development thread (to separate it from the discussion thread). Rough sketch of the next coding contest is here: https://bitcointalk.org/index.php?topic=265488.msg3358444#msg3358444

I had a long phone-call this morning with the board, which was very productive (Ron's minutes from the meeting should be public soon), but that call put me behind on other obligations. I may be unresponsive/offline for awhile - sorry!

[dacoinminster]

I have updated this thread with the official rules about contest #2. My intention is to have all development-related discussion here, but I'm not going to be a jerk about it (if people post development stuff in the other thread, they might get a gentle reminder from me).

The other thread is now intended to be for general MasterCoin discussion.

Please take a look at the rules for this contest, and let me know if anything isn't clear. Note that I added one thing to the original proposal: for the PC clients we need both Linux and Windows to be supported.

Thanks!

-J.R.

[Tachikoma]

Tachikoma:
Just a minor order issue on http://mastercoin-explorer.com/
http://mastercoin-explorer.com/transactions/69a67d4840cb5e9ea75c8bc4ea6aeb0985d5dc1d710c8de7b0771360b6968f44 has position 176 and
http://mastercoin-explorer.com/transactions/766646269feb962c95dd38e163158b658aad0520cb5bcb4e0d2d01a868a5c2b6 has position 178
but you show them in the wrong order.

In the wrong order where exactly?

On the main page http://mastercoin-explorer.com/  69a67d appears before 766646 but 69a67d is older.

Thanks, updated it.

[Tachikoma]

I've simulated 200.000 simple send public keys to make sure brute-forcing is viable, the highest sequence I needed was 19.

Here is the distribution over a 20.000 sample set. Where k is amount of sequence alterations needed and v the amount of keys.

Code:

{0=>10005, 2=>2511, 4=>649, 1=>5032, 3=>1208, 7=>64, 5=>309, 8=>37, 6=>136, 9=>23, 10=>13, 11=>9, 12=>3, 13=>1}

[grazcoin]

Tachikoma:
Just a minor order issue on http://mastercoin-explorer.com/
http://mastercoin-explorer.com/transactions/69a67d4840cb5e9ea75c8bc4ea6aeb0985d5dc1d710c8de7b0771360b6968f44 has position 176 and
http://mastercoin-explorer.com/transactions/766646269feb962c95dd38e163158b658aad0520cb5bcb4e0d2d01a868a5c2b6 has position 178
but you show them in the wrong order.

In the wrong order where exactly?

On the main page http://mastercoin-explorer.com/  69a67d appears before 766646 but 69a67d is older.

Thanks, updated it.

good
now to the next difference between http://mastercoin-explorer.com/ and http://masterchain.info/
http://mastercoin-explorer.com/transactions/28ffa93e3d3091f7c501585fd741327d3c58ef3f45bcd94f72166889798283cf claims that the tx is valid but
http://masterchain.info/tx/28ffa93e3d3091f7c501585fd741327d3c58ef3f45bcd94f72166889798283cf.json says that the tx has an ambiguous sequence [119, 119, 120]

[Tachikoma]

I'm currently not implementation sequence checking in that regard, I hope to convince J.R. it's not the best solution. If it becomes part of the spec I will implement it as well. But as I said in the other topic I don't really agree with it.

[grazcoin]

I've simulated 200.000 simple send public keys to make sure brute-forcing is viable, the highest sequence I needed was 19.

Here is the distribution over a 20.000 sample set. Where k is amount of sequence alterations needed and v the amount of keys.

Code:

{0=>10005, 2=>2511, 4=>649, 1=>5032, 3=>1208, 7=>64, 5=>309, 8=>37, 6=>136, 9=>23, 10=>13, 11=>9, 12=>3, 13=>1}

I see that the brute force for getting a valid point is indeed shorter/simpler with compressed pubkey.
Still I would prefer to limit the amount of outputs we use from 4 to 3.
What about sending all the change to the multisig output instead of having another change output? Will this be considered a valid tx by your parser?
And what about encoding the recipient address in a remaining place of the second pubkey + using a third pubkey (reducing another output?)

[Tachikoma]

Multisig outputs are currently hard to spend, the reference client has no Gui support for it. It will need to be build into a Mastercoin wallet to make it easier. I think we better wait until there are some stable-ish wallets out before doing this.

Simple sends transactions would have plenty of space in the output for a target address, other messages however might not have enough space. Perhaps we can support both? If there is room in the multisig use that as target address, if not use an other output.

[grazcoin]

Multisig outputs are currently hard to spend, the reference client has no Gui support for it. It will need to be build into a Mastercoin wallet to make it easier. I think we better wait until there are some stable-ish wallets out before doing this.

Simple sends transactions would have plenty of space in the output for a target address, other messages however might not have enough space. Perhaps we can support both? If there is room in the multisig use that as target address, if not use an other output.

I have showed already in https://github.com/grazcoin/mastercoin-tools/blob/master/NOTES how to spend multisig using the sx, and my wallet will support (eventually) also multisig as input, so:
I prefer that we support both - extra change address (like your current implementation) as well as change inside the multisig.

I am also for supporting both extra target address (like your current implementation) as well as embedded target address whenever possible.

dacoinminster: do we get an OK here?

[Tachikoma]

Multisig outputs are currently hard to spend, the reference client has no Gui support for it. It will need to be build into a Mastercoin wallet to make it easier. I think we better wait until there are some stable-ish wallets out before doing this.

Simple sends transactions would have plenty of space in the output for a target address, other messages however might not have enough space. Perhaps we can support both? If there is room in the multisig use that as target address, if not use an other output.

I have showed already in https://github.com/grazcoin/mastercoin-tools/blob/master/NOTES how to spend multisig using the sx, and my wallet will support (eventually) also multisig as input, so:

It's not hard for us to do, but for somebody who needs a GUI to make payments it will be. Until we have a user friendly way to do it I rather not support it yet. But let's see what J.R. has to say about the topic :}

[zathras]

I've simulated 200.000 simple send public keys to make sure brute-forcing is viable, the highest sequence I needed was 19.

Here is the distribution over a 20.000 sample set. Where k is amount of sequence alterations needed and v the amount of keys.

Code:

{0=>10005, 2=>2511, 4=>649, 1=>5032, 3=>1208, 7=>64, 5=>309, 8=>37, 6=>136, 9=>23, 10=>13, 11=>9, 12=>3, 13=>1}

Thanks Tachikoma, this also reflects my testing (I ran a much larger set after posting).  Given Peter's feedback also I think it's very unlikely we're not going to be able to churn a public key into a valid ECDSA point with my proposed byte rotation technique.

As per my previous posts, I propose we adopt this as the method for making our keys ECDSA valid.

The question then becomes one of what we put before the last byte (ie do we encrypt/obfuscate), and how much effort to we go to make it look like random data.

If we already run brute force iterations to make the pubkey valid, we could consider doing the same for the non-compressed pubkeys (MIP1) and have 2 outputs instead of 4, plus extra place for future required data. I didn't check how much more iteration that would take, but it would add much less contamination to the blockchain.

We're using compressed keys so we only have to worry about the X co-ordinates and can thus store data - that's kind of the point.  If we had to make a valid ECDSA key from an uncompressed key, let's take example mastercoin X co-ordinates of 0100000014000000020000000005f5e10000000000000f424006000000000000.  The y co-ordinates must be 4B808A82AA5574B899D629F4EC7D77B044D75230FD13C7530F2E6CA5E03D95C8 - we can't change these and still remain ECDSA valid so there is no data we can embed here, and if we can't embed data in the Y co-ordindates, what's the value in using them?  This is why I've personally never viewed uncompressed keys as viable - but hey, I'm certainly not the authority on these matters so happy to be corrected

Is this really necessary? We have no control over the sequence number for a change address, is it fair to disregard a transaction based on random luck? I would like to propose to do a sanity check before invalidating a transaction based on sequence. You could try to decode the address and see if the transaction_type and the other options based on that transaction_type make sense. If one of the addresses with the same sequence for instance does that, but an other does not you know which one is the data address and which one the target. If that also fails it seems safe to flag it as invalid but I think we should try harder before falling back to invalid.

It's not really about removing ambiguity about which address is the data address, the sequence numbers and the requirement that they not be all in continuous sequence are for ensuring we always pick the right reference (destination) address.  If we have ambiguous sequence numbers then sure we can decode each address to look for the data, but how do we know we're sending the mastercoins to the right recipient and not to the change address?  Note in simple sends change doesn't need to = sending address.  Example based on change and reference having the same sequence number.

Edit for clarity.

[grazcoin]

I'm currently not implementation sequence checking in that regard, I hope to convince J.R. it's not the best solution. If it becomes part of the spec I will implement it as well. But as I said in the other topic I don't really agree with it.

It is a good idea to avoid sending such a tx in the first place, but once such a tx got sent, there is no clear way to differ which output is which, and a good solution is to consider the tx as invalid.

[grazcoin]

Multisig outputs are currently hard to spend, the reference client has no Gui support for it. It will need to be build into a Mastercoin wallet to make it easier. I think we better wait until there are some stable-ish wallets out before doing this.

Simple sends transactions would have plenty of space in the output for a target address, other messages however might not have enough space. Perhaps we can support both? If there is room in the multisig use that as target address, if not use an other output.

I have showed already in https://github.com/grazcoin/mastercoin-tools/blob/master/NOTES how to spend multisig using the sx, and my wallet will support (eventually) also multisig as input, so:

It's not hard for us to do, but for somebody who needs a GUI to make payments it will be. Until we have a user friendly way to do it I rather not support it yet. But let's see what J.R. has to say about the topic :}

I suggested supporting additionally the "compressed tx" (2 or 3 outputs) while keeping the "uncompressed tx" (4 outpus) as well.
GUI users could still use the "uncompressed tx".
I just don't want to develop the "compressed tx" if you guys don't intend to support it.

[grazcoin]

We're using compressed keys so we only have to worry about the X co-ordinates and can thus store data - that's kind of the point.

Thanks. I have already agreed to go for the compressed pubkeys:

I see that the brute force for getting a valid point is indeed shorter/simpler with compressed pubkey.

And http://masterchain.info reflects that.

[Tachikoma]

I suggested supporting additionally the "compressed tx" (2 or 3 outputs) while keeping the "uncompressed tx" (4 outpus) as well.
GUI users could still use the "uncompressed tx".
I just don't want to develop the "compressed tx" if you guys don't intend to support it.

What problem are you solving by encoding the receiving address in the public key?

I rather spend time working on implementing more of the protocol then rewriting the way we encode it at this moment.

[zathras]

Multisig outputs are currently hard to spend, the reference client has no Gui support for it. It will need to be build into a Mastercoin wallet to make it easier. I think we better wait until there are some stable-ish wallets out before doing this.

Simple sends transactions would have plenty of space in the output for a target address, other messages however might not have enough space. Perhaps we can support both? If there is room in the multisig use that as target address, if not use an other output.

I have showed already in https://github.com/grazcoin/mastercoin-tools/blob/master/NOTES how to spend multisig using the sx, and my wallet will support (eventually) also multisig as input, so:

It's not hard for us to do, but for somebody who needs a GUI to make payments it will be. Until we have a user friendly way to do it I rather not support it yet. But let's see what J.R. has to say about the topic :}

I suggested supporting additionally the "compressed tx" (2 or 3 outputs) while keeping the "uncompressed tx" (4 outpus) as well.
GUI users could still use the "uncompressed tx".
I just don't want to develop the "compressed tx" if you guys don't intend to support it.

We have to be a little careful here - if we include change in the multisig then unless we immediately redeem it, users will see their bitcoin balance drop by changeamount which could cause confusion and fear.  With the current method the bitcoin balance never drops as we return change in the original transaction.

As I've made a lot of posts on the topic, to summarize my proposed spec changes in simple form:

* We use only compressed keys (sounds like we have consensus on this now, thanks Grazcoin)
* We use only ECDSA valid points (eg via my suggestion to rotate the last byte)
* We obfuscate the data so it appears like a random key, but do not invest too much effort in encryption as censorship essentially boils down in its simplest form to miners blocking transactions with an output to Exodus

Points 1 & 2 are easy (eg I know Tachikoma and I both already have code that does this and it shouldn't be too much work for grazcoin).  Point 3 may take a little more effort depending on just how far we go to make the key look 'real'.

JR, care to weigh in?

Thanks!

[zathras]

I suggested supporting additionally the "compressed tx" (2 or 3 outputs) while keeping the "uncompressed tx" (4 outpus) as well.
GUI users could still use the "uncompressed tx".
I just don't want to develop the "compressed tx" if you guys don't intend to support it.

What problem are you solving by encoding the receiving address in the public key?

I rather spend time working on implementing more of the protocol then rewriting the way we encode it at this moment.

FWIW I agree to a point - I think your multsig is the right way for us to do it (at least until other more suitable opcodes become standard).  With that said I think we need not to rewrite encoding, but to refine it so we keep ECDSA valid points and don't have obvious ascii data in the pubkey.

Sorry if I'm sounding like a broken record, I just want to make sure we build the mastercoin house on a solid foundation

Thanks!

[dacoinminster]

Replying to some development-related stuff from the other thread . . .

Paid or not Peter this is extremely helpful, thank you (though it will take multiple readings for me to even remotely try to understand it all!).  

JR, without wanting to be badgering I feel this is the most critical issue for mastercoin right now.  How we store data in the blockchain is fundamental and should be locked away as early as possible (and ideally written into the spec).  As you made that the number one goal of the first coding contest I'm guessing you feel the same  Tachikoma's work is great but perhaps we could refine it somewhat - in development we're spitting out invalid ECDSA points in multi-sigs some of the time and as Jeff has raised above, pubkey checking is on the way regardless of mastercoin.

As I've mentioned before I view the miners as our critical issue and if some of the major pools are doing things like looking for obvious compressable/text data as Peter notes, perhaps some further investigation into steganography (an apt analogy I think) would be in order - obfuscating the data we're storing in the pubkey (IMO) seems quite achievable and spotting our padding ("000000000" etc) isn't going to be hard.

Thoughts?

I agree that Peter's comments are extremely helpful. I think  you guys are on the right track (massaging Tachikoma's multisig method output until it is valid). I can offer some general guidelines here:

• We don't want to to anything that can be easily blocked without specifically targeting MasterCoin. For instance anything which could be screened out by a validity check, or a "too much ASCII" check
• We can't really worry about blacklists. If something like that happens, we have a few options. The Exodus Address can always be changed. We could even get rid of it altogether, although that would make finding MasterCoins transactions MUCH more difficult (we'd have to watch the transactions from any address which holds MasterCoins).
• We also have the "nuclear option" of returning to the original spec (spending to fake addresses), but I don't think that will be needed.
• All clients should be generous with fees to bitcoin miners by default. We want to create a situation where an anti-mastercoin stance by a miner should be very expensive for them!

Found the problem, the official spec is still not updated. This makes it a lot harder for new developers (and developers who forget stuff...)

J.R. Could you please update the spec with all the new data packet order stuff and the new validation rules? (broken sequence, ambiguous sequence etc.)

Rolling out fix in the next few minutes.

Edit:

Transaction should be fixed.

I somehow missed part of the sequence discussion.

If there is a broken sequence (i.e. 3,4,8), then the odd-man-out is the change address (8 in this example)
If there is an ambiguous sequence (i.e. 3,4,4), then the transaction is invalid!
If there is a perfect sequence (i.e. 3,4,5), then the transaction is invalid!

Is this really necessary? We have no control over the sequence number for a change address, is it fair to disregard a transaction based on random luck? I would like to propose to do a sanity check before invalidating a transaction based on sequence. You could try to decode the address and see if the transaction_type and the other options based on that transaction_type make sense. If one of the addresses with the same sequence for instance does that, but an other does not you know which one is the data address and which one the target. If that also fails it seems safe to flag it as invalid but I think we should try harder before falling back to invalid.

Sorry for the out-of-date spec. Fixing this (and adding some new stuff) is at the top of my list.

Note that the sequence number of the change address only needs to be considered when the change amount is exactly the same as all the other outputs. Invalidating a MasterCoin transaction because the change amount just happens to be 0.00006 BTC AND a bad sequence number should be exceedingly rare.

Multisig outputs are currently hard to spend, the reference client has no Gui support for it. It will need to be build into a Mastercoin wallet to make it easier. I think we better wait until there are some stable-ish wallets out before doing this.

Simple sends transactions would have plenty of space in the output for a target address, other messages however might not have enough space. Perhaps we can support both? If there is room in the multisig use that as target address, if not use an other output.

I have showed already in https://github.com/grazcoin/mastercoin-tools/blob/master/NOTES how to spend multisig using the sx, and my wallet will support (eventually) also multisig as input, so:

It's not hard for us to do, but for somebody who needs a GUI to make payments it will be. Until we have a user friendly way to do it I rather not support it yet. But let's see what J.R. has to say about the topic :}

Spending multisig bitcoins is painful right now, and I'd rather avoid that extra complexity until it isn't painful. Let's keep that extra output to the destination address for now. I think that supporting two different encoding methods will end up increasing the testing burden dramatically, and I'd rather not do that yet.

Let me see if I understand the current proposal:

We are (if I understand it correctly) taking Tachikoma's proposed multisig, then for each key after the first one we change the sequence number until we get a valid ECDSA point? Can anybody explain why this problem only affects keys after the first one (sorry if I missed this somewhere)?

Current valid transactions (not using multisig) have the last data packet sequence number before the target address be n-1. Theoretically, earlier data packets would have had n-2, n-3, all the way back to the first data packet (although simple send never has more than one data packet). Perhaps for multi-sig we should change this paradigm. It might be easier to start at the sequence number of the destination/target address, then increment up from there. If a given sequence number does not pass our "valid ECDSA" test, we just go on to the next one. Is that what you guys are doing already?

It sounds like this method significantly reduces how much data we can potentially store per transaction. Can anybody give a guess as to what a reasonable upper bound for how much data we should try to store using this method in a single transaction?

[dacoinminster]

Multisig outputs are currently hard to spend, the reference client has no Gui support for it. It will need to be build into a Mastercoin wallet to make it easier. I think we better wait until there are some stable-ish wallets out before doing this.

Simple sends transactions would have plenty of space in the output for a target address, other messages however might not have enough space. Perhaps we can support both? If there is room in the multisig use that as target address, if not use an other output.

I have showed already in https://github.com/grazcoin/mastercoin-tools/blob/master/NOTES how to spend multisig using the sx, and my wallet will support (eventually) also multisig as input, so:

It's not hard for us to do, but for somebody who needs a GUI to make payments it will be. Until we have a user friendly way to do it I rather not support it yet. But let's see what J.R. has to say about the topic :}

I suggested supporting additionally the "compressed tx" (2 or 3 outputs) while keeping the "uncompressed tx" (4 outpus) as well.
GUI users could still use the "uncompressed tx".
I just don't want to develop the "compressed tx" if you guys don't intend to support it.

We have to be a little careful here - if we include change in the multisig then unless we immediately redeem it, users will see their bitcoin balance drop by changeamount which could cause confusion and fear.  With the current method the bitcoin balance never drops as we return change in the original transaction.

As I've made a lot of posts on the topic, to summarize my proposed spec changes in simple form:

* We use only compressed keys (sounds like we have consensus on this now, thanks Grazcoin)
* We use only ECDSA valid points (eg via my suggestion to rotate the last byte)
* We obfuscate the data so it appears like a random key, but do not invest too much effort in encryption as censorship essentially boils down in its simplest form to miners blocking transactions with an output to Exodus

Points 1 & 2 are easy (eg I know Tachikoma and I both already have code that does this and it shouldn't be too much work for grazcoin).  Point 3 may take a little more effort depending on just how far we go to make the key look 'real'.

JR, care to weigh in?

Thanks!

I agree with this approach, but I'm curious how we would obfuscate (point 3). That might be something to do later . . .

Edit: Does byte rotation mean we can still use all sequence numbers? It sounds like we'd be sacrificing the last byte of every key, which seems like a good tradeoff to be able to store data for every sequence number.