Topic: Nxt :: Automated Transactions (AT) - progress and discussion - page 7. (Read 17307 times)

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.

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").

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.

TF requires that rate of orphaned blocks is very high.

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?

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

See this one: https://bitcointalksearch.org/topic/m.5158434

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.

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?)

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).

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.

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").

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



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?)

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.

@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.

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.

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?

My proposal to solve this issue:
Add a field to every block in the blockchain. This field contains the ECDSA signature of the same field in the previous block (calculated with the forgers private Key).
Use this signature to seed the random function.

Of course that "could be done" as JavaScript is "Turing complete" but it is not an exercise that I would be interested in doing (debugging such scripting languages is a real PITA).

no I know what you mean by "script"

I was just wondering independently could you write most of the nxt client in javascript