darkfi/doc/src/architecture/blockchain.md

Dynamic Proof of Stake

Overview

Darkfi is based off Ouroboros Crypsinous, a privacy focused proof-of-stake algorithm. Below is a specification of how DarkFi's current blockchain achieves consensus.

Blockchain

Blockchain $\mathbb{C{loc}}$ is a series of epochs: it's a tree of chains, $C^1$, $C^2$, $\dots$, $C^n$, the chain of the max length in $\mathbb{C{loc}}$ is the driving chain $C_{loc}$.

Crypsinous Blockchain is built on top of Zerocash sapling scheme, and Ouroboros Genesis blockchain. Each part $Up$ stores it's own local view of the Blockchain $C{loc}^{Up}$. $C{loc}$ is a sequence of blocks $Bi$ (i>0), where each $B \in C{loc}$ $$ B = (tx{lead},st)$$ $$tx{lead} = (LEAD,st\overrightarrow{x}{ref},stx{proof})$$ $st\overrightarrow{x}{ref}$ it's a vector of $tx{lead}$ that aren't yet in $C{loc}$. $stx{proof}=(cm_{\prime{c}},snc,ep,sl,\rho,h,ptr,\pi)$ the Blocks' $\emph{st}$ is the block data, and $\emph{h}$ is the hash of that data. the commitment of the newly created coin is: $(cm{c2},r{c_2})=COMM(pk^{COIN}||\tau||vc||\rho{c_2})$, $\tau$ is the clock current time. \emph{$sn_c$} is the coin's serial number revealed to spend the coin. $$snc=PRF{root_{sk}^{COIN}}^{sn}(\rhoc)$$ $$\rho=\eta^{sk{sl}^{COIN}}$$ $\eta$ is is from random oracle evaluated at $(Nonce||\eta_{ep}||sl)$, $\rho$ is the following epoch's seed. $\emph{ptr}$ is the hash of the previous block, $\pi$ is the NIZK proof of the LEAD statement.

st transactions

the blockchain view is a chain of blocks, each block $Bj=(tx{lead},st)$, while st being the merkle tree structure of the validated transactions received through the network, that include transfer, and public transactions.

LEAD statement

for $x=(cm_{c2},sn{c1},\eta,sl,\rho,h,ptr,\mu{\rho},\mu{y},root)$, and $w=(path,root{sk^{COIN}},path_{sk^{COIN}},\tau_c,\rhoc,r{c1},v,r{c2})$ for tuple $(x,w) \in L{lead}$ iff:

• $pk^{COIN} = PRF{root{sk}^{COIN}}^{pk}(\tau_c)$.
• $\rho_{c2}=PRF{root{sk{c1}}^{COIN}}^{evl}(\rho{c_1})$. note here the nonce of the new coin is deterministically driven from the nonce of the old coin, this works as resistance mechanism to allow the same coin to be eligible for leadership more than once in the same epoch.
• $\forall i \in {1,2} : DeComm(cm_{ci},pk^{COIN}||v||\rho{ci},r{c_i})=T$.
• \emph{path} is a valid Merkle tree path to $cm_{c_1}$ in the tree with the root \emph{root}.
• \emph{$path_{sk^{COIN}}$} is a valid path to a leaf at position $sl-\tauc$ in a tree with a root $root{sk}^{COIN}$.
• $sn_{c1}= PRF{root{sk}^{COIN}}^{sn}(\rho{c_1})$
• $y = \mu{y}^{root{sk_{c_1}}^{COIN}||\rho_c}$
• $\rho = \mu{\rho}^{root{sk_{c_1}}^{COIN}||\rho_c}$
• $y< ord(G)\phi_f(v)$ note that this process involves renewing the old coin $c_1$ who's serial number gets revealed(proof of spending), becoming an input, to $c_2$ of the same value,

transfer transaction $tx_{xfer}$

transfer transaction of the pouring mechanism of input: old coin, and public coin, with output: new return change coin, and further recipient coin. such that input total value $v^{old}1 + v{pub} = v^{new}_3 + v^{new}4$ $$ tx{xfer} = (TRANSFER,stx_{proof},cr)$$ $$stx{proof} = ({cm{c{3}}),cm{c{4}}}),({sn_{c2},{sn{c_1}}}),\tau,root,\pi)$$ $cr$ is forward secure encryption of $stx{rcpt}=(\rho_{c3},r{c3},v{c_3})$ to $pk_r$. the commitment of the new coins $c_3$, $c4$ is: $$(cm{c3},r{c3})=Comm(pk{pks}^{COIN}||\tau||v{c3}||\rho{c3})$$ $$(cm{c4},r{c4})=Comm(pk{pkr}^{COIN}||\tau||v{c4}||\rho{c_4})$$

spend proof

the spend proofs of the old coins $sn_{c1},sn{c_2}$ are revealed.

NIZK proof $\pi$

for the circuit inputs, and witnesses

$$x = ({cm_{c3},cm{c4}},{sn{c1},sn{c2}},\tau,root)$$ $$w = (root{sk_{c1}^{COIN}},path{sk_{c1}^{COIN}},root{sk_{c2}^{COIN}},path{sk_{c2}^{COIN}},pk{c3}^{COIN},pk{c4}^{COIN},(\rho{c1},r{c_1},v_1,path1),(\rho{c2},r{c_2},v_2,path2),(\rho{c1},r{c_1},v_1,path_1))$$

$\pi$ is a proof for the following transfer statement using zerocash pouring mechanism.

$$\foralli \in {1,2}: pk{ci}^{COIN} = PRF{root{sk{c_i}}^{COIN}}^{pk}(1)$$ $$\foralli \in {1,\dots,4} : DeComm(cm{ci},pk{c_i}^{COIN}||vi||\rho{ci},r{c_i})=T$$ $$v_1+v_2=v_3+v_4$$

$$path1\text{ is a valid path to } cm{c_1} \text{ in a tree with the root} \emph{ root}$$

$$path2\text{ is a valid path to } cm{c2} \text{ in a tree with the root} \emph{ root}, sn{c2}=PRF{root{sk{c1}^{COIN}}}^{zdrv}(\rho{c_1})$$

$$path{sk{ci}^{COIN}} \text{ is a valid path to a leaf at position } \tau \text{ in }, root{sk_{c_i}^{COIN}} i \in {1,2}$$

$$sn_{ci}=PRF{root{sk{ci}^{COIN}}}^{sn}(\rho{c_i}), \forall_i \in {1,2}$$

toward better decentralization in ouroboros

the randomization of the leader selection at each slot is hinged on the random $y$, $\mu_y$, $\rho_c$, those three values are dervied from $\eta$, and root of the secret keys, the root of the secret keys for each stakeholder can be sampled, and derived beforehand, but $\eta$ is a response to global random oracle, so the whole security of the leader selection is hinged on $\textit{centralized global random node}$.

solution

to break this centeralization, a decentralized emulation of $G_{ro}$ functionality for calculation of: $\etai=PRF^{G{ro}}{\eta{i-1}}(\psi)$ $$\psi=hash(tx^{ep}_{0})$$ $$\eta_0=hash("let there be dark!")$$ note that first transaction in the block, is the proof transaction.

Epoch

An epoch is a vector of blocks. Some of the blocks might be empty if there is no winnig leader.

Leader selection

At the onset of each slot each stakeholder needs to verify if it's the weighted random leader for this slot.

$$y < T_{i}$$ ^{check if the random y output is less than some threshold}

This statement might hold true for zero or more stakeholders, thus we might end up with multiple leaders for a slot, and other times no leader. Also note that no node would know the leader identity or how many leaders are there for the slot, until it receives a signed block with a proof claiming to be a leader.

^{$\eta$ is random nonce generated from the blockchain, $\textbf{sid}$ is block id}

$$\phi_{f} = 1 - (1-f)^{\alphai}$$ $$T{i} = L \phi_{f}(\alpha_i^j)$$

Note that $\phi_f(1)=f$, $\textbf{f}$: the active slot coefficient is the probability that a party holding all the stake will be selected to be a leader. Stakeholder is selected as leader for slot j with probability $\phi_f(\alpha_i)$, $\alpha_i$ is $U_i$ relative stake.

The following are absolute stake aggregation dependent leader selection family of functions.

Linear family functions

In the previous leader selection function, it has the unique property of independent aggregation of the stakes, meaning the property of a leader winning leadership with stakes $\sigma$ is independent of whether the stakeholder would act as a pool of stakes, or distributed stakes on competing coins. "one minus the probability" of winning leadership with aggregated stakes is $1-\phi(\sum_{i}\sigma_i)=1-(1+(1-f)^{\sigmai})=-(1-f)^{\sum{i}\sigma_i}$, the joint "one minus probability" of all the stakes (each with probability $\phi(\sigmai))$ winning aggregated winning the leadership $\prod{i}^{n}(1-\phi(\sigma_i))=-(1-f)^{\sum_i(\sigmai)}$ thus: $$ 1-\phi(\sum{i}\sigmai) =\prod{i}^{n}(1-\phi(\sigma_i)) $$

A non-exponential linear leader selection can be:

$$y < T $$ $$y = 2^lk \mid 0 \le k \le 1$$ $$T = 2^l\phi(v)$$ $$ \phi(v)=\frac{1}{v_{max+}+c}v \mid c \in \mathbb{Z}$$

Dependent aggregation

Linear leader selection has the dependent aggregation property, meaning it's favorable to compete in pools with sum of the stakes over aggregated stakes of distributed stakes:

$$\phi(\sum_{i}{\sigmai})>\prod{i}^{n}{\sigmai}$$ $$\sum{i}{\sigmai}>(\frac{1}{v{max}+c})^{n-1}v_1v_2 \dots v_n$$ let's assume the stakes are divided to stakes of value $\sigmai=1$ for $\Sigma>1 \in \mathbb{Z}$, $\sum{i}{\sigmai}=V$ $$V>(\frac{1}{v{max}+c})^{n-1}$$ note that $(\frac{1}{v_{max}+c})^{n-1} < 1, V>1$, thus competing with single coin of the sum of stakes held by the stakeholder is favorable.

Scalar linear aggregation dependent leader selection

A target function T with scalar coefficients can be formalized as $$T=2^lk\phi(\Sigma)=2^l(\frac{1}{v{max}+c})\Sigma$$ let's assume $v{max}=2^v$, and $c=0$ then: $$T=2^lk\phi(\Sigma)=2^{l-v}\Sigma$$ then the lead statement is $$y<2^{l-v}\Sigma$$ for example for a group order or l= 24 bits, and maximum value of $v_{max}=2^{10}$, then lead statement: $$y<2^{14}\Sigma$$

Competing max value coins

For a stakeholder with $nv_{max}$ absolute stake, $\mid n \in \mathbb{Z}$ it's advantageous for the stakeholder to distribute stakes on $n$ competing coins.

Inverse functions

Inverse lead selection functions doesn't require maximum stake, most suitable for absolute stake, it has the disadvantage that it's inflating with increasing rate as time goes on, but it can be function of the inverse of the slot to control the increasing frequency of winning leadership.

Leader selection without maximum stake upper limit

The inverse leader selection without maximum stake value can be $\phi(v)=\frac{v}{v+c} \mid c > 1$ and inversely proportional with probability of winning leadership, let it be called leadership coefficient.

Decaying linear leader selection

As the time goes one, and stakes increase, this means the combined stakes of all stakeholders increases the probability of winning leadership in next slots leading to more leaders at a single slot, to maintain, or to be more general to control this frequency of leaders per slot, c (the leadership coefficient) need to be function of the slot $sl$, i.e $c(sl) = \frac{sl}{R}$ where $R$ is epoch size (number of slots in epoch).

Pairing leader selection independent aggregation function

The only family of functions $\phi(\alpha)$ that are isomorphic to summation on multiplication $\phi(\alpha_1+\alpha_2) = \phi(\alpha_1)\phi(\alpha_2)$(having the independent aggregation property) is the exponential function, and since it's impossible to implement in plonk, a re-formalization of the lead statement using pairing that is isomorphic to summation on multiplication is an option.

Let's assume $\phi$ is isomorphic function between multiplication and addition, $\phi(\alpha) = \phi(\frac{\alpha}{2})\phi(\frac{\alpha}{2})=\phi(\frac{\alpha}{2})^2$, thus: $$\phi(\alpha)=\underbrace{\phi(1)\dots\phi(1)}_\text{$\alpha$}=\phi(1)^\alpha$$ then the only family of functions $\phi : \mathbb{R} \rightarrow \mathbb{R}$ satisfying this is the exponential function $$\phi(\alpha)=c^{\alpha} \mid c \in \mathbb{R}$$

no solution for the lead statement parameters, and constants $S,f, \alpha$ defined over group of integers.

assume there is a solution for the lead statement parameters and constants $S, f, \alpha$ defined over group of integers. for the statement $y1$, the smallest value satisfying f is $f=2$, then $$\phi{max} = 2^{2^{64}}$$ note that since $ord(G)<<\phi{max}$ thus $S<<1$, contradiction.

target T n term approximation

• s is stake, and $\Sigma$ is total stake.
• $$ \sigma = \frac{s}{\Sigma} $$
• $$ T = -[\frac{k}{\Sigma}s + \frac{k^{''}}{\Sigma^2 2!} s^2 + \dots +\frac{k^{'n}}{\Sigma^n n!} s^n] $$

Leaky non-resettable beacon

Built on top of globally synchronized clock, that leaks the nonce $\eta$ of the next epoch a head of time (thus called leaky), non-resettable in the sense that the random nonce is deterministic at slot s, while assuring security against adversary controlling some stakeholders.

For an epoch j, the nonce $\eta_j$ is calculated by hash function H, as:

$$\etaj = H(\eta{j-1}||j||v)$$

v is the concatenation of the value $\rho$ in all blocks from the beginning of epoch $e_{i-1}$ to the slot with timestamp up to $(j-2)R + \frac{16k}{1+\epsilon}$, note that k is a persistence security parameter, R is the epoch length in terms of slots.

Appendix

This section gives further details about the structures that will be used by the protocol.

Blockchain

Field	Type	Description
blocks	Vec<Block>	Series of blocks consisting the Blockchain

Header

Field	Type	Description
version	u8	Version
state	blake3Hash	Previous block hash
epoch	u64	Epoch
slot	u64	Slot UID
timestamp	Timestamp	Block creation timestamp
root	MerkleRoot	Root of the transaction hashes merkle tree

Block

Field	Type	Description
magic	u8	Magic bytes
header	blake3Hash	Header hash
txs	Vec<blake3Hash>	Transaction hashes
metadata	Metadata	Additional block information

Metadata

Field	Type	Description
signature	Signature	Block owner signature
public_inputs	Vec<pallas::Base>	Nizk proof public inputs
serial_number	pallas::Base	competing coin's nullifier
eta	[u8; 32]	randomness from the previous epoch
proof	Vec<u8>	Nizk $\pi$ Proof the stakeholder is the block owner