Topic: MasterCoin: New Protocol Layer Starting From “The Exodus Address” - page 100. (Read 448462 times)

Good to have you in our thread Jeff.  Thanks for checking in.

This is already being implemented, in fact.  Nothing to do with mastercoin.

It looks like a valid transaction.

19ejn7TuHM1MhjuhfT99T7125yHikznf4H sequence number 94 (5E) is the change address
115eZwFLjHS2NWS1feH55LU7bKG45QsbBU sequence number 0 (00) is the reference address
1QFKJvAyJ1EBJ1iFDjgAzMULpGWLaivP7c sequence number 255 (FF) is the data address

The reference address sequence number should be data address sequence number+1, but since the data address sequence number is 255 the next sequence number for the ref address is 0 (ie 256=0, 255+1=0).

From the spec:

I've coded for this scenario (as had mastercoin advisor) which is why the transaction looks OK in masterchest.info.  Probably just that Tachikoma hasn't had time to code for this case yet in mastercoin-explorer.

@Tachikoma: There's an issue with this transaction on mastercoin-explorer:
http://mastercoin-explorer.com/transactions/afa3193c43bdc0554554f1a1fae2428f30dd0bfdea28627f178a49281455d79a
It does not show the correct "To" address.

It looks like masterchest.info shows correct data:
https://masterchest.info/lookuptx.aspx?txid=afa3193c43bdc0554554f1a1fae2428f30dd0bfdea28627f178a49281455d79a

Do you know what's up here?

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:


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.

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.

colorcoin.org.....

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

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)


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:


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.

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

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.

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.

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.

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.


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.

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.

Hey Bitoy,

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

Hmm no the transaction fee should be 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 :  66182 (0000000000010286)

Data Code is

4tvtzmG2Ximf57U7rLZrDLHH6SbM8Ptqebfiqs6n1XDh9oYvdx
4ubsdohy5gbQBQ9tsqAgEw6QSt6gdKsCwCwSmmzao5YuR6NCHk

Is tis correct?

No. But please prove me wrong.

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.