MasterCoin: New Protocol Layer Starting From “The Exodus Address”

[Bitoy]

I've created public keys for a  "Sell Mastercoin for Bitcoin" offer. I would appreciate it if an other developer could decode the keys and tell me what they think it says before I broadcast it to the world

Code:

020100000014000000020000000005f5e10000000000000f424060000000000018
02026a000000000000000000000000000000000000000000000000000000000000

Back to back meetings today but will take a look this evening

Data Sequence 1: 1 (01)
Send Type: 20 (00000014)
Coin Type: 2 (00000002)
Amount for Sale: 100000000 (0000000005f5e100)
BitCoins Desired:  1000000 (00000000000f4240)
Time Limit:  96 (60)
Transaction Fee Satoshi :  1573482 (000000000018026a)

1 Test Master coin for sale for 0.01 BTC.

These i'm not sure.

Time Limit is 96 Blocks
Transaction fee is  0.01573482 BTC

[Tachikoma]

Code:

020100000014000000020000000005f5e10000000000000f424006000000000001
020286a00000000000000000000000000000000000000000000000000000000000

Try these instead BitBoy, I think these should work.

A new problem exists though since that second public key is not a valid compressed ECDSA point. It would really help if I could figure out why not.

[HammerFist]

I'd use the word symbiotic rather than parasitic, since I believe we'll be good for bitcoin in the long run.

I had a similar thought as I read it.  "epiphytic" - is more accurate in my view.  See: http://en.wikipedia.org/wiki/Epiphyte  Mastercoin doesn't take nutrients from or otherwise 'feed' off the blockchain - it merely hangs thereon and takes nothing away therefrom.   A true 'parasite' feeds off its host and takes essence therefrom.  

But this cannot be a surprise.  Both Peter and Meni jump at every chance to play Mastercoin into poor light - even when that includes using terms which are not accurate.

[lebing]

Please please design Mastercoin in a way to make attaching it to an altcoin profitable for the current Mastercoin owners. That would be a brilliant move.

I Second this.

Is that even possible?

[Peter Todd]

I'd use the word symbiotic rather than parasitic, since I believe we'll be good for bitcoin in the long run.

I had a similar thought as I read it.  "epiphytic" - is more accurate in my view.  See: http://en.wikipedia.org/wiki/Epiphyte  Mastercoin doesn't take nutrients from or otherwise 'feed' off the blockchain - it merely hangs thereon and takes nothing away therefrom.   A true 'parasite' feeds off its host and takes essence therefrom.  

But this cannot be a surprise.  Both Peter and Meni jump at every chance to play Mastercoin into poor light - even when that includes using terms which are not accurate.

I'm writing a paper on digital asset representation - the term "parasitic consensus system" refers to a whole class of systems, not just Mastercoin. Systems that I incidentally happen to think are the only sane and safe way to to decentralized consensus actually, at least if you're creating something new.

Anyway, if you guys can come up with a neutral term for these systems I'm open to suggestions. The term "embedded consensus system" is a possibility, although I don't know that it gets the meaning across.

Here's a (very) rough draft of that section of my paper:

A proof-of-work blockchain, such as the Bitcoin blockchain, can be made use of
parasistically for a secondary consensus system. Recall the two fundemental
proofs that a blockchain provides: consensus ordering/timestamping and and
proof-of-publication. A Satoshi-style blockchain can be used as an ordered
message publication service - it is not possible to completely prevent the
publication of data without whitelisting censorship\footnote{By this we mean
    that a majority of miners use whitelists to determine if a transaction is
allowed to be mined.} although publication can be made expensive.\footnote{By
"expensive" we mean the fees required to get the transction mined; see FIXME
for a discussion of data embedding techniques.} Thus for a given block height
$i$ we have a set of blocks $B={b_0 ... b_i}$ containing messages $M={m_0 ...
m_j}$. By applying a fixed set of rules to that set of messages multiple
parties can independently arrive at the same state of the system.

A concrete toy example is the is the "String Bling" system. Here we want to
determine what string $s$ is defined as being the most "blinged", where bling
is gained by provably destroying Bitcoins. In addition we want to make it
possible for a given string $s_1$ to have its bling stolen and transferred to
another string, $s_2$, by a hostile act.

FIXME: rewrite without OP_RETURN, making bling be abstract

To do this we make use of provably unspendable
outputs\cite{provably_unspendable}: a scriptPubKey whose first operation is
OP\_RETURN can never evaluate true, and thus is trivially proven to be
unspendable. We say that if a transaction with an output containing a
scriptPubKey of the following form exists in the Bitcoin blockchain $v$ BTC
worth of bling have been assigned to string $s$:

OP\_RETURN "BLING" s

We also say that the bling associated with $s_1$ can be transferred to $s_2$ if
a transaction of the following form exists in the Blockchain, provided that the
total bling associated with $s_1$ at the transaction's height is less than $v$:

OP\_RETURN "STEAL" s\_1 s\_2

The algorithm to evaluate the amount of bling associated with all blinged strings is simple:

S = map()

for block in blocks:
    for tx in block:
        if tx is of form bling:
            S[\s] += tx.value

        else if tx is of form steal:
            if S[s_1] <= tx.value:
                S[s_2] += S[s_1]
                S[s_1] = 0

Note how there may be transactions in the blockchain that are invalid according
to the rules of the bling system - a transaction ma have fields missing or an
attempt to steal bling may have less value than the bling stolen. The presence
of such transactions is of no concern however as it is the rules, not the
blockchain data to which the rules are applied, that determines of the final
state of the system.

The Mastercoin system uses this principle. While not yet well developed, there
exists an agreed upon set of rules that, from the contents of the Bitcoin
blockchain, can derive a set of "Mastercoin" transactions and a final ledger
state derived from data encoded in the Bitcoin blockchain.

Parasitic consensus systems inherently gain the benefits of the security of the
underlying consensus system. Though the "string bling" system may have only a
handful of users interested in it, an attacker attempting to change the state
of the consensus of what strings have what bling would need to attack the
Bitcoin blockchain directly - a signififantly harder problem. A merge-mined or
independently mined string-bling implementation would probably never be secure
against an attacker with a budget of even just a few thousands dollars; by
parasiticly using the Bitcoin blockchain the attacker\'s required budget swells
to hundreds of millions of dollars.

[Tachikoma]

Please please design Mastercoin in a way to make attaching it to an altcoin profitable for the current Mastercoin owners. That would be a brilliant move.

I Second this.

Is that even possible?

No. But please prove me wrong.

[Bitoy]

Code:

020100000014000000020000000005f5e10000000000000f424006000000000001
020286a00000000000000000000000000000000000000000000000000000000000

Try these instead BitBoy, I think these should work.

A new problem exists though since that second public key is not a valid compressed ECDSA point. It would really help if I could figure out why not.

Data Sequence 1: 1 (01)
Send Type: 20 (00000014)
Coin Type: 2 (00000002)
Amount for Sale: 100000000 (0000000005f5e100)
BitCoins Desired:  1000000 (00000000000f4240)
Time Limit:  6 (06)
Transaction Fee Satoshi :  66182 (0000000000010286)

Data Code is

4tvtzmG2Ximf57U7rLZrDLHH6SbM8Ptqebfiqs6n1XDh9oYvdx
4ubsdohy5gbQBQ9tsqAgEw6QSt6gdKsCwCwSmmzao5YuR6NCHk

Is tis correct?

[Tachikoma]

Hmm no the transaction fee should be 100000.

[zathras]

Code:

020100000014000000020000000005f5e10000000000000f424006000000000001
020286a00000000000000000000000000000000000000000000000000000000000

Try these instead BitBoy, I think these should work.

A new problem exists though since that second public key is not a valid compressed ECDSA point. It would really help if I could figure out why not.

Data Sequence 1: 1 (01)
Send Type: 20 (00000014)
Coin Type: 2 (00000002)
Amount for Sale: 100000000 (0000000005f5e100)
BitCoins Desired:  1000000 (00000000000f4240)
Time Limit:  6 (06)
Transaction Fee Satoshi :  66182 (0000000000010286)

Data Code is

4tvtzmG2Ximf57U7rLZrDLHH6SbM8Ptqebfiqs6n1XDh9oYvdx
4ubsdohy5gbQBQ9tsqAgEw6QSt6gdKsCwCwSmmzao5YuR6NCHk

Is tis correct?

Hey Bitoy,

You're including the second byte of the second packet; that's a sequence number

[prophetx]

Our first blog article giving you the latest updates and news in now available online!  Please excuse the stock wordpress template.

Hello, Mastercoin World
http://blog.mastercoin.org/2013/10/18/hello-mastercoin-world/

Here is a summary, for the rest click on the link.

We would like to welcome you to the first issue of the Mastercoin blog.

Each week, right here, rather than having to wade through hundreds of forum posts you will find a summary of the most relevant developments related to Mastercoin.  The focus of the blog initially will be on summarizing project developments, service announcements, exchange market updates, and Mastercoin Foundation financials and developments.  If you have any important news scroll down to the form at the bottom and let us know about what you are working on.

The first two weeks of October brought us some exciting news with more code releases coming out for the $25,000 Code Contest and the final awards going to four developers.  Check the repositories out on GitHub, install them and test them so our community of developers can get your feedback and thoughts!

We also have a proposal...

$25k Code Contest Complete!

Repo Updates & Announcements

Market Update

Protocol & Proposals

Mastercoin Foundation Financials

Job Openings

[Tachikoma]

There is still a problem with creation valid ECDSA points. I'm asking people who are more familiar with ECDSA if they know how we can calculate what a valid key must look like because right now the only option I see is brute-forcing the sequence number to a value that works. If anybody knows more about how to calculate a valid key please let me know.

Let's use the example earlier in this thread.

Code:

1.9.3-p286 :040 > (0..9).to_a.collect{|sequence| {sequence => Mastercoin::Util.valid_ecdsa_point?("020#{sequence}00000014000000020000000005f5e10000000000000f424006000000000001")} }
 => [{0=>true}, {1=>false}, {2=>false}, {3=>true}, {4=>true}, {5=>true}, {6=>false}, {7=>true}, {8=>false}, {9=>false}]

1.9.3-p286 :041 > (0..9).to_a.collect{|sequence| {sequence => Mastercoin::Util.valid_ecdsa_point?("020#{sequence}86a00000000000000000000000000000000000000000000000000000000000")} }
 => [{0=>true}, {1=>true}, {2=>false}, {3=>true}, {4=>true}, {5=>false}, {6=>true}, {7=>true}, {8=>true}, {9=>false}]

The result you see is the sequence number and whether this creates a valid point or not. As you can see it is very random and I don't know exactly why that is.

The other option is of course go Grazcoin's way and simply use invalid ECDSA points. Although I have no clue whether all Bitcoin implementations support this. And even if none of the implementations check the points, is this a well over thought decision or negligence.

[Bitoy]

Hi Zathras,

Thank you.  The Transaction fee is 100000


Data Sequence 1: 1 (01)
Send Type: 20 (00000014)
Coin Type: 2 (00000002)
Amount for Sale: 100000000 (0000000005f5e100)
BitCoins Desired:  1000000 (00000000000f4240)
Time Limit:  6 (06)
Transaction Fee Satoshi :  100000 (00000000000186a0)


Please check this transaction
006a0000001400000001000000003b9aca000000000001c9c38006000000000001
006986a00000000000000000000000000000000000000000000000000000000000

Selling 10 MSC for 0.30 BTC.  Is this correct?

Data Sequence 1: 106 (6a)
Send Type: 20 (00000014)
Coin Type: 1 (00000001)
Amount for Sale: 1000000000 (000000003b9aca00)
BitCoins Desired:  30000000 (0000000001c9c380)
Time Limit:  6 (06)
Transaction Fee Satoshi :  100000 (00000000000186a0)

Note:  Fixed the previous transaction.

Hey Bitoy,

You're including the second byte of the second packet; that's a sequence number

[Tachikoma]

Data sequences for public keys start with 01 for the moment (although my problem described above might change that), no reference to the address is needed, also all compressed keys start with 02.

[Luckybit]

Please please design Mastercoin in a way to make attaching it to an altcoin profitable for the current Mastercoin owners. That would be a brilliant move.

I Second this.

Is that even possible?

No. But please prove me wrong.

It's not impossible. You just have to conceptually think of the current mastercoin owners as shareholders of all future implementations on altcoins. So if there is a mastercoin2, and it's backwards compatible with mastercoin1, then it benefits the owners of mastercoin1.

There are probably ways to do it, but I don't know enough about the protocol to tell you exactly how it can be done. I'm just guessing if its just a protocol layer then the same way our Bitcoins became Mastercoins the Mastercoin1 could become Mastercoin2.

[zathras]

There is still a problem with creation valid ECDSA points. I'm asking people who are more familiar with ECDSA if they know how we can calculate what a valid key must look like because right now the only option I see is brute-forcing the sequence number to a value that works. If anybody knows more about how to calculate a valid key please let me know.

Let's use the example earlier in this thread.

Code:

1.9.3-p286 :040 > (0..9).to_a.collect{|sequence| {sequence => Mastercoin::Util.valid_ecdsa_point?("020#{sequence}00000014000000020000000005f5e10000000000000f424006000000000001")} }
 => [{0=>true}, {1=>false}, {2=>false}, {3=>true}, {4=>true}, {5=>true}, {6=>false}, {7=>true}, {8=>false}, {9=>false}]

1.9.3-p286 :041 > (0..9).to_a.collect{|sequence| {sequence => Mastercoin::Util.valid_ecdsa_point?("020#{sequence}86a00000000000000000000000000000000000000000000000000000000000")} }
 => [{0=>true}, {1=>true}, {2=>false}, {3=>true}, {4=>true}, {5=>false}, {6=>true}, {7=>true}, {8=>true}, {9=>false}]

The result you see is the sequence number and whether this creates a valid point or not. As you can see it is very random and I don't know exactly why that is.

The other option is of course go Grazcoin's way and simply use invalid ECDSA points. Although I have no clue whether all Bitcoin implementations support this. And even if none of the implementations check the points, is this a well over thought decision or negligence.

Hey Tachikoma,

I'm still not learned enough on ECDSA (or elliptic curve cryptography in general) to really be too much help, let's hope someone with better knowledge of ECDSA can steer you in the right direction.

I don't think we should use invalid ECDSA points if at all possible though as we'd be making it blindingly easy to censor mastercoin; the bitcoin devs could simply enforce ECDSA point validity checking on multisig pubkeys and we'd be in trouble.  We're doing what we can to minimize blockchain bloat by using provably redeemable outputs, but I'm conscious that they'll do what they think is in the best interests of bitcoin (rightly so) - it would likely come down to weighing up whatever reasons they may have for wanting to censor mastercoin against how expensive it would be (compute wise) having to verify ECDSA point validity on all output pubkeys.

If you don't get much help on understanding exactly why the keys are not valid ECDSA points there is an ugly solution; sequence numbers don't necessarily have to increment by one for each packet.  As we include all packets in the same multisig output, when we create each packet we could check its ECDSA point validity (does y²=x³+(a*x)+b) and if it's not valid, move the sequence number up one and try again.  Thus the sequence numbers would increment at different intervals but on decoding we can simply take all the packets, order them ascending by sequence number and off we go.  It's not like we have to worry about looking for missing packets (bitcoin should never 'drop' a signatory (ie packet) from a multisig output) and we thus only use valid keys and remove this particular censorship vector.  

As I say, ugly & a last resort (not least because it shrinks our available number of packets) but thought I'd throw it out there, especially since we're limited to 2 data packets at the moment anyway (M of N with the reference client is limited to N=3 right now I think).

Thanks!

EDIT: for clarity

[zathras]

There is still a problem with creation valid ECDSA points. I'm asking people who are more familiar with ECDSA if they know how we can calculate what a valid key must look like because right now the only option I see is brute-forcing the sequence number to a value that works. If anybody knows more about how to calculate a valid key please let me know.

Let's use the example earlier in this thread.

Code:

1.9.3-p286 :040 > (0..9).to_a.collect{|sequence| {sequence => Mastercoin::Util.valid_ecdsa_point?("020#{sequence}00000014000000020000000005f5e10000000000000f424006000000000001")} }
 => [{0=>true}, {1=>false}, {2=>false}, {3=>true}, {4=>true}, {5=>true}, {6=>false}, {7=>true}, {8=>false}, {9=>false}]

1.9.3-p286 :041 > (0..9).to_a.collect{|sequence| {sequence => Mastercoin::Util.valid_ecdsa_point?("020#{sequence}86a00000000000000000000000000000000000000000000000000000000000")} }
 => [{0=>true}, {1=>true}, {2=>false}, {3=>true}, {4=>true}, {5=>false}, {6=>true}, {7=>true}, {8=>true}, {9=>false}]

The result you see is the sequence number and whether this creates a valid point or not. As you can see it is very random and I don't know exactly why that is.

The other option is of course go Grazcoin's way and simply use invalid ECDSA points. Although I have no clue whether all Bitcoin implementations support this. And even if none of the implementations check the points, is this a well over thought decision or negligence.

Hey Tachikoma,

I'm still not learned enough on ECDSA (or elliptic curve cryptography in general) to really be too much help, let's hope someone with better knowledge of ECDSA can steer you in the right direction.

I don't think we should use invalid ECDSA points if at all possible though as we'd be making it blindingly easy to censor mastercoin; the bitcoin devs could simply enforce ECDSA point validity checking on multisig pubkeys and we'd be in trouble.  We're doing what we can to minimize blockchain bloat by using provably redeemable outputs, but I'm conscious that they'll do what they think is in the best interests of bitcoin (rightly so) - it would likely come down to weighing up whatever reasons they may have for wanting to censor mastercoin against how expensive it would be (compute wise) having to verify ECDSA point validity on all output pubkeys.

If you don't get much help on understanding exactly why the keys are not valid ECDSA points there is an ugly solution; sequence numbers don't necessarily have to increment by one for each packet.  As we include all packets in the same multisig output, when we create each packet we could check its ECDSA point validity (does y²=x³+(a*x)+b) and if it's not valid, move the sequence number up one and try again.  Thus the sequence numbers would increment at different intervals but on decoding we can simply take all the packets, order them ascending by sequence number and off we go.  It's not like we have to worry about looking for missing packets (bitcoin should never 'drop' a signatory (ie packet) from a multisig output) and we thus only use valid keys and remove this particular censorship vector.  

As I say, ugly & a last resort (not least because it shrinks our available number of packets) but thought I'd throw it out there, especially since we're limited to 2 data packets at the moment anyway (M of N with the reference client is limited to N=3 right now I think).

Thanks!

EDIT: for clarity

Considering this further, a cleaner approach would be to reserve the last byte of the compressed public key as disposable data.  From my testing, by manipulating the last byte we can get any sequence number into a key that's also ECDSA valid.  It doesn't seem to be very compute expensive as we're only testing at worst 255 iterations - in testing the most I found necessary was 5 though I've only had time to do very limited testing.

I'd like to propose the following amendment to multisig to solve the ECDSA point validity issue (hope you don't mind me using your visualization Tachikoma ):



If we take Tachikoma's first example key 020100000014000000020000000005f5e10000000000000f424006000000000001, let's pop off the last byte as that is now reserved (that byte would begin the next packet) so we now have 020100000014000000020000000005f5e10000000000000f4240060000000000 and a byte to do with as we like.

By manipulating the last byte, we can use whatever sequence number we like and still turn them all into valid keys - the below are all (I believe) valid ECDSA points (as you can see we don't have to work very hard to find a byte that does the job)

Code:

020100000014000000020000000005f5e10000000000000f424006000000000000
020200000014000000020000000005f5e10000000000000f424006000000000002
020300000014000000020000000005f5e10000000000000f424006000000000001
020400000014000000020000000005f5e10000000000000f424006000000000001
020500000014000000020000000005f5e10000000000000f424006000000000001
020600000014000000020000000005f5e10000000000000f424006000000000000
020700000014000000020000000005f5e10000000000000f424006000000000001
020800000014000000020000000005f5e10000000000000f424006000000000000
020900000014000000020000000005f5e10000000000000f424006000000000000
021000000014000000020000000005f5e10000000000000f424006000000000000
021100000014000000020000000005f5e10000000000000f424006000000000000
021200000014000000020000000005f5e10000000000000f424006000000000000
021300000014000000020000000005f5e10000000000000f424006000000000001

Let's do the same with the second example key 020286a00000000000000000000000000000000000000000000000000000000000, again that last byte is reserved so we'll take that off which gives us 020286a000000000000000000000000000000000000000000000000000000000.  Let's see if playing with the last byte can let us use any sequence number and still have valid ECDSA points:

Code:

020186a00000000000000000000000000000000000000000000000000000000000
020286a00000000000000000000000000000000000000000000000000000000005
020386a00000000000000000000000000000000000000000000000000000000000
020486a00000000000000000000000000000000000000000000000000000000000
020586a00000000000000000000000000000000000000000000000000000000001
020686a00000000000000000000000000000000000000000000000000000000000
020786a00000000000000000000000000000000000000000000000000000000000
020886a00000000000000000000000000000000000000000000000000000000000
020986a00000000000000000000000000000000000000000000000000000000001
021086a00000000000000000000000000000000000000000000000000000000000
021186a00000000000000000000000000000000000000000000000000000000001
021286a00000000000000000000000000000000000000000000000000000000002
021386a00000000000000000000000000000000000000000000000000000000001

Again I believe those are all valid ECDSA points.

This would obviously need further testing, I'll put together some code to generate a bunch of different mastercoin data pubkeys and then run them against ECDSA validity checks while manipulating the last byte.

This would of course be compatible with existing multisig sends as the last byte on them is already just padding.

Feedback/thoughts on this proposed amendment to multisig would be most welcome.

Thanks!

EDIT: I've written the above primarily discussing sequence numbers as that was the context of the discussion, but it's worth noting that data throughout the key (not just sequence numbers) influences ECDSA point validity, and this last byte technique should allow us to make any of the varying mastercoin pubkeys we create ECDSA valid.

[stink]

Please please design Mastercoin in a way to make attaching it to an altcoin profitable for the current Mastercoin owners. That would be a brilliant move.

I Second this.

Is that even possible?

No. But please prove me wrong.

It's not impossible. You just have to conceptually think of the current mastercoin owners as shareholders of all future implementations on altcoins. So if there is a mastercoin2, and it's backwards compatible with mastercoin1, then it benefits the owners of mastercoin1.

There are probably ways to do it, but I don't know enough about the protocol to tell you exactly how it can be done. I'm just guessing if its just a protocol layer then the same way our Bitcoins became Mastercoins the Mastercoin1 could become Mastercoin2.

I think i have it all figured out.....hummm

[stink]

Please please design Mastercoin in a way to make attaching it to an altcoin profitable for the current Mastercoin owners. That would be a brilliant move.

I Second this.

Is that even possible?

colorcoin.org.....

[Tachikoma]

There is still a problem with creation valid ECDSA points. I'm asking people who are more familiar with ECDSA if they know how we can calculate what a valid key must look like because right now the only option I see is brute-forcing the sequence number to a value that works. If anybody knows more about how to calculate a valid key please let me know.

Let's use the example earlier in this thread.

Code:

1.9.3-p286 :040 > (0..9).to_a.collect{|sequence| {sequence => Mastercoin::Util.valid_ecdsa_point?("020#{sequence}00000014000000020000000005f5e10000000000000f424006000000000001")} }
 => [{0=>true}, {1=>false}, {2=>false}, {3=>true}, {4=>true}, {5=>true}, {6=>false}, {7=>true}, {8=>false}, {9=>false}]

1.9.3-p286 :041 > (0..9).to_a.collect{|sequence| {sequence => Mastercoin::Util.valid_ecdsa_point?("020#{sequence}86a00000000000000000000000000000000000000000000000000000000000")} }
 => [{0=>true}, {1=>true}, {2=>false}, {3=>true}, {4=>true}, {5=>false}, {6=>true}, {7=>true}, {8=>true}, {9=>false}]

The result you see is the sequence number and whether this creates a valid point or not. As you can see it is very random and I don't know exactly why that is.

The other option is of course go Grazcoin's way and simply use invalid ECDSA points. Although I have no clue whether all Bitcoin implementations support this. And even if none of the implementations check the points, is this a well over thought decision or negligence.

Hey Tachikoma,

I'm still not learned enough on ECDSA (or elliptic curve cryptography in general) to really be too much help, let's hope someone with better knowledge of ECDSA can steer you in the right direction.

I don't think we should use invalid ECDSA points if at all possible though as we'd be making it blindingly easy to censor mastercoin; the bitcoin devs could simply enforce ECDSA point validity checking on multisig pubkeys and we'd be in trouble.  We're doing what we can to minimize blockchain bloat by using provably redeemable outputs, but I'm conscious that they'll do what they think is in the best interests of bitcoin (rightly so) - it would likely come down to weighing up whatever reasons they may have for wanting to censor mastercoin against how expensive it would be (compute wise) having to verify ECDSA point validity on all output pubkeys.

If you don't get much help on understanding exactly why the keys are not valid ECDSA points there is an ugly solution; sequence numbers don't necessarily have to increment by one for each packet.  As we include all packets in the same multisig output, when we create each packet we could check its ECDSA point validity (does y²=x³+(a*x)+b) and if it's not valid, move the sequence number up one and try again.  Thus the sequence numbers would increment at different intervals but on decoding we can simply take all the packets, order them ascending by sequence number and off we go.  It's not like we have to worry about looking for missing packets (bitcoin should never 'drop' a signatory (ie packet) from a multisig output) and we thus only use valid keys and remove this particular censorship vector.  

As I say, ugly & a last resort (not least because it shrinks our available number of packets) but thought I'd throw it out there, especially since we're limited to 2 data packets at the moment anyway (M of N with the reference client is limited to N=3 right now I think).

Thanks!

EDIT: for clarity

Considering this further, a cleaner approach would be to reserve the last byte of the compressed public key as disposable data.  From my testing, by manipulating the last byte we can get any sequence number into a key that's also ECDSA valid.  It doesn't seem to be very compute expensive as we're only testing at worst 255 iterations - in testing the most I found necessary was 5 though I've only had time to do very limited testing.

I'd like to propose the following amendment to multisig to solve the ECDSA point validity issue (hope you don't mind me using your visualization Tachikoma ):



If we take Tachikoma's first example key 020100000014000000020000000005f5e10000000000000f424006000000000001, let's pop off the last byte as that is now reserved (that byte would begin the next packet) so we now have 020100000014000000020000000005f5e10000000000000f4240060000000000 and a byte to do with as we like.

By manipulating the last byte, we can use whatever sequence number we like and still turn them all into valid keys - the below are all (I believe) valid ECDSA points (as you can see we don't have to work very hard to find a byte that does the job)

Code:

020100000014000000020000000005f5e10000000000000f424006000000000000
020200000014000000020000000005f5e10000000000000f424006000000000002
020300000014000000020000000005f5e10000000000000f424006000000000001
020400000014000000020000000005f5e10000000000000f424006000000000001
020500000014000000020000000005f5e10000000000000f424006000000000001
020600000014000000020000000005f5e10000000000000f424006000000000000
020700000014000000020000000005f5e10000000000000f424006000000000001
020800000014000000020000000005f5e10000000000000f424006000000000000
020900000014000000020000000005f5e10000000000000f424006000000000000
021000000014000000020000000005f5e10000000000000f424006000000000000
021100000014000000020000000005f5e10000000000000f424006000000000000
021200000014000000020000000005f5e10000000000000f424006000000000000
021300000014000000020000000005f5e10000000000000f424006000000000001

Let's do the same with the second example key 020286a00000000000000000000000000000000000000000000000000000000000, again that last byte is reserved so we'll take that off which gives us 020286a000000000000000000000000000000000000000000000000000000000.  Let's see if playing with the last byte can let us use any sequence number and still have valid ECDSA points:

Code:

020186a00000000000000000000000000000000000000000000000000000000000
020286a00000000000000000000000000000000000000000000000000000000005
020386a00000000000000000000000000000000000000000000000000000000000
020486a00000000000000000000000000000000000000000000000000000000000
020586a00000000000000000000000000000000000000000000000000000000001
020686a00000000000000000000000000000000000000000000000000000000000
020786a00000000000000000000000000000000000000000000000000000000000
020886a00000000000000000000000000000000000000000000000000000000000
020986a00000000000000000000000000000000000000000000000000000000001
021086a00000000000000000000000000000000000000000000000000000000000
021186a00000000000000000000000000000000000000000000000000000000001
021286a00000000000000000000000000000000000000000000000000000000002
021386a00000000000000000000000000000000000000000000000000000000001

Again I believe those are all valid ECDSA points.

This would obviously need further testing, I'll put together some code to generate a bunch of different mastercoin data pubkeys and then run them against ECDSA validity checks while manipulating the last byte.

This would of course be compatible with existing multisig sends as the last byte on them is already just padding.

Feedback/thoughts on this proposed amendment to multisig would be most welcome.

Thanks!

EDIT: I've written the above primarily discussing sequence numbers as that was the context of the discussion, but it's worth noting that data throughout the key (not just sequence numbers) influences ECDSA point validity, and this last byte technique should allow us to make any of the varying mastercoin pubkeys we create ECDSA valid.

I've been using sequence incrementation to get around the problem for now, but as you mentioned it's not that pretty. A month ago when I first started doing pubkeys I think I also tried incrementing the last byte. But even that was not fail safe. I will see if I have saved the examples that I worked with then. I will also work on a small test suite to see if this will solve the problem once and for all. Although I would still like to understand _why_ it is happening.

bybitcoin: I'm not sure how to ask the question mathematically (if that's a word but we basically want to know what a valid coordinate for a ECDSA curve looks like.
For instance why is '020000000014000000020000000005f5e10000000000000f424006000000000001' a valid point but '020100000014000000020000000005f5e10000000000000f424006000000000001' not.

I gone for the weekend in an hour or so, taking a small trip with the family so I might not be around much this weekend, I'm not sure how the wifi will be. I will try to check in.

[zathras]

I ran up 20,000 compressed pubkeys from random, then used the last byte rotation method to try and make them valid ECDSA points.  

Seems to have worked for all 20,000 - but my ECDSA point validity testing is being done with code from the Casascius Bitcoin Address Utility and there is a line in there that is making me wonder whether the validatePoint() and other check functions are giving me the whole picture on whether the keys are valid:

Code:

// todo: ensure X and Y are on the curve

You can find the results here.  Tachikoma, when you're back and have a bit of time would you mind taking the '*RAW' file and running some of those pubkeys through your Mastercoin::Util.valid_ecdsa_point? function and see what results you get?  They are the corrected keys with the last byte rotated and all 20,000 are supposed to be valid.