darkfi/script/research/crypsinous

this is an effort to break down the building blocks of crypsinous blockchain

Crypsinous blockchain

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

\begin{math} 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)) \end{math}

$\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.

(TODO add UC proof)

Performance

since Crypsinous is based of sapling scheme, the performance relative to zerocash sapling scheme is that number of constraints in the PRF is improved by replacing sha256 (83,712 constraints) by pederson commitment (2,542 constraints), but on the other hand the proving take twice that of the sapling.

Appendix

PRF

pseudo random function $f(x)$ is defined as elliptic curve encryption over the group $$ of random output as \emph{elligator} curves of poseidon hash H

$PRF^{sn}$:

$$ PRF^{sn}{root{sk}^{COIN}}(x)= H(x||0b00)^{root_{sk}^{COIN}}$$

$PRF^{pk}$:

$$ PRF^{pk}{root{sk}^{COIN}}(x)= H(x||0b01)^{root_{sk}^{COIN}}$$

$PRF^{evl}$:

$$ PRF^{evl}{root{sk}^{COIN}}(x)= H(x||0b10)^{root_{sk}^{COIN}}$$

$root^{COIN}_{sk}(\tau)$

the root in the merkle tree of the current epoch's coins secret keys, at the onset of the epoch, the initial slot's coin's secret key at time $\tau$ is sampled at random $sk{\tau}^{COIN}\xleftarrow{s} {0,1}^{l{PRF}}$, and $sk{i+1}^{COIN} \leftarrow PRF{sk_i}^{evl}(1)$

Comm,DeComm

the equivocal commitment $(cm,r) \leftarrow Comm(m)$, while the de-commitment is $DeComm(cm,m,r)\rightarrow True$ if it verifies. the commitment can be implemented as blinded encryption of m, as follows $$mG_1 + rG_2$$

for random groups $G_1$, $G_2$, or as $PRF_{r}^{comm}(m)$
$$ PRF^{comm}_{r}(m)= H(m||0b11)^{r}$$

references

https://eprint.iacr.org/2018/1132.pdf