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

[zathras]

Dexx got me thinking about packet ordering, and as we all know it's the sequence numbers that determine the order.  The order of outputs or keys within multisig outputs is not mandated by the spec, only that we grab all the public keys and order them by sequence number.

So for the first test, a simple send where the multisig still has the correct public keys and sequence number, it's just that the master protocol packet public key is before the senders public key in the multisig instead of the other way around.

MyMastercoins decodes it as an unmatched purchase (http://www.mymastercoins.com/default.aspx?TXID=1ce1e44f40da1f7eddca5f81d72d76a005f8f45b83ee1f9b07ca901f3e6ec235)
Masterchain declares it invalid based on unknown transaction type (5cc2) (https://masterchain.info/simplesend.html?tx=1ce1e44f40da1f7eddca5f81d72d76a005f8f45b83ee1f9b07ca901f3e6ec235&currency=TMSC)
Masterchest (after a bugfix) now decodes it correctly (https://masterchest.info/lookuptx.aspx?txid=1ce1e44f40da1f7eddca5f81d72d76a005f8f45b83ee1f9b07ca901f3e6ec235)

Next up I'm going to simulate a sell offer because it spans multiple packets, with the public key order in the multisig of [sender],[packetseqnum2],[packetseqnum1] which will again be a perfectly valid transaction, but will test each implementations ability to deal with ordering packets properly.

Thanks
Zathras

[Bitoy]

Can we just change the specs ie

For multisig transaction the following order is followed

 first mastercoin packet
Second mastercoin packet (if required)
Senders  public key

Please don't introduce another peak and decode for multisig.

If  mymastercoins can't find a transaction type it will assume it is a payment and try to look for a purchase offer.

Dexx got me thinking about packet ordering, and as we all know it's the sequence numbers that determine the order.  The order of outputs or keys within multisig outputs is not mandated by the spec, only that we grab all the public keys and order them by sequence number.

So for the first test, a simple send where the multisig still has the correct public keys and sequence number, it's just that the master protocol packet public key is before the senders public key in the multisig instead of the other way around.

MyMastercoins decodes it as an unmatched purchase (http://www.mymastercoins.com/default.aspx?TXID=1ce1e44f40da1f7eddca5f81d72d76a005f8f45b83ee1f9b07ca901f3e6ec235)
Masterchain declares it invalid based on unknown transaction type (5cc2) (https://masterchain.info/simplesend.html?tx=1ce1e44f40da1f7eddca5f81d72d76a005f8f45b83ee1f9b07ca901f3e6ec235&currency=TMSC)
Masterchest (after a bugfix) now decodes it correctly (https://masterchest.info/lookuptx.aspx?txid=1ce1e44f40da1f7eddca5f81d72d76a005f8f45b83ee1f9b07ca901f3e6ec235)

Next up I'm going to simulate a sell offer because it spans multiple packets, with the public key order in the multisig of [sender],[packetseqnum2],[packetseqnum1] which will again be a perfectly valid transaction, but will test each implementations ability to deal with ordering packets properly.

Thanks
Zathras

[dexX7]

first mastercoin packet
Second mastercoin packet (if required)
Senders  public key

You probably mean:

Sender's pubKey
Mastercoin data-package #1
Mastercoin data-package #2

^ this is the order of almost all transactions that were made in the past.


Given that DEX starts in a few days, I tend to agree with Bitoy, should probably locked into the stec temporarily. But solving this should stay high priority, the more packages there are, the less trivial is the solution. With four packages (e.g. the smart property stuff), it's already 24 combinations, with 5 packages it's 120. If a brute force approach is used.

[grazcoin]

first mastercoin packet
Second mastercoin packet (if required)
Senders  public key

You probably mean:

Sender's pubKey
Mastercoin data-package #1
Mastercoin data-package #2

^ this is the order of almost all transactions that were made in the past.


Given that DEX starts in a few days, I tend to agree with Bitoy, should probably locked into the stec temporarily. But solving this should stay high priority, the more packages there are, the less trivial is the solution. With four packages (e.g. the smart propertie stuff), it's already 24 combinations, with 5 packages it's 120. If a brute force approach is used.

dexX7 is right.
Example sell offer is:
https://masterchain.info/selloffer.html?tx=ccc6c0ed758c42a950b1f54956d74db0a84783908fe41427a540b1221f5887e5&currency=TMSC
The BIP11 part is:
"script": "1 [ 047992ccb171ca59d39432dc93eba2301188b68ead661dd9fdfe3dda47e2f27ebfff9a0a069d4cb 3851ce19fe5be7ea1b772ee4b678e3bdcc7769713cd675e14c7 ] [ 021bf733f7beb3932563cd8e8a3ec13fb22047f0694a0b6e8a2ad08e63bba57cbb ] [ 026c3fe6ffe4fdf222b80142d95c275753e49587546ef02c40e3e06ee449b27109 ] 3 checkmultisig",
Which is:

Sender's pubKey
Mastercoin data-package #1
Mastercoin data-package #2

note that if you look at the transaction on blockchain.info, the order of pubkeys inside the BIP11 looks opposite:
https://blockchain.info/tx/ccc6c0ed758c42a950b1f54956d74db0a84783908fe41427a540b1221f5887e5

[dexX7]

I submitted a spec adjustment request: https://github.com/mastercoin-MSC/spec/issues/78

[dacoinminster]

We had a productive meeting today, and Craig and I were able to make some decisions regarding the last remaining consensus issues:

1) Minimum fees must be respected, as has been in the spec since the beginning. I believe Bitoy and Grazcoin both need to make this change. Without this change, someone can shut down the whole dEX with spam transactions. The fix is simple: if someone tries to accept coins without paying the minimum fee, invalidate that transaction.

2) We're going to have to disable multiple accept offers. This was a harder decision to make, but it boils down to reducing complexity. Also, since graz and bitoy both need to make the minimum fee change, we can't keep the parsing libraries static. This should also be a simple fix: only one accept offer from a buyer to a seller. Additional accept offers are invalid.

3) Zathras is going to have to drop his change to respect packet sequence numbers in class B transactions. We simply can't afford the time, and we believe we can rely on the order of outputs not changing in the transaction, so sequence numbers are probably redundant for class B transactions. If we do packets out-of-sequence someday, we'll have to change the version number of all transaction types.

Sorry that further changes must be made, but we needed to choose a direction and stick with it. Both Craig and I are committed to this direction, and I'll be updating the spec to reflect #2 and #3.

Thanks guys!

 

[dexX7]

We simply can't afford the time, and we believe we can rely on the order of outputs not changing in the transaction, so sequence numbers are probably redundant for class B transactions.

Well, they offer also some further insight in form of "this is indeed a MSC data-package".

How about something like: "use the longest sequence of MSC data-packages within a transaction's output with ascending sequence numbers, starting from 01"? This gives some space to allow junk packages, even if amigiousness exists for the first package. Not that I encourage to include some, but I mention it in light of potentially not-exactly-the-input-pubKeys and unknown packages as listed a few posts earlier. Currently all those transactions are "valid".

Not sure how to handle a sequence that goes over two outputs, but I think the same should apply, but starting from last-seq-num + 1, e.g.:

Output 1:

Pos 0: junk
Pos 1: junk, seq num 01 (appearingly)
Pos 2: junk
Pos 3: Mastercoin data-package, seq num 01
Pos 4: Mastercoin data-package, seq num 02
Pos 5: junk

Longest sequence is pos 3 + pos 4, so take them.

Output 2:

Pos 6: junk
Pos 7: Mastercoin data-package, seq num 03
Pos 8: Mastercoin data-package, seq num 04
Pos 9: Mastercoin data-package, seq num 05

The longest sequence starting with a sequence number of 2 + 1 = 03 starts at pos 7 and ends with pos 9.

So the actual data-stream is within pos 3, 4, 7, 8, 9.

[zathras]

We simply can't afford the time, and we believe we can rely on the order of outputs not changing in the transaction, so sequence numbers are probably redundant for class B transactions.

Well, they offer also some further insight in form of "this is indeed a MSC data-package".

How about something like: "use the longest sequence of MSC data-packages within transaction outputs with ascending sequence numbers, starting from 01"? This gives some space to allow junk packages. Not that I encourage to include some, but I mention it in light of potentially not-exactly-the-input-pubKeys and unknown packages as listed a few posts earlier. Currently all those transactions are "valid".

FYI currently none of the implementations validates the first key is redeemable by the sender as that's in no way required for transaction security (that's provided by the input signing) and as I think I mentioned compression can change the apparent address for a given key. Since it serves no purpose in the Master Protocol transaction itself I don't think any of us actually enforce any validation checks here - its only purpose is outside of the Master Protocol transaction and rather on the bitcoin side to redeem the output and recover the 0.00012BTC spent on fees at a later point in time.

Thanks
Zathras

[dacoinminster]

We simply can't afford the time, and we believe we can rely on the order of outputs not changing in the transaction, so sequence numbers are probably redundant for class B transactions.

Well, they offer also some further insight in form of "this is indeed a MSC data-package".

How about something like: "use the longest sequence of MSC data-packages within transaction outputs with ascending sequence numbers, starting from 01"? This gives some space to allow junk packages, even if amigiousness exists for the first package. Not that I encourage to include some, but I mention it in light of potentially not-exactly-the-input-pubKeys and unknown packages as listed a few posts earlier. Currently all those transactions are "valid".

Anything that is valid now probably needs to stay valid. We're going to try to keep the current logic and formalize that in the spec.

I plan to add a note in the spec in the section about class B transactions: "Note that current implementations do not allow out-of-order sequence numbers, but rely on the immutability of transaction output ordering instead."

[dexX7]

Slighthly edited the post with an example which should cover all potential cases without rendering anything invalid, but with as much space for errors as possible.

[zathras]

Slighthly edited the post with an example which should cover all potential cases without rendering anything invalid, but with as much space for errors as possible.

Hey Dexx,

If it helps, being discussed on email as we speak, packet order is explicit in each multisig, so assuming the first multisig in the transaction was n=2:

Perfect.  Then we can translate what we do in reality to the spec to make this a little clearer.  So we're essentially saying (assuming n=2 is the first multisig vout)

n2 {senderkey, masterpacket1, masterpacket2}
n3 {senderkey, masterpacket3, masterpacket4}
n4 {senderkey, masterpacket5, masterpacket6}
n5 ... and so on

Thanks
Zathras

Sequence numbers can then be used as a sanity check to double check the packet order is as expected.

[dexX7]

Didn't receive the mail you quoted, but including the pubKey shouldn't be required, at least on the spec level, and as you said, it's not validated at the moment anyway. Keep also in mind that the number of n-of-m multisig parts will rise and won't be limited to 3. Actually those are already "accepted", but the standard client refuses to send them.

[dacoinminster]

Didn't receive the mail you quoted, but including the pubKey shouldn't be required, at least on the spec level, and as you said, it's not validated at the moment anyway. Keep also in mind that the number of n-of-m multisig parts will rise and won't be limited to 3. Actually those are already "accepted", but the standard client refuses to send them.

dexx, are you suggesting something other than what is described in your github issue? :https://github.com/mastercoin-MSC/spec/issues/78

There you say:

I suggest to temporarily insert a line in the spec that Mastercoin data packages should be in order within an output:

Sender's pubKey
Mastercoin data-package 1
Mastercoin data-package 2

It appears that data-packages are only parsed correctly, if this order is given and allowing unordered data packages is probably not trivial. See the discussion here: https://bitcointalk.org/index.php?topic=292628.msg5646781#msg5646781 (and a few posts earlier)

I think that is the current behavior, and the spec just needs a note about it.

[dexX7]

dexx, are you suggesting something other than what is described in your github issue? :https://github.com/mastercoin-MSC/spec/issues/78

No, I'm not. The order of packages should be required.

I tried to formalize this with something like "use the longest sequence of MSC data-packages within a transaction's output with ascending sequence numbers, starting from 01 and in the case that multiple multisig outputs are available, the same should apply, but starting from last-seq-num + 1", here an example:

Output 1:

Pos 0: junk
Pos 1: junk, seq num 01 (appearingly)
Pos 2: junk
Pos 3: Mastercoin data-package, seq num 01
Pos 4: Mastercoin data-package, seq num 02
Pos 5: junk

Longest sequence is pos 3 + pos 4, so take them.

Output 2:

Pos 6: junk
Pos 7: Mastercoin data-package, seq num 03
Pos 8: Mastercoin data-package, seq num 04
Pos 9: Mastercoin data-package, seq num 05

The longest sequence starting with a sequence number of 2 + 1 = 03 starts at pos 7 and ends with pos 9.

So the actual data-stream is within pos 3, 4, 7, 8, 9.

This gives some space to cover the transactions that are already out which don't fit exactly in the schema "sender-pubKey, data #1, data #2".

I don't suggest to change anything, but to be very specific about how packages are handled.

[dacoinminster]

I guess I'd like to hear the other devs comment about these packets with "junk" in them which are there already. Can you point a couple of them out?

I'd like to know what logic currently makes them valid. That is what will probably end up in the spec, just to avoid changing anything.

[Bitoy]

I'm using blockchain

047992ccb171ca59d39432dc93eba2301188b68ead661dd9fdfe3dda47e2f27ebfff9a0a069d4cb 3851ce19fe5be7ea1b772ee4b678e3bdcc7769713cd675e14c7   Senders Public

021bf733f7beb3932563cd8e8a3ec13fb22047f0694a0b6e8a2ad08e63bba57cbb   This is packet 2?

026c3fe6ffe4fdf222b80142d95c275753e49587546ef02c40e3e06ee449b27109  Packet 1


The important thing in the spec is the packets must be in order.

Ex. Valid
Packet 1
Packet 2
Junk
Packet 3

Ex. Invalid.  It can't be jumbled

Packet 1
Packet 3
Junk
Packet 2

first mastercoin packet
Second mastercoin packet (if required)
Senders  public key

You probably mean:

Sender's pubKey
Mastercoin data-package #1
Mastercoin data-package #2

^ this is the order of almost all transactions that were made in the past.


Given that DEX starts in a few days, I tend to agree with Bitoy, should probably locked into the stec temporarily. But solving this should stay high priority, the more packages there are, the less trivial is the solution. With four packages (e.g. the smart propertie stuff), it's already 24 combinations, with 5 packages it's 120. If a brute force approach is used.

dexX7 is right.
Example sell offer is:
https://masterchain.info/selloffer.html?tx=ccc6c0ed758c42a950b1f54956d74db0a84783908fe41427a540b1221f5887e5&currency=TMSC
The BIP11 part is:
"script": "1 [ 047992ccb171ca59d39432dc93eba2301188b68ead661dd9fdfe3dda47e2f27ebfff9a0a069d4cb 3851ce19fe5be7ea1b772ee4b678e3bdcc7769713cd675e14c7 ] [ 021bf733f7beb3932563cd8e8a3ec13fb22047f0694a0b6e8a2ad08e63bba57cbb ] [ 026c3fe6ffe4fdf222b80142d95c275753e49587546ef02c40e3e06ee449b27109 ] 3 checkmultisig",
Which is:

Sender's pubKey
Mastercoin data-package #1
Mastercoin data-package #2

note that if you look at the transaction on blockchain.info, the order of pubkeys inside the BIP11 looks opposite:
https://blockchain.info/tx/ccc6c0ed758c42a950b1f54956d74db0a84783908fe41427a540b1221f5887e5

[Bitoy]

1. Ok will enforce the req minimum fees require for purchase accept.

2.  I think it should be.   A buyer can place only one purchase offer transaction on any sell offer transaction.

We had a productive meeting today, and Craig and I were able to make some decisions regarding the last remaining consensus issues:

1) Minimum fees must be respected, as has been in the spec since the beginning. I believe Bitoy and Grazcoin both need to make this change. Without this change, someone can shut down the whole dEX with spam transactions. The fix is simple: if someone tries to accept coins without paying the minimum fee, invalidate that transaction.


2) We're going to have to disable multiple accept offers. This was a harder decision to make, but it boils down to reducing complexity. Also, since graz and bitoy both need to make the minimum fee change, we can't keep the parsing libraries static. This should also be a simple fix: only one accept offer from a buyer to a seller. Additional accept offers are invalid.

3) Zathras is going to have to drop his change to respect packet sequence numbers in class B transactions. We simply can't afford the time, and we believe we can rely on the order of outputs not changing in the transaction, so sequence numbers are probably redundant for class B transactions. If we do packets out-of-sequence someday, we'll have to change the version number of all transaction types.

Sorry that further changes must be made, but we needed to choose a direction and stick with it. Both Craig and I are committed to this direction, and I'll be updating the spec to reflect #2 and #3.

Thanks guys!

 

[zathras]

I guess I'd like to hear the other devs comment about these packets with "junk" in them which are there already. Can you point a couple of them out?

I'd like to know what logic currently makes them valid. That is what will probably end up in the spec, just to avoid changing anything.

I think what Dexx is getting it is allowing a sequence of Master Protocol packets anywhere in the multisig outputs, as long as the packets are contiguous.  I'm not sure that's necessary at this stage (I think if we're to lock in packet ordering then let's keep it simple).  Also re 1-of-3, yep I know technically we can go higher but not while maintaining widespread support.  My own view is that we'll see OP_RETURN before better native multisig handling in the reference client, but that's pure speculation of course.

Dexx, I know you posted an analysis a few pages back but could you pick say two or three transactions, post them & a brief summary on why you think they're invalid/contain junk.  Happy to take a look

[zathras]

1. Ok will enforce the req minimum fees require for purchase accept.

2.  I think it should be.   A buyer can place only one purchase offer transaction on any sell offer transaction.

Awesome

[dexX7]

I think what Dexx is getting it is allowing a sequence of Master Protocol packets anywhere in the multisig outputs, as long as the packets are contiguous.  I'm not sure that's necessary at this stage (I think if we're to lock in packet ordering then let's keep it simple).  Also re 1-of-3, yep I know technically we can go higher but not while maintaining widespread support.  My own view is that we'll see OP_RETURN before better native multisig handling in the reference client, but that's pure speculation of course.

Dexx, I know you posted an analysis a few pages back but could you pick say two or three transactions, post them & a brief summary on why you think they're invalid/contain junk.  Happy to take a look

Thanks. Yes and I agree, keeping it as simple as possible, would be good.

Okay, I'll try to cover a few cases I found:


1. https://blockchain.info/tx/bda81e0c2117fb6ecefb92143995a6ebc3d9569f54c4a0c074ff3070bcf3e011

Input: compressed public key
Output: compressed input public key, data-package #1, data-package #2

No conflict.


2. https://blockchain.info/tx/95b10a4721a69a1028e70fd2ccd0692219095fb6f5087b9e72b155a3e0832602

Input: uncompressed public key
Output: uncompressed public key, data package #1

Conflict: "Has one or more 1-of-n OP_CHECKMULTISIG outputs each containing at least two compressed public keys, one of which must be the senders address" (has only one compressed public key)


3. https://blockchain.info/tx/f8e2eb56f50f7a98a8c76ef45ed591aedd8aa973c5f4dfd5b7685aae4b48ae6c

Input: uncompressed public key
Output: compressed public key, data package #1

Public key was compressed, but that's no conflict.


4. https://blockchain.info/tx/4842af86dac35a2c294f56511c7d08362330e82bd5fcae32c07119844e019b0a

Input: uncompresssed public key
Output: compressed public key with flawed prefix byte, data package #1

Conflict: "As one signatory must be the sender for redemption purposes, ..."

"Has one or more 1-of-n OP_CHECKMULTISIG outputs each containing at least two compressed public keys, one of which must be the senders address" (not the case, because of a small flaw during the compression [prefix "02" instead of "03"], so this output is neither redeemable nor the sender's address)


5. https://blockchain.info/tx/2ae17011888e9a2e6c752999774cd6d88feb7c0751abe72a602be89858e44f6a

Input: compressed public key
Output: unknown package, data package #1

Conflict: "As one signatory must be the sender for redemption purposes, ..."

"Has one or more 1-of-n OP_CHECKMULTISIG outputs each containing at least two compressed public keys, one of which must be the senders address" (not the case, because the first package has no relation to the input address)


6. https://blockchain.info/tx/1ce1e44f40da1f7eddca5f81d72d76a005f8f45b83ee1f9b07ca901f3e6ec235

Input: uncompressed public key
Output: data package #1, compressed public key

This is an edge case. All data packages are ordered (it's only one) and it includes the sender's address.