elective-stereophonic
elective-stereophonic
Thoughts on this POS whitepaper from March 2015? singapore
Please login or register.

Login with username, password and session length
Advanced search  

News:

Latest Stable Nxt Client: Nxt 1.11.15 | Latest Experimental Nxt Client: Nxt 1.12.0e

Author Topic: Thoughts on this POS whitepaper from March 2015?  (Read 910 times)

box1413

  • Hero Member
  • *****
  • Karma: +101/-4
  • Offline Offline
  • Posts: 687
    • View Profile
Thoughts on this POS whitepaper from March 2015?
« on: April 25, 2015, 09:46:03 pm »

https://download.wpsoftware.net/bitcoin/pos.pdf -- updated march 2015

Seems to be an anti-pos article. Not sure if this was discussed already or not.

Quote
Conclusions and Further Research
We have described a mechanism, DMMS, for obtaining a distributed consensus. While DMMS,
in conjunction with some economic requirements, is sufficient to form consensus, it is probably
not necessary. Open problems include reducing these economic assumptions (or showing they
cannot be removed), and determining necessary conditions under which distributed consensus can
be obtained.
We also explored an alternative to DMMS, proof of stake. We showed that by depending only
on resources within the system, proof of stake cannot be used to form a distributed consensus, since
it depends on the very history it is trying to form to enforce loss of value.







Quote
On Stake and Consensus
Andrew Poelstra
2015-03-22
fe81626
This work is released into the public domain.
Note. This document was significantly revised in March 2015. The old version can be found at
https://download.wpsoftware.net/bitcoin/old-pos.pdf.
1 Introduction
In 2009, Satoshi Nakamoto introduced the Bitcoin cryptocurrency[Nak09], an online currency system
which allowed peer-to-peer transfer of digital tokens. To ensure a consistent view of token
ownership, Nakamoto used a public ledger which can be replicated and validated by all network
participants. To avoid a single point of failure, this ledger is authenticated using a dynamic membership
multiparty signature (DMMS)[BCD+14] consisting of an expensive (but cheaply verifiable)
computation done on the entire ledger history every “heartbeat”.
Unlike a traditional digital signature, there is no notion of “forgeability” for a DMMS. Instead,
every DMMS is costly to produce (in Bitcoin, by requiring a large energy expenditure) and rewarded
by introduction of new coins on the ledger. Since these coins are only useful if others recognize
them, participants are incentivized to extend one “true ledger” rather than attempting to create their
own version of history1
.
Because Bitcoin’s DMMS is computationally, and therefore thermodynamically[Poe14a], very
expensive, alternatives have been proposed which seek to be economically and environmentally
more efficient. One popular alternative, proof-of-stake, is frequently proposed as a mechanism
for a cheap distributed consensus. As argued by the author[Poe14b] in 2014, this is simply not
workable, but nonetheless the idea continues to arise in various forms. Meanwhile, the author’s
argument is commonly asserted on various forums to be “debunked” or “wrong”, despite the author
having never been made aware of any workable counterexamples or mistakes. This, combined with
(correct) accusations that the paper is obtuse and unreadable, demonstrate that its exposition leaves
much to be desired. Although this author is not aware of any inaccuracies in his former work, he
has taken the opportunity to continue and elaborate his argument more formally.
Further, there has been significant progress in scientific understanding of Bitcoin’s consensus[MLJ14,
BMC+15] which was not available when the original paper was written.
This paper aims to be an updated version of the author’s original paper, which gives more
explication on the problem Bitcoin solves, why it makes the design decisions that it does, and why
1To ensure that the “true ledger” is visible to all participants, we require a synchronous network such that all (valid) data
reaches all participants in some characteristic time λ, and that the network heartbeat time is much larger than λ. Without a
synchronous network, distributed consensus is much harder. (There is an oft-cited impossibility result for distributed consensus
using deterministic algorithms [FLP85]; this is easy to evade simply by using probabilistic algorithms, and therefore
doesn’t say much about the difficulty of designing consensus systems. Thanks to Dominic Williams for pointing this out;
an earlier version of this document erroneously quoted this result as blocking any distributed consensus in an asynchronous
network.)
1
proof-of-stake and similar mechanisms are fundamentally unable to produce a distributed consensus
within Bitcoin’s trust model.
2 Distributed Consensus
Before discussing Bitcoin’s solution to the distributed consensus problem, it is good to understand
what this problem is. A distributed consensus, as the term is used in Bitcoin, is a consensus (i.e.
global agreement) between many mutually-distrusting parties who lack identities and were not necessarily
present at the time of system set up. As explained in the author’s original paper,
For the purposes of cryptocurrency, it is sufficient to achieve distributed consensus on
the time-ordering of transactions (and nothing else). This implies consensus on the
“first transaction which moves these particular funds”, which assures the funds’ new
owner that the network recognizes them as such.
The reason that this consensus is needed is called the double-spending problem. That
is, in any decentralized digital currency scheme there is the possibility that a spender
might send the same money to two different people, and both spends would appear to be
valid. Recipients therefore need a way to be assured that there are no conflicts, or that
if there are conflicts, that the network will recognize their version as the correct one.
A distributed consensus on transaction ordering achieves this: in the case of conflict,
everyone agrees that the transaction which came first is valid while all others are not.
(The other problems with digital currency, e.g. authentication and prevention of forgery,
are comparatively easy and can be handled with traditional cryptography.)
It is important to realize that while distributed consensus is a hard problem, ordinary consensus
is much easier and better studied, and can be solved some trillions of times more efficiently by use of
trusted identifiable signing parties. Therefore, cryptocurrencies which compromise by introducing
trusted parties, even under limited circumstances, should consider whether their new trust model is
one for which consensus is easily achieved by some other mechanism. Readers interested in more
efficient, trusted schemes are encouraged to investigate this.
3 Dynamic Membership Multiparty Signatures
Bitcoin’s ledger is publically available and the validity of its transactions can be checked by any
participant in the network. However, because the ledger is ultimately a historical claim, and cryptography
cannot distinguish a true history from a false one, there must be some party to authenticate
the ledger, and this party must be trusted not to sign false histories.
The earliest digital cash systems used a single non-anonymous party to sign all transactions[Cha83].
However, this introduced a single point-of-failure for the system as well as giving the signing party
(and everyone with legal or physical power to coerce said party) the ability to censor transactions
or enable double-spending. Although censorship can be prevented by use of blind signatures (also
2
described in [Cha83]), both the single-point-of-failure and double-spending problems cannot be.
They may be alleviated by using multiple signing parties, but the requirement that these parties be
difficult to simultaneously coerce (e.g. by putting them in different legal jurisdictions) conflicts with
the requirement that these parties be trusted by all participants. Their non-anonymity also means
that a dedicated attacker will eventually always be able to attack the system.
Bitcoin’s solution is to do away with the idea of a fixed, identifiable signer entirely. Instead
Bitcoin’s ledger is authenticated by a collection of signers called miners who do not identify themselves
to other participants and may costlessly enter or leave the system. They produce signatures
by a process called mining wherein they collectively produce proofs of work[Bac02] on successive
blocks of transactions.
In this section we explain how mining works and how it provides authentication.
3.1 Authentication in an Anonymous World
A cryptographic digital signature scheme works as follows. A signing party produces a keypair
(s, v) of “signing” and “verification” keys, and publishes v in some public channel alongside her
name. Then given a message m, she can produce a signature σ such that anyone can check that σ
is valid. That is, there is a verification algorithm which takes v, m and σ and will always output 1 if
the signature was created honestly.
To be secure, traditional digital signatures must be unforgeable by any computationally-bounded
adversary except with negligible probability, where forging specifically means winning at the following
game:
1. The signer gives the verification key v to the adversary.
2. The adversary sends messages mi and to the challenger and receives valid signatures σi on
these messages. He may do this as many times as he likes.
3. The adversary produces a message m, which was not queried on earlier, along with a valid
signature σ on m.
This notion of security is known as existential unforgeability under chosen-message attack and is
standard in the cryptographic literature.
(For a multiparty signature, there are multiple verification keys corresponding to multiple signers,
and signatures are only valid if they are produced by an “admissible subset” of them. To define
security, the above game is modified so that the adversary may also request (and receive) secret
keys, as long as no subset of the secret keys that he requests forms an admissible subset.)
We see the verification algorithm uses the verification key v to check signatures, and in this
way checks the “identity” of the signer that produced it. Since anyone can produce a keypair, for
such signatures to be valuable there must be some public record tying verification keys to reallife
identities. Then given dishonest behaviour, i.e. signatures on invalid histories, blame can be
assigned.
It seems then that this notion of authentication cannot be adapted for use in a system where the
signing parties are anonymous and ephemeral. In fact, it’s not clear what “authentication” can even
3
mean in such a system! After all, if anyone can anonymously produce a signature, there is nothing
distinguishing dishonest signatures from honest ones, false histories from the true one. Formally,
the above security definition no longer makes sense since the adversary is free to join the set of
signers and produce a “forgery” that way2
.
To get around this problem, Bitcoin uses an alternate security model in which all parties are on
equal footing, but they are incentivized to agree. We describe this in the next section.
3.2 Defining Security for a DMMS
For a DMMS, all parties are on equal footing; we cannot have a security property with an “adversary”
having incomplete knowledge. We therefore define a DMMS in three components, none of
which resemble the key generation algorithm of a traditional signature:
• A cost function c which takes a trace of an algorithm’s execution and outputs a “cost” t ∈ T ,
where T is some “cost domain”. It must be linear in the sense that the cost of running two
algorithms in series is the sum of their individual costs.
• A randomized algorithm AttemptSign which takes a message m and outputs a signature σ.
The cost of this algorithm should be 1 for every message m.
• A deterministic algorithm Verify which takes a message m, signature σ, and target cost T,
and outputs either 0 or 1.
We say the DMMS is correct if Verify(m,T,AttemptSign(m)) = 1 with probability 1/T for all
T ∈ T , where the probability is taken over the coins of AttemptSign. We say it is secure if no
polynomial-time algorithm A can acheive
Verify(m,T,A (m)) = 1
with probability greater than 1−(1−1/T)
t
, where t is the cost of A ’s execution.
In other words, a secure DMMS is one for which there is no better (in the sense of producing
signatures which verify) signing algorithm than to simply execute AttemptSign repeatedly.
We briefly justify our security definition. In order to achieve a dynamic membership set, we
cannot have expensive entrance costs, nor can we allow existing signers to exclude new entrants
either explicitly or through economic consideration. This implies that signing should be “separable”
in the sense of neither requiring nor rewarding any communication between the signers, which
in turn means that running a signing algorithm for twice as long should be exactly as likely to
succeed as running signing algorithms in parallel across twice as much hardware. In the limit, this
means that the optimal signing algorithm should consist of executing a single basic step many times
independently, which is the given definition.
2As we will see in Section 4, given a cryptocurrency, it is actually possible for anonymous parties to bond value, giving a
mechanism to punish dishonest behaviour without identifying anyone. This is essentially what proof-of-stake is. However, a
cryptocurrency needs a consensus to work, so the phrase given a cryptocurrency prevents us from using proof-of-stake here,
on pain of circular reasoning. We address this further in a later section.
4
3.3 Mining as a DMMS
Bitcoin mining works using a hash-based proof-of-work called hashcash[Bac02]. It is a DMMS in
the random oracle model[BR93]. The random oracle model is a computational model in which a
hash function is modelled as a “random oracle” or truly random function3 whose output is uniformly
random and cannot be computed except by evaluating the function itself.
The use of the random oracle model is quite controversial[Gre11] but there is strong empirical
evidence justifying its use in security arguments. From here on H will denote a hash function taking
arbitrarily many bits to 256 bits, modelled as a random oracle.
Here is Bitcoin’s DMMS:
• The cost function gives the number of random oracle calls in the execution.
• AttemptSign takes a message m, and outputs a random σ ∈ {0,1}
256
.
• Verify takes a signature σ, message m, and target T. It outputs 1 if and only if H(mkσ) < 2
256/T.
It easy to see that in the random oracle model, there is no better way to produce valid signatures
than to simply query the random oracle repeatedly.
3.4 No Universal Time
Notice that in the previous section we used the number of hash-function calls as our cost function,
which is roughly proportional to the number of computations, which in turn is roughly proportional
to the amount of heat dissipated, which finally is roughly proportional to the economic and
environmental cost of producing these signatures.
An obvious question is whether we can use a cost function which is “cheaper” to satisfy; in
particular, why can’t we directly use clock time? For that matter, why are we creating chains
of DMMS-signed blocks instead of just directly ordering transactions in time, always resolving
conflicts in favor of the first?
The answer is that there is no well-defined clock time in a distributed system. Network latency
gives a finite speed of information propagation, which we know from special relativity means
different observers cannot agree on the time-ordering of events that occur closely in time.
If this were the only problem, requiring transactions to be spaced out by several seconds would
be sufficient (if conflicting transactions occur too close together, both are thrown out; but by waiting
a few seconds after each transaction all parties can be assured that this won’t happen). However,
the situation is worse than this for two reasons:
• “Network latency” is not something that can be bounded in an adversarial setting. An attacker
may be able to slow systems by arbitrary amounts using denial-of-service measures, and may
be able to physically partition the network by other means.
In relativistic terms, this means that there is no amount of waiting that will assure somebody
that they are no longer spacelike separated from other participants in the network.
3This model is thoroughly unrealistic, since a truly random function from, say, 512 bits to 256 bits, would require almost
2
512
· 256 bits on average to represent. This is more bits than can be represented in the known universe.
5

......
Logged

rtrtcrypto

  • Sr. Member
  • ****
  • Karma: +37/-5
  • Offline Offline
  • Posts: 279
    • View Profile
Re: Thoughts on this POS whitepaper from March 2015?
« Reply #1 on: April 25, 2015, 09:52:51 pm »

I'm really confused by this NOT WORKABLE rhetoric. HELLO IT'S WORKING!

It's like a mathematical paper on "the inability of earth to ever sustain life"... the fact that the paper is contradicted by actual working systems seems sort of problematic to me.
Logged

box1413

  • Hero Member
  • *****
  • Karma: +101/-4
  • Offline Offline
  • Posts: 687
    • View Profile
Re: Thoughts on this POS whitepaper from March 2015?
« Reply #2 on: April 26, 2015, 01:05:39 am »

its a nice good way to spread FUD... put it on a whitepaper!... would like some devs to chime in on it.
Logged

jl777

  • Hero Member
  • *****
  • Karma: +718/-123
  • Offline Offline
  • Posts: 6170
    • View Profile
Re: Thoughts on this POS whitepaper from March 2015?
« Reply #3 on: April 26, 2015, 01:34:01 am »

I'm really confused by this NOT WORKABLE rhetoric. HELLO IT'S WORKING!

It's like a mathematical paper on "the inability of earth to ever sustain life"... the fact that the paper is contradicted by actual working systems seems sort of problematic to me.
please dont let the facts get in the way of the agenda
Logged
There are over 1000 people in SuperNET slack! http://slackinvite.supernet.org/ automatically sends you an invite

I am just a simple C programmer

jl777

  • Hero Member
  • *****
  • Karma: +718/-123
  • Offline Offline
  • Posts: 6170
    • View Profile
Re: Thoughts on this POS whitepaper from March 2015?
« Reply #4 on: April 26, 2015, 02:11:16 am »

its a nice good way to spread FUD... put it on a whitepaper!... would like some devs to chime in on it.
it is a false logic that is being used.

There are some cases where PoW is required and PoS wont work, therefore you extrapolate that to say PoS will never work and PoW is the only solution.

however any claims that a PoS network cant be made secure has the problem that NXT has simulated mining and so if they prove that NXT doesnt work, then either the NXT simulation of mining is broken or that PoW doesnt work either.

Using common sense, instead of fancy math that nobody understands, the key question is if NXT stake properly simulates mining. There are of course edge cases, but smart guys like BCnext, Cunicula and Come-from-Beyond have dealt with those.

How does mining work? Theoretically, the more hashpower you have, the more likely you are to find the next block. This is because you are doing sha256 calcs with random numbers against the previous block until you find one with a lot of zeroes at the beginning. Similar to finding a NXT account with a lot fewer digits. The reason why more hash power means you can find the next block at a higher probability is that sha256 does a pretty good job scrambling the bits so there is no known way to go backwards, ie start with the answer of having 14 zeroes (bits) and find out what value (nonce) combined with the past block will make that pretty number.

So, you hash, and hash and hash and hash and odds are 2^14 (if you want to find 14 zeroes) to 1 you will find it. Something like that, not sure of the exact probability equation but basically the more hashes you can test, the more likely you are to find the magic value.

How does NXT do it?

It pretends that each NXT you have is hashpower, so the more NXT you have, the more hashes you are doing. OK, that's easy to say but we need a bit more detail to understand how it maps mining. Actually what is important is not the mining (calculating hashes) process, but the distribution of the winning blocks according to mining power.

Now I understand it, this seems a lot simpler than at first when it seemed like magic, so I can understand if you also feel it is magic and therefore not reliable. I will leave out the small details, but the core of how it works is by hashing! Yes, but it does it once. So we get the same randomization effect. But how on earth can 1 hash be mapped to billions of them you ask.

We turn it upside down.

Remember about working backwards from 000000000000001001101010011... to get a bitcoin block, well that doesnt work, but we do have a specific target based on the current block. It is some random hash of hashes of the past hashes hashed against pubkeys, which are in turn curve25519 operations on hashes of passphrases. So, we can assume the reference number is a pretty randomized scramble of bits and this changes with each block, so each block every account can make a specific hash value that will be quite different after each block. You can see this jumping around effect on the various transparent forging sites. The ranking of a specific account changes rather dramatically, but only when there is a new block.

What this means is that we need a way to rank these random numbers against each other and find a winner. I think a large variety of distance functions will work, so we can now make an account with twice the NXT have double the chance of winning, just by multiplying their "hit" (the name for that specific block's hash for a user) by their stake.

Just by using common sense, we can see that if a bigger number is better, you multiply the random hit number by stake. If we want a smaller number, we divide. It is important that the relationship is linear, otherwise either larger accounts or smaller accounts will get an advantage. With NXT the larger accounts get the smallest of advantages and this discourages sybil attacks.

One final tweak is to simulate the passage of time. I hope you can imagine that each block all the accounts are sorted using a very random number specific to each account that is multplied by their stake. So pretty instantly we know who would generate the next block, but we dont want to do it at full speed as then propagation delays and other thinks create all sorts of variations of what nodes think is the correct chain. So we add a factor based on time. As time passes, the threshold needed to forge a block gets easier and easier, so it is just a matter of time before some account(s) qualify.

this seems quite similar to how bitcoin mining works, with some critical differences, but at the heart of it they are quite similar. user specific random numbers multiplied by resources to find a winner using a random mathematical process that cant be cheated.

James

Logged
There are over 1000 people in SuperNET slack! http://slackinvite.supernet.org/ automatically sends you an invite

I am just a simple C programmer
 

elective-stereophonic
elective-stereophonic
assembly
assembly