elective-stereophonic
elective-stereophonic
Show Posts - mthcl
Please login or register.

Login with username, password and session length
Advanced search  

News:

Latest Stable Nxt Client: Nxt 1.12.2

Show Posts

This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.

Messages - mthcl

Pages: 1 ... 19 20 [21]
401
Transparent Forging / Re: Math of Nxt forging
« on: March 26, 2014, 04:25:10 pm »
Quote from: mthcl
Quote from: ChuckOne

Quote from: mthcl
I was mostly thinking about a "standalone" procedure: you calculate the inverse weights as usual, but then, instead of letting the winner to forge a block, you take the X winners, and tell them "give me you random numbers!" (we assume that they have already published the hashes). Then you sum these random numbers, take the fractional part, and the result is truly Uniform[0,1], provided there is at least one honest guy between the X.

Okay, got that, too.

Just one remark: it does not only require at least one honest guy to create a truly random number but also requires one honest guy to use it (i.e. while forging and accepting blocks).
This random number can be published in the blockchain, so we can even oblige everybody to use it?..

402
Transparent Forging / Re: Math of Nxt forging
« on: March 26, 2014, 04:23:52 pm »
Quote from: ChuckOne
Quote from: mthcl
modulo 1 = fractional part (what's after the decimal dot)

Got it.
(Should be scaled to 256 bits or so.)

Quote from: mthcl
I was mostly thinking about a "standalone" procedure: you calculate the inverse weights as usual, but then, instead of letting the winner to forge a block, you take the X winners, and tell them "give me you random numbers!" (we assume that they have already published the hashes). Then you sum these random numbers, take the fractional part, and the result is truly Uniform[0,1], provided there is at least one honest guy between the X.

Okay, got that, too.

Just one remark: it does not only require at least one honest guy to create a truly random number but also requires one honest guy to use it (i.e. while forging and accepting blocks).

403
Transparent Forging / Re: Math of Nxt forging
« on: March 26, 2014, 04:23:01 pm »
Quote from: mthcl
Quote from: ChuckOne
Quote from: mthcl
Not the hash; it should be a Uniform [0,1] r.v., independent of everything. Supposed to be, say, sum of the outputs of rand() modulo 1.

modulo 1 = divided by 1?

( JFTR, we cannot store real numbers in a block, just a fraction of it. )

Quote from: mthcl
If we do not obscure numbers, then the bad guy can see the X-1 numbers that are already published, and then publish something nonrandom that suits him. If we obscure them first, then the bad guy cannot manipulate, he can only invalidate.

Alright. So, these signed hashes are included in the blocks over time. What happens then? How does the network agree on what outputs to include in the "sum of the outputs of rand() modulo 1"? When will the real outputs be propagated?
modulo 1 = fractional part (what's after the decimal dot)

I was mostly thinking about a "standalone" procedure: you calculate the inverse weights as usual, but then, instead of letting the winner to forge a block, you take the X winners, and tell them "give me you random numbers!" (we assume that they have already published the hashes). Then you sum these random numbers, take the fractional part, and the result is truly Uniform[0,1], provided there is at least one honest guy between the X.

404
Transparent Forging / Re: Math of Nxt forging
« on: March 26, 2014, 04:21:36 pm »
Quote from: ChuckOne
Quote from: mthcl
Not the hash; it should be a Uniform [0,1] r.v., independent of everything. Supposed to be, say, sum of the outputs of rand() modulo 1.

modulo 1 = divided by 1?

( JFTR, we cannot store real numbers in a block, just a fraction of it. )

Quote from: mthcl
If we do not obscure numbers, then the bad guy can see the X-1 numbers that are already published, and then publish something nonrandom that suits him. If we obscure them first, then the bad guy cannot manipulate, he can only invalidate.

Alright. So, these signed hashes are included in the blocks over time. What happens then? How does the network agree on what outputs to include in the "sum of the outputs of rand() modulo 1"? When will the real outputs be propagated?

405
Transparent Forging / Re: Math of Nxt forging
« on: March 26, 2014, 04:19:41 pm »
Quote from: mthcl
Quote from: ChuckOne
Quote from: mthcl
The random number provided by this procedure is supposed to be known to everyone (say, from time to time we insert it to the blockchain) and used to "break" the determinism.

I know. Nevertheless, what exactly is this one number supposed to be? The hash of the sum of the hashes?
Not the hash; it should be a Uniform [0,1] r.v., independent of everything. Supposed to be, say, sum of the outputs of rand() modulo 1.


Quote from: ChuckOne
Quote from: mthcl
The random numbers the accounts provide cannot be precalculated, they are just outputs of rand() or smth similar. In principle, there should not be any "errors" in the procedure: the account first publishes the hash, and then (if required) the number itself. The error can only appear if the guy is deliberately cheating; but, in this case, he doesn't get nothing for it: his account is banned, and the procedure is repeated after some time.

The number should be signed. Otherwise, others could manipulate it and therefore ban certain forgers deliberately. Is it necessary to obscure the numbers?
If we do not obscure numbers, then the bad guy can see the X-1 numbers that are already published, and then publish something nonrandom that suits him. If we obscure them first, then the bad guy cannot manipulate, he can only invalidate.

I agree, it should be signed (so that the we are sure that it was really this account that published it, right?).

406
Transparent Forging / Re: Math of Nxt forging
« on: March 26, 2014, 04:18:21 pm »
Quote from: ChuckOne
Quote from: mthcl
The random number provided by this procedure is supposed to be known to everyone (say, from time to time we insert it to the blockchain) and used to "break" the determinism.

I know. Nevertheless, what exactly is this one number supposed to be? The hash of the sum of the hashes?

Quote from: mthcl
The random numbers the accounts provide cannot be precalculated, they are just outputs of rand() or smth similar. In principle, there should not be any "errors" in the procedure: the account first publishes the hash, and then (if required) the number itself. The error can only appear if the guy is deliberately cheating; but, in this case, he doesn't get nothing for it: his account is banned, and the procedure is repeated after some time.

The number should be signed. Otherwise, others could manipulate it and therefore ban certain forgers deliberately. Is it necessary to obscure the numbers?

407
Transparent Forging / Re: Math of Nxt forging
« on: March 26, 2014, 04:17:09 pm »
I'll publish here now my discussion with ChuckOne (with his permission):

408

The problem with the "random numbers" is that that you can't be sure of the *randomness* so in all likelihood it can and will be *gamed*.

Also it doesn't require "all the members to collude" as just 1 carefully injected number will affect the outcome.

The idea in both mczarnek's and mthcl's algorithms is that nobody can "carefully inject" a number (Matt, correct?). Because, first, only their hashes are known, and then accounts can only include numbers corresponding to these hashes.

409
Transparent Forging / Math of Nxt forging
« on: March 26, 2014, 02:32:34 pm »
Version 0.4.1: http://www.docdroid.net/ahms/forging0-4-1.pdf.html

Added a new section on a "randomization" algorithm.

Conclusions:
- The current forging algorithm is only pseudorandom (deterministic but unpredictable), and there is concern whether this situation could be potentially dangerous. I do think that this danger is not very serious, since  the real world will not hesitate in introducing  some ``real randomness'' to the system (because nodes go  online and offline, money are transferred, etc.).

- Nevertheless, it is possible to propose an extra randomization algorithm,  i.e., the network can achieve a consensus on a Uniform[0,1] random number  independent of the previously published data.

- The procedure for obtaining this random number can be roughly  described in the following way.  First k0 accounts (with respect to the inverse weights) choose some ``random"  numbers locally (e.g., take a local output of rand()),  and publish their hashes.  Then, they publish numbers themselves; if the published number does not correspond  to the hash or is not published at all, then the corresponding account is penalized.  If that happens for at least one account, the whole procedure is invalidated  (and we wait for the next try).

- One can then ``mix'' the k0 numbers (e.g., by summing them modulo 1); if  at least one of the best k0 accounts does not belong to the attacker, the result is ``truly random'' (it cannot be manipulated, even if we suppose that  the attacker controls the otherk0 accounts and cheats by choosing their numbers at will).

- The probability that the attacker controls the best k0  accounts can be bounded from above by bk0, where b is the attacker's stake.

- As noted in the last section, the best strategy for the attacker is to split his money  into many small accounts; so, it is good that the splitting is discouraged  (as shown in Section 2.1).

Please feel free to criticize the algorithm; I don't have any knowledge in cryptography, so I'll be glad to take the opportunity to learn something.   :)

Pages: 1 ... 19 20 [21]
elective-stereophonic
elective-stereophonic
assembly
assembly