Stake and Consensus part 1

In 2009, Satoshi Nakamoto introduced the Bitcoin cryptocurrency[1], 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 consisting of an expensive (but cheaply verifiable) computation done on the entire ledger history every “heartbeat”

Because Bitcoin’s DMMS is computationally, and therefore thermodynamically[2], 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.

Distributed Consensus

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.

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.

Dynamic Membership Multiparty Signatures

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.

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[3] on successive blocks of transactions.

Authentication in an Anonymous world

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

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.

In, Bitcoin uses an alternate security model in which all parties are on equal footing, but they are incentivized to agree.

Security for DMMS

We define DMMS in three components, none of which resembles the key generation algorithm for 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 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.

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.

Here is Bitcoin 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.

No Universal Time

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.

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.
  • Users who are new to the network or have been offline recently need access to historical data. But there is no way to verify after-the-fact what order transactions occurred in, so they cannot be assured that the transactions they are receiving actually occurred before any conflicting ones.

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. In the next part we will understand the Proof of Stake consensus.

Saransh Sharma

Saransh Sharma

Thanks for dropping by, i am currently working on multiple research on Mathematics and Computer Science, and writing codes for Open Source Meanwhile in the process of writing a book about Blockchain and AI.