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

[zathras]

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?

Regarding the output amounts & change, we've already removed the requirement for outputs to be the same amount in an earlier effort (ref).

The ECDSA issue affects the first key same as any other.  The last byte rotation method (ref) gives us all available sequence numbers at the cost of the last byte.  In total I think Tachikoma & I have tested a combined million plus keys with this method successfully.  I believe my suggestion solves the ECDSA point validity issue for good.

As to obfuscation - that's how we avoid obvious ascii (eg "000000") - the method has not yet been decided upon, I'm just advocating for it's use right now - if we agree on the need for it, we can focus on the how.

Excuse spelling/grammar in this post, I'm currently sitting in a keynote typing this on a tablet

[1714797839]

1714797839

[1714797839]

1714797839

[1714797839]

1714797839

[dacoinminster]

Regarding the output amounts & change, we've already removed the requirement for outputs to be the same amount in an earlier effort (ref).

The ECDSA issue affects the first key same as any other.  The last byte rotation method (ref) gives us all available sequence numbers at the cost of the last byte.  In total I think Tachikoma & I have tested a combined million plus keys with this method successfully.  I believe my suggestion solves the ECDSA point validity issue for good.

As to obfuscation - that's how we avoid obvious ascii (eg "000000") - the method has not yet been decided upon, I'm just advocating for it's use right now - if we agree on the need for it, we can focus on the how.

Excuse spelling/grammar in this post, I'm currently sitting in a keynote typing this on a tablet

I see from your first referenced post that you require the change address to be the same as the sending address. Since we are reusing addresses all over the place (including the Exodus Address) I don't see any problem with doing that. We'll never get a sequence number collision that way. Any objections on this?

One way to avoid looking like ASCII without a lot of work would be to flip (XOR) the most-significant bit of every byte. This would be essentially zero cost to us, and would make all ASCII characters non-ASCII (and many non-ASCII characters would consequently become ASCII). How does that sound? We could also just XOR everything (flip every bit we store), if that seems simpler.

I realize that the spec is overdue for a revision - this stuff will go in there for sure

[dacoinminster]

Another idea for obfuscation: instead of always flipping the most significant bit or flipping all bits (XOR with 0x80 or 0xFF), we could XOR with data which can only be known to someone parsing MasterCoin transactions. For instance, what if we run the user's MSC balance through SHA256, and then XOR that with the data that is being encoded. Only someone who knows the MasterCoin balance of the address could tell if the address was sending a MasterCoin transaction (aside from the Exodus Address tell, which could also be obfuscated if desired) . . .

That's probably too complicated for now, but if we get into a war with miners trying to exclude us, we have a LOT of options.

[Bitoy]

For the distributed exchange. Smart Property

1. Transaction type = 50 for creating new property (32-bit unsigned integer, 4 bytes)
2. Property Type = 1 for indivisible shares (2 is divisible currency) (32-bit unsigned integer, 4 bytes)
3. Property Name = “ master miner corp.  \0” (21 bytes)
4. Number Properties = 1,000,000 indivisible shares (64-bit unsigned integer, 8 bytes)

To create the property, send data above to the exodus address. 
(I think we should add if it is denominated in MSC or BTC)

This will become  property of the Issuer (Sender)

Seller IPO (Initial Public Offering)
Allow anyone to post Max highest bid price for a share.  Bidder must have sufficient BTC balance
At the end of IPO period.
Arrange Bids Highest to lowest

Ex. Total Shares 1,000,000
UserA 500,000 @ 9.0
UserB 400,000 @ 8.5
UserC 300,000 @ 7.0  <- Cut off
UserD 300,000 @ 7.0

Final Share Distribution (System post to exodus,Seller Address,Bidder Address?)
UserA 500,000 @ 7.0
UserB 400,000 @ 7.0
UserC 100,000 @ 7.0

What protocol should we use to post shares?

[Tachikoma]

Another idea for obfuscation: instead of always flipping the most significant bit or flipping all bits (XOR with 0x80 or 0xFF), we could XOR with data which can only be known to someone parsing MasterCoin transactions. For instance, what if we run the user's MSC balance through SHA256, and then XOR that with the data that is being encoded. Only someone who knows the MasterCoin balance of the address could tell if the address was sending a MasterCoin transaction (aside from the Exodus Address tell, which could also be obfuscated if desired) . . .

That's probably too complicated for now, but if we get into a war with miners trying to exclude us, we have a LOT of options.

I think the question should be; how soon talking about months, do we expect such an "ASCII-protection" by miners to really become a standard. I honestly don't think we can even say with certainty that it will happen. However, since we are at the beginning stages now anyway it might be worth it to spend some extra effort in obfuscating the keys anyway.

I think using data that only a Mastercoin parser would know is a great last option idea, but for now I would want to focus on something a little easier.

How about we use the redeemable public key from the sender and impose it (xor it) over the data keys? I think it would great very random looking strings and it's easy to decode since the key is always easily available.

[zathras]

Another idea for obfuscation: instead of always flipping the most significant bit or flipping all bits (XOR with 0x80 or 0xFF), we could XOR with data which can only be known to someone parsing MasterCoin transactions. For instance, what if we run the user's MSC balance through SHA256, and then XOR that with the data that is being encoded. Only someone who knows the MasterCoin balance of the address could tell if the address was sending a MasterCoin transaction (aside from the Exodus Address tell, which could also be obfuscated if desired) . . .

That's probably too complicated for now, but if we get into a war with miners trying to exclude us, we have a LOT of options.

I think the question should be; how soon talking about months, do we expect such an "ASCII-protection" by miners to really become a standard. I honestly don't think we can even say with certainty that it will happen. However, since we are at the beginning stages now anyway it might be worth it to spend some extra effort in obfuscating the keys anyway.

I think using data that only a Mastercoin parser would know is a great last option idea, but for now I would want to focus on something a little easier.

How about we use the redeemable public key from the sender and impose it (xor it) over the data keys? I think it would great very random looking strings and it's easy to decode since the key is always easily available.

That's what I've been thinking for the obfuscation step, combined with byte rotation I believe we'll be in pretty good shape - it's not perfect but guys feel free to have a read of a draft appendix to the spec I've been putting together to button up tight how we're storing data.  JR can obviously choose to use as is or just select bits (or none at all).

I'd still like to clean it up some more and flesh out a few of the details but feedback welcome, feel free to tear it apart if needed

[grazcoin]

Another idea for obfuscation: instead of always flipping the most significant bit or flipping all bits (XOR with 0x80 or 0xFF), we could XOR with data which can only be known to someone parsing MasterCoin transactions. For instance, what if we run the user's MSC balance through SHA256, and then XOR that with the data that is being encoded. Only someone who knows the MasterCoin balance of the address could tell if the address was sending a MasterCoin transaction (aside from the Exodus Address tell, which could also be obfuscated if desired) . . .

That's probably too complicated for now, but if we get into a war with miners trying to exclude us, we have a LOT of options.

I think the question should be; how soon talking about months, do we expect such an "ASCII-protection" by miners to really become a standard. I honestly don't think we can even say with certainty that it will happen. However, since we are at the beginning stages now anyway it might be worth it to spend some extra effort in obfuscating the keys anyway.

I think using data that only a Mastercoin parser would know is a great last option idea, but for now I would want to focus on something a little easier.

How about we use the redeemable public key from the sender and impose it (xor it) over the data keys? I think it would great very random looking strings and it's easy to decode since the key is always easily available.

+1 for xor with redeemable public key (the first key in the multisig).

[Tachikoma]

Awesome stuff Zathras.

Can anybody think of a reason to prefer the public key to the receiving address or visa-versa?

[zathras]

Awesome stuff Zathras.

Can anybody think of a reason to prefer the public key to the receiving address or visa-versa?

Actually thinking about it public key would be preferred over the receiving address just purely for length purposes (ideally we need >=31 bytes) - the compressed public key will always be 33 bytes compared to the address which could technically be as low as 27 - though <31 is extremely rare I believe we'd still have to cover that scenario in the code for completeness with looping or something, so I'd say save ourselves the trouble and just use the public key which we know has enough bytes.

I'll amend the draft accordingly

[Tachikoma]

Cool, if/when J.R. gives the go ahead I think we should create some test vectors so all our implementations will have the same result when XORing the data.

[zathras]

Cool, if/when J.R. gives the go ahead I think we should create some test vectors so all our implementations will have the same result when XORing the data.

Testing may have answered this for us - it seems actually pubkey may not be such a good idea, I'll stick with addresses for now.

Since most of our data is zero, our XOR is returning an almost identical pubkey to the sender:

Code:

02 0100000000000000010000000002faf0800000000000000000000000000000 XX  'data to be encoded
02 1BFC32C40F01EFD61535CAE8B297257E536B140EE6C727F576698E70D24CF5 75  'senders pub key
02 1AFC32C40F01EFD61435CAE8B295DF8ED36B140EE6C727F576698E70D24CF5 XX  'obfuscated data pub key

The result would be great if we were not also including the senders pubkey elsewhere in the transaction.  We thus have two very similar but slightly different pubkeys in the transaction.  If we instead take 31 bytes from the address:

Code:

02 0100000000000000010000000002faf0800000000000000000000000000000 XX  'data to be encoded
1Cd ighsfdfRcj4ytQSskZgQXbUEamuMUNF 'reference address we take 31 bytes from for the XOR
02 464E554D756D614555625851675A6B7BFC7E7479346A7352666466736867 XX  'obfuscated data pub key

Using the address means a similar pub key won't be found anywhere else in the transaction so would be a better method for obfuscation.

Unfortunately this only goes for the first packet - but calls into question the second and subsequent packets, as if they're full of zeros also & we XOR against the same reference address bytes we're going to again end up with similar looking pubkeys.

[Tachikoma]

We could SHA the address an amount of times for each added output and use that to XOR the key.

The first would use just the address, the second output would SHA256(address), the third SHA256(SHA256(address)) etc.

[zathras]

We could SHA the address an amount of times for each added output and use that to XOR the key.

The first would use just the address, the second output would SHA256(address), the third SHA256(SHA256(address)) etc.

That could work, I'll do some further testing.  Thanks

[Tachikoma]

The OP_RETURN patch for transaction metadata was just merged into bitcoin/bitcoin.git.

This is certainly interesting. Although I prefer compress keys because they offer more space this will mean that in the near future we could go back to address based communication.

[dacoinminster]

This is brilliant. You guys are awesome.

I support the nested SHA256(address) method that Tachikoma and Zathras have been discussing here. I'll add the data in Zathras' appendix to the spec in some way.

In the unlikely event that we end up in a war with miners, we can always add the MSC balance of the address to what is being hashed, but I agree that shouldn't be done right now. At this point they would be more likely to target the Exodus Address anyway. If they ever do that, we can obfuscate the Exodus Address too (which would create unspendable UTXOs, so hopefully that won't be necessary)

Zathras, when you and Tachikoma feel the appendix is final, let me know, and I'll link to it from the OP of this thread.

grazcoin, I hope this sounds good to you too?

[grazcoin]

This is brilliant. You guys are awesome.

I support the nested SHA256(address) method that Tachikoma and Zathras have been discussing here. I'll add the data in Zathras' appendix to the spec in some way.

In the unlikely event that we end up in a war with miners, we can always add the MSC balance of the address to what is being hashed, but I agree that shouldn't be done right now. At this point they would be more likely to target the Exodus Address anyway. If they ever do that, we can obfuscate the Exodus Address too (which would create unspendable UTXOs, so hopefully that won't be necessary)

Zathras, when you and Tachikoma feel the appendix is final, let me know, and I'll link to it from the OP of this thread.

grazcoin, I hope this sounds good to you too?

The appendix looks good, assuming that the nested SHA256 method is added.
I would suggest allowing another optional dust output without address limitations, mainly for class B, to allow cross-currency use (e.g. a second marker to a different exodus). Then the transactions could belong to two currencies and enable atomic exchange between them.

[grazcoin]

What about older multisig tx which are already on the blockchain?
The options I see are:
1. Parse the using the old method until some block height, and starting that height using the new method.
2. Ignore all old multisig tx - treat them as invalid.
3. Treat both old multisig method and new multisig method as valid tx.

[dacoinminster]

What about older multisig tx which are already on the blockchain?
The options I see are:
1. Parse the using the old method until some block height, and starting that height using the new method.
2. Ignore all old multisig tx - treat them as invalid.
3. Treat both old multisig method and new multisig method as valid tx.

I think (hope) that nobody transferred any major amount of money that way yet, at least, not to a different person than themselves. If somebody did transfer a bunch of money that way in good faith, we should try to support it . . .

[Tachikoma]

I'm 95% sure it's safe to ignore them.

Code:

13NRX88EZbS5q81x6XFrTECzrciPREo821, 1J2svn2GxYx9LPrpCLFikmzn9kkrXBrk8B, 1.337
13NRX88EZbS5q81x6XFrTECzrciPREo821, 1J2svn2GxYx9LPrpCLFikmzn9kkrXBrk8B, 0.00000013
13NRX88EZbS5q81x6XFrTECzrciPREo821, 1J2svn2GxYx9LPrpCLFikmzn9kkrXBrk8B, 0.00000011
1MCHESTbJhJK27Ygqj4qKkx4Z4ZxhnP826, 157L78NE1PB1CjRKnXKNWjwXzroyeA9dkt, 0.5
1MCHESTbJhJK27Ygqj4qKkx4Z4ZxhnP826, 15irickEziQ8qdTuT75adX15zDLrySM32W, 1.0
1MCHESTbJhJK27Ygqj4qKkx4Z4ZxhnP826, 1MCHESTxYkPSLoJ57WBQot7vz3xkNahkcb, 1.234
1MCHESTbJhJK27Ygqj4qKkx4Z4ZxhnP826, 1MCHESTptvd2LnNp7wmr2sGTpRomteAkq8, 2.0
1MCHESTbJhJK27Ygqj4qKkx4Z4ZxhnP826, 1MCHESTptvd2LnNp7wmr2sGTpRomteAkq8, 1.0
1MCHESTbJhJK27Ygqj4qKkx4Z4ZxhnP826, 1MCHESTxYkPSLoJ57WBQot7vz3xkNahkcb, 2.5
1MCHESTbJhJK27Ygqj4qKkx4Z4ZxhnP826, 1MCHESTptvd2LnNp7wmr2sGTpRomteAkq8, 1.234
1MCHESTbJhJK27Ygqj4qKkx4Z4ZxhnP826, 1MCHESTptvd2LnNp7wmr2sGTpRomteAkq8, 1.5

These are the valid multi-sig transactions, as you can see all of them are from Zathras and me. Just need to make sure Zathras didn't use any of these transactions for real.

[Peter Todd]

What about older multisig tx which are already on the blockchain?
The options I see are:
1. Parse the using the old method until some block height, and starting that height using the new method.
2. Ignore all old multisig tx - treat them as invalid.
3. Treat both old multisig method and new multisig method as valid tx.

I think (hope) that nobody transferred any major amount of money that way yet, at least, not to a different person than themselves. If somebody did transfer a bunch of money that way in good faith, we should try to support it . . .

Suggestion: put your protocol documentation in a git repo along with a reference to the git commit hashes of one or more implementations of the protocol. If a new type of transaction is sufficiently well defined to be something that should be Mastercoin "officially", PGP sign a statement saying so and saying on what block # this takes effect.

The PGP isn't really the important thing FWIW, it's having a solid definition of what's what and making that public.

Also you guys really need to think through out the Mastercoin equiv of a soft-fork would work... killerstorm has a very good point re: that.