Pages:
Author

Topic: 300 BTC Coding Contest: Distributed Exchange (MasterCoin Developer Thread) - page 57. (Read 129207 times)

sr. member
Activity: 449
Merit: 250


For ECDSA validity (I'll also put a check function into the masterchest library) I took my inspiration from the casascius bitcoin address utility - have a read through some of the pubkey and ECDSA stuff to point you in the right direction.

Thanks!


Thanks zathras.  Will get some ecdsa information there.
hero member
Activity: 938
Merit: 1000
Yeah, why not. As long as people understand this limitation. Smiley
sr. member
Activity: 266
Merit: 250
In the future new currencies could be created that could be sent using a Class A transaction. So I think in the future the currency id should be one of the created currency ids, for now 01 or 02 should suffice.
I currently have this in the amendment:
Quote
NOTE: Class A transactions are restricted to the ‘simple send’ transaction type only. All other Mastercoin transaction types are supported by Class B transactions only. Client implementations should utilize Class B for all transaction types, including ‘simple send’.
I had envisaged us using Class A transactions only for backwards compatibility (for example to allow people to transfer Mastercoins out of certain web wallets) and implementing Class B for everything from now on - thus Class A simple send would only ever need to support currencies 01 & 02.

If we want to allow Class A transactions to be used in future with new currencies I guess we can do so, but personally I'd rather discourage their use (bloat) and simply say simple sends for currencies other than mastercoin (& test mastercoin) must be done via Class B.
hero member
Activity: 938
Merit: 1000
In the future new currencies could be created that could be sent using a Class A transaction. So I think in the future the currency id should be one of the created currency ids, for now 01 or 02 should suffice.
sr. member
Activity: 266
Merit: 250
I did some googling and I think using upcase is more dominant. Unless somebody has a reason not to upcase I suggest we use this for now.
Great.  Again updated the amendment to add the byte checks & that we run multiple hash passes against an uppercase hex representation of the previous hash.

I've set the byte checks at byte2 to byte8 = 00 & byte9=01 or 02.  Would you say that's sufficient?  The chances on us having to fall back on 'peek & decode' are very slim, and if we do then the chances of then getting a random collission on those bytes with an address that isn't a Mastercoin packet are astronomically low (one in 70,110,209,207,109,376 to be specific). 

hero member
Activity: 938
Merit: 1000
I did some googling and I think using upcase is more dominant. Unless somebody has a reason not to upcase I suggest we use this for now.
sr. member
Activity: 266
Merit: 250
hahahahaahaha, duh. Is one way better then the other, or the default?

Don't think it matters as long as we explicitly define which way we're going - for me it's as easy as changing an X to an x in the string format so if there is either that is easier or default for you I'm happy either way Smiley
hero member
Activity: 938
Merit: 1000
Yeah that was what I meant.

I think currency_id and transaction_type are the most important to check. The change of those two being valid values in a random address are very slim.
sr. member
Activity: 266
Merit: 250
I've updated the amendment to include the changes we've discussed.  If viewing in browser you may need to refresh.

Anything we're missing, anything unclear?

Thanks! Smiley

Should we perhaps specify the rules what 'peek and decode' means? Other than that it looks good Smiley

I've got:

Quote
A last resort 'peek and decode' method may be used to identify the data packet in the event of ambiguity following the above rules. This involves decoding each packet and looking for the correct bytes for a simple send (the majority of bytes in a Class A simple send do not change).

Perhaps specify the bytes that we'll want to look for?  Eg first byte must be 01 and so on?
hero member
Activity: 938
Merit: 1000
hahahahaahaha, duh. Is one way better then the other, or the default?
sr. member
Activity: 266
Merit: 250
You were right about using the bytes, I coded that up wrong. It was late last night (and it's early now.. Wink

I'm still not getting the same sequence as you are however. I think we might be doing this differently.

Code:
d42c390e52f1110412078a9db148e7a306924666fb10aaaa9bffcc2e2ecde344
370ee8c285babbf857761796c0ab5c652db7da17fdd2fea8657809ca8428bd2f
e3ab016c159270d4649ab732d41c7895ad3e05f5b94d611f7a5e19780c6502d2
...etc...

Just so I know we are doing the same thing.

Code:
sequence1 = Digest::SHA256.hexdigest("1J2svn2GxYx9LPrpCLFikmzn9kkrXBrk8B")
sequence2 = Digest::SHA256.hexdigest(sequence1)
sequence3 = Digest::SHA256.hexdigest(sequence2)
..etc..


Haha that took a little figuring out - you're hashing lowercase hex, I'm hashing uppercase hex Smiley

hero member
Activity: 938
Merit: 1000
I've updated the amendment to include the changes we've discussed.  If viewing in browser you may need to refresh.

Anything we're missing, anything unclear?

Thanks! Smiley

Should we perhaps specify the rules what 'peek and decode' means? Other than that it looks good Smiley
sr. member
Activity: 266
Merit: 250
I've updated the amendment to include the changes we've discussed.  If viewing in browser you may need to refresh.

Anything we're missing, anything unclear?

Thanks! Smiley
sr. member
Activity: 449
Merit: 250

We haven't discussed what we will use to XOR data for a 'Selling MasterCoins for Bitcoins' package. I want to propose using the sending address whenever a Mastercoin message does not contain a recipient address.
Agreed.  Though I actually think we should make it the sender address for everything because as you note, not all transactions will have a reference address.  We may as well stick with an address we know will always be there.  Unless you guys know of a reason for not using the sender address let's lock that in as our initial source for the SHA256 hashing & I'll update the amendment accordingly.

Agreed, let's just use the sending address for all packages. This should go into the spec. Smiley


Excellent, using the sender address for all transactions will simplify the coding (and lessen the bugs).
sr. member
Activity: 266
Merit: 250
After reading a lot of old posts I think I know where we are.

That quote
...
  • All protocol transactions should have the same output amount. If one output is different, that is the change address.
  • If all outputs are the same, then look at sequence numbers:
    • 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!
...

It was originally stated that all outputs should be for the same amount & the odd one out was change.  Then we needed bigger outputs and larger fees, so that requirement was made more of a convenience and we started to use outputs with different amounts, making checking for the odd one out as change no longer reliable and change was identified with sequence numbers instead. 

It's all in the interpretation - just because the 'odd one out is change' method was no longer reliable as the outputs no longer had to be the same amount, that doesn't mean I can't use it to decode and validate a transaction in some cases.  In other words, my implementation is being too strict/literal.  I thus consider this transaction valid and will amend my code to reflect this Smiley

I definitely agree we should make the outputs be the same amount a requirement for Class A.  If you guys & JR adopt the amendment we'll now have (logically) two classes of transaction, so we can make this really clear for others since we can apply rules to one class but not the other.  We can make matching output values a requirement for Class A ('original') transactions but not Class B ('multisig'). We can apply the change-goes-to-sender rule to Class B and not Class A.  Add peek & decode to Class A etc.  Helps me keep things clear anyway Smiley

sr. member
Activity: 266
Merit: 250
Sorry guys have to be quick - back to back meetings today.

Long story short according to the current rules that transaction is not valid due to ambiguous sequence numbers, this is why masterchest.info throws the transaction out.

19b5BiXWZERFoCNhVKiYDf9i829P1W1wiE has a sequence number of 94
19UjqqjXmQxyyn4xStA7mWXVkzXwVDgu7Z has a sequence number of 93
19feAR37pguLwDyEMc8oiW2WT4esrgR5z6 has a sequence number of 95

Having all the outputs be the same amount is merely a convenience for identifying the change address. I'm fine with a less strict implementation as long as it is still possible to identify the change address.

So I removed the requirement for outputs to be the same amount to allow for multisig outputs no longer meeting said requirement.  So as it stands now I no longer evaluate what the value is of each vout, only the sequence numbers matter.

I think we need some further discussion on backwards compatibility for these Class A transactions.  Perhaps we need to re-introduce the 'same output amount' rule as a requirement just for Class A transactions as we can then use the amounts to help identify change as per the original spec - at the moment there seems to be some ambiguity around Class A transaction validity between our implementations and we need to clear this up.  You can probably understand now why I'm putting so much effort into having these rules explicitly defined and documented Smiley  I do concur that random chance of sequence number collisions should not be a factor in transaction validity.

None of this is an issue in multisig as we require change to be from the sender as a method of removing address ambiguity.

This is why I am not a fan of flagging a transaction invalid based sequence. This guy was just trying to create a transaction and he had no way that random chance could make it invalid.

Completely agree the guy was not at fault at all, just unlucky.  As rough as it sounds though it has to be the rules of the protocol that define transaction validity regardless of whether it's right or wrong from a particular point of view.  I'm with definitely on board that this should be a valid transaction though and I'm confident if we present the right set of changes to include fringe cases that JR will be open to adopting them and dropping things like the perfect sequence invalidation (which would then make this transaction valid).

As long as we can safely identify the data address then a perfect sequence number is not a problem. I say we simply peak into each address and see if it contains a known Mastercoin message. Currently only SimpleSends are supported so we can just peak into an address, decode it and see if the transaction type is 0 and the and currency_id is within limits and if the sequence number makes sense. If we can say with a certain certainty that this is most likely a simple send then we have our data address and know which sequence the target address should be. This will work for a broken sequence as well. The only problem is the ambiguous sequence. In this case there is simply no way of finding out the correct address and the transaction should be made invalid. Since the random factor can't be solved here we might need to solve it differently and go back a step.

How about we do the following.

  • Only allow Simple Sends to be encoded as addresses. All new messages should use pulic keys.
  • All outputs that contain Mastercoin data for Class A transaction should have the same output amount, but it doesn't matter how much this amount is.
  • Probe each address to see if it's a Mastercoin encoded address using the checks outlined above.

Checks to see if it's a Mastercoin encoded address
  • Transaction type is 0
  • Currency ID is an existing Currency ID, for now only 1 and 2 are created but this might chance in the future

If we follow these rules then there should always be three outputs. One you can rule out based on the fact that it's Exodus. One of those is the data package and one the target address. In most cases you can probably know which is which even without the sequence number.

I will make some time today to see if this change would affect any existing transactions but I highly doubt it. 

I definitely support only allowing simple sends, I have this in the amendment:
Quote
NOTE: Class A transactions are restricted to the ‘simple send’ transaction type only. All other Mastercoin transaction types are supported by Class B transactions only. Client implementations should utilize Class B for all transaction types, including ‘simple send’.

Also agree with re-instating the requirement for outputs to be for the same amount, I actually really liked this Smiley  This requirement would only be for Class A transactions as you note.

If someone gets really unlucky and creates a transaction where the change amount equals the rest of the output, and then also gets ambiguous sequence numbers, we could use the decode & peek method - I'm just trying to consider ways this could be abused but I can't think of any (since we would throw the transaction out if we found 2 decode-able packets in a Class A transaction).




hero member
Activity: 938
Merit: 1000
Some notes. When I SHA the reference I only take the first 62 bytes since this is the exact amount we need for the obfuscation. This will change the the SHA of the next iteration of hashes that follow so I'm open to discuss this.
Wasn't quite sure what you meant by this so I thought I'd just note that there is no need to drop or add bytes to/from the inputs of our SHA256 hashing if that's what you mean?  SHA256 hashing will always produce a 256 bit (32 byte) hash regardless of input length.  To clarify my take on things:

With each packet:
   * For sequence number 1 we SHA256 the entire length of the address (which could be anywhere from 27 to 34 bytes), result = 32 byte hash.  
   * For sequence numbers 2 onwards, we take the previous 32 byte hash and SHA256 it again (and again), result = 32 byte hash.  
   * We then take the resulting 32 byte hash, grab the first 31 bytes and XOR with the cleartext Mastercoin packet.
Rinse & repeat.

Perhaps that's what you meant, sorry if I'm getting confused or repeating stuff - there's been so much thought & discussion on this stuff it's all kind of a blur! Smiley

So for your address of 1J2svn2GxYx9LPrpCLFikmzn9kkrXBrk8B, the first 5 packets should have hashes of (in between { } is what you would XOR with):

Code:
SEQNUM=1   {D42C390E52F1110412078A9DB148E7A306924666FB10AAAA9BFFCC2E2ECDE3}44
SEQNUM=2   {000EC2C68806819E67A030E82A6AF98376DAC1065D7FE533DAF251D43AA836}3B
SEQNUM=3   {999722F745CC7EA5559D871285A697513D6D1F69294A472AB71499C280CFDA}72
SEQNUM=4   {23C4AC723733621964260EC4639D9DF3469E983E677B083457F325C6F56FA5}D0
SEQNUM=5   {A2989BBA3E4BF3B2995A8573E19450381C94CDE10F95A157756148217B0E37}1B

Thoughts?

You were right about using the bytes, I coded that up wrong. It was late last night (and it's early now.. Wink

I'm still not getting the same sequence as you are however. I think we might be doing this differently.

Code:
d42c390e52f1110412078a9db148e7a306924666fb10aaaa9bffcc2e2ecde344
370ee8c285babbf857761796c0ab5c652db7da17fdd2fea8657809ca8428bd2f
e3ab016c159270d4649ab732d41c7895ad3e05f5b94d611f7a5e19780c6502d2
...etc...

Just so I know we are doing the same thing.

Code:
sequence1 = Digest::SHA256.hexdigest("1J2svn2GxYx9LPrpCLFikmzn9kkrXBrk8B")
sequence2 = Digest::SHA256.hexdigest(sequence1)
sequence3 = Digest::SHA256.hexdigest(sequence2)
..etc..


We haven't discussed what we will use to XOR data for a 'Selling MasterCoins for Bitcoins' package. I want to propose using the sending address whenever a Mastercoin message does not contain a recipient address.
Agreed.  Though I actually think we should make it the sender address for everything because as you note, not all transactions will have a reference address.  We may as well stick with an address we know will always be there.  Unless you guys know of a reason for not using the sender address let's lock that in as our initial source for the SHA256 hashing & I'll update the amendment accordingly.

Agreed, let's just use the sending address for all packages. This should go into the spec. Smiley
hero member
Activity: 938
Merit: 1000
Sorry guys have to be quick - back to back meetings today.

Long story short according to the current rules that transaction is not valid due to ambiguous sequence numbers, this is why masterchest.info throws the transaction out.

19b5BiXWZERFoCNhVKiYDf9i829P1W1wiE has a sequence number of 94
19UjqqjXmQxyyn4xStA7mWXVkzXwVDgu7Z has a sequence number of 93
19feAR37pguLwDyEMc8oiW2WT4esrgR5z6 has a sequence number of 95

Having all the outputs be the same amount is merely a convenience for identifying the change address. I'm fine with a less strict implementation as long as it is still possible to identify the change address.

So I removed the requirement for outputs to be the same amount to allow for multisig outputs no longer meeting said requirement.  So as it stands now I no longer evaluate what the value is of each vout, only the sequence numbers matter.

I think we need some further discussion on backwards compatibility for these Class A transactions.  Perhaps we need to re-introduce the 'same output amount' rule as a requirement just for Class A transactions as we can then use the amounts to help identify change as per the original spec - at the moment there seems to be some ambiguity around Class A transaction validity between our implementations and we need to clear this up.  You can probably understand now why I'm putting so much effort into having these rules explicitly defined and documented Smiley  I do concur that random chance of sequence number collisions should not be a factor in transaction validity.

None of this is an issue in multisig as we require change to be from the sender as a method of removing address ambiguity.

This is why I am not a fan of flagging a transaction invalid based sequence. This guy was just trying to create a transaction and he had no way that random chance could make it invalid.

As long as we can safely identify the data address then a perfect sequence number is not a problem. I say we simply peak into each address and see if it contains a known Mastercoin message. Currently only SimpleSends are supported so we can just peak into an address, decode it and see if the transaction type is 0 and the and currency_id is within limits and if the sequence number makes sense. If we can say with a certain certainty that this is most likely a simple send then we have our data address and know which sequence the target address should be. This will work for a broken sequence as well. The only problem is the ambiguous sequence. In this case there is simply no way of finding out the correct address and the transaction should be made invalid. Since the random factor can't be solved here we might need to solve it differently and go back a step.

How about we do the following.

  • Only allow Simple Sends to be encoded as addresses. All new messages should use pulic keys.
  • All outputs that contain Mastercoin data for Class A transaction should have the same output amount, but it doesn't matter how much this amount is.
  • Probe each address to see if it's a Mastercoin encoded address using the checks outlined above.

Checks to see if it's a Mastercoin encoded address
  • Transaction type is 0
  • Currency ID is an existing Currency ID, for now only 1 and 2 are created but this might chance in the future

If we follow these rules then there should always be three outputs. One you can rule out based on the fact that it's Exodus. One of those is the data package and one the target address. In most cases you can probably know which is which even without the sequence number.

I will make some time today to see if this change would affect any existing transactions but I highly doubt it. 
sr. member
Activity: 266
Merit: 250
Some notes. When I SHA the reference I only take the first 62 bytes since this is the exact amount we need for the obfuscation. This will change the the SHA of the next iteration of hashes that follow so I'm open to discuss this.
Wasn't quite sure what you meant by this so I thought I'd just note that there is no need to drop or add bytes to/from the inputs of our SHA256 hashing if that's what you mean?  SHA256 hashing will always produce a 256 bit (32 byte) hash regardless of input length.  To clarify my take on things:

With each packet:
   * For sequence number 1 we SHA256 the entire length of the address (which could be anywhere from 27 to 34 bytes), result = 32 byte hash.  
   * For sequence numbers 2 onwards, we take the previous 32 byte hash and SHA256 it again (and again), result = 32 byte hash.  
   * We then take the resulting 32 byte hash, grab the first 31 bytes and XOR with the cleartext Mastercoin packet.
Rinse & repeat.

Perhaps that's what you meant, sorry if I'm getting confused or repeating stuff - there's been so much thought & discussion on this stuff it's all kind of a blur! Smiley

So for your address of 1J2svn2GxYx9LPrpCLFikmzn9kkrXBrk8B, the first 5 packets should have hashes of (in between { } is what you would XOR with):

Code:
SEQNUM=1   {D42C390E52F1110412078A9DB148E7A306924666FB10AAAA9BFFCC2E2ECDE3}44
SEQNUM=2   {000EC2C68806819E67A030E82A6AF98376DAC1065D7FE533DAF251D43AA836}3B
SEQNUM=3   {999722F745CC7EA5559D871285A697513D6D1F69294A472AB71499C280CFDA}72
SEQNUM=4   {23C4AC723733621964260EC4639D9DF3469E983E677B083457F325C6F56FA5}D0
SEQNUM=5   {A2989BBA3E4BF3B2995A8573E19450381C94CDE10F95A157756148217B0E37}1B

Thoughts?

We haven't discussed what we will use to XOR data for a 'Selling MasterCoins for Bitcoins' package. I want to propose using the sending address whenever a Mastercoin message does not contain a recipient address.
Agreed.  Though I actually think we should make it the sender address for everything because as you note, not all transactions will have a reference address.  We may as well stick with an address we know will always be there.  Unless you guys know of a reason for not using the sender address let's lock that in as our initial source for the SHA256 hashing & I'll update the amendment accordingly.

EDIT: for clarity
sr. member
Activity: 449
Merit: 250
    Hi Grazcoin

    You are the first to post to the the blockchain using the new multi sig.  Nice work!   ( I was able to parse your transaction  =)   

    Data to Parse: 021bf733f7aab3932560cd8e8a3ec11b45ee47f0694a0b61c86ab48e63bba57cd4
    OBFUSCATED MASTERCOIN PACKET: 1bf733f7aab3932560cd8e8a3ec11b45ee47f0694a0b61c86ab48e63bba57c
    SHA256 HASH: 1af733f7aab3932561cd8e8a3ec1a724a047f0694a0b61c86ab48e63bba57cd0
    REFERENCE ADDRESS: 17RVTF3vJzsuaGh7a94DFkg4msJ7FcBYgX
    CLEARTEXT MASTERCOIN PACKET: 0100000000000000010000000000bc614e0000000000000000000000000000

    01: 1 (01)
    Trans Type: 0 (00000000)
    Currency ID: 1 (00000001)
    Amount for Sale: 12345678 (0000000000bc614e)


  • The padded dataHex is 0100000000000000010000000000bc614e0000000000000000000000000000
  • After obfuscation (using sha256 of the string '17RVTF3vJzsuaGh7a94DFkg4msJ7FcBYgX') and adding 02 at the beginning and a random tail, it becomes 021bf733f7aab3932560cd8e8a3ec11b45ee47f0694a0b61c86ab48e63bba57cd4
  • Within 4 iterations of searching for a valid pubkey (each time adding 1), a valid one is found.
  • A transaction is created and signed.
  • A parsing test shows the same values.

On blockchain.info, the transaction looks this way. Note that the input used for the transaction was too small to include also change (the change was less than the dust limit), so all the under-dust change got added to the fee. The fee then increased to 0.0001228 instead of the requested 0.0001.


Pages:
Jump to: