Nxt :: Automated Transactions (AT) - progress and discussion

[greatwolf]

As I understand, the tx malleability in bitcoin is possible because the transaction id isn't being signed by the private key when doing ECDSA. Since Nxt is designed from the ground-up with its own protocol, why are tx id's still malleable?

If you design it so the tx id is part of the hash being ECDSA signed would this not address the malleability problem since changing the tx id at this point by an attacker would invalidate the ECDSA signature and consequently rejected by nodes?

[1715178630]

1715178630

[1715178630]

1715178630

[1715178630]

1715178630

[Zahlen]

Well - one big snag with a "use case" that I think a few had hoped we would be able to do.

We were thinking of something like a Nxt "lottery" where you would send amounts to the "script" and after x amount of time it would pay out its balance to a "winner".

The problem is that it doesn't seem possible to get "random" data in Nxt. People can change txid's (due to malleability) and forgers can simply omit transactions including those that run the script making it impossible for such a lottery to be actually "fair". Also TF means that you can actually predict some hashes even in the future (was BCNext trying to tell us "not to gamble"?).

Perhaps there is something we haven't thought of yet to still make this possible so if anyone has a great idea about that please let us know!

If the lottery takes place over a long time, you could use info from a block that's generated a long time after lottery entries are no longer allowed, long enough to be essentially unpredictable.


Alternatively, this might be one way to do it. There's a flaw, I'll explain a patch to it later to keep the description simple.

1) Before the lottery starts, lottery starter chooses a hash function Hash() with range 0 to N-1 inclusive, and also picks a number OFFSET. He announces Hash, Hash(OFFSET) and the number of lottery winners publicly.

2) During the lottery, all lottery participants and the lottery starter each pick a different number l_i and announce it publicly in any order.

3) At the end of the lottery, lottery starter reveals OFFSET. Hash(l_i + OFFSET) is computed for all lottery participants and the lottery starter, and the winners are the participants whose hashes are closest to that of the lottery starter's in Z/N (i.e. regarding N-1 as "wrapping around" to 0).


If Hash is a strong hash function and if OFFSET is essentially uniform random from the perspective of the participants, then the lottery is fair, since the distribution of the Hash(l_i + OFFSET)s will be essentially uniform random and unpredictable before the lottery has ended. Any Evil Dave (note the space!) who waits until the last possible moment before announcing their l_ED so as to get as much info as possible about the other participants' l_i s can still do no better than making a random choice of l_ED.


The hitch is that this depends on OFFSET being difficult to predict. Consequently this depends on the lottery starter being competent and honest: they need to choose OFFSET sufficiently randomly, and not reveal it to any of the participants before the lottery has finished. But there is much lower burden for OFFSET to be difficult to predict than there is for the draw (all the Hash(l_i + OFFSET)) to be, since there's a large computation burden in order to make use of any bias in the distribution of OFFSET: If Evil Dave wants to find a favourable l_ED, he will need to compute Hash(l_i + OFFSET) for all participants i and all likely OFFSETs, whereas anyone verifying the lottery only needs to compute Hash(l_i + OFFSET) for all i and a fixed offset. Hash() could also be chosen to be many iterations of a common hash function.

So a way to adjust it without depending on the honesty of the lottery starter is, instead of having the lottery starter choose OFFSET, to have OFFSET be determined by the lottery participants in a difficult to predict way (not necessarily uniform random). OFFSET = sum of account numbers of all participants might work, if participants don't need to pre-register for the lottery.

[CIYAM]

@Fry - I like your thinking as the forger can't do anything to change that (other than not forge which results in the not allowed to forge for a while penalty), however, it still means that the forger at least knows this value and so might decide whether or not to include their own tx depending upon whether they win (effectively improving their odds vs. non-forgers).

@greatwolf - I am not sure of the exact reason for the malleability (perhaps it is due to the choice of a random value for the signature stuff?) but have been assured by CfB that this is the case. This type of malleability also exists in Bitcoin but it isn't the cause of the recent problems as only the private key holder can create a different but still valid signature by using a different random number (if you play with "signrawtransaction" you'll notice that each time you call it you end up with a result due to this behaviour).

@Zahlen - I had also started to think along those lines and it could work fairly for players other than in the "final" block. The problem in the final block is once again the forger can check whether or not their own tx will be a winner and if not simply omit it. In fact you could even end up with the lottery being stuck as each forger might refuse to run that script unless their own tx can be inserted as the winner.

Effectively you need the block that marks where the payout applies from to be one that has already been forged *but* not knowable until a subsequent block and also not even approximately knowable in order to prevent gaming the system.

And btw thanks for the input guys - as you can see we are dealing with some rather tricky problems.

[CIYAM]

Okay - one thing that does help out with this difficult problem is "confirmations" as we wouldn't accept "tickets" that aren't fully confirmed.

So if people are going to wait until the "last minute" to purchase a ticket then that isn't going to be perfectly predictable as the timing for block forging isn't exact (so hard to know when we are exactly 10 blocks before the "payout"). This also means it isn't dead easy for the forger to know that the current block they are forging will be *the* block that counts.

What I am thinking might work (although I doubt it is perfect) is that you combine the public key of the tx owner (which can't be changed thus avoiding malleability) with the "secondary hash" (which can't really be predicted) of a block that comes x blocks *after* it (in order to be more sure of that block you'd want to make sure that it has had at least 10 confirmations).

So in this case a valid entrant might be a tx with say 15 confirmations and the entrant's public key is concatenated with the hash of the block that is 5 in front of its own and then hashed with the lowest 64 bits returned as your "ticket number".

I don't think that this idea is perfect but I do think it is at least getting closer to being a "fair" lottery.

[Zahlen]

The problem in the final block is once again the forger can check whether or not their own tx will be a winner and if not simply omit it. In fact you could even end up with the lottery being stuck as each forger might refuse to run that script unless their own tx can be inserted as the winner.

Ah, right! I forgot that some of the lottery players could actually control execution. Wow, crypto$ thinking is tricky...

Effectively you need the block that marks where the payout applies from to be one that has already been forged *but* not knowable until a subsequent block and also not even approximately knowable in order to prevent gaming the system.

I thought about this as well, but figured it might cause players who missed out by 1 block to scream bloody murder. Even if you know intellectually and logically that the rule is "fair" for everyone, psychologically it still sucks. (But I'm thinking about how people respond to games of chance in RL; maybe I'm misunderstanding the mindsets of crypto$ dice rollers?)

[CIYAM]

I thought about this as well, but figured it might cause players who missed out by 1 block to scream bloody murder. Even if you know intellectually and logically that the rule is "fair" for everyone, psychologically it still sucks. (But I'm thinking about how people respond to games of chance in RL; maybe I'm misunderstanding the mindsets of crypto$ dice rollers?)

Actually as it would be a "continuous" lottery they would just end up with a ticket in the "next round" so I don't think it would be such a problem (the draws could be done daily or weekly I guess).

Now that I think about it perhaps instead of using the secondary hash (which can be altered by the forger) it might be better just to simply add up x time stamps from the following blocks and hash that (as a forger can't modify the time stamp by very much or they would end up creating an invalid block).

So given that the forger can only alter the time stamp by +-15 seconds (or it is more - am not sure about that) then at best they can decide which of 30 different values would be most suitable for a ticket that was purchased x blocks ago. It is still of some advantage to the forger who happens to be a player but it isn't a huge advantage (and you wouldn't always be able to predict that you will be the one forging the block x blocks in the future so you are still taking a risk by "buying a ticket").

[Zahlen]

Now that I think about it perhaps instead of using the secondary hash (which can be altered by the forger) it might be better just to simply add up x time stamps from the following blocks and hash that (as a forger can't modify the time stamp by very much or they would end up creating an invalid block).

So given that the forger can only alter the time stamp by +-15 seconds (or it is more - am not sure about that) then at best they can decide which of 30 different values would be most suitable for a ticket that was purchased x blocks ago. It is still of some advantage to the forger who happens to be a player but it isn't a huge advantage (and you wouldn't always be able to predict that you will be the one forging the block x blocks in the future so you are still taking a risk by "buying a ticket").

Timestamp sounds like a good hard-to-predict data source! Will the timestamp be in seconds or something smaller like milliseconds? And how punctual will most forgers be in practice, once TF is activated? But whatever the case, you can control the granularity by taking e.g. floor(time / CONSTANT), or some other more sophisticated function that makes all output values approximately equally likely, so you can control how many possibilities a forging entrant could choose from.

Let N be the number of possibilities of the timestamp -> data function. You'll want N small enough to minimize cheating forger advantage, but N^x large enough that it's impractical for other cheating participants to compute a significant advantage. It's a balancing act, but sounds doable with suitable obfuscations/iterations to the lottery function.

Is there another hard-to-predict data source that can be used in addition to timestamp?

EDIT: Plenty I think, if we're sampling over multiple blocks. Total # of transactions, total Nxt transacted, sum of account numbers of everyone who made a transaction, etc. Granularity can again be controlled by suitable functions. The key thing is that we're taking data over multiple blocks, not just one, so no single forging participant can have large control.

[Come-from-Beyond]

Is there another hard-to-predict data source that can be used in addition to timestamp?

In future we'll get rid of timestamps, we don't need them coz block height will define the timestamp (we'll have exactly 60 sec between blocks).

[Zahlen]

Is there another hard-to-predict data source that can be used in addition to timestamp?

In future we'll get rid of timestamps, we don't need them coz block height will define the timestamp (we'll have exactly 60 sec between blocks).

That means the network will treat blocks as generated right on the minute then? (In practice they won't be, due to processing lag, connection lag, etc, just that for computation purposes we regard it as exact, then try to adjust the practice to keep as close to that as possible?)

[CIYAM]

Plenty I think, if we're sampling over multiple blocks. Total Nxt transacted, sum of account numbers of everyone who made a transaction, etc. The key thing is that we're taking data over multiple blocks, not just one, so no single forging participant can have large control.

Indeed - as CfB has pointed out "time stamp" isn't going to cut it so I think something like a hash of the sum of account numbers will probably have to do the trick.

I guess also that if the number of blocks required to be known about in the future is big enough (maybe something like 100 might be a more reasonable choice) then hopefully the uncertainty of at least a few forgers not "taking their turn" would make the chance of a forger being able to gain an advantage by omitting some transactions fairly slim (as they would have to had to purchase their own "lottery ticket" exactly x blocks before).

EDIT: Perhaps 64 will be the magic number. I am thinking we take 1 bit (say mod 2 of the second hash) from each of the 64 blocks that come after the block that the tx comes from and then finally hash that. In this way there is no benefit to "mine" for a better hash as each forger (on their own) can only affect the outcome by 1 bit so you would require collusion from numerous forgers (who are all forging one after another) to have a real chance of being able to "rig" the result.

[ChuckOne]

If you like living on the edge these days: "Malleable Operations"

Indeed - btw - after some consideration the "use case" of the "dividend" doesn't actually seem to be a very good use case for scripting anyway (it could be done more efficiently with a special "pay to many" tx type).

So we are interested in some better use cases - a couple of ideas we have so far are:

1) A "lotto" in which the script contains the "hash" of a secret. People send funds to the script and then when the secret is revealed the funds are sent to the tx whose hash (or time stamp or combination) is closest.

2) A "dead man's switch" savings account that will send your funds to another account if you don't instruct it otherwise (say once per year).

Perhaps we could come up with something better than these as a more "compelling" use case to justify why we want to create such a script system?

See this one: https://bitcointalk.org/index.php?topic=458036.msg5158434#msg5158434

[ZeroTheGreat]

Is there another hard-to-predict data source that can be used in addition to timestamp?

In future we'll get rid of timestamps, we don't need them coz block height will define the timestamp (we'll have exactly 60 sec between blocks).

What about network topology (even if Nxt'll be world-wide network, in some areas for plenty of reasons could happen blackouts) and orphans?

[ChuckOne]

Indeed - btw - after some consideration the "use case" of the "dividend" doesn't actually seem to be a very good use case for scripting anyway (it could be done more efficiently with a special "pay to many" tx type).

Distributed computing in general. The fees should be therefore really small to encourage it.

Will we limit the number of ops per block as we limit the number of transactions per block?

[Come-from-Beyond]

What about network topology (even if Nxt'll be world-wide network, in some areas for plenty of reasons could happen blackouts) and orphans?

TF requires that rate of orphaned blocks is very high.

[ChuckOne]

What about network topology (even if Nxt'll be world-wide network, in some areas for plenty of reasons could happen blackouts) and orphans?

TF requires that rate of orphaned blocks is very high.

Speaking of orphaned blocks, I would say limiting the number of ops per block can be healthy to reduce wasted computing.

Thinking this further: nodes are then interested to get their blocks accepted because computing is expensive.

[CIYAM]

After some discussion CfB and myself are thinking that the best "random" data we can get is going to be the block id of the block 1440 blocks later than the block someone's "ticket" is purchased in the "lottery" (so the lottery would likely be a "weekly" event rather than a daily one).

What we'd really like to find is a "math guru" who could help us out with determining whether our approach will be "fair". If you are or you know any such "math guru" please let them know (there will be a reward provided the said person has the skills and the "rep").

[Fry]

@Fry - I like your thinking as the forger can't do anything to change that (other than not forge which results in the not allowed to forge for a while penalty), however, it still means that the forger at least knows this value and so might decide whether or not to include their own tx depending upon whether they win (effectively improving their odds vs. non-forgers).

I see the problem with my proposal.
But having true random data would be great.
If we had true randomness on the Blockchain we could even do this:
For specific accounts we could set a random lock time for new outgoing transactions to be added to the Blockchain.
This would make Instant Payments for such accounts possible because an attacker would not know who the forger is, that can add the next transaction for this account to the Blockchain.

[landomata]

Would it be possible to do the Following with these Scripts?
Forgers, Stakholders or some other trusted entitys post regulary what they think the current USD value of NXT is to the Blockchain.
The script Calculates somehow an average USD price.
The Script now uses its own funds to Buy and Sell an NXT Asset called USD at that price.
Which results in having an Asset USD that has a stable USD value without having a Counterparty Risks (at least as long as the Script has enough NXT to buy that USD Asset).
 

Autonomous pegging is it even possible?

USD Asset price can be set extremely low...

[CIYAM]

But having true random data would be great.

Indeed it would be great but unfortunately the very nature of TF makes this rather tricky.

We have decided to employ the help of a math expert to study what we have come up with so far and work out whether or not it is going to be close enough to random.

[CIYAM]

Autonomous pegging is it even possible?

I think it would be a potential use case although it would need likely need a large amount of NXT to even get close to "pegging" the price.