DarkFi

About DarkFi

DarkFi is a new Layer 1 blockchain, designed with anonymity at the forefront. It offers flexible private primitives that can be wielded to create any kind of application. DarkFi aims to make anonymous engineering highly accessible to developers.

DarkFi uses advances in zero-knowledge cryptography and includes a contracting language and developer toolkits to create uncensorable code.

In the open air of a fully dark, anonymous system, cryptocurrency has the potential to birth new technological concepts centered around sovereignty. This can be a creative, regenerative space - the dawn of a Dark Renaissance.

Connect to DarkFi IRC

Follow the installation instructions for the P2P IRC daemon.

Build

This project requires the Rust compiler to be installed. Please visit Rustup for instructions.

You have to install a native toolchain, which is set up during Rust installation, and wasm32 toolchain. To install wasm32 toolchain, execute:

% rustup target add wasm32-unknown-unknown

Minimum Rust version supported is 1.67.0 (stable).

The following dependencies are also required:

Users of Debian-based systems (e.g. Ubuntu) can simply run the following to install the required dependencies:

# apt-get update
# apt-get install -y git make jq gcc pkg-config libmpg123-dev

Alternatively, users can try using the automated script under contrib folder by executing:

% sh contrib/dependency_setup.sh

The script will try to recognize which system you are running, and install dependencies accordingly. In case it does not find your package manager, please consider adding support for it into the script and sending a patch.

To build the necessary binaries, we can just clone the repo, checkout to the latest tag, and use the provided Makefile to build the project:

% git clone https://github.com/darkrenaissance/darkfi
% cd darkfi && git checkout v0.4.1
% make

Development

If you want to hack on the source code, make sure to read some introductory advice in the DarkFi book.

Install

This will install the binaries on your system (/usr/local by default). The configuration files for the binaries are bundled with the binaries and contain sane defaults. You'll have to run each daemon once in order for them to spawn a config file, which you can then review.

# make install

Examples and usage

See the DarkFi book

Go Dark

Let's liberate people from the claws of big tech and create the democratic paradigm of technology.

Self-defense is integral to any organism's survival and growth.

Power to the minuteman.

DarkFi Philosophy

State Civilization and the Democratic Nation

State civilization has a 5000 year history. The origin of civilizations in mesopotamia experienced a cambrian explosion of various forms. The legacy of state civilization can be traced back to ancient assyria which was essentially a military dictatorship that mobilized all of society's resources to wage war and defeat other civilizations, enslaving them and seizing their wealth.

Wikipedia defines civilization:

Civilizations are organized densely-populated settlements divided into hierarchical social classes with a ruling elite and subordinate urban and rural populations.

Civilization concentrates power, extending human control over the rest of nature, including over other human beings.

However this destiny of civilization was not inherent as history teaches us. This definition is one particular mode of civilization that become prevalent. During human history there has been plethora forms of civilizations. Our role as revolutionaries is to reconstruct the civilizational paradigm.

The democratic nation is synonymous with society, and produces all value include that which the state extracts. Creative enterprise and wealth production originates in society from small scale business, artisans and inventors, and anybody driven by intent or ambition to create works.

Within society, there are multiple coexisting nations which are communities of people sharing language, history, ethnicity or culture. For example there could be a nation based on spiritual belief, the nation of women, or a distinct cultural nation.

The nation state is an extreme variant of the state civilization tendency. Like early state civilizations, the development of the French nation-state was more effective at seizing the wealth of society to mobilize in war against the existing empires of the time.

Soon after, the remaining systems were forced to adopt the nation state system, including its ideology of nationalism. It is no mistake that the nation state tends towards nationalism and fascism including the worst genocides in human history. Nationalism is a blind religion supplanting religious ideologies weakened by secularism. However nationalism is separate from patriotism.

Loving one's country for which you have struggled and fought over for centuries or even millenia as an ethnic community or nation, which you have made your homeland in this long struggle, represents a sacred value.

~ Ocalan's "PKK and Kurdish Question in the 21st century"

Modernity and the Subject of Ideology

Modernity was born in the "age of reason" and represents the overturning of prevailing religious ideas and rejection of tradition in favour of secularization. Modernity has a mixed legacy which includes alienation, commodity festishism, scientific positivism and rationalism.

During this period of modernity, 4 major ideologies developed, each with their own specific subject as its focus.

• Liberalism and its subject of the individual. Individuals are atomic units existing under the state system which guarantees them certain bargains in the form of laws and rights.
• Communism which focused on the concept of class warfare, and economic justice through state power.
• Fascism which put the volk or state at the center of society, whereby all resources would be mobilized to serve the state.
• Anarchism with its critiques of power, and favouring social freedom.

The particular form of modernity that is predominant can be characterized as capitalist modernity. Capitalism, otherwise referred to by others as corporatism can be likened to a religion, whereby a particular elite class having no ideology except self profit uses the means of the state to protect its own interests and extract the wealth of society through nefarious means. In some ways, it is a parasite on the state.

Agorist free markets is the democratic tendency of economy. The word 'economy' derives from the Ancient Greek 'oikonomos' which means household management. Economy was during ancient periods connected with nature, the role of motherhood, life and freedom. It was believed that wealth derived from the quality of our lived our environments. The Kurds use the feminine word 'mal' to refer to the house, while the masculine variant refers to actual property. Later during the Roman period, economy came to be understood as the accumulation of property in the form of number of slaves owned, amount of land seized or the quantity of money.

The subject of our ideology is the moral and political society. Society exists within a morality and a politics. Here we use politics to refer not to red team vs blue team, but instead all social activity concerned with our security, necessity and life. A society can only be free when it has its own morality and politics. The state seeks to keep society weak by depriving it of morality and replacing society's politics with statecraft.

The Extinction of Humanity

During the 20th century, liberals, communists and fascists vyed for state power each promising a new form of society. State power existed with these external ideological justifications.

With the end of the soviet union, and the end of history (according to liberalism), state power morphed into pure domination and profit. The system simply become a managerial form of raw power over society without purpose or aim. Wars such as Iraq were invented by neoliberals to breathe a new purpose into society. Indeed there is no more effective means to support despotism than war.

Today the military industrial complex has grown into a gigantic leviathan that threatens the world driving economies into an ever greater spiral of desperation. The push the development of automated weapons, aerial drones and ninja missiles that eliminate all space for human resistance against tyranny.

Meanwhile social credit scoring is being introduced as CBDCs with incentivization schemes such as UBI. Such systems will give more effective means for the seizure of wealth by the state from society, centralizing economic power within an already deeply corrupt elite class.

Liberal ideologies have made people indifferent to their own situation, turning society inwards focused on social media, unable to organize together to oppose rising authoritarianism. Liberalism is essentially a tendency towards extinction or death.

Nature, Life, Freedom

Nature is the center of spiritual belief. Humanity is an aspect of nature. Nature is more than the number of trees. It is the going up, the ascending of life. Through struggle, we overcome obstacles, becoming harder and stronger along the way. This growth makes us more human, and closer with nature.

People naturally feel an empathy with nature such as when an animal is injured, or generous feelings towards the young of any species. This feeling was put in us by evolution. We feel an attachment and empathy towards our lived environment, and want to see it improve. This feeling is mother nature speaking through us. The more in touch we are with this deeper feeling, the more free we are since we are able to develop as higher human beings.

Freedom does not mean the ability to be without constraint or enact any wild fantasy at a moment's notice. Freedom means direct conscious action with power that makes us ascend upwards. Nature is full of interwoven threads of organisms vying for influence or power, with time doing an ordered dance punctuated by inflection points of change. It is during those moments that our ability of foresight and prescience allow us to deeply affect events along alternative trajectories.

Re-Evaluating Anarchism

Anarchists had the correct critique & analysis of power. In particular seeing that the nation state would grow into a monster that would consume society. However they were the least equipped of all the other ideologies during modernity to enact their vision and put their ideas into practice.

• They fell victim to the same positivist forces that they claimed to be fighting against.
• They lacked a coherent vision, and had little strategy or roadmap for how the revolution would happen.
• Their utopian demand that the state must be eliminated immediately and at all costs meant they were not able to plan how that would happen.
• Their opposition to all forms of authority, even legitimate leadership meant they were ineffective at organizing revolutionary forces.

Revolutionary Objectives

• Our movement is primarily a spiritual one. One cannot understand christianity by studying its system of churches, since primarily it is a body of teachings. Likewise the core of our movement is in our philosophy, ideas and concepts, which then inform our ideas on governance and economics.
• We must build a strong intellectual fabric that innocuates us and fosters resilience, as well as equipping us with the means to be effective in our work.
• There are two legacies in technology. One informed by state civilization, and the other by society. The technology we create is to solve problems that society and aligned communities have.

Definition of Democratic Civilization

From 'The Sociology of Freedom: Manifesto of the Democratic Civilization, Volume 3' by Abdullah Ocalan.

Annotations are our own. The text is otherwise unchanged.

What is the subject of moral and political society?

The school of social science that postulates the examination of the existence and development of social nature on the basis of moral and political society could be defined as the democratic civilization system. The various schools of social science base their analyses on different units. Theology and religion prioritize society. For scientific socialism, it is class. The fundamental unit for liberalism is the individual. There are, of course, schools that prioritize power and the state and others that focus on civilization. All these unit-based approaches must be criticized, because, as I have frequently pointed out, they are not historical, and they fail to address the totality. A meaningful examination would have to focus on what is crucial from the point of view of society, both in terms of history and actuality. Otherwise, the result will only be one more discourse.

Identifying our fundamental unit as moral and political society is significant, because it also covers the dimensions of historicity and totality. Moral and political society is the most historical and holistic expression of society. Morals and politics themselves can be understood as history. A society that has a moral and political dimension is a society that is the closest to the totality of all its existence and development. A society can exist without the state, class, exploitation, the city, power, or the nation, but a society devoid of morals and politics is unthinkable. Societies may exist as colonies of other powers, particularly capital and state monopolies, and as sources of raw materials. In those cases, however, we are talking about the legacy of a society that has ceased to be.

Individualism is a state of war

There is nothing gained by labeling moral and political society—the natural state of society—as slave-owning, feudal, capitalist, or socialist. Using such labels to describe society masks reality and reduces society to its components (class, economy, and monopoly). The bottleneck encountered in discourses based on such concepts as regards the theory and practice of social development stems from errors and inadequacies inherent in them. If all of the analyses of society referred to with these labels that are closer to historical materialism have fallen into this situation, it is clear that discourses with much weaker scientific bases will be in a much worse situation. Religious discourses, meanwhile, focus heavily on the importance of morals but have long since turned politics over to the state. Bourgeois liberal approaches not only obscure the society with moral and political dimensions, but when the opportunity presents itself they do not hesitate to wage war on this society. Individualism is a state of war against society to the same degree as power and the state is. Liberalism essentially prepares society, which is weakened by being deprived of its morals and politics, for all kinds of attacks by individualism. Liberalism is the ideology and practice that is most anti-society.

The rise of scientific positivism

In Western sociology (there is still no science called Eastern sociology) concepts such as society and civilization system are quite problematic. We should not forget that the need for sociology stemmed from the need to find solutions to the huge problems of crises, contradictions, and conflicts and war caused by capital and power monopolies. Every branch of sociology developed its own thesis about how to maintain order and make life more livable. Despite all the sectarian, theological, and reformist interpretations of the teachings of Christianity, as social problems deepened, interpretations based on a scientific (positivist) point of view came to the fore. The philosophical revolution and the Enlightenment (seventeenth and eighteenth centuries) were essentially the result of this need. When the French Revolution complicated society’s problems rather than solving them, there was a marked increase in the tendency to develop sociology as an independent science. Utopian socialists (Henri de Saint-Simon, Charles Fourier, and Pierre-Joseph Proudhon), together with Auguste Comte and Émile Durkheim, represent the preliminary steps in this direction. All of them are children of the Enlightenment, with unlimited faith in science. They believed they could use science to re-create society as they wished. They were playing God. In Hegel’s words, God had descended to earth and, what’s more, in the form of the nation-state. What needed to be done was to plan and develop specific and sophisticated “social engineering” projects. There was no project or plan that could not be achieved by the nation-state if it so desired, as long as it embraced the “scientific positivism” and was accepted by the nation-state!

Capitalism as an iron cage

British social scientists (political economists) added economic solutions to French sociology, while German ideologists contributed philosophically. Adam Smith and Hegel in particular made major contributions. There was a wide variety of prescriptions from both the left and right to address the problems arising from the horrendous abuse of the society by the nineteenth-century industrial capitalism. Liberalism, the central ideology of the capitalist monopoly has a totally eclectic approach, taking advantage of any and all ideas, and is the most practical when it comes to creating almost patchwork-like systems. It was as if the right- and left- wing schematic sociologies were unaware of social nature, history, and the present while developing their projects in relation to the past (the quest for the “golden age” by the right) or the future (utopian society). Their systems would continually fragment when they encountered history or current life. The reality that had imprisoned them all was the “iron cage” that capitalist modernity had slowly cast and sealed them in, intellectually and in their practical way of life. However, Friedrich Nietzsche’s ideas of metaphysicians of positivism or castrated dwarfs of capitalist modernity bring us a lot closer to the social truth. Nietzsche leads the pack of rare philosophers who first drew attention to the risk of society being swallowed up by capitalist modernity. Although he is accused of serving fascism with his thoughts, his foretelling of the onset of fascism and world wars was quite enticing.

The increase in major crises and world wars, along with the division of the liberal center into right- and left-wing branches, was enough to bankrupt positivist sociology. In spite of its widespread criticism of metaphysics, social engineering has revealed its true identity with authoritarian and totalitarian fascism as metaphysics at its shallowest. The Frankfurt School is the official testimonial of this bankruptcy. The École Annales and the 1968 youth uprising led to various postmodernist sociological approaches, in particular Immanuel Wallerstein’s capitalist world-system analysis. Tendencies like ecology, feminism, relativism, the New Left, and world-system analysis launched a period during which the social sciences splintered. Obviously, financial capital gaining hegemony as the 1970s faded also played an important role. The upside of these developments was the collapse of the hegemony of Eurocentric thought. The downside, however, was the drawbacks of a highly fragmented social sciences.

The problems of Eurocentric sociology

Let’s summarize the criticism of Eurocentric sociology:

1. Positivism, which criticized and denounced both religion and metaphysics, has not escaped being a kind of religion and metaphysics in its own right. This should not come as a surprise. Human culture requires metaphysics. The issue is to distinguish good from bad metaphysics.

2. An understanding of society based on dichotomies like primitive vs. modern, capitalist vs. socialist, industrial vs. agrarian, progressive vs. reactionary, divided by class vs. classless, or with a state vs. stateless prevents the development of a definition that comes closer to the truth of social nature. Dichotomies of this sort distance us from social truth.

3. To re-create society is to play the modern god. More precisely, each time society is recreated there is a tendency to form a new capital and power-state monopoly. Much like medieval theism was ideologically connected to absolute monarchies (sultanates and shāhanshāhs), modern social engineering as recreation is essentially the divine disposition and ideology of the nation-state. Positivism in this regard is modern theism.

4. Revolutions cannot be interpreted as the re-creation acts of society. When thusly understood they cannot escape positivist theism. Revolutions can only be defined as social revolutions to the extent that they free society from excessive burden of capital and power.

5. The task of revolutionaries cannot be defined as creating any social model of their making but more correctly as playing a role in contributing to the development of moral and political society.

6. Methods and paradigms to be applied to social nature should not be identical to those that relate to first nature. While the universalist approach to first nature provides results that come closer to the truth (I don’t believe there is an absolute truth), relativism in relation to social nature may get us closer to the truth. The universe can neither be explained by an infinite universalist linear discourse or by a concept of infinite similar circular cycles.

7. A social regime of truth needs to be reorganized on the basis of these and many other criticisms. Obviously, I am not talking about a new divine creation, but I do believe that the greatest feature of the human mind is the power to search for and build truth.

A new social science

In light of these criticisms, I offer the following suggestions in relation to the social science system that I want to define:

A more humane social nature

1. I would not present social nature as a rigid universalist truth with mythological, religious, metaphysical, and scientific (positivist) patterns. Understanding it to be the most flexible form of basic universal entities that encompass a wealth of diversities but are tied down to conditions of historical time and location more closely approaches the truth. Any analysis, social science, or attempt to make practical change without adequate knowledge of the qualities of social nature may well backfire. The monotheistic religions and positivism, which have appeared throughout the history of civilization claiming to have found the solution, were unable to prevent capital and power monopolies from gaining control. It is therefore their irrevocable task, if they are to contribute to moral and political society, to develop a more humane analysis based on a profound self-criticism.

2. Moral and political society is the main element that gives social nature its historical and complete meaning and represents the unity in diversity that is basic to its existence. It is the definition of moral and political society that gives social nature its character, maintains its unity in diversity, and plays a decisive role in expressing its main totality and historicity. The descriptors commonly used to define society, such as primitive, modern, slave-owning, feudal, capitalist, socialist, industrial, agricultural, commercial, monetary, statist, national, hegemonic, and so on, do not reflect the decisive features of social nature. On the contrary, they conceal and fragment its meaning. This, in turn, provides a base for faulty theoretical and practical approaches and actions related to society.

Protecting the social fabric

3. Statements about renewing and re-creating society are part of operations meant to constitute new capital and power monopolies in terms of their ideological content. The history of civilization, the history of such renewals, is the history of the cumulative accumulation of capital and power. Instead of divine creativity, the basic action the society needs most is to struggle against factors that prevent the development and functioning of moral and political social fabric. A society that operates its moral and political dimensions freely, is a society that will continue its development in the best way.

4. Revolutions are forms of social action resorted to when society is sternly prevented from freely exercising and maintaining its moral and political function. Revolutions can and should be accepted as legitimate by society only when they do not seek to create new societies, nations, or states but to restore moral and political society its ability to function freely.

5. Revolutionary heroism must find meaning through its contributions to moral and political society. Any action that does not have this meaning, regardless of its intent and duration, cannot be defined as revolutionary social heroism. What determines the role of individuals in society in a positive sense is their contribution to the development of moral and political society.

6. No social science that hopes to develop these key features through profound research and examination should be based on a universalist linear progressive approach or on a singular infinite cyclical relativity. In the final instance, instead of these dogmatic approaches that serve to legitimize the cumulative accumulation of capital and power throughout the history of civilization, social sciences based on a non-destructive dialectic methodology that harmonizes analytical and emotional intelligence and overcomes the strict subject-object mold should be developed.

The framework of moral and political society

The paradigmatic and empirical framework of moral and political society, the main unit of the democratic civilization system, can be presented through such hypotheses. Let me present its main aspects:

1. Moral and political society is the fundamental aspect of human society that must be continuously sought. Society is essentially moral and political.

2. Moral and political society is located at the opposite end of the spectrum from the civilization systems that emerged from the triad of city, class, and state (which had previously been hierarchical structures).

3. Moral and political society, as the history of social nature, develops in harmony with the democratic civilization system.

4. Moral and political society is the freest society. A functioning moral and political fabric and organs is the most decisive dynamic not only for freeing society but to keep it free. No revolution or its heroines and heroes can free the society to the degree that the development of a healthy moral and political dimension will. Moreover, revolution and its heroines and heroes can only play a decisive role to the degree that they contribute to moral and political society.

5. A moral and political society is a democratic society. Democracy is only meaningful on the basis of the existence of a moral and political society that is open and free. A democratic society where individuals and groups become subjects is the form of governance that best develops moral and political society. More precisely, we call a functioning political society a democracy. Politics and democracy are truly identical concepts. If freedom is the space within which politics expresses itself, then democracy is the way in which politics is exercised in this space. The triad of freedom, politics, and democracy cannot lack a moral basis. We could refer to morality as the institutionalized and traditional state of freedom, politics, and democracy.

6. Moral and political societies are in a dialectical contradiction with the state, which is the official expression of all forms of capital, property, and power. The state constantly tries to substitute law for morality and bureaucracy for politics. The official state civilization develops on one side of this historically ongoing contradiction, with the unofficial democratic civilization system developing on the other side. Two distinct typologies of meaning emerge. Contradictions may either grow more violent and lead to war or there may be reconciliation, leading to peace.

7. Peace is only possible if moral and political society forces and the state monopoly forces have the will to live side by side unarmed and with no killing. There have been instances when rather than society destroying the state or the state destroying society, a conditional peace called democratic reconciliation has been reached. History doesn’t take place either in the form of democratic civilization—as the expression of moral and political society—or totally in the form of civilization systems—as the expression of class and state society. History has unfolded as intense relationship rife with contradiction between the two, with successive periods of war and peace. It is quite utopian to think that this situation, with at least a five-thousand-year history, can be immediately resolved by emergency revolutions. At the same time, to embrace it as if it is fate and cannot be interfered with would also not be the correct moral and political approach. Knowing that struggles between systems will be protracted, it makes more sense and will prove more effective to adopt strategic and tactical approaches that expand the freedom and democracy sphere of moral and political society.

8. Defining moral and political society in terms of communal, slave-owning, feudal, capitalist, and socialist attributes serves to obscure rather than elucidate matters. Clearly, in a moral and political society there is no room for slave-owning, feudal, or capitalist forces, but, in the context of a principled reconciliation, it is possible to take an aloof approach to these forces, within limits and in a controlled manner. What’s important is that moral and political society should neither destroy them nor be swallowed up by them; the superiority of moral and political society should make it possible to continuously limit the reach and power of the central civilization system. Communal and socialist systems can identify with moral and political society insofar as they themselves are democratic. This identification is, however, not possible, if they have a state.

9. Moral and political society cannot seek to become a nation-state, establish an official religion, or construct a non-democratic regime. The right to determine the objectives and nature of society lies with the free will of all members of a moral and political society. Just as with current debates and decisions, strategic decisions are the purview of society’s moral and political will and expression. The essential thing is to have discussions and to become a decision-making power. A society who holds this power can determine its preferences in the soundest possible way. No individual or force has the authority to decide on behalf of moral and political society, and social engineering has no place in these societies.

Liberating democratic civilization from the State

When viewed in the light of the various broad definitions I have presented, it is obvious that the democratic civilization system—essentially the moral and political totality of social nature—has always existed and sustained itself as the flip side of the official history of civilization. Despite all the oppression and exploitation at the hands of the official world-system, the other face of society could not be destroyed. In fact, it is impossible to destroy it. Just as capitalism cannot sustain itself without noncapitalist society, civilization— the official world system— also cannot sustain itself without the democratic civilization system. More concretely the civilization with monopolies cannot sustain itself without the existence of a civilization without monopolies. The opposite is not true. Democratic civilization, representing the historical flow of the system of moral and political society, can sustain itself more comfortably and with fewer obstacles in the absence of the official civilization.

I define democratic civilization as a system of thought, the accumulation of thought, and the totality of moral rules and political organs. I am not only talking about a history of thought or the social reality within a given moral and political development. The discussion does, however, encompass both issues in an intertwined manner. I consider it important and necessary to explain the method in terms of democratic civilization’s history and elements, because this totality of alternate discourse and structures are prevented by the official civilization. I will address these issues in subsequent sections.

Recommended Books

• Core Texts
• Philosophy
• Python
• C
• Rust
• Mathematics
  • Abstract Algebra
  • Elliptic Curves
  • Algebraic Geometry
    • Commutative Algebra
  • Algebraic Number Theory
• Cryptography
  • ZK
• Miscellaneous

Core Texts

• Manifesto for a Democratic Civilization parts 1, 2 & 3 by Ocalan. This are a good high level overview of history, philosophy and spiritualism talking about the 5000 year legacy of state civilization, the development of philosophy and humanity's relationship with nature.
• New Paradigm in Macroeconomics by Werner explains how economics and finance work on a fundamental level. Emphasizes the importance of economic networks in issuing credit, and goes through all the major economic schools of thought.
• Authoritarian vs Democratic Technics by Mumford is a short 10 page summary of his books The Myth of the Machine parts 1 & 2. Mumford was a historian and philosopher of science and technology. His books describe the two dominant legacies within technology; one enslaving humanity, and the other one liberating humanity from the state.
• GNU and Free Software texts

Philosophy

• The Story of Philosophy by Will Durant
• The Sovereign Individual is very popular among crypto people. Makes several prescient predictions including about cryptocurrency, algorithmic money and the response by nation states against this emeregent technology. Good reading to understand the coming conflict between cryptocurrency and states.

Python

• Python Crash Course by Eric Matthes. Good beginner text.
• O'Reilly books: Python Data Science, Python for Data Analysis

C

• The C Programming Language by K&R (2nd Edition ANSI C)

Rust

• The Rust Programming Language from No Starch Press. Good intro to learn Rust.
• Rust for Rustaceans from No Starch Press is an advanced Rust book.

Mathematics

Abstract Algebra

• Pinter is your fundamental algebra text. Everybody should study this book. My full solutions here.
• Basic Abstract Algebra by Dover is also a good reference.
• Algebra by Dummit & Foote. The best reference book you will use many times. Just buy it.
• Algebra by Serge Lang. More advanced algebra book but often contains material not found in the D&F book.

Elliptic Curves

• Washington is a standard text and takes a computational approach. The math is often quite obtuse because he avoids introducing advanced notation, instead keeping things often in algebra equations.
• Silverman is the best text but harder than Washington. The material however is rewarding.

Algebraic Geometry

• Ideals, Varieties and Algorithms by Cox, Little, O'Shea. They have a follow up advanced graduate text called Using Algebraic Geometry. It's the sequel book explaining things that were missing from the first text.
• Hartshorne is a famous text.

Commutative Algebra

• Atiyah-MacDonald. Many independent solution sheets online if you search for them. Or ask me ;)

Algebraic Number Theory

• Algebraic Number Theory by Frazer Jarvis, chapters 1-5 (~100 pages) is your primary text. Book is ideal for self study since it has solutions for exercises.
• Introductory Algebraic Number Theory by Alaca and Williams is a bit dry but a good supplementary reference text.
• Elementary Number Theory by Jones and Jones, is a short text recommended in the preface to the Jarvis book.
• Algebraic Number Theory by Milne, are course notes written which are clear and concise.
• Short Algebraic Number Theory course, see also the lecture notes.
• Cohen book on computational number theory is a gold mine of standard algos.
• LaVeque Fundamentals of Number Theory

Cryptography

ZK

• Proofs, Arguments, and Zero-Knowledge by Justin Thaler.

Miscellaneous

• Cryptoeconomics by Eric Voskuil.

DarkFi Testnet User Guide

This document presents a short user guide for the initial DarkFi testnet. In it, we cover basic setup of the darkfid node daemon, initializing a wallet, and interacting with the money contract, which provides infrastructure for payments and atomic swaps.

1. Compile and run a node
2. Airdrop yourself funds
3. Make some payments
4. Do some atomic swaps
5. Create an on-chain DAO

Compiling and Running a Node

Since this is still an early phase, we will not be installing any of the software system-wide. Instead, we'll be running all the commands from the git repository, so we're able to easily pull any necessary updates.

Compiling

Refer to the main README file for instructions on how to install Rust and necessary deps.

Once you have the repository in place, and everything is installed, we can compile the darkfid node and the drk wallet CLI:

$ make darkfid drk

This process will now compile the node and the wallet CLI tool. When finished, we can begin using the network. Run darkfid once so that it spawns its config file on your system. This config file will be used by darkfid in order to configure itself. The defaults are already preset for using the testnet network.

$ ./darkfid
Config file created in "~/.config/darkfi/darkfid_config.toml". Please review it and try again.

Running

Once that's in place, you can run it again and darkfid will start, create necessary keys for validation of blocks and transactions, and begin syncing the blockchain. Keep it running, and you should see a Blockchain is synced! message after some time.

$ ./darkfid

Now it's time to initialize your wallet. For this we use a separate wallet CLI which is created to interface with the smart contract used for payments and swaps.

We simply have to initialize a wallet, and create a keypair:

$ ./drk wallet --initialize
$ ./drk wallet --keygen

The second command will print out your new DarkFi address where you can receive payments. Take note of it. Alternatively, you can always retrieve it using:

$ ./drk wallet --address

In order to receive incoming coins, you'll need to use the drk tool to subscribe on darkfid so you can receive notifications for incoming blocks. The blocks have to be scanned for transactions, and to find coins that are intended for you. In another terminal, you can run the following commands to first scan the blockchain, and then to subscribe to new blocks:

$ ./drk scan
$ ./drk subscribe blocks

Now you can leave the subscriber running. In case you stop it, just run drk scan again until the chain is fully scanned, and then you should be able to subscribe again.

Advanced Usage

To run a node in full debug mode:

LOG_TARGETS="\!sled,\!net" ./darkfid -v | tee /tmp/darkfid.log

The sled and net targets are very noisy and slow down the node so we disable those.

We can now view the log, and grep through it.

tail -n +0 -f /tmp/darkfid.log | grep -a --line-buffered -v DEBUG

Airdrops

Now you have your wallet set up. Let's proceed with getting some tokens from the faucet. The testnet has a running faucet which is able to airdrop native network tokens.

So let's airdrop some of these into our wallet:

$ ./drk airdrop 42.69

There is a limit of 100 for testnet airdrops currently.

Note: you have wait some minutes between airdrops since they're rate-limited.

On success, you should see a transaction ID. If successful, the airdrop transactions will how be in the consensus' mempool, waiting for inclusion in the next block. Depending on the network, finalization of the blocks could take some time. You'll have to wait for this to happen. If your drk subscribe blocks is running, then after some time your balance should be in your wallet.

You can check your wallet balance using drk:

$ ./drk wallet --balance

Aliases

To make our life easier, we can create token ID aliases, so when we are performing transactions with them, we can use that instead of the full token ID. Multiple aliases per token ID is supported.

Example addition:

$ ./drk alias add {ALIAS} {TOKEN}

So lets add the native token as DARK by executing:

$ ./drk alias add DARK 12ea8e3KVuBhmSnr29iV34Zd2RsD1MEeGk9xJhcipUqx

From now on, we can use DARK to refer to the native token when executing transactions using it.

We can also list all our aliases using:

$ ./drk alias show

Note: this aliases are only local to your machine. When exchanging with other users, always verify that your aliases token IDs match.

Minting tokens

On the DarkFi network, we're also able to mint custom tokens with some supply. To do this, we need to generate a mint authority keypair, and derive a token ID from it. We can simply do this by executing the following command:

$ ./drk token generate-mint

This will generate a new token mint authority and will tell you what your new token ID is. For this tutorial we will need two tokens so execute the command again to generate another one.

You can list your mint authorities with:

$ ./drk token list

Now lets add those two token IDs to our aliases:

$ ./drk alias add WCKD {TOKEN1}
$ ./drk alias add MLDY {TOKEN2}

Now let's mint some tokens to ourself. First grab your wallet address, and then create the token mint transaction, and finally - broadcast it:

$ ./drk wallet --address
$ ./drk token mint WCKD 42.69 {YOUR_ADDRESS} > mint_tx
$ ./drk broadcast < mint_tx

$ ./drk token mint MLDY 20.0 {YOUR_ADDRESS} > mint_tx
$ ./drk broadcast < mint_tx

Now the transaction should be published to the network. If you have an active block subscription (which you can do with drk subscribe blocks), then when the transaction is finalized, your wallet should have your new tokens listed when you request to see the balance.

Payments

Using the tokens we minted, we can make payments to other addresses. Let's try to send some WCKD tokens to 8sRwB7AwBTKEkyTW6oMyRoJWZhJwtqGTf7nyHwuJ74pj:

$ ./drk transfer 2.69 WCKD \
    8sRwB7AwBTKEkyTW6oMyRoJWZhJwtqGTf7nyHwuJ74pj > payment_tx

The above command will create a transfer transaction and place it into the file called payment_tx. Then we can broadcast this transaction to the network:

$ ./drk broadcast < payment_tx

On success we'll see a transaction ID. Now again the same finalization process has to occur and 8sRwB7AwBTKEkyTW6oMyRoJWZhJwtqGTf7nyHwuJ74pj will receive the tokens you've sent.

We can see the spent coin in our wallet.

$ ./drk wallet --coins

We have to wait until the next block to see our change balance reappear in our wallet.

$ ./drk wallet --balance

Atomic Swaps

In order to do an atomic swap with someone, you will first have to come to consensus on what tokens you wish to swap. For example purposes, let's say you want to swap 40 WCKD (which is the balance you should have left over after doing the payment from the previous page) for your counterparty's 20 MLDY. For this tutorial the counterparty is yourself.

To protect your anonymity from the counterparty, the swap can only send entire coins. To create a smaller coin denomination, send yourself the amount you want to swap. Then check you have a spendable coin to swap with:

$ ./drk wallet --coins

You'll have to initiate the swap and build your half of the swap tx:

$ ./drk otc init -v 40.0:20.0 -t WCKD:MLDY > half_swap

Then you can send this half_swap file to your counterparty and they can create the other half by running:

$ ./drk otc join < half_swap > full_swap

They will sign the full_swap file and send it back to you. Finally, to make the swap transaction valid, you need so sign it as well, and broadcast it:

$ ./drk otc sign < full_swap > signed_swap
$ ./drk broadcast < signed_swap

On success, you should see a transaction ID. This transaction will now also be in the mempool, so you should wait again until it's finalized.

After a while you should see the change in balances in your wallet:

$ ./drk wallet --balance

If you see your counterparty's tokens, that means the swap was successful. In case you still see your old tokens, that could mean that the swap transaction has not yet been finalized.

DAO

On the testnet, we are also able to create an anonymous DAO. Using the drk CLI tool, we have a dao subcommand that can perform the necessary operations. Let's create a DAO with the following parameters:

• Proposer limit: 20
• Quorum: 10
• Approval ratio: 0.67
• Governance token: MLDY

You can see what these parameters mean with the help command.

$ ./drk help dao create

Lets create our DAO.

$ ./drk dao create 20 10 0.67 MLDY > dao.dat
$ ./drk dao view < dao.dat

The view command will show us the parameters. If everything looks fine, we can now import it into our wallet:

./drk dao import MiladyMakerDAO < dao.dat
./drk dao list
./drk dao list 1

Minting

If parameters are shown, this means the DAO was successfully imported into our wallet. The DAO's index in our wallet is 1, so we'll use that to reference it. Now we can create a transaction that will mint the DAO on-chain, and broadcast it:

./drk dao mint 1 > dao_mint_tx
./drk broadcast < dao_mint_tx

Now the transaction is broadcasted to the network. Wait for it to finalize, and if your drk is subscribed, after finalization you should see a leaf_position and a transaction ID when running dao list 1.

Sending money to the treasury

Let's send some tokens to the DAO's treasury so we're able to make a proposal to send those somewhere. First find the DAO bulla and the DAO public key with dao list and then create a transfer transaction:

$ ./drk dao list 1
$ ./drk transfer 10 WCKD {DAO_PUBLIC_KEY} \
    --dao {DAO_BULLA} > dao_transfer
$ ./drk broadcast < dao_transfer

Wait for it to finalize, and if subscribed, you should see the DAO receive the funds:

$ ./drk dao balance 1

Creating a proposal

Now that the DAO has something in their treasury, we can create a proposal to send it somewhere. Let's send 5 of the 10 tokens to our address (we can find that with drk wallet --address):

$ ./drk dao propose 1 {YOUR_ADDRESS} 5 WCKD > proposal_tx
$ ./drk broadcast < proposal_tx

Once finalized and scanned, the proposal should be viewable in the wallet. We can see this with the proposal subcommands:

$ ./drk dao proposals 1
$ ./drk dao proposal 1 1

NOTE: vote & exec is todo, check src/contract/dao/ for code.

Notes for developers

Making life easy for others

Write useful commit messages.

If your commit is changing a specific module in the code and not touching other parts of the codebase (as should be the case 99% of the time), consider writing a useful commit message that also mentions which module was changed.

For example, a message like:

added foo

is not as clear as

crypto/keypair: Added foo method for Bar struct.

Also keep in mind that commit messages can be longer than a single line, so use it to your advantage to explain your commit and intentions.

ChangeLog

Whenever a major change or sub-project is completed, a summary must be noted in the ChangeLog. Think of this as a bulletin board where the rest of the team is notified of important progress.

As we move through the stages, the current yyyy-mm-dd marker is updated with the current date, and a new section above is created.

cargo fmt pre-commit hook

To ensure every contributor uses the same code style, make sure you run cargo fmt before committing. You can force yourself to do this by creating a git pre-commit hook like the following:

#!/bin/sh
if ! cargo fmt -- --check >/dev/null; then
    echo "There are some code style issues. Run 'cargo fmt' to fix it."
    exit 1
fi

exit 0

Place this script in .git/hooks/pre-commit and make sure it's executable by running chmod +x .git/hooks/pre-commit.

Testing crate features

Our library heavily depends on cargo features. Currently there are more than 650 possible combinations of features to build the library. To ensure everything can always compile and works, we can use a helper for cargo called cargo hack.

The Makefile provided in the repository is already set up to use it, so it's enough to install cargo hack and run make check.

Etiquette

These are not hard and fast rules, but guidance for team members working together. This allows us to coordinate more effectively.

* once we have proper syncing implemented in ircd, these will become less relevant and not needed.

Another option is to run your ircd inside a persistant tmux session, and never miss messages.

Areas of work

Every monday 16:00 CET, there is our main dev meeting on our chat. Feel free to join and discuss with other darkfi devs.

There are several areas of work that are either undergoing maintenance or need to be maintained:

• Documentation: general documentation and code docs (cargo doc). this is a very important work for example overview page is out of date.
• Tooling: Such as the drk tool. right now we're adding DAO functionality to it.
• Tests: Throughout the project there are either broken or commented out unit tests, they need to be fixed.
• Cleanup: General code cleanup. for example flattening headers and improving things like in this commit.
• ZK Debugger: The ZKVM needs a debugger so we can interactively inspect values at each step to see where problems go wrong.
• ZK Special Tool: We need a special tool to run zk contracts, where you can create a json file with the input values and public values, then run the zk contract without having to write any rust code. so you can write .zk files and try them out without having to write rust code. It will tell you the time to create and verify the proof, as well as the byte size of the proof.
  • We should also have Python bindings for working with Scalars, EC points, merkle trees and hashing.
• Events System: We need to fix IRCD, we will need to implement the events system.

Agorism Hackers Study Guide

During the 90s, the crypto-anarchists sought to apply the emerging technology of cryptography to create online zones which contain the seed of resistance in their code. Cryptocurrency descends from that lineage, and lies at the intersection of economics, politics and technology.

The agorists were a community who believed in leveraging economic power to create free and democratic parallel societies. We define revolution as a transformation in the moral and political fabric of society. By leveraging crypto technology, we can create free online zones.

Money takes money forms, whether cash, credit, loans or debt, and changes properties depending on location. Measures like interest rates and inflation obscure local differences. In fact the source of power lies in economic networks, and money is a unit of account between these networks. By understanding economics, we can use technological techniques to greatly influence the material and political worlds, encoding them with our values and philosophy.

Methodology

We critique the student-teacher relation, where a teacher dictates a course schedule to a student who has to learn the material.

1. Students are not self led, and instead become reliant on an instructor, instead of developing independently.
2. Creativity is supressed since students do not explore and engage with knowledge in a dialectic way.

In our system, we have a system of mentorship. Everybody engages in study and research inside the organization. Subjects are not separated from one another and we encourage people to read multiple subjects, but in a directed way. Our aim is to train leaders, and bring people up. Therefore they must possess:

1. Strategic knowledge to be able to make strong macro analysis and direct activity.
2. Strong skills to directly affect change themselves.

We emphasize a combination of both. As Marx said: ideas should not gather dust in books. We must put our ideas into action through practice. However blind undirected action is wasted effort. Therefore we seek to foster both aspects in participants.

With the mentorship system, whenever members are studying, they are self directed but under the influence of more senior mentors. If they get stuck, they can ask mentors for assistance to get past difficult concepts or discuss ideas to gain a better understanding. Learning through dialogue is encouraged since it creates stronger bonds and relations between people in the community.

Progression

Mandatory Initial Stage

Everybody in the organization must study philosophy and programming as essential skills. To start there are two objects of study:

1. "Manifesto for a Democratic Civilization" by Ocalan, is 3 separate books. You should complete at least 1 book for the initial stage, and then study the other two as you continue further into later stages.
2. "Project Based Python Programming" this will teach you Python programming which will be an essential skill for any branch you decide to continue onto.

Programming takes time and dedicated to become proficient at. Many people give up during the initial phase which can take more than a year. You have to push through it. Once you master programming, it becomes enjoyable and fun. Code is the medium of our organization, and we are hacker-artists.

Branches

All branches take roughly the same time to become highly proficient in, around 1-2 years, but even after 6 months, adherents can begin using their acquired knowledge in a practical way with small limited tasks. We actively encourage the combination of theory and practice to strengthen one another.

Token Scientist

Token engineering is a new emerging science. Tokens are a breakthrough in building online networks, since we have a means to engineer incentive mechanisms and encourage certain user behaviours.

DeFi protocols in crypto make extensive use of token engineering to design how liquidity flows in and out of networks, and is an important key part of leveraging crypto economic power.

To become proficient in this area requires study of economics, mathematics, and finance. It also makes heavy use of Python programming to build simulations and economic models.

1. "New Paradigm for Macroeconomics" by Werner. This book will take several months to study but is a strong basis for understanding economics.
   1. Notes from the introduction to Werner's book.
   2. Notes on 'Shifting from Central Planning to a Decentralized Economy
2. "Understanding Pure Mathematics". We have a full high school mathematics course. This can also be skipped if you already know maths well.
   1. Continuing on with mathematics, you can learn more about stochastics, statistics, probability and analysis.
3. The DeFi and Token Engineering book.

Software Developer

Software developers create the end result software that others use. They take research and create a product from that research by applying the ideas. Developers can further be focused more on creating prototypes from research, or developing prototypes into polished final products.

To become a senior developer means learning about how the computer works on a deep level, and learning advanced programming skills. It takes time to fully master with a lot of early frustration but is eventually highly rewarding and creative. Developers are highly sought after and rare.

1. Learn from various materials about computer architecture, operating systems, and software architecture.
   1. Books such as the history of UNIX or the mythical man month.
   2. Articles by hintjens.com
2. Rust programming book
3. Install Arch Linux, learn to use the terminal

Cryptography Researcher

Cryptography researchers create the mathematics or repurpose existing algorithms to craft the weapons or implements of change that the developers use. They make use of advanced algebra to exploit the boundaries or hard limits set by the universe on reality to create cryptographic schemes that obey certain properties. They are in a sense reality hackers. They hack reality to create systems that obey objective properties due to the underlying mathematics. Needless to say, the advanced cryptographer is a good mathematician.

For cryptography, you will study "Abstract Algebra" by Pinter, and starting with simple cryptographic schemes gradually move towards learning more complex ones. You will prototype these schemes using a computer algebra system called SAGE.

Protocol Engineer

Good knowledge of computer science fundamentals as well as the ability to write code. There is also study of algebra but not to the same degree as for cryptography.

The protocol engineer is responsible for blockchain consensus algorithms, developing p2p networks, and other forms of distributed synchronization such as CRDTs. They establish the fundamentals for creating distributed applications and hardening the anti-censorship properties of crypto. They also harden networks against de-anonymization attempts through the use of encrypted mixnetworking and other techniques.

Protocol engineers have to possess a good knowledge about the theory behind distributed networks, as well as experience in how they work in practice. This topic is part theory, and part practical. They have a good grasp of algorithms and computer science theory.

Other

Alongside this study, continuing to study Ocalan is required. After finishing the Ocalan texts, you can then read Werner's book on economics, as well as Mumford or other philosophers.

Also engagement and familiarization with crypto is a must. Begin following this list and participating in crypto communities.

Starting

1. Download and install a simple Linux operating system to get started. Options can be Ubuntu or Manjaro Linux.
2. Watch Finematics videos.
3. Begin the initial stage listed above.
4. Follow the instructions on the Darkfi Book and run [ircd](Book https://darkrenaissance.github.io/darkfi/misc/ircd/ircd.html) to connect with the team.

Further Reading

Current Situation and Macro Overview

• Gensler Vows Action Against DeFi
• Crypto Mega Theses
• The Future of DeFi Must be No KYC
• Every single Bitcoin product banned in the UK as regulators crack down on crypto

Further Reading

Current Situation and Macro Overview

• Gensler Vows Action Against DeFi
• Crypto Mega Theses
• The Future of DeFi Must be No KYC
• Every single Bitcoin product banned in the UK as regulators crack down on crypto
• The DOJ’s ‘Crypto Enforcement Framework’ Argues Against Privacy Tools and for International Regulation
• The Coming Storm – Terrorists Using Cryptocurrency
• Report finds 50 billion of cryptocurrency moved out of China hinting at capital flight against Beijing rules

Economics

• mattigag's required reading
• Deribit, On Reflexivity and Imitation, Part 1
  • Part 2
• The Fraying of the US Global Currency Reserve System
• Introduction to Richard Werner: New Paradigm in Marcoeconomics
• Shifting from Central Planning to a Decentralized Economy
• The Great Race to Crypto Banking
• Dreams of a Peasant
• DAO Lay Lo Mo
• Crypto Market Structure

Web 3.0

• Ethereum's Political Philosophy Explained
• Squad Wealth
• Prehistory of DAOs
• Inventories, not Identities
• The origin of the digital antiquities market (NFTs)

Agorism and crypto-anarchy

• How to Return to Crypto's Subversive Roots
• The Crypto Anarchist Manifesto
• Collected Quotations of The Dread Pirate Roberts
• New Libertarian Manifesto
• A Declaration of the Independence of Cyberspace
• A Cypherpunk's Manifesto

rustdoc

Here the rustdoc for this repository's crates can be found.

Libraries

• darkfi
• darkfi-sdk
• darkfi-serial
• darkfi-derive
• darkfi-derive-internal

Binaries

• darkfid
• drk
• faucetd
• fu
• fud
• ircd
• lilith
• tau
• taud
• vanityaddr
• zkas

Smart contracts

• darkfi-money-contract
• darkfi-dao-contract

Architecture design

This section of the book shows the software architecture of DarkFi and the network implementations.

For this phase of development we organize into teams lead by a single surgeon. The role of the team is to give full support to the surgeon and make his work effortless and smooth.

Release Cycle

gantt
    title Release Cycle
    dateFormat  DD-MM-YYYY
    axisFormat  %m-%y
    section Phases
    Dcon0            :done, d0, 11-12-2021, 120d
    Dcon1            :done, d1, after d0,   120d
    Dcon2            :done, d2, after d1,   120d
    Dcon3            :done, d3, after d2,   60d
    Dcon4            :      d4, after d3,   14d
    Dcon5            :      d5, after d4,   7d

Overview

DarkFi is a layer one proof-of-stake blockchain that supports anonymous applications. It is currently under development. This overview will outline a few key terms that help explain DarkFi.

Blockchain: The DarkFi blockchain is based off proof of stake Ouroboros Crypsinous, tuned with a discrete controller to achieve a stable supply, currently under development to achieve instant finality using parallel leader election blockchain. uses Drk consensus token.

DarkFi blockchain's leadership, staking, unstaking, and transaction contracts are written in zkas language, on a P2P Network.

Wallet: A wallet is a portal to the DarkFi network. It provides the user with the ability to send and receive anonymous darkened tokens. Each wallet is a full node and stores a copy of the blockchain. All contract execution is done locally on the DarkFi wallet.

P2P Network: The DarkFi ecosystem runs as a network of P2P nodes, where these nodes interact with each other over specific protocols (see node overview). Nodes communicate on a peer-to-peer network, which is also home to tools such as our P2P irc and P2P task manager tau.

ZK smart contracts: Anonymous applications on DarkFi run on proofs that enforce an order of operations. We call these zero-knowledge smart contracts. Anonymous transactions on DarkFi is possible due to the interplay of two contracts, mint and burn (see the sapling payment scheme). Using the same method, we can define advanced applications.

zkas: zkas is the compiler used to compile zk smart contracts in its respective assembly-like language. The "assembly" part was chosen as it's the bare primitives needed for zk proofs, so later on the language can be expanded with higher-level syntax. Zkas enables developers to compile and inspect contracts.

zkVM: DarkFi's zkVM executes the binaries produced by zkas. The zkVM aims to be a general-purpose zkSNARK virtual machine that empowers developers to quickly prototype and debug zk contracts. It uses a trustless zero-knowledge proof system called Halo 2 with no trusted setup.

Anonymous assets

DarkFi network allows for the issuance and transfer of anonymous assets with an arbitrary number of parameters. These tokens are anonymous, relying on zero-knowledge proofs to ensure validity without revealing any other information.

New tokens are created and destroyed every time you send an anonymous transaction. To send a transaction on DarkFi, you must first issue a credential that commits to some value you have in your wallet. This is called the Mint phase. Once the credential is spent, it destroys itself: what is called the Burn.

Through this process, the link between inputs and outputs is broken.

Mint

During the Mint phase we create a new coin $C$, which is bound to the public key $P$. The coin $C$ is publicly revealed on the blockchain and added to the merkle tree, which is stored locally on the DarkFi wallet.

We do this using the following process:

Let $v$ be the coin's value. Generate random $r_C$, $r_V$ and serial $\rho$.

Create a commitment to these parameters in zero-knowledge:

$$C=H(P,v,\rho ,r_C)$$

Check that the value commitment is constructed correctly:

$$v>0$$ $$V=v{G}_1+r_V{G}_2$$

Reveal $C$ and $V$. Add $C$ to the Merkle tree.

Burn

When we spend the coin, we must ensure that the value of the coin cannot be double spent. We call this the Burn phase. The process relies on a $N$ nullifier, which we create using the secret key $x$ for the public key $P$. Nullifiers are unique per coin and prevent double spending. $R$ is the Merkle root. $v$ is the coin's value.

Generate a random number $r_V$.

$$N=H(x,\rho )$$

Check that the secret key corresponds to a public key:

$$P=xG$$

Check that the public key corresponds to a coin which is in the merkle tree $R$:

$$C=H(P,v,\rho ,r_C)$$ $$C\in R$$

Check that the value commitment is constructed correctly:

$$v>0$$ $$V=v{G}_1+r_V{G}_2$$

Reveal $N$, $V$ and $R$. Check $R$ is a valid Merkle root. Check $N$ does not exist in the nullifier set.

The zero-knowledge proof confirms that $N$ binds to an unrevealed value $C$, and that this coin is in the Merkle tree, without linking $N$ to $C$. Once the nullifier is produced the coin becomes unspendable.

Adding values

Assets on DarkFi can have any number of values or attributes. This is achieved by creating a credential $C$ and hashing any number of values and checking that they are valid in zero-knowledge.

We check that the sum of the inputs equals the sum of the outputs. This means that:

$$B=\sum V_{in}-\sum V_{out}$$

And that $B$ is a valid point on the curve $G_2$.

This proves that $B=0G_1+b{G}_2=b{G}_2$ where $b$ is a secret blinding factor for the amounts.

Diagram

Dynamic Proof of Stake

Overview

The DarkFi blockchain is based off proof of stake privacy focused Ouroboros Crypsinous, tunned with a discrete controller to achieve a stable supply.

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 ending in a single leader per slot singls finalization.

Crypsinous Blockchain is built on top of Zerocash sapling scheme, and Ouroboros Genesis blockchain. Each participant $U_p$ stores it's own local view of the Blockchain $C_{loc}^{U_p}$. $C_{loc}$ is a sequence of blocks $B_i$ (i>0), where each $B\in C_{loc}$ $$B=(t{x}_{lead},st)$$ $$t{x}_{lead}=(LEAD,header,txs,st{x}_{proof})$$ LEAD is a magic word, header is a metadata, and txs is a vector of transaction hash (see appendix). $st{x}_{proof}=(c{m}_{\prime c},s{n}_c,ep,sl,\rho ,h,\pi )$ the Block's st is the block data, and h is the hash of that data. the commitment of the newly created coin is: $(c{m}_{c_2},r_{c_2})=COMM(p{k}^{COIN}||\tau ||v_c||{\rho }_{c_2})$, $\tau$ is slot timestamp, or index. $s{n}_c$ is the coin's serial number revealed to spend the coin. $$s{n}_c=PR{F}_{roo{t}_{sk}^{COIN}}^{sn}({\rho }_c)$$ $$\rho ={\eta }^{s{k}_{sl}^{COIN}}$$ $\eta$ is randomness from random oracle implemented as hash of previous epoch, $\rho$ id derived randomness from $\eta$. $\pi$ is the NIZK proof of the LEAD statement.

st transactions

the blockchain view is a chain of blocks, each block $B_j=(t{x}_{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=(c{m}_{c_2},s{n}_{c_1},\eta ,sl,\rho ,h,ptr,{\mu }_{\rho },{\mu }_y,root)$, and $w=(path,roo{t}_{s{k}^{COIN}},pat{h}_{s{k}^{COIN}},{\tau }_c,{\rho }_c,r_{c_1},v,r_{c_2})$ for tuple $(x,w)\in L_{lead}$ iff:

• $p{k}^{COIN}=PR{F}_{roo{t}_{sk}^{COIN}}^{pk}({\tau }_c)$.
• ${\rho }_{c_2}=PR{F}_{roo{t}_{s{k}_{c_1}}^{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(c{m}_{c_i},p{k}^{COIN}||v||{\rho }_{c_i},r_{c_i})=T$.
• path is a valid Merkle tree path to $c{m}_{c_1}$ in the tree with the root root.
• $pat{h}_{s{k}^{COIN}}$ is a valid path to a leaf at position $sl-{\tau }_c$ in a tree with a root $roo{t}_{sk}^{COIN}$.
• $s{n}_{c_1}=PR{F}_{roo{t}_{sk}^{COIN}}^{sn}({\rho }_{c_1})$
• $y={\mu }_y^{roo{t}_{s{k}_{c_1}}^{COIN}||{\rho }_c}$
• $\rho ={\mu }_{\rho }^{roo{t}_{s{k}_{c_1}}^{COIN}||{\rho }_c}$
• $y<T(v)$ note that this process involves burning old coin $c_1$, minting new $c_2$ of the same value + reward.

validation rules

validation of proposed lead proof as follows:

• slot index is less than current slot index
• proposal extend from valid fork chain
• transactions doesn't exceed max limit
• signature is valid based off producer public key
• verify block hash
• verify block header hash
• public inputs ${\mu }_y$, ${\mu }_{rho}$ are hash of current consensus $\eta$, and current slot
• public inputs of target 2-term approximations ${\sigma }_1$, ${\sigma }_2$ are valid given total network stake and controller parameters
• the competing coin nullifier isn't published before to protect against double spening, before burning the coin.
• verify block transactions

Epoch

An epoch is a vector of blocks. Some of the blocks might be empty if there is no winnig leader. tokens in stake are constant during the epoch.

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

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.

$${\varphi }_f=1-(1-f{)}^{{\alpha }_i}$$ $$T_i=L{\varphi }_f({\alpha }_i^j)$$

Note that ${\varphi }_f(1)=f$, $\text{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 ${\varphi }_f({\alpha }_i)$, ${\alpha }_i$ is $U_i$ relative stake.

see the appendix for absolute stake aggregation dependent leader selection family of functions.

automating f tuning

the stable consensus token supply is maintained by the help of discrete PID controller, that maintain stabilized occurance of single leader per slot.

control lottery f tunning paramter

$$f[k]=f[k-1]+K_{1}e[k]+K_{2}e[k-1]+K_{3}e[k-2]$$

with $k_1=k_p+K_i+K_d$, $k_2=-K_p-2K_d$, $k_3=K_d$, and e is the error function.

target T n-term approximation

target function is approximated to avoid use of power, and division in zk, since no function in the family of functions that have independent aggregation property achieve avoid it (see appendix).

target function

target fuction T: $$T=L\ast \varphi (\sigma )=L\ast (1-(1-f{)}^{\sigma })$$ $\sigma$ is relative stake. f is tuning parameter, or the probability of winning have all the stake L is field length

$\varphi (\sigma )$ approximation

$$\varphi (\sigma )=1-(1-f{)}^{\sigma }$$ $$=1-e^{\sigma ln(1-f)}$$ $$=1-(1+\sum _{n=1}^{\infty }\frac{(\sigma ln(1-f){)}^n}{n!})$$ $$\sigma =\frac{s}{\Sigma }$$ s is stake, and $\Sigma$ is total stake.

target T n term approximation

$$k=Lln(1-f{)}^1$$ $$k^{{}^{\prime }n}=Lln(1-f{)}^n$$ $$T=-[k\sigma +\frac{k^{{}^{\prime \prime }}}{2!}{\sigma }^2+\cdots +\frac{k^{{}^{\prime }n}}{n!}{\sigma }^n]$$ $$=-[\frac{k}{\Sigma }s+\frac{k^{{}^{\prime \prime }}}{{\Sigma }^{2}2!}{s}^2+\cdots +\frac{k^{{}^{\prime }n}}{{\Sigma }^{n}n!}{s}^n]$$

comparison of original target to approximation

Appendix

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

Blockchain

Header

Block

LeadInfo

Public Inputs

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-\varphi ({\sum }_i{\sigma }_i)=1-(1+(1-f{)}^{{\sigma }_i})=-(1-f{)}^{{\sum }_i{\sigma }_i}$, the joint "one minus probability" of all the stakes (each with probability $\varphi ({\sigma }_i))$ winning aggregated winning the leadership ${\prod }_i^n(1-\varphi ({\sigma }_i))=-(1-f{)}^{{\sum }_i({\sigma }_i)}$ thus: $$1-\varphi (\sum _i{\sigma }_i)=\prod _i^n(1-\varphi ({\sigma }_i))$$

A non-exponential linear leader selection can be:

$$y<T$$ $$y=2^{l}k\mid 0\le k\le 1$$ $$T=2^l\varphi (v)$$ $$\varphi (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:

$$\varphi (\sum _i{\sigma }_i)>\prod _i^n{\sigma }_i$$ $$\sum _i{\sigma }_i>(\frac{1}{v_{max}+c}{)}^{n-1}{v}_1{v}_2\dots v_n$$ let's assume the stakes are divided to stakes of value ${\sigma }_i=1$ for $\Sigma >1\in \mathbb{Z}$, ${\sum }_i{\sigma }_i=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^{l}k\varphi (\Sigma )=2^l(\frac{1}{v_{max}+c})\Sigma$$ let's assume $v_{max}=2^v$, and $c=0$ then: $$T=2^{l}k\varphi (\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 $n{v}_{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 $\varphi (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 $\varphi (\alpha )$ that are isomorphic to summation on multiplication $\varphi ({\alpha }_1+{\alpha }_2)=\varphi ({\alpha }_1)\varphi ({\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 $\varphi$ is isomorphic function between multiplication and addition, $\varphi (\alpha )=\varphi (\frac{\alpha }{2})\varphi (\frac{\alpha }{2})=\varphi (\frac{\alpha }{2}{)}^2$, thus: $$\varphi (\alpha )=\underset{\text{α}}{\underbrace{\varphi (1)\dots \varphi (1)}}=\varphi (1{)}^{\alpha }$$ then the only family of functions $\varphi :\mathbb{R}\to \mathbb{R}$ satisfying this is the exponential function $$\varphi (\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 $y<T$, $$T=L{\varphi }_{max}\varphi (\alpha )=S\varphi (\alpha )$$ $$S=ord(G){\varphi }_{max}\varphi (\alpha )$$ such that S $inZ$ ${\varphi }_{max}=\varphi ({\alpha }_{max})$ where ${\alpha }_{max}$ is the maximum stake value being $2^{64}$, following from the previous proof that the family of function haveing independent aggregation property is the exponential function $f^{\alpha }$, and $f\in Z|f>1$, the smallest value satisfying f is $f=2$, then $${\varphi }_{max}=2^{2^{64}}$$ note that since $ord(G)<<{\varphi }_{max}$ thus $S<<1$, contradiction.

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:

$${\eta }_j=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+ϵ}$, note that k is a persistence security parameter, R is the epoch length in terms of slots.

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 query, so it's security is hinged on $\text{centralized global random node}$.

solution

to break this centeralization, a decentralized emulation of $G_{ro}$ functionality for calculation of: ${\eta }_i=PR{F}_{{\eta }_{i-1}}^{G_{ro}}(\psi )$ $$\psi =hash(t{x}_0^{ep})$$ $${\eta }_0=hash("let\mathrm{there}\mathrm{be}\mathrm{dark}!")$$ note that first transaction in the block, is the proof transaction.

Consensus

This section of the book describes how nodes participating in the DarkFi blockchain achieve consensus.

Glossary

Node main loop

As described in previous chapter, DarkFi is based on Ouroboros Crypsinous. Therefore, block production involves the following steps:

At the start of every slot, each node runs the leader selection algorithm to determine if they are the slot's leader. If successful, they can produce a block containing unproposed transactions. This block is then appended to the largest known fork and shared with rest of the nodes on the P2P network as a block proposal.

Before the end of every slot each node triggers a finalization check, to verify which block proposals can be finalized onto the canonical blockchain. This is also known as the finalization sync period.

Pseudocode:

loop {
    wait_for_next_slot_start()

    if is_slot_leader() {
        block = propose_block()
        p2p.broadcast_block(block)
    }

    wait_for_slot_end()

    chain_finalization()
}

Listening for blocks

Each node listens to new block proposals concurrently with the main loop. Upon receiving block proposals, nodes try to extend the proposals onto a fork that they hold in memory. This process is described in the next section.

Fork extension

Since there can be more than one slot leader, each node holds a set of known forks in memory. When a node becomes a leader, they extend the longest fork they hold.

Upon receiving a block, one of the following cases may occur:

Visual Examples

Starting state:

               |--[L0] <-- F0
[C]--...--[C]--|
               |--[L1] <-- F1

Case 1

Extending F0 fork with a new block proposal:

               |--[L0]+--[L2] <-- F0
[C]--...--[C]--|
               |--[L1]        <-- F1

Case 2

Extending F0 fork at [L0] slot with a new block proposal, creating a new fork chain:

               |--[L0]--[L2]   <-- F0
[C]--...--[C]--|
               |--[L1]         <-- F1
               |
               |+--[L0]+--[L3] <-- F2

Case 3

Extending the canonical blockchain with a new block proposal:

               |--[L0]--[L2] <-- F0
[C]--...--[C]--|
               |--[L1]       <-- F1
               |
               |--[L0]--[L3] <-- F2
               |
               |+--[L4]      <-- F3

Finalization

When the finalization sync period kicks in, each node looks up the longest fork chain it holds. There must be no other fork chain with same length. If such a fork chain exists, nodes finalize all block proposals by appending them to the canonical blockchain.

Once finalized, all fork chains are removed from the memory pool. Practically this means that no finalization can occur while there are competing fork chains of the same length. In such a case, finalization can only occur when we have a a slot with a single leader.

We continue Case 3 from the previous section to visualize this logic. On slot 5, a node observes 2 proposals. One extends the F0 fork, and the other extends the F2 fork:

               |--[L0]--[L2]+--[L5a] <-- F0
[C]--...--[C]--|
               |--[L1]               <-- F1
               |
               |--[L0]--[L3]+--[L5b] <-- F2
               |
               |--[L4]               <-- F3

Since we have two competing fork chains finalization cannot occur.

On next slot, a node only observes 1 proposal. So it extends the F2 fork:

               |--[L0]--[L2]--[L5a]        <-- F0
[C]--...--[C]--|
               |--[L1]                     <-- F1
               |
               |--[L0]--[L3]--[L5b]+--[L6] <-- F2
               |
               |--[L4]                     <-- F3

When the finalization sync period starts, the node finalizes fork F2 and all other forks get dropped:

               |/--[L0]--[L2]--[L5a]      <-- F0
[C]--...--[C]--|
               |/--[L1]                   <-- F1
               |
               |--[L0]--[L3]--[L5b]--[L6] <-- F2
               |
               |/--[L4]                   <-- F3

The canonical blockchain now contains blocks L0, L3, L5b and L6 from fork F2.

Transactions

(Temporary document, to be integrated into other docs)

Transaction behaviour

In our network context, we have two types of nodes.

1. Consensus Participant (CP)
2. Consensus Spectator (non-participant) (CS)

CS acts as a relayer for transactions in order to help out that transactions reach CP.

To avoid spam attacks, CS should keep $tx$ in their mempool for some period of time, and then prune it.

Ideal simulation with instant finality

The lifetime of a transaction $tx$ that passes verification and whose state transition can be applied on top of the finalized (canonical) chain:

1. User creates a transaction $tx$
2. User broadcasts $tx$ to CS
3. CS validates $tx$ state transition
4. $tx$ enters CS mempool
5. CS broadcasts $tx$ to CP
6. CP validates $tx$ state transition
7. $tx$ enters CP mempool
8. CP validates all transactions in its mempool in sequence
9. CP proposes a block finalization containing $tx$
10. CP writes the state transition update of $tx$ to their chain
11. CP removes $tx$ from their mempool
12. CP broadcasts the finalizated proposal
13. CS receives the proposal and validates transactions
14. CS writes the state updates to their chain
15. CS removes $tx$ from their mempool

Real-world simulation with non-instant finality

The lifetime of a transaction $tx$ that passes verification and whose state transition is pending to be applied on top of the finalized (canonical) chain:

1. User creates a transaction $tx$
2. User broadcasts $tx$ to CS
3. CS validates $tx$ state transition
4. $tx$ enters CS mempool
5. CS broadcasts $tx$ to CP
6. CP validates $tx$ state transition
7. $tx$ enters CP mempool
8. CP proposes a block proposal containing $tx$
9. CP proposes more block proposals
10. When proposals can be finalized, CP validates all their transactions in sequence
11. CP writes the state transition update of $tx$ to their chain
12. CP removes $tx$ from their mempool
13. CP broadcasts the finalizated proposals sequence
14. CS receives the proposals sequence and validates transactions
15. CS writes the state updates to their chain
16. CS removes $tx$ from their mempool

Real-world simulation with non-instant finality, forks and multiple CP nodes

The lifetime of a transaction $tx$ that passes verifications and whose state transition is pending to be applied on top of the finalized (canonical) chain:

1. User creates a transaction $tx$
2. User broadcasts $tx$ to CS
3. CS validates $tx$ state transition against canonical chain state
4. $tx$ enters CS mempool
5. CS broadcasts $tx$ to CP
6. CP validates $tx$ state transition against all known fork states
7. $tx$ enters CP mempool
8. CP broadcasts $tx$ to rest CP nodes
9. Slot producer CP (SCP) node finds which fork to extend
10. SCP validates all unproposed transactions in its mempool in sequence, against extended fork state, discarding invalid
11. SCP creates a block proposal containing $tx$ extending the fork
12. CP receives block proposal and validates its transactions against the extended fork state
13. SCP proposes more block proposals extending a fork state
14. When a fork can be finalized, CP validates all its proposals transactions in sequence, against canonical state
15. CP writes the state transition update of $tx$ to their chain
16. CP removes $tx$ from their mempool
17. CP drop rest forks and keeps only the finalized one
18. CP broadcasts the finalizated proposals sequence
19. CS receives the proposals sequence and validates transactions
20. CS writes the state updates to their chain
21. CS removes $tx$ from their mempool

CP will keep $tx$ in its mempool as long as it is a valid state transition for any fork(including canonical) or it get finalized.

Unproposed transactions refers to all $tx$ not included in a proposal of any fork.

If a fork that can be finalized fails to validate all its transactions(14), it should be dropped.

The Transaction object

pub struct ContractCall {
    /// The contract ID to which the payload is fed to
    pub contract_id: ContractId,
    /// Arbitrary payload for the contract call
    pub payload: Vec<u8>,
}

pub struct Transaction {
    /// Calls executed in this transaction
    pub calls: Vec<ContractCall>,
    /// Attached ZK proofs
    pub proofs: Vec<Vec<Proof>>,
    /// Attached Schnorr signatures
    pub signatures: Vec<Vec<Signature>>,
}

A generic DarkFi transaction object is simply an array of smart contract calls, along with attached ZK proofs and signatures needed to properly verify the contracts' execution. A transaction can have any number of calls, and proofs, provided it does not exhaust a set gas limit.

In DarkFi, every operation is a smart contract. This includes payments, which we'll explain in the following section.

Payments

For A -> B payments in DarkFi we use the Sapling scheme that originates from zcash. A payment transaction has a number of inputs (which are coins being burned/spent), and a number of outputs (which are coins being minted/created). An explanation for the ZK proofs for this scheme can be found in the Zkas section of this book, under Sapling.

In code, the structs we use are the following:

pub struct MoneyTransferParams {
    pub inputs: Vec<Input>,
    pub outputs: Vec<Output>,
}

pub struct Input {
    /// Pedersen commitment for the input's value
    pub value_commit: ValueCommit,
    /// Pedersen commitment for the input's token ID
    pub token_commit: ValueCommit,
    /// Revealed nullifier
    pub nullifier: Nullifier,
    /// Revealed Merkle root
    pub merkle_root: MerkleNode,
    /// Public key for the Schnorr signature
    pub signature_public: PublicKey,
}

pub struct Output {
    /// Pedersen commitment for the output's value
    pub value_commit: ValueCommit,
    /// Pedersen commitment for the output's token ID
    pub token_commit: ValueCommit,
    /// Minted coin: poseidon_hash(pubkey, value, token, serial, blind)
    pub coin: Coin,
    /// The encrypted note ciphertext
    pub encrypted_note: EncryptedNote,
}

pub struct EncryptedNote {
    pub ciphertext: Vec<u8>,
    pub ephemeral_key: PublicKey,
}

pub struct Note {
    /// Serial number of the coin, used to derive the nullifier
    pub serial: pallas::Base,
    /// Value of the coin
    pub value: u64,
    /// Token ID of the coin
    pub token_id: TokenId,
    /// Blinding factor for the coin bulla
    pub coin_blind: pallas::Base,
    /// Blinding factor for the value Pedersen commitment
    pub value_blind: ValueBlind,
    /// Blinding factor for the token ID Pedersen commitment
    pub token_blind: ValueBlind,
    /// Attached memo (arbitrary data)
    pub memo: Vec<u8>,
}

In the blockchain state, every minted coin must be added into a Merkle tree of all existing coins. Once added, the new tree root is used to prove existence of this coin when it's being spent.

Let's imagine a scenario where Alice has 100 ALICE tokens and wants to send them to Bob. Alice would create an Input object using the info she has of her coin. She has to derive a nullifier given her secret key and the serial number of the coin, hash the coin bulla so she can create a merkle path proof, and derive the value and token commitments using the blinds.

let nullifier = poseidon_hash([alice_secret_key, serial]);
let signature_public = alice_secret_key * Generator;
let coin = poseidon_hash([signature_public, value, token_id, blind]);
let merkle_root = calculate_merkle_root(coin);
let value_commit = pedersen_commitment(value, value_blind);
let token_commit = pedersen_commitment(token_id, token_blind);

The values above, except coin become the public inputs for the Burn ZK proof. If everything is correct, this allows Alice to spend her coin. In DarkFi, the changes have to be atomic, so any payment transaction that is burning some coins, has to mint new coins at the same time, and no value must be lost, nor can the token ID change. We enforce this by using Pedersen commitments.

Now that Alice has a valid Burn proof and can spend her coin, she can mint a new coin for Bob.

let blind = pallas::Base::random();
let value_blind = ValueBlind::random();
let token_blind = ValueBlind::random();
let coin = poseidon_hash([bob_public, value, token_id, blind]);
let value_commit = pedersen_commitment(value, value_blind);
let token_commit = pedersen_commitment(token, token_blind);

coin, value_commit, and token_commit become the public inputs for the Mint ZK proof. If this proof is valid, it creates a new coin for Bob with the given parameters. Additionally, Alice would put the values and blinds in a Note which is encrypted with Bob's public key so only Bob is able to decrypt it. This Note has the necessary info for him to further spend the coin he received.

At this point Alice should have 1 input and 1 output. The input is the coin she burned, and the output is the coin she minted for Bob. Along with this, she has two ZK proofs that prove creation of the input and output. Now she can build a transaction object, and then use her secret key she derived in the Burn proof to sign the transaction and publish it to the blockchain.

The blockchain will execute the smart contract with the given payload and verify that the Pedersen commitments match, that the nullifier has not been published before, and also that the merkle authentication path is valid and therefore the coin existed in a previous state. Outside of the VM, the validator will also verify the signature(s) and the ZK proofs. If this is valid, then Alice's coin is now burned and cannot be used anymore. And since Alice also created an output for Bob, this new coin is now added to the Merkle tree and is able to be spent by him. Effectively this means that Alice has sent her tokens to Bob.

Anonymous Smart Contracts

• Important Invariants
• Global Smart Contract State
• Atomic Transactions
• ZK Proofs and Signatures
• Parallelisation Techniques

Every full node is a verifier.

Prover is the person executing the smart contract function on their secret witness data. They are also verifiers in our model.

Lets take a pseudocode smart contract:

contract Dao {
    # 1: the DAO's global state
    dao_bullas = DaoBulla[]
    proposal_bullas = ProposalBulla[]
    proposal_nulls = ProposalNull[]

    # 2. a public smart contract function
    #    there can be many of these
    fn mint(...) {
        ...
    }

    ...
}

Important Invariants

1. The state of a contract (the contract member values) is globally readable but only writable by that contract's functions.
2. Transactions are atomic. If a subsequent contract function call fails then the earlier ones are also invalid. The entire tx will be rolled back.
3. foo_contract::bar_func::validate::state_transition() is able to access the entire transaction to perform validation on its structure. It might need to enforce requirements on the calldata of other function calls within the same tx. See DAO::exec().

Global Smart Contract State

Internally we represent this smart contract like this:

mod dao_contract {
    // Corresponds to 1. above, the global state
    struct State {
        dao_bullas: Vec<DaoBulla>,
        proposal_bullas: Vec<ProposalBulla>,
        proposal_nulls: Vec<ProposalNull>
    }

    // Corresponds to 2. mint()
    // Prover specific
    struct MintCall {
        ...
        // secret witness values for prover
        ...
    }

    impl MintCall {
        fn new(...) -> Self {
            ...
        }

        fn make() -> FuncCall {
            ...
        }
    }

    // Verifier code
    struct MintParams {
        ...
        // contains the function call data
        ...
    }
}

There is a pipeline where the prover runs MintCall::make() to create the MintParams object that is then broadcast to the verifiers through the p2p network.

The CallData usually is the public values exported from a ZK proof. Essentially it is the data used by the verifier to check the function call for DAO::mint().

Atomic Transactions

Transactions represent several function call invocations that are atomic. If any function call fails, the entire tx is rejected. Additionally some smart contracts might impose additional conditions on the transaction's structure or other function calls (such as their call data).

/// A Transaction contains an arbitrary number of `ContractCall` objects,
/// along with corresponding ZK proofs and Schnorr signatures.
#[derive(Debug, Clone, Eq, PartialEq, SerialEncodable, SerialDecodable)]
pub struct Transaction {
    /// Calls executed in this transaction
    pub calls: Vec<ContractCall>,
    /// Attached ZK proofs
    pub proofs: Vec<Vec<Proof>>,
    /// Attached Schnorr signatures
    pub signatures: Vec<Vec<Signature>>,
}

Function calls represent mutations of the current active state to a new state.

/// A ContractCall is the part of a transaction that executes a certain
/// `contract_id` with `data` as the call's payload.
#[derive(Debug, Clone, Eq, PartialEq, SerialEncodable, SerialDecodable)]
pub struct ContractCall {
    /// ID of the contract invoked
    pub contract_id: ContractId,
    /// Call data passed to the contract
    pub data: Vec<u8>,
}

The contract_id corresponds to the top level module for the contract which includes the global State.

The func_id of a function call corresponds to predefined objects in the submodules:

• Builder creates the anonymized CallData. Ran by the prover.
• CallData is the parameters used by the anonymized function call invocation. Verifiers have this.
• state_transition() that runs the function call on the current state using the CallData.
• apply() commits the update to the current state taking it to the next state.

An example of a contract_id could represent DAO or Money. Examples of func_id could represent DAO::mint() or Money::transfer().

Each function call invocation is ran using its own state_transition() function.

mod dao_contract {
    ...

    // DAO::mint() in the smart contract pseudocode
    mod mint {
        ...

        fn state_transition(states: &StateRegistry, func_call_index: usize, parent_tx: &Transaction) -> Result<Update> {
            // we could also change the state_transition() function signature
            // so we pass the func_call itself in
            let func_call = parent_tx.func_calls[func_call_index];
            let call_data = func_call.call_data;
            // It's useful to have the func_call_index within parent_tx because
            // we might want to enforce that it appears at a certain index exactly.
            // So we know the tx is well formed.

            ...
        }
    }
}

The state_transition() has access to the entire atomic transaction to enforce correctness. For example chaining of function calls is used by the DAO::exec() smart contract function to execute moving money out of the treasury using Money::transfer() within the same transaction.

Additionally StateRegistry gives smart contracts access to the global states of all smart contracts on the network, which is needed for some contracts.

Note that during this step, the state is not modified. Modification happens after the state_transition() is run for all function call invocations within the transaction. Assuming they all pass successfully, the updates are then applied at the end. This ensures atomicity property of transactions.

mod dao_contract {
    ...

    // DAO::mint() in the smart contract pseudocode
    mod mint {
        ...

        // StateRegistry is mutable
        fn apply(states: &mut StateRegistry, update: Update) {
            ...
        }
    }
}

The transaction verification pipeline roughly looks like this:

1. Loop through all function call invocations within the transaction:
   1. Lookup their respective state_transition() function based off their contract_id and func_id. The contract_id and func_id corresponds to the contract and specific function, such as DAO::mint().
   2. Call the state_transition() function and store the update. Halt if this function fails.
2. Loop through all updates
   1. Lookup specific apply() function based off the contract_id and func_id.
   2. Call apply(update) to finalize the change.

ZK Proofs and Signatures

Lets review again the format of transactions.

/// A Transaction contains an arbitrary number of `ContractCall` objects,
/// along with corresponding ZK proofs and Schnorr signatures.
#[derive(Debug, Clone, Eq, PartialEq, SerialEncodable, SerialDecodable)]
pub struct Transaction {
    /// Calls executed in this transaction
    pub calls: Vec<ContractCall>,
    /// Attached ZK proofs
    pub proofs: Vec<Vec<Proof>>,
    /// Attached Schnorr signatures
    pub signatures: Vec<Vec<Signature>>,
}

And corresponding function calls.

/// A ContractCall is the part of a transaction that executes a certain
/// `contract_id` with `data` as the call's payload.
#[derive(Debug, Clone, Eq, PartialEq, SerialEncodable, SerialDecodable)]
pub struct ContractCall {
    /// ID of the contract invoked
    pub contract_id: ContractId,
    /// Call data passed to the contract
    pub data: Vec<u8>,
}

As we can see the ZK proofs and signatures are separate from the actuall call_data interpreted by state_transition(). They are both automatically verified by the VM.

However for verification to work, the ZK proofs also need corresponding public values, and the signatures need the public keys. We do this by exporting these values. (TODO: link the code where this happens)

These methods export the required values needed for the ZK proofs and signature verification from the actual call data itself.

For signature verification, the data we are verifying is simply the entire transactions minus the actual signatures. That's why the signatures are a separate top level field in the transaction.

Parallelisation Techniques

Since verification is done through state_transition() which returns an update that is then committed to the state using apply(), we can verify all transactions in a block in parallel.

To enable calling another transaction within the same block (such as flashloans), we can add a special depends field within the tx that makes a tx wait on another tx before being allowed to verify. This causes a small deanonymization to occur but brings a massive scalability benefit to the entire system.

ZK proof verification should be done automatically by the system. Any proof that fails marks the entire tx as invalid, and the tx is discarded. This should also be parallelized.

Anonymous Bridge (DRAFT)

We present an overview of a possibility to develop anonymous bridges from any blockchain network that has tokens/balances on some address owned by a secret key. Usually in networks, we have a secret key which we use to derive a public key (address) and use this address to receive funds. In this overview, we'll go through such an operation on the Ethereum network and see how we can bridge funds from ETH to DarkFi.

Preliminaries

Verifiable secret sharing¹

Verifiable secret sharing ensures that even if the dealer is malicious there is a well-defined secret that the players can later reconstruct. VSS is defined as a secure multi-party protocol for computing the randomized functionality corresponding to some secret sharing scheme.

Secure multiparty computation²

Multiparty computation is typically accomplished by making secret shares of the inputs, and manipulating the shares to compute some function. To handle "active" adversaries (that is, adversaries that corrupt nodes and make them deviate from the protocol), the secret sharing scheme needs to be verifiable to prevent the deviating nodes from throwing off the protocol.

General bridge flow

Assume Alice wants to bridge 10 ETH from the Ethereum network into DarkFi. Alice would issue a bridging request and perform a VSS scheme with a network of nodes in order to create an Ethereum secret key, and with it - derive an Ethereum address. Using such a scheme should prevent any single party to retrieve the secret key and steal funds. This also means, for every bridging operation, a fresh and unused Ethereum address is generated and as such gives no convenient ways of tracing bridge deposits.

Once the new address has been generated, Alice can now send funds to the address and either create some proof of deposit, or there can be an oracle that verifies the state on Ethereum in order to confirm that the funds have actually been sent.

Once confirmed, the bridging smart contract is able to freshly mint the counterpart of the deposited funds on a DarkFi address of Alice's choice.

Open questions:

• What to do with the deposited funds?

It is possible to send them to some pool or smart contract on ETH, but this becomes an address that can be blacklisted as adversaries can assume it is the bridge's funds. Alternatively, it could be sent into an L2 such as Aztec in order to anonymise the funds, but (for now) this also limits the variety of tokens that can be bridged (ETH & DAI).

• How to handle network fees?

In the case where the token being bridged cannot be used to pay network fees (e.g. bridging DAI from ETH), there needs to be a way to cover the transaction costs. The bridge nodes could fund this themselves but then there also needs to be some protection mechanism to avoid people being able to drain those wallets from their ETH.

Tooling

DarkFi Fullnode Daemon

darkfid is the darkfi fullnode. It manages the blockchain, validates transactions and remains connected to the p2p network.

Clients can connect over localhost RPC or secure socket and perform these functions:

• Get the node status and modify settings realtime.
• Query the blockchain.
• Broadcast txs to the p2p network.
• Get tx status, query the mempool and interact with components.

darkfid does not have any concept of keys or wallet functionality. It does not manage keys.

Low Level Client

Clients manage keys and objects. They make queries to darkfid, and receive notes encrypted to their public keys.

Their design is usually specific to their application but modular.

They also expose a high level simple to use API corresponding exactly to their commands so that product teams can easily build an application. They will use the command line tool as an interactive debugging application and point of reference.

The API should be well documented with all arguments explained. Likewise for the commands help text.

Command cheatsheets and example sessions are strongly encouraged.

zkas

zkas is a compiler for the Halo2 zkVM language used in DarkFi.

The current implementation found in the DarkFi repository inside src/zkas is the reference compiler and language implementation. It is a toolchain consisting of a lexer, parser, static and semantic analyzers, and a binary code compiler.

The main.rs file shows how this toolchain is put together to produce binary code from source code.

Architecture

The main part of the compilation happens inside the parser. New opcodes can be added by extending opcode.rs.

    // The lexer goes over the input file and separates its content into
    // tokens that get fed into a parser.
    let lexer = Lexer::new(filename, source.chars());
    let tokens = lexer.lex();

    // The parser goes over the tokens provided by the lexer and builds
    // the initial AST, not caring much about the semantics, just enforcing
    // syntax and general structure.
    let parser = Parser::new(filename, source.chars(), tokens);
    let (namespace, constants, witnesses, statements) = parser.parse();

    // The analyzer goes through the initial AST provided by the parser and
    // converts return and variable types to their correct forms, and also
    // checks that the semantics of the ZK script are correct.
    let mut analyzer = Analyzer::new(filename, source.chars(), constants, witnesses, statements);
    analyzer.analyze_types();

    if args.interactive {
        analyzer.analyze_semantic();
    }

    if args.evaluate {
        println!("{:#?}", analyzer.constants);
        println!("{:#?}", analyzer.witnesses);
        println!("{:#?}", analyzer.statements);
        println!("{:#?}", analyzer.stack);
        exit(0);
    }

    let compiler = Compiler::new(
        filename,
        source.chars(),
        namespace,
        analyzer.constants,
        analyzer.witnesses,
        analyzer.statements,
        analyzer.literals,
        !args.strip,
    );

    let bincode = compiler.compile();

zkas bincode

The bincode design for zkas is the compiled code in the form of a binary blob, that can be read by a program and fed into the VM.

Our programs consist of four sections: constant, literal, contract, and circuit. Our bincode represents the same. Additionally, there is an optional section called .debug which can hold debug info related to the binary.

We currently keep all variables on one stack, and literals on another stack. Therefore before each STACK_INDEX we prepend STACK_TYPE so the VM is able to know which stack it should do lookup from.

The compiled binary blob has the following layout:

MAGIC_BYTES
BINARY_VERSION
NAMESPACE
.constant
CONSTANT_TYPE CONSTANT_NAME 
CONSTANT_TYPE CONSTANT_NAME 
...
.literal
LITERAL
LITERAL
...
.contract
WITNESS_TYPE
WITNESS_TYPE
...
.circuit
OPCODE ARG_NUM STACK_TYPE STACK_INDEX ... STACK_TYPE STACK_INDEX
OPCODE ARG_NUM STACK_TYPE STACK_INDEX ... STACK_TYPE STACK_INDEX
...
.debug
TBD

Integers in the binary are encoded using variable-integer encoding. See the serial crate and module for our Rust implementation.

Sections

MAGIC_BYTES

The magic bytes are the file signature consisting of four bytes used to identify the zkas binary code. They consist of:

0x0b 0x01 0xb1 0x35

BINARY_VERSION

The binary code also contains the binary version to allow parsing potential different formats in the future.

0x02

NAMESPACE

This sector after MAGIC_BYTES and BINARY_VERSION contains the reference namespace of the code. This is the namespace used in the source code, e.g.:

constant "MyNamespace" { ... }
contract "MyNamespace" { ... }
circuit  "MyNamespace" { ... }

The string is serialized with variable-integer encoding.

.constant

The constants in the .constant section are declared with their type and name, so that the VM knows how to search for the builtin constant and add it to the stack.

.literal

The literals in the .literal section are currently unsigned integers that get parsed into a u64 type inside the VM. In the future this could be extended with signed integers, and strings.

.contract

The .contract section holds the circuit witness values in the form of WITNESS_TYPE. Their stack index is incremented for each witness as they're kept in order like in the source file. The witnesses that are of the same type as the circuit itself (typically Base) will be loaded into the circuit as private values using the Halo2 load_private API.

.circuit

The .circuit section holds the procedural logic of the ZK proof. In here we have statements with opcodes that are executed as understood by the VM. The statements are in the form of:

OPCODE ARG_NUM STACK_TYPE STACK_INDEX ... STACK_TYPE STACK_INDEX

where:

In case an opcode has a return value, the value shall be pushed to the stack and become available for later references.

.debug

TBD

Syntax Reference

Variable Types

Literal Types

Opcodes

Built-in Opcode Wrappers

Decoding the bincode

An example decoder implementation can be found in zkas' decoder.rs module.

Examples

This section holds practical and real-world examples of the use for zkas.

• Sapling payment scheme
• Anonymous voting

Anonymous voting

Anonymous voting¹ is a type of voting process where users can vote without revealing their identity, by proving they are accepted as valid voters.

The proof enables user privacy and allows for fully anonymous voting.

The starting point is a Merkle proof², which efficiently proves that a voter's key belongs to a Merkle tree. However, using this proof alone would allow the organizer of a process to correlate each vote envelope with its voter's key on the database, so votes wouldn't be secret.

Vote proof

constant "Vote" {
	EcFixedPointShort VALUE_COMMIT_VALUE,
	EcFixedPoint VALUE_COMMIT_RANDOM,
	EcFixedPointBase NULLIFIER_K,
}

contract "Vote" {
	Base process_id_0,
	Base process_id_1,
	Base secret_key,
	Base vote,
	Scalar vote_blind,
	Uint32 leaf_pos,
	MerklePath path,
}

circuit "Vote" {
	# Nullifier hash
	process_id = poseidon_hash(process_id_0, process_id_1);
	nullifier = poseidon_hash(secret_key, process_id);
	constrain_instance(nullifier);

	# Public key derivation and hashing
	public_key = ec_mul_base(secret_key, NULLIFIER_K);
	public_x = ec_get_x(public_key);
	public_y = ec_get_y(public_key);
	pk_hash = poseidon_hash(public_x, public_y);

	# Merkle root
	root = merkle_root(leaf_pos, path, pk_hash);
	constrain_instance(root);

	# Pedersen commitment for vote
	vcv = ec_mul_short(vote, VALUE_COMMIT_VALUE);
	vcr = ec_mul(vote_blind, VALUE_COMMIT_RANDOM);
	vote_commit = ec_add(vcv, vcr);
	# Since vote_commit is a curve point, we fetch its coordinates
	# and constrain_them:
	vote_commit_x = ec_get_x(vote_commit);
	vote_commit_y = ec_get_y(vote_commit);
	constrain_instance(vote_commit_x);
	constrain_instance(vote_commit_y);
}

Our proof consists of four main operation. First we are hashing the nullifier using our secret key and the hashed process ID. Next, we derive our public key and hash it. Following, we take this hash and create a Merkle proof that it is indeed contained in the given Merkle tree. And finally, we create a Pedersen commitment³ for the vote choice itself.

Our vector of public inputs can look like this:

let public_inputs = vec![
    nullifier,
    merkle_root,
    *vote_coords.x(),
    *vote_coords.y(),
]

And then the Verifier uses these public inputs to verify the given zero-knowledge proof.

Sapling payment scheme

Sapling is a type of transaction which hides both the sender and receiver data, as well as the amount transacted. This means it allows a fully private transaction between two addresses.

Generally, the Sapling payment scheme consists of two ZK proofs - mint and burn. We use the mint proof to create a new coin $C$, and we use the burn proof to spend a previously minted coin.

Mint proof

constant "Mint" {
	EcFixedPointShort VALUE_COMMIT_VALUE,
	EcFixedPoint VALUE_COMMIT_RANDOM,
	EcFixedPointBase NULLIFIER_K,
}

contract "Mint" {
	Base pub_x,
	Base pub_y,
	Base value,
	Base token,
	Base serial,
	Base coin_blind,
	Scalar value_blind,
	Scalar token_blind,
}

circuit "Mint" {
	# Poseidon hash of the coin
	C = poseidon_hash(pub_x, pub_y, value, token, serial, coin_blind);
	constrain_instance(C);

	# Pedersen commitment for coin's value
	vcv = ec_mul_short(value, VALUE_COMMIT_VALUE);
	vcr = ec_mul(value_blind, VALUE_COMMIT_RANDOM);
	value_commit = ec_add(vcv, vcr);
	# Since the value commit is a curve point, we fetch its coordinates
	# and constrain them:
	value_commit_x = ec_get_x(value_commit);
	value_commit_y = ec_get_y(value_commit);
	constrain_instance(value_commit_x);
	constrain_instance(value_commit_y);

	# Pedersen commitment for coin's token ID
	tcv = ec_mul_base(token, NULLIFIER_K);
	tcr = ec_mul(token_blind, VALUE_COMMIT_RANDOM);
	token_commit = ec_add(tcv, tcr);
	# Since token_commit is also a curve point, we'll do the same
	# coordinate dance:
	token_commit_x = ec_get_x(token_commit);
	token_commit_y = ec_get_y(token_commit);
	constrain_instance(token_commit_x);
	constrain_instance(token_commit_y);

	# At this point we've enforced all of our public inputs.
}

As you can see, the Mint proof basically consists of three operations. First one is hashing the coin $C$, and after that, we create Pedersen commitments¹ for both the coin's value and the coin's token ID. On top of the zkas code, we've declared two constant values that we are going to use for multiplication in the commitments.

The constrain_instance call can take any of our assigned variables and enforce a public input. Public inputs are an array (or vector) of revealed values used by verifiers to verify a zero knowledge proof. In the above case of the Mint proof, since we have five calls to constrain_instance, we would also have an array of five elements that represent these public inputs. The array's order must match the order of the constrain_instance calls since they will be constrained by their index in the array (which is incremented for every call).

In other words, the vector of public inputs could look like this:

let public_inputs = vec![
    coin,
    *value_coords.x(),
    *value_coords.y(),
    *token_coords.x(),
    *token_coords.y(),
];

And then the Verifier uses these public inputs to verify a given zero knowledge proof.

Coin

During the Mint phase we create a new coin $C$, which is bound to the public key $P$. The coin $C$ is publicly revealed on the blockchain and added to the Merkle tree.

Let $v$ be the coin's value, $t$ be the token ID, $\rho$ be the unique serial number for the coin, and $r_C$ be a random blinding value. We create a commitment (hash) of these elements and produce the coin $C$ in zero-knowledge:

$$C=H(P,v,t,\rho ,r_C)$$

An interesting thing to keep in mind is that this commitment is extensible, so one could fit an arbitrary amount of different attributes inside it.

Value and token commitments

To have some value $v$ for our coin, we ensure it's greater than zero, and then we can create a Pedersen commitment $V$ where $r_V$ is the blinding factor for the commitment, and $G_1$ and $G_2$ are two predefined generators:

$$v>0$$ $$V=v{G}_1+r_V{G}_2$$

The token ID can be thought of as an attribute we append to our coin so we can have a differentiation of assets we are working with. In practice, this allows us to work with different tokens, using the same zero-knowledge proof circuit. For this token ID, we can also build a Pedersen commitment $T$ where $t$ is the token ID, $r_T$ is the blinding factor, and $G_1$ and $G_2$ are predefined generators:

$$T=t{G}_1+r_T{G}_2$$

Pseudo-code

Knowing this we can extend our pseudo-code and build the before-mentioned public inputs for the circuit:

let bincode = include_bytes!("../proof/mint.zk.bin");
let zkbin = ZkBinary::decode(bincode)?;

// ======
// Prover
// ======

// Witness values
let value = 42;
let token_id = pallas::Base::random(&mut OsRng);
let value_blind = pallas::Scalar::random(&mut OsRng);
let token_blind = pallas::Scalar::random(&mut OsRng);
let serial = pallas::Base::random(&mut OsRng);
let coin_blind = pallas::Base::random(&mut OsRng);
let public_key = PublicKey::from_secret(SecretKey::random(&mut OsRng));
let (pub_x, pub_y) = public_key.xy();

let prover_witnesses = vec![
    Witness::Base(Value::known(pub_x)),
    Witness::Base(Value::known(pub_y)),
    Witness::Base(Value::known(pallas::Base::from(value))),
    Witness::Base(Value::known(token_id)),
    Witness::Base(Value::known(serial)),
    Witness::Base(Value::known(coin_blind)),
    Witness::Scalar(Value::known(value_blind)),
    Witness::Scalar(Value::known(token_blind)),
];

// Create the public inputs
let msgs = [pub_x, pub_y, pallas::Base::from(value), token_id, serial, coin_blind];
let coin = poseidon_hash(msgs);

let value_commit = pedersen_commitment_u64(value, value_blind);
let value_coords = value_commit.to_affine().coordinates().unwrap();

let token_commit = pedersen_commitment_base(token_id, token_blind);
let token_coords = token_commit.to_affine().coordinates().unwrap();

let public_inputs = vec![
    coin,
    *value_coords.x(),
    *value_coords.y(),
    *token_coords.x(),
    *token_coords.y(),
];

// Create the circuit
let circuit = ZkCircuit::new(prover_witnesses, zkbin.clone());

let proving_key = ProvingKey::build(13, &circuit);
let proof = Proof::create(&proving_key, &[circuit], &public_inputs, &mut OsRng)?;

// ========
// Verifier
// ========

// Construct empty witnesses
let verifier_witnesses = empty_witnesses(&zkbin);

// Create the circuit
let circuit = ZkCircuit::new(verifier_witnesses, zkbin);

let verifying_key = VerifyingKey::build(13, &circuit);
proof.verify(&verifying_key, &public_inputs)?;

Burn

constant "Burn" {
	EcFixedPointShort VALUE_COMMIT_VALUE,
	EcFixedPoint VALUE_COMMIT_RANDOM,
	EcFixedPointBase NULLIFIER_K,
}

contract "Burn" {
	Base secret,
	Base serial,
	Base value,
	Base token,
	Base coin_blind,
	Scalar value_blind,
	Scalar token_blind,
	Uint32 leaf_pos,
	MerklePath path,
	Base signature_secret,
}

circuit "Burn" {
	# Poseidon hash of the nullifier
	nullifier = poseidon_hash(secret, serial);
	constrain_instance(nullifier);

	# Pedersen commitment for coin's value
	vcv = ec_mul_short(value, VALUE_COMMIT_VALUE);
	vcr = ec_mul(value_blind, VALUE_COMMIT_RANDOM);
	value_commit = ec_add(vcv, vcr);
	# Since value_commit is a curve point, we fetch its coordinates
	# and constrain them:
	value_commit_x = ec_get_x(value_commit);
	value_commit_y = ec_get_y(value_commit);
	constrain_instance(value_commit_x);
	constrain_instance(value_commit_y);

	# Pedersen commitment for coin's token ID
	tcv = ec_mul_base(token, NULLIFIER_K);
	tcr = ec_mul(token_blind, VALUE_COMMIT_RANDOM);
	token_commit = ec_add(tcv, tcr);
	# Since token_commit is also a curve point, we'll do the same
	# coordinate dance:
	token_commit_x = ec_get_x(token_commit);
	token_commit_y = ec_get_y(token_commit);
	constrain_instance(token_commit_x);
	constrain_instance(token_commit_y);

	# Coin hash
	pub = ec_mul_base(secret, NULLIFIER_K);
	pub_x = ec_get_x(pub);
	pub_y = ec_get_y(pub);
	C = poseidon_hash(pub_x, pub_y, value, token, serial, coin_blind);

	# Merkle root
	root = merkle_root(leaf_pos, path, C);
	constrain_instance(root);

	# Finally, we derive a public key for the signature and
	# constrain its coordinates:
	signature_public = ec_mul_base(signature_secret, NULLIFIER_K);
	signature_x = ec_get_x(signature_public);
	signature_y = ec_get_y(signature_public);
	constrain_instance(signature_x);
	constrain_instance(signature_y);

	# At this point we've enforced all of our public inputs.
}

The Burn proof consists of operations similar to the Mint proof, with the addition of a Merkle root² calculation. In the same manner, we are doing a Poseidon hash instance, we're building Pedersen commitments for the value and token ID, and finally we're doing a public key derivation.

In this case, our vector of public inputs could look like:

let public_inputs = vec![
    nullifier,
    *value_coords.x(),
    *value_coords.y(),
    *token_coords.x(),
    *token_coords.y(),
    merkle_root,
    *sig_coords.x(),
    *sig_coords.y(),
];

Nullifier

When we spend the coin, we must ensure that the value of the coin cannot be double spent. We call this the Burn phase. The process relies on a nullifier $N$, which we create using the secret key $x$ for the public key $P$ and a unique random serial $\rho$. Nullifiers are unique per coin and prevent double spending:

$$N=H(x,\rho )$$

Merkle root

We check that the merkle root corresponds to a coin which is in the Merkle tree $R$

$$C=H(P,v,t,\rho ,r_C)$$ $$C\in R$$

Value and token commitments

Just like we calculated these for the Mint proof, we do the same here:

$$v>0$$ $$V=v{G}_1+r_V{G}_2$$ $$T=t{G}_1+r_T{G}_2$$

Public key derivation

We check that the secret key $x$ corresponds to a public key $P$. Usually, we do public key derivation my multiplying our secret key with a genera tor $G$, which results in a public key:

$$P=xG$$

Pseudo-code

Knowing this we can extend our pseudo-code and build the before-mentioned public inputs for the circuit:

let bincode = include_bytes!("../proof/burn.zk.bin");
let zkbin = ZkBinary::decode(bincode)?;

// ======
// Prover
// ======

// Witness values
let value = 42;
let token_id = pallas::Base::random(&mut OsRng);
let value_blind = pallas::Scalar::random(&mut OsRng);
let token_blind = pallas::Scalar::random(&mut OsRng);
let serial = pallas::Base::random(&mut OsRng);
let coin_blind = pallas::Base::random(&mut OsRng);
let secret = SecretKey::random(&mut OsRng);
let sig_secret = SecretKey::random(&mut OsRng);

// Build the coin
let coin2 = {
    let (pub_x, pub_y) = PublicKey::from_secret(secret).xy();
    let messages = [pub_x, pub_y, pallas::Base::from(value), token_id, serial, coin_blind];
    poseidon_hash(messages)
};

// Fill the merkle tree with some random coins that we want to witness,
// and also add the above coin.
let mut tree = BridgeTree::<MerkleNode, 32>::new(100);
let coin0 = pallas::Base::random(&mut OsRng);
let coin1 = pallas::Base::random(&mut OsRng);
let coin3 = pallas::Base::random(&mut OsRng);

tree.append(&MerkleNode::from(coin0));
tree.witness();
tree.append(&MerkleNode::from(coin1));
tree.append(&MerkleNode::from(coin2));
let leaf_pos = tree.witness().unwrap();
tree.append(&MerkleNode::from(coin3));
tree.witness();

let root = tree.root(0).unwrap();
let merkle_path = tree.authentication_path(leaf_pos, &root).unwrap();
let leaf_pos: u64 = leaf_pos.into();

let prover_witnesses = vec![
    Witness::Base(Value::known(secret.inner())),
    Witness::Base(Value::known(serial)),
    Witness::Base(Value::known(pallas::Base::from(value))),
    Witness::Base(Value::known(token_id)),
    Witness::Base(Value::known(coin_blind)),
    Witness::Scalar(Value::known(value_blind)),
    Witness::Scalar(Value::known(token_blind)),
    Witness::Uint32(Value::known(leaf_pos.try_into().unwrap())),
    Witness::MerklePath(Value::known(merkle_path.try_into().unwrap())),
    Witness::Base(Value::known(sig_secret.inner())),
];

// Create the public inputs
let nullifier = Nullifier::from(poseidon_hash::<2>([secret.inner(), serial]));

let value_commit = pedersen_commitment_u64(value, value_blind);
let value_coords = value_commit.to_affine().coordinates().unwrap();

let token_commit = pedersen_commitment_base(token_id, token_blind);
let token_coords = token_commit.to_affine().coordinates().unwrap();

let sig_pubkey = PublicKey::from_secret(sig_secret);
let (sig_x, sig_y) = sig_pubkey.xy();

let merkle_root = tree.root(0).unwrap();

let public_inputs = vec![
    nullifier.inner(),
    *value_coords.x(),
    *value_coords.y(),
    *token_coords.x(),
    *token_coords.y(),
    merkle_root.inner(),
    sig_x,
    sig_y,
];

// Create the circuit
let circuit = ZkCircuit::new(prover_witnesses, zkbin.clone());

let proving_key = ProvingKey::build(13, &circuit);
let proof = Proof::create(&proving_key, &[circuit], &public_inputs, &mut OsRng)?;

// ========
// Verifier
// ========

// Construct empty witnesses
let verifier_witnesses = empty_witnesses(&zkbin);

// Create the circuit
let circuit = ZkCircuit::new(verifier_witnesses, zkbin);

let verifying_key = VerifyingKey::build(13, &circuit);
proof.verify(&verifying_key, &public_inputs)?;

Clients

This section gives information on DarkFi's clients, such as darkfid and cashierd. Currently this section offers documentation on the client's RPC API.

darkfid JSON-RPC API

blockchain methods

• blockchain.get_slot
• blockchain.get_tx
• blockchain.last_known_slot
• blockchain.subscribe_blocks
• blockchain.subscribe_err_txs
• blockchain.lookup_zkas

blockchain.get_slot

Queries the blockchain database for a block in the given slot. Returns a readable block upon success.
^[src]

--> {"jsonrpc": "2.0", "method": "blockchain.get_slot", "params": [0], "id": 1}
<-- {"jsonrpc": "2.0", "result": {...}, "id": 1}

blockchain.get_tx

Queries the blockchain database for a block in the given slot. Returns a readable block upon success.
^[src]

--> {"jsonrpc": "2.0", "method": "blockchain.get_tx", "params": ["TxHash"], "id": 1}
<-- {"jsonrpc": "2.0", "result": {...}, "id": 1}

blockchain.last_known_slot

Queries the blockchain database to find the last known slot
^[src]

--> {"jsonrpc": "2.0", "method": "blockchain.last_known_slot", "params": [], "id": 1}
<-- {"jsonrpc": "2.0", "result": 1234, "id": 1}

blockchain.subscribe_blocks

Initializes a subscription to new incoming blocks. Once a subscription is established, darkfid will send JSON-RPC notifications of new incoming blocks to the subscriber.
^[src]

--> {"jsonrpc": "2.0", "method": "blockchain.subscribe_blocks", "params": [], "id": 1}
<-- {"jsonrpc": "2.0", "method": "blockchain.subscribe_blocks", "params": [`blockinfo`]}

blockchain.subscribe_err_txs

Initializes a subscription to erroneous transactions notifications. Once a subscription is established, darkfid will send JSON-RPC notifications of erroneous transactions to the subscriber.
^[src]

--> {"jsonrpc": "2.0", "method": "blockchain.subscribe_err_txs", "params": [], "id": 1}
<-- {"jsonrpc": "2.0", "method": "blockchain.subscribe_err_txs", "params": [`tx_hash`]}

blockchain.lookup_zkas

Performs a lookup of zkas bincodes for a given contract ID and returns all of them, including their namespace.
^[src]

--> {"jsonrpc": "2.0", "method": "blockchain.lookup_zkas", "params": ["6Ef42L1KLZXBoxBuCDto7coi9DA2D2SRtegNqNU4sd74"], "id": 1}
<-- {"jsonrpc": "2.0", "result": [["Foo", [...]], ["Bar", [...]]], "id": 1}

tx methods

• tx.simulate
• tx.broadcast

tx.simulate

Simulate a network state transition with the given transaction. Returns true if the transaction is valid, otherwise, a corresponding error.
^[src]

--> {"jsonrpc": "2.0", "method": "tx.simulate", "params": ["base58encodedTX"], "id": 1}
<-- {"jsonrpc": "2.0", "result": true, "id": 1}

tx.broadcast

Broadcast a given transaction to the P2P network. The function will first simulate the state transition in order to see if the transaction is actually valid, and in turn it will return an error if this is the case. Otherwise, a transaction ID will be returned.
^[src]

--> {"jsonrpc": "2.0", "method": "tx.broadcast", "params": ["base58encodedTX"], "id": 1}
<-- {"jsonrpc": "2.0", "result": "txID...", "id": 1}

wallet methods

• wallet.query_row_single
• wallet.query_row_multi
• wallet.exec_sql

wallet.query_row_single

Attempts to query for a single row in a given table. The parameters given contain paired metadata so we know how to decode the SQL data. An example of params is as such:

params[0] -> "sql query"
params[1] -> column_type
params[2] -> "column_name"
...
params[n-1] -> column_type
params[n] -> "column_name"

This function will fetch the first row it finds, if any. The column_type field is a type available in the WalletDb API as an enum called QueryType. If a row is not found, the returned result will be a JSON-RPC error. NOTE: This is obviously vulnerable to SQL injection. Open to interesting solutions.
^[src]

--> {"jsonrpc": "2.0", "method": "wallet.query_row_single", "params": [...], "id": 1}
<-- {"jsonrpc": "2.0", "result": ["va", "lu", "es", ...], "id": 1}

wallet.query_row_multi

Attempts to query for all available rows in a given table. The parameters given contain paired metadata so we know how to decode the SQL data. They're the same as above in wallet.query_row_single. If there are any values found, they will be returned in a paired array. If not, an empty array will be returned.
^[src]

--> {"jsonrpc": "2.0", "method": "wallet.query_row_multi", "params": [...], "id": 1}
<-- {"jsonrpc": "2.0", "result": [["va", "lu"], ["es", "es"], ...], "id": 1}

wallet.exec_sql

Executes an arbitrary SQL query on the wallet, and returns true on success. params[1..] can optionally be provided in pairs like in wallet.query_row_single.
^[src]

--> {"jsonrpc": "2.0", "method": "wallet.exec_sql", "params": ["CREATE TABLE ..."], "id": 1}
<-- {"jsonrpc": "2.0", "result": true, "id": 1}

misc methods

• ping
• clock
• get_info
• get_consensus_info

ping

Returns a pong to the ping request.
^[src]

--> {"jsonrpc": "2.0", "method": "ping", "params": [], "id": 1}
<-- {"jsonrpc": "2.0", "result": "pong", "id": 1}

clock

Returns current system clock in Timestamp format.
^[src]

--> {"jsonrpc": "2.0", "method": "clock", "params": [], "id": 1}
<-- {"jsonrpc": "2.0", "result": {...}, "id": 1}

get_info

Returns sync P2P network information.
^[src]

--> {"jsonrpc": "2.0", "method": "get_info", "params": [], "id": 42}
<-- {"jsonrpc": "2.0", result": {"nodeID": [], "nodeinfo": [], "id": 42}

get_consensus_info

Returns consensus P2P network information.
^[src]

--> {"jsonrpc": "2.0", "method": "get_consensus_info", "params": [], "id": 42}
<-- {"jsonrpc": "2.0", result": {"nodeID": [], "nodeinfo": [], "id": 42}

cashierd JSON-RPC API

• deposit
• withdraw
• features

deposit

Executes a deposit request given network and token_id. Returns the address where the deposit shall be transferred to.
^[src]

--> {"jsonrpc": "2.0", "method": "deposit", "params": ["network", "token", "publickey"], "id": 1}
<-- {"jsonrpc": "2.0", "result": "Ht5G1RhkcKnpLVLMhqJc5aqZ4wYUEbxbtZwGCVbgU7DL", "id": 1}

withdraw

Executes a withdraw request given network, token_id, publickey and amount. publickey is supposed to correspond to network. Returns the transaction ID of the processed withdraw.
^[src]

--> {"jsonrpc": "2.0", "method": "withdraw", "params": ["network", "token", "publickey", "amount"], "id": 1}
<-- {"jsonrpc": "2.0", "result": "txID", "id": 1}

features

Returns supported cashier features, like network, listening ports, etc.
^[src]

--> {"jsonrpc": "2.0", "method": "features", "params": [], "id": 1}
<-- {"jsonrpc": "2.0", "result": {"network": ["btc", "sol"]}, "id": 1}

faucetd JSON-RPC API

• airdrop

airdrop

Processes a native token airdrop request and airdrops requested amount to address. Returns the transaction ID upon success. Params: 0: base58 encoded address of the recipient 1: Amount to airdrop in form of f64
^[src]

--> {"jsonrpc": "2.0", "method": "airdrop", "params": ["1DarkFi...", 1.42], "id": 1}
<-- {"jsonrpc": "2.0", "result": "txID", "id": 1}

Hosting anonymous nodes

Using Tor, we can host anonymous nodes as Tor hidden services. To do this, we need to set up our Tor daemon and create a hidden service. The following instructions should work on any Linux system.

1. Install Tor

Tor can usually be installed with your package manager. For example on an apt based system we can run:

# apt install tor

This will install it. Now in /etc/tor/torrc we can set up the hidden service. For hosting an anonymous ircd node, set up the following lines in the file:

HiddenServiceDir /var/lib/tor/darkfi_ircd
HiddenServicePort 25551 127.0.0.1:25551

Then restart Tor:

# /etc/init.d/tor restart

You can grab the hostname of your hidden service from the directory:

# cat /var/lib/tor/darkfi_ircd/hostname

For example purposes, let's assume it's jamie3vkiwibfiwucd6vxijskbhpjdyajmzeor4mc4i7yopvpo4p7cyd.onion.

2. Setup ircd

After compiling ircd, run it once to spawn the config file. Then edit it to contain the following:

inbound = ["tcp://127.0.0.1:25551"]
external_addr = ["tor://jamie3vkiwibfiwucd6vxijskbhpjdyajmzeor4mc4i7yopvpo4p7cyd.onion:25551"]

Now when you start ircd, the hidden service will be announced as a peer and people will be able to connect to it when they discover you as a peer.

These instructions are also applicable to other nodes in the DarkFi ecosystem, e.g. darkfid.

Crypto

Discrete Fast Fourier Transform

Available code files:

• fft2.sage: implementation using vandermonde matrices illustrating the theory section below.
• fft3.sage: simple example with $n=4$ showing 3 steps of the algorithm.
• fft4.sage: illustrates the full working algorithm.

Theory

$$f(x)g(x)\in {\mathbb{F}}_{<2n}[x]$$ $$fg=\sum _{i+j<2n-2}{a}_i{b}_j{x}^{i+j}$$ Complexity: $O(n^2)$

Suppose $\omega \in \mathbb{F}$ is an nth root of unity.

Recall: if $\mathbb{F}={\mathbb{F}}_{p^k}$ then $\exists N:{\mathbb{F}}_{p^N}$ contains all nth roots of unity.

$${\text{DFT}}_{\omega }:{\mathbb{F}}^n\to {\mathbb{F}}^n$$ $${\text{DFT}}_{\omega }(f)=(f({\omega }^0),f({\omega }^1),\dots ,f({\omega }^{n-1}))$$

$$V_{\omega }=\left(\begin{array}{ccccc}1& 1& 1& \cdots & 1\\ 1& {\omega }^1& {\omega }^2& \cdots & {\omega }^{n-1}\\ 1& {\omega }^2& {\omega }^4& \cdots & {\omega }^{2(n-1)}\\ ⋮& & & & \\ 1& {\omega }^{n-1}& {\omega }^{2(n-1)}& \cdots & {\omega }^{(n-1{)}^2}\end{array}\right)$$

$${\text{DFT}}_{\omega }(f)=V_{\omega }\cdot f^T$$ since vandermonde multiplication is simply evaluation of a polynomial.

Lemma: $V_{\omega }^{-1}=\frac{1}{n}{V}_{{\omega }^{-1}}$

Use $1+\omega +\cdots +{\omega }^{n-1}$ and compute $V_{\omega }{V}_{{\omega }^{-1}}$

Corollary: ${\text{DFT}}_{\omega }$ is invertible.

Definitions

1. Convolution $f\ast g=fg\mathrm{mod}(x^n-1)$
2. Pointwise product $$(a_0,\dots ,a_{n-1})\cdot (b_0,\dots ,b_{n-1})=(a_0{b}_0,\dots ,a_{n-1}{b}_{n-1})\in {\mathbb{F}}^n\to {\mathbb{F}}_{<n}[x]$$

Theorem: ${\text{DFT}}_{\omega }(f\ast g)={\text{DFT}}_{\omega }(f)\cdot {\text{DFT}}_{\omega }(g)$

$$fg=q^{\prime }(x^n-1)+f\ast g$$ $$\Rightarrow f\ast g=fg+q(x^n-1)$$ $$\mathrm{deg}fg\le 2n-2$$

$$\begin{array}{rl}(f\ast g)({\omega }^i)& =f({\omega }^i)g({\omega }^i)+q({\omega }^i)({\omega }^{in}-1)\\ & =f({\omega }^i)g({\omega }^i)\end{array}$$

Result

$$f,g\in {\mathbb{F}}_{<n/2}[x]$$ $$fg=f\ast g$$ $${\text{DFT}}_{\omega }(f\ast g)={\text{DFT}}_{\omega }(f)\cdot {\text{DFT}}_{\omega }(g)$$ $$fg=\frac{1}{n}{\text{DFT}}_{{\omega }^{-1}}({\text{DFT}}_{\omega }(f)\cdot {\text{DFT}}_{\omega }(g))$$

Finite Field Extension Containing Nth Roots of Unity

$${\mu }_N=⟨\omega ⟩,|{\mathbb{F}}_{p^N}^{\times }|=p^N-1$$ $$\text{ord}(\omega )=n|p^N-1$$ but ${\mathbb{F}}_{p^N}^{\times }$ is cyclic.

For all $d|p^N-1$, there exists $x\in {\mathbb{F}}_{p^N}^{\times }$ with ord$(x)=d$.

Finding $n|p^N-1$ is sufficient for $\omega \in {\mathbb{F}}_{p^N}$ $$n|p^N-1\iff \text{ord}(p)=(Z/nZ{)}^{\times }$$

FFT Algorithm Recursive Compute

We recurse to a depth of $\log n$. Since each recursion uses ${\omega }^i$, then in the final step ${\omega }^i=1$, and we simply return $f^T$.

We only need to prove a single step of the algorithm produces the desired result, and then the correctness is inductively proven.

$$\begin{array}{rl}f(X)& =a_0+a_{1}X+a_2{X}^2+\cdots +a_{n-1}{X}^{n-1}\\ & =g(X)+X^{n/2}h(X)\end{array}$$

Algorithm

Implementation of this algorithm is available in fft4.sage. Particularly the function called calc_dft().

function DFT($n=2^d,f(X)$)
if $n=1$ then
return $f(X)$
end
Write $f(X)$ as the sum of two polynomials with equal degree
$f(X)=g(X)+X^{n/2}h(X)$
Let $\mathbf{g},\mathbf{h}$ be the vector representations of $g(X),h(X)$

$\mathbf{r}=\mathbf{g}+\mathbf{h}$
$\mathbf{s}=(\mathbf{g}-\mathbf{h})\cdot ({\omega }^0,\dots ,{\omega }^{n/2-1})$
Let $r(X),s(X)$ be the polynomials represented by the vectors $\mathbf{r},\mathbf{s}$

Compute $(r({\omega }^0),\dots ,r({\omega }^{n/2}))={\text{DFT}}_{{\omega }^2}(n/2,r(X))$
Compute $(s({\omega }^0),\dots ,s({\omega }^{n/2}))={\text{DFT}}_{{\omega }^2}(n/2,s(X))$

return $(r({\omega }^0),s({\omega }^0),r({\omega }^2),s({\omega }^2),\dots ,r({\omega }^{n/2}),s({\omega }^{n/2}))$
end

Sage code:

def calc_dft(ω_powers, f):
    m = len(f)
    if m == 1:
        return f
    g, h = vector(f[:m/2]), vector(f[m/2:])

    r = g + h
    s = dot(g - h, ω_powers)

    ω_powers = vector(ω_i for ω_i in ω_powers[::2])
    rT = calc_dft(ω_powers, r)
    sT = calc_dft(ω_powers, s)

    return list(alternate(rT, sT))

Even Values

$$\begin{array}{rl}r(X)& =g(X)+h(X)\\ & \\ f({\omega }^{2i})& =g({\omega }^{2i})+({\omega }^{2i}{)}^{n/2}h({\omega }^{2i})\\ & =g({\omega }^{2i})+h({\omega }^{2i})\\ & =(g+h)({\omega }^{2i})\end{array}$$

So then we can now compute $DF{T}_{\omega }(f{)}_{k=2i}=DF{T}_{{\omega }^2}(r)$ for the even powers of $f({\omega }^{2i})$.

Odd Values

For odd values $k=2i+1$

$$\begin{array}{rl}s(X)& =(g(X)-h(X))\cdot ({\omega }^0,\dots ,{\omega }^{n/2-1})\\ & \\ f(X)& =a_0+a_{1}X+a_2{X}^2+\cdots +a_{n-1}{X}^{n-1}\\ & =g(X)+X^{n/2}h(X)\\ f({\omega }^{2i+1})& =g({\omega }^{2i+1})+({\omega }^{2i+1}{)}^{n/2}h({\omega }^{2i+1})\end{array}$$ But observe that for any $n$th root of unity ${\omega }^n=1$ and ${\omega }^{n/2}=-1$ $$({\omega }^{2i+1}{)}^{n/2}={\omega }^{in}{\omega }^{n/2}={\omega }^{n/2}=-1$$ $$\begin{array}{rl}\Rightarrow f({\omega }^{2i+1})& =g({\omega }^{2i+1})-h({\omega }^{2i+1})\\ & =(g-h)({\omega }^{2i+1})\end{array}$$

Let $\mathbf{s}=(\mathbf{g}-\mathbf{h})\cdot ({\omega }^0,\dots ,{\omega }^{n/2-1})$ be the representation for $s(X)$. Then we can see that $s({\omega }^{2i})=(g-h)({\omega }^{2i+1})$ as desired.

So then we can now compute $DF{T}_{\omega }(f{)}_{k=2i+1}=DF{T}_{{\omega }^2}(s)$ for the odd powers of $f({\omega }^{2i+1})$.

Example

Let $n=8$ $$\begin{array}{rl}f(X)& =(a_0+a_{1}X+a_2{X}^2+a_3{X}^3)+(a_4{X}^4+a_5{X}^5+a_6{X}^6+a_7{X}^7)\\ & =(a_0+a_{1}X+a_2{X}^2+a_3{X}^3)+X^4(a_4+a_{5}X+a_6{X}^2+a_7{X}^3)\\ & =g(X)+X^{n/2}h(X)\\ g(X)& =a_0+a_{1}X+a_2{X}^2+a_3{X}^3\\ h(X)& =a_4+a_{5}X+a_6{X}^2+a_7{X}^3\end{array}$$ Now vectorize $g(X),h(X)$ $$\begin{array}{rl}\mathbf{g}& =(a_0,a_1,a_2,a_3)\\ \mathbf{h}& =(a_4,a_5,a_6,a_7)\end{array}$$ Compute reduced polynomials in vector form $$\begin{array}{rl}\mathbf{r}& =\mathbf{g}+\mathbf{h}\\ & =(a_0+a_4,a_1+a_5,a_2+a_6,a_3+a_7)\\ \mathbf{s}& =(\mathbf{g}-\mathbf{h})\cdot (1,\omega ,{\omega }^2,{\omega }^3)\\ & =(a_0-a_4,a_1-a_5,a_2-a_6,a_3-a_7)\cdot (1,\omega ,{\omega }^2,{\omega }^3)\\ & =(a_0-a_4,\omega (a_1-a_5),{\omega }^2(a_2-a_6),{\omega }^3(a_3-a_7))\end{array}$$ Convert them to polynomials from the vectors. We also expand them out below for completeness. $$\begin{array}{rl}r(X)& =r_0+r_{1}X+r_2{X}^2+r_3{X}^3\\ & =(a_0+a_4)+(a_1+a_5)X+(a_2+a_6)X^2+(a_3+a_7)X^3\\ s(X)& =s_0+s_{1}X+s_2{X}^2+s_3{X}^3\\ & =(a_0-a_4)+\omega (a_1-a_5)X+{\omega }^2(a_2-a_6)X^2+{\omega }^3(a_3-a_7)X^3\end{array}$$ Compute $${\text{DFT}}_{{\omega }^2}(4,r(X)),{\text{DFT}}_{{\omega }^2}(4,s(X))$$ The values returned will be $$(r(1),s(1),r({\omega }^2),s({\omega }^2),r({\omega }^4),s({\omega }^4),r({\omega }^6),s({\omega }^6))=(f(1),f(\omega ),f({\omega }^2),f({\omega }^3),f({\omega }^4),f({\omega }^5),f({\omega }^6),f({\omega }^7))$$ Which is the output we return.