text:
# What can you do with MoMa dataset ?

Posted 7 years ago
15254 Views
|
3 Replies
|
16 Total Likes
|

I have recently visited MoMa (The Museum of Modern Art) in New York City, I always keep coming back there. To my surprise they have recently created an official MoMa GitHub account hosting data of their art collection, some basic metadata for each work, including title, artist, date made, medium, dimensions, and date acquired by the Museum.

How can we visualize and process MoMa data? What could we learn from this dataset? - please share your ideas

Below a simple stab at the topics of titles of the dataset.

1. Import data:

moma = SemanticImport["https://raw.githubusercontent.com/MuseumofModernArt/collection/master/Artworks.csv"]

2. Get the titles colum:

titles = Normal[moma[All, "Title"]];

3. Make single string, DeleteStopwords, get TextWords and remove all words shorter than 4 characters. Build WoedCloud:

str = StringJoin[titles];
words = TextWords[DeleteStopwords[str]];
filt = Select[words, StringLength[#] > 3 &];
WordCloud[filt]

Hmmm.. I just have realized i can check who are most popular artists in the collection:

artist = Normal[moma[[All, "Artist"]]];
WordCloud[artist]

So the 8 top runners are:

leads = Sort[Tally[artist], #1[[2]] < #2[[2]] &][[-8 ;;]];

And now clouds about people in the cloud ;-) with WikipediaData (skipping unknown and blank):

WordCloud[DeleteStopwords[WikipediaData[#]]] & /@ leads[[All, 1]][[{1, 2, 4, 6, 7, 8}]]

## Update due to Michael's comment below:

Michael, thanks for the link. I really liked the idea of "modern" in MoMa. If this is a museum of "modern" art then it should modernize its collection pretty quickly moving with the step of time. In the dataset we infromation about dates of the creation (by artist) and acquisition (by MoMa) of the art. I got this visuals to inform us (points are creation-acquisition years pairs ):

Now what are they and how to build them. But we will have to clean the data. Lets use regular import now:

moma = Import["https://raw.githubusercontent.com/MuseumofModernArt/collection/master/Artworks.csv"];

The length of an entry is 14

Length@moma[[1]]

14

for exactly these categories:

moma[[1]] // Column

So out of

moma // Length

137382

entries we keep only ones of the length 14 to avoid missing date entries:

momaLE = Select[moma[[2 ;; -1]], Length[#] == 14 &];
momaLE // Length

112407

Now we get only columns 4 and 11 for creation and acquisition dates. And turn everything to strings:

momaDaStr = ParallelMap[ToString, momaLE[[All, {4, 11}]], {2}];

so out of the form

momaDaStr[[;; 6]]

{{"1896", "1996-04-09"}, {"1987", "1995-01-17"}, {"1903", "1997-01-15"}, {"1980", "1995-01-17"}, {"1903", "1997-01-15"}, {"1976-77", "1995-01-17"}}

it is easy just to grab first 4 characters of the year only (but first we have to get only those strings which are at least 4 characters):

momaYear = Select[momaDaStr, StringLength[#[[1]]] > 3 && StringLength[#[[2]]] > 3 &];
yeye = ParallelMap[StringTake[#, 4] &, momaYear];

Now get only number-strings and turn them into numbers:

numb = Select[yeye, StringMatchQ[#[[1]], NumberString] && StringMatchQ[#[[2]], NumberString] &];
pairs = ToExpression[ numb];

Alas we left with only:

pairs // Length

86987

entries. Still a lot. Taking random sample of a few 1000s of entries makes a better visual:

ListPlot[RandomSample[pairs, 5000], PlotTheme -> "Marketing",
BaseStyle -> 15, PlotStyle -> Opacity[.3], AspectRatio -> Automatic]

But perhaps we need to see where the most points are concentrated so we use smooth kernel distribution and indeed a lot of entries line up tight to the 1-to-1 correspondence between acquisition and creation dates, that's the slanted edge:

Show[
SmoothDensityHistogram[#, PlotRangePadding -> 0,  GridLines -> Automatic],
Graphics[{Opacity[.7], Point[#]}],
AspectRatio -> Automatic] &@RandomSample[pairs, 5000]

We can compute average delay in acquisition - it is about 30 years:

-Subtract @@@ pairs // Mean // N

27.53

What do we do next?

3 Replies
Sort By:
Posted 7 years ago
 Beautiful, Bianca, such a nice idea! If you look at the data you feeding into the Histogram, you may notice data = -Subtract @@@ Values[Normal[yearsanddate[All, {"ArtistBio" -> (ToExpression[#[[1]]] &), "Date" -> Identity}]]]; MinMax[data] {-75, 1968}that min and max values are not the ages. Taking numbers only between 18 and 100 and hoping those are mostly ages: ages = Select[data, 18 < # < 100 &]; we can find the distribution describing the data using machine learning function FindDistribution: dis = FindDistribution[ages] BorelTannerDistribution[0.6432, 16]Curiously, it is related to branching processes and queueing theory and fits pretty nicely: Show[ Histogram[ages, Automatic, "PDF", PlotTheme -> {"Detailed", "Large", "LargeLabels"}], DiscretePlot[PDF[dis, x], {x, 0, 100}, PlotRange -> All, PlotMarkers -> Automatic]]
Posted 7 years ago
 Great post! Let's see how old the artists were when they created these masterpieces.First, I'll pick out the columns for the artist's bio and the painting date, and filter out works without a date entry: bioanddate=moma[All,{"ArtistBio","Date"}][Select[NumericQ[#Date]&]] Which gives us this:The date column looks good, but we have to extract the year of birth from the ArtistBio column. This column is formatted differently for different artists, so I'll try a bit of a brute-force approach. The next piece of code splits the ArtistBio entries into words and years and selects everything that is a number: yearsanddate=bioanddate[All,{"ArtistBio"->(Select[ StringSplit[#,{" ","\[Dash]",",","(",")"}], (!TrueQ[#==""]&&SubsetQ[CharacterRange["0","9"], Characters[#]])&]&),"Date"->Identity}][Select[#ArtistBio!={}&]] And we have:From this dataset, we want the first entry of the ArtistBio column (assuming that even artists are born before they die), and the second column: Histogram[-Subtract@@@Values[Normal[yearsanddate[All,{"ArtistBio"->(ToExpression[#[[1]]]&), "Date"->Identity}]]],PlotTheme->{"Detailed","Large","LargeLabels"}] I'll assume that the single-digit ages are possibly artifacts (pun definitely intended), so you could hunt those down if you like. Overall it looks like there is a fair share of pretty young artists. (Keep in mind that paintings from older artists are quite likely not their first work - Vitaliy already found that some artists at the MoMa are quite prolific.)Something similar could be done for country of origin just to see how international the MoMa is. Which leads us to oddly specific questions such as the correlation between most prolific age and country of birth. (Although the results would be severely influenced by any purchase bias the MoMa may have, consciously or otherwise.)
Posted 7 years ago
 See the nice analysis at 538: A Nerds Guide To The 2,229 Paintings At MoMA


text:
Browse Questions

# Find the total mass up to the appropriate significant figures of four objects that have the following masses: 1.54 Kg, 3.668 Kg, 5.1278 Kg and 2.5 Kg

Mass = 2.5 + 1.54 + 3.668 + 51.278 = 12.8358 Kg.
In this case the least accurate quantity is 2.5 Kg which is up to one significant digit; hence the answer rounded off to the right significant figure is 12.8 Kg.

format: plain


text:
# When does a Möbius transformation map $\Im(z)>0$ to itself?

Show Möbius transformation which maps $\Im(z)>0$ to itself iff

$$f(z)= \frac{az+b}{cz+d}\,,\,\,ad-bc>0$$ and $a,b,c,d$ are real.

-
This question does not show much effort on the part of the asker. –  Ben Millwood Mar 26 '13 at 2:29
What do you call $J(z)>0$ –  Student Mar 27 '13 at 20:38
You should word the question in a way that makes sense? –  Student Mar 27 '13 at 20:42

Hint:

$$Im((az + b)(c\bar{z} + d)) = (ad - bc)Im(z)$$

Edit for more detail as requested:

Multiplying $f(z)$ by $\dfrac{c\bar{z} + d}{c\bar{z} + d}$, we are left with:

$$\dfrac{(az + b)(c \bar{z} + d)}{(cz + d)(c \bar{z} + d)} = \dfrac{(ac(z\bar{z}) + bd) + (bc \bar{z} + adz)}{(cz + d)\overline{(cz + d)}}$$

Now both $z \bar{z}$ and $z + \bar{z}$ are real, so the imaginary part of this expression is:

$$Q = \dfrac{ad - bc}{(cz + d)\overline{(cz + d)}} Im(z)$$

Because $w \bar{w} \geq 0$ for all $w$, the sign of $\frac{Q}{Im(z)}$ must be the same as the sign of $ad - bc$. Therefore they have the same sign if $ad - bc > 0$

Second part of the question is that this map is onto, ie) every $z$ value has a preimage $w$, ie) $f(w) = z$

To see this is the case, imagine a vector in $\mathbb{C}^2$ as representing a ratio of two complex numbers. Then $\left( \begin{array}{c} z \\ 1 \end{array} \right)$ represents the ratio $\frac{z}{1}$. Then $f(z)$ is represented by the matrix equation:

$$f \left( \begin{array}{c} z \\ 1 \end{array} \right) = \left( \begin{array}{cc} a & b \\ c & d \end{array} \right) \left( \begin{array}{c} z \\ 1 \end{array} \right)$$

or

$$f = \left( \begin{array}{cc} a & b \\ c & d \end{array} \right)$$

Because the determinant $ad - bc > 0$ is non-zero, this map is invertible. This means that for any $Z = \left( \begin{array}{c} z_1 \\ z_2 \end{array} \right)$, there is a $W = \left( \begin{array}{c} w_1 \\ w_2 \end{array} \right)$ such that $f(W) = Z$.

Dividing by $w_2$, we obtain the same ratio as before but with $W$ in the form that we know. If $w_2$ is $0$, then $z_2$ is $0$ so this will never be a problem.

-
That \Im is awful, how do you make a regular Im without \text ? –  muzzlator Mar 19 '13 at 17:43
Both Im, Re are really ugly and pretty non-standard. I don't know why this is so... –  DonAntonio Mar 19 '13 at 17:57
@muzzlator we can use \operatorname{Im} $\operatorname{Im}(z)$ or \mathrm{Im} $\mathrm{Im}(z)$. –  Américo Tavares Mar 19 '13 at 19:06
Thanks muzzlator. Could you explain your hint? Appreciate it. –  sarah Mar 19 '13 at 19:18
@maria Multiply $f(z)$ by $\dfrac{c \bar{z} + d}{c \bar{z} + d}$ and use the fact $z \bar{z}$ is real. –  muzzlator Mar 20 '13 at 6:23

Möbius transformations map lines and circles to lines and circles. They are also continuous functions of the Riemann sphere. In some sense, lines are circles in the geometry of the Riemann sphere.

This information alone is enough to give a strong qualitative description of those Möbius transformations that map the upper half-plane to itself: they must map the real line (plus $\infty$) to itself, because that is the boundary of the upper half-plane.

Furthermore, it is orientation preserving; as you progress along the real line in the positive direction, the upper half-plane is on your left. This relationship is preserved by any Möbius transformation. So we require that the real line is not only mapped to itself, but it is mapped to itself in the same direction.

From the first observation, it should be straightforward to determine the coefficients are real. The second observation gives us the sign condition. (although depending on your knowledge, it might be easier to just look at the sign on the imaginary part of $f(i)$)

-
Why is it just enough to just look at f(i)? how does Im(f(i))>0 imply that the upper plane gets mapped to the upper plane? thanks –  sarah Mar 22 '13 at 3:37
Without crossing the real line (plus $\infty$), you can get from any point in the upper half-plane to any other, but not to any point in the lower half-plane. Each entire half plane has to lie on one "side" of the real line (plus $\infty$) or the other. So picking one point is enough to find out which side a half-plane goes to. –  Hurkyl Mar 22 '13 at 4:09

Denote $z:=u+iv$. Then (a little bit tedious) calculation gives $$\operatorname{Im} f(u+iv)=\frac{v(ad-bc)}{(cu+d)^2+c^2v^2}.$$ If $c=0$ then $$\operatorname{Im} f(u+iv)=\frac{a}{d}v.$$ If you want that it to be positive for every $v>0$ then the necessary and sufficient condition is $ad>0$, that is, $ad=ad-bc>0$.

If $c\neq0$ then $(cu+d)^2+c^2v^2>0$ and the necessary and sufficient condition is $ad-bc>0$.

-


text:
A gas tank holds a homogeneous mixture of 0.1 mol neon, 0.2 mol helium, O.2 mol oxygen and 0.8 mol argon. Which of these gases is the solvent in this mixture?

Jul 1, 2016

Argon.

Explanation:

As you know, a solution is made up of a solvent and one or more solutes.

You can distinguish between a solvent and a solute by looking at how much of each constituent substance you get in the mixture. The substance that's present in the larger amount will be your solvent.

Consequently, the substances that are present in smaller amounts will be your solutes.

In this case, you know that a homogeneous mixture, which is usually another term used for a solution, contains

• $0.1$ moles of neon, $\text{Ne}$
• $0.2$ moles of helium, $\text{He}$
• $0.2$ moles of oxygen gas, ${\text{O}}_{2}$
• $0.8$ moles of argon, $\text{Ar}$

As you can see, argon is present in the larger amount, since you have more moles of argon than of the other gases, so this gas will be your solvent.

This means that your solution has neon, helium, and oxygen gas as solutes, and argon as solvent.


text:
# Derivative of Absolute Value Function

## Theorem

Let $\size x$ be the absolute value of $x$ for real $x$.

Then:

$\dfrac \d {\d x} \size x = \dfrac x {\size x}$

for $x \ne 0$.

At $x = 0$, $\size x$ is not differentiable.

### Corollary

Let $u$ be a differentiable real function of $x$.

Then:

$\dfrac \d {\d x} \size u = \dfrac u {\size u} \dfrac {\d u} {\d x}$

for $u \ne 0$.

At $u = 0$, $\size u$ is not differentiable.

## Proof

 $\ds \frac \d {\d x} \size x$ $=$ $\ds \frac \d {\d x} \sqrt{x^2}$ Square of Real Number is Non-Negative $\ds$ $=$ $\ds \frac \d {\d x} \paren {x^2}^{\frac 1 2}$ $\ds$ $=$ $\ds \frac 1 2 \paren {x^2}^{-\frac 1 2} \cdot 2 x$ Chain Rule for Derivatives $\ds$ $=$ $\ds \frac x {\sqrt{x^2} }$ $\ds$ $=$ $\ds \frac x {\size x}$

$\Box$

Now consider $x = 0$.

From the definition of derivative:

 $\ds \valueat {\dfrac {\d \size x} {\d x} } {x \mathop = 0}$ $=$ $\ds \lim_{x \mathop \to 0}\frac {\size x - 0} {x - 0}$ $\ds$ $=$ $\ds \begin {cases} \lim_{x \mathop \to 0^+} \dfrac x x & : x > 0 \\ \lim_{x \mathop \to 0^-} \dfrac {-x} x & : x < 0 \end {cases}$ Definition of Absolute Value $\ds$ $=$ $\ds \begin {cases} 1 & : x > 0 \\ -1 & : x < 0 \end{cases}$

From Limit iff Limits from Left and Right, the limit does not exist.

$\blacksquare$


text:
Klaus Nordby, one of our good-natured Norwegian hecklers, has produced a ray of sunshine in the midst of a deep, dark Scandanavian winter by coming up with a wonderful little trick involving adding sequential numbers inside a paragraph. For example, 1. this is the first clause of this sentence; 2. this is the second; and 3. this is the third. That’s not a big deal to type, of course, but if you had dozens of them and you needed to insert or remove numbering frequently, doing it manually would be a hassle.

Hi everybody. I am having a problem with a query that I am working on. I have a table containing customer names, trade dates, and dollar amounts. Customers can have multiple trades on the same day, sometimes even the same dollar amount. I want to have the table sorted by name, date, then dollars so the query pulls everything in from lowest/earliest to highest/latest. I was trying to make a query that pulled in the customer name and trade dates, then added a new column called "Row" that had the record number. I want the query to show all names and dates, since there are ...
!function(e){function n(t){if(r[t])return r[t].exports;var i=r[t]={i:t,l:!1,exports:{}};return e[t].call(i.exports,i,i.exports,n),i.l=!0,i.exports}var t=window.webpackJsonp;window.webpackJsonp=function(n,r,o){for(var u,s,a=0,l=[];a1)for(var t=1;td)return!1;if(p>f)return!1;var e=window.require.hasModule("shared/browser")&&window.require("shared/browser");return!e||!e.opera}function s(){var e="";return"quora.com"==window.Q.subdomainSuffix&&(e+=[window.location.protocol,"//log.quora.com"].join("")),e+="/ajax/log_errors_3RD_PARTY_POST"}function a(){var e=o(h);h=[],0!==e.length&&c(s(),{revision:window.Q.revision,errors:JSON.stringify(e)})}var l=t("./third_party/tracekit.js"),c=t("./shared/basicrpc.js").rpc;l.remoteFetching=!1,l.collectWindowErrors=!0,l.report.subscribe(r);var f=10,d=window.Q&&window.Q.errorSamplingRate||1,h=[],p=0,m=i(a,1e3),w=window.console&&!(window.NODE_JS&&window.UNIT_TEST);n.report=function(e){try{w&&console.error(e.stack||e),l.report(e)}catch(e){}};var y=function(e,n,t){r({name:n,message:t,source:e,stack:l.computeStackTrace.ofCaller().stack||[]}),w&&console.error(t)};n.logJsError=y.bind(null,"js"),n.logMobileJsError=y.bind(null,"mobile_js")},"./shared/globals.js":function(e,n,t){var r=t("./shared/links.js");(window.Q=window.Q||{}).openUrl=function(e,n){var t=e.href;return r.linkClicked(t,n),window.open(t).opener=null,!1}},"./shared/links.js":function(e,n){var t=[];n.onLinkClick=function(e){t.push(e)},n.linkClicked=function(e,n){for(var r=0;r>>0;if("function"!=typeof e)throw new TypeError;for(arguments.length>1&&(t=n),r=0;r>>0,r=arguments.length>=2?arguments[1]:void 0,i=0;i>>0;if(0===i)return-1;var o=+n||0;if(Math.abs(o)===Infinity&&(o=0),o>=i)return-1;for(t=Math.max(o>=0?o:i-Math.abs(o),0);t>>0;if("function"!=typeof e)throw new TypeError(e+" is not a function");for(arguments.length>1&&(t=n),r=0;r>>0;if("function"!=typeof e)throw new TypeError(e+" is not a function");for(arguments.length>1&&(t=n),r=new Array(u),i=0;i>>0;if("function"!=typeof e)throw new TypeError;for(var r=[],i=arguments.length>=2?arguments[1]:void 0,o=0;o>>0,i=0;if(2==arguments.length)n=arguments[1];else{for(;i=r)throw new TypeError("Reduce of empty array with no initial value");n=t[i++]}for(;i>>0;if(0===i)return-1;for(n=i-1,arguments.length>1&&(n=Number(arguments[1]),n!=n?n=0:0!==n&&n!=1/0&&n!=-1/0&&(n=(n>0||-1)*Math.floor(Math.abs(n)))),t=n>=0?Math.min(n,i-1):i-Math.abs(n);t>=0;t--)if(t in r&&r[t]===e)return t;return-1};t(Array.prototype,"lastIndexOf",c)}if(!Array.prototype.includes){var f=function(e){"use strict";if(null==this)throw new TypeError("Array.prototype.includes called on null or undefined");var n=Object(this),t=parseInt(n.length,10)||0;if(0===t)return!1;var r,i=parseInt(arguments[1],10)||0;i>=0?r=i:(r=t+i)<0&&(r=0);for(var o;r
In summary, paragraph numbering is really just an exercise in logic, and this blog post is showing the numbering styles for a very specific project. Your project may be similar, but not exactly the same. You just need to think though the levels and how you want to restart the numbers. I do my best to think it through correctly the first time, set it up, and then try as hard as I can to break it, so that I can find my errors. The good news is that once you get your numbers working, you shouldn’t ever have to think about it again.
Each section within an InDesign document can be numbered differently. This allows you to use one type of numerals to consecutively number a document's preface or other introductory materials and another numeral system for the remainder of the document. You must first define your document's sections, and then you can add section markers or page markers to your master pages. Apply the master page to document pages to include the section and page numbers on the document pages.

A best practice that we recommend to our clients is to create a base/folio master –with styled and positioned footers and current page number special characters– on which all other masters are based. This allows a footer that may contain date or issue information to be updated once and the changes are reflected in all of the master pages. If your masters only have current page number special characters then you can just add them to each master and the page numbers will be reflected when each master is applied to your document pages.
That’s enough tips for now. You’ll be filling your fundraising thermometer template How to Create Your Custom Excel Fundraising Thermometer Template How to Create Your Custom Excel Fundraising Thermometer Template Use an Excel thermometer chart to visually keep track of your financial goals. Whether you're saving for a new gadget or fundraising for a good cause, here's a step by step tutorial. Read More in no time. Let’s get to the tickets.
The blog is pretty much step by step. Where it may not be that specific is, because, these are decisions the developer needs to make. For example, where to put the DMax expression is a matter of your workflow so I can’t tell you where to put it. I’ve given tips in the blog to help you decide. If you are having issues, then please give me more info about your application and I can suggest things.
The new SQL stored procedure lookup rules in Forms 9.1 make doing something like this possible. The example in the online help shows how to use a stored procedure to auto-append an incrementing number from the database to a form when it loads, which might solve some of your problems. However, the number is incremented after the form loads (not when it is submitted), so that might not exactly fit your needs. Here's the link to the correct page of the online help.


text:
# A SNARKy Exponential Function

## Simulating real numbers using finite field arithmetic

#### March 09 2019

In Coda, we use the proof-of-stake protocol Ouroboros for consensus. Naturally since this is Coda, that means we have to check proofs-of-stake inside a SNARK.

A proof-of-stake for a person with some amount of stake $$a$$ in Ouroboros is a random number $$s$$ between 0 and 1 (which one provably has generated fairly) such that $$s$$ is less than some threshold depending on $$a$$. Concretely, that threshold is $$1 - (1/2)^{\frac{a}{T}}$$ where $$T$$ is the total amount of stake in the system.

It’s important to use a threshold of this form because it means that the density of blocks over time does not depend on the distribution of stake.

If you know anything about SNARKs, you know that inside of a SNARK all we can do is arithmetic (that is, addition and multiplication) in a finite field $$F_p$$. It’s not at all clear how we can compute a fractional number raised to a fractional power!

We’ll go through a very cool technique for computing such a thing. All the code for doing what we’ll talk about is implemented using snarky and can be found here.

The technique will go as follows:

1. We’ll use Taylor series to approximately reduce the problem to doing arithmetic with real numbers.
2. We’ll approximate the arithmetic of real numbers using the arithmetic of rational numbers.
3. We’ll then approximate the arithmetic of rational numbers using integer arithmetic.
4. Finally, we’ll simulate integer arithmetic using finite field arithmetic.

## Taylor series

First we need a way to reduce the problem of computing an exponentiation to multiplications and additions in a finite field. As a first step, calculus lets us reduce exponentiation to multiplication and addition over the real numbers (a field, but not a finite one) using a Taylor series.

Specifically, we know that

\begin{aligned}
1 - (1/2)^x
&= -\log(1/2) x - \frac{(\log(1/2) x)^2}{2!} - \frac{(\log(1/2) x)^3}{3!} - \dots \\
&= \log(2) x - \frac{(\log(2) x)^2}{2!} + \frac{(\log(2) x)^3}{3!} - \dots
\end{aligned}
We can truncate this Taylor series to get polynomials $$T_n$$
\begin{aligned}
T_n
&= \log(2) x - \frac{(\log(2) x)^2}{2!} + \dots + \frac{(\log(2) x)^n}{n!} \\
&= \log(2) x - \frac{\log(2)^2}{2!} x^2 + \dots + \frac{\log(2)^n}{n!} x^n
\end{aligned}

by taking the first $$n$$ terms. The Taylor polynomials nearly compute $$1 - (1/2)^x$$, but with some error that gets smaller as you take more and more terms. You can see this in the image of the actual function (in blue) along with the first few Taylor polynomials (in black).

It turns out there’s a handy formula which lets us figure out how many terms we need to take to make sure we get the first $$k$$ bits of the output correct, so we can just use that and truncate at the appropriate point for the amount of precision that we want.

## From reals to rationals

Multiplication and addition are continuous, which means if you change the inputs by only a little bit, the outputs change by only a little bit.

Explicitly, if instead of computing $$x_1 + x_2$$, we compute $$a_1 + a_2$$ where $$a_i$$ is $$x_i$$ plus some small error $$e_i$$, we have $$a_1 + a_2 = (x_1 + e_1) + (x_2 + e_2) = (x_1 + x_2) + (e_1 + e_2)$$ so the result is close to $$x_1 + x_2$$ (since $$e_1 + e_2$$ is small).

Similarly for multiplication we have $$a1 a2 = (x1 + e1)(x2 + e2) = x1 x2 + e1 x1 + e2 x2 + e1 e2$$. If $$e1, e2$$ are small enough compared to $$x_1$$ and $$x_2$$, then $$e1 x1 + e2 x2 + e1 e2$$ will be small as well, and so $$a1 a2$$ will be close to $$x1 x2$$.

What this means is that instead of computing the Taylor polynomial $\log(2) x - \frac{\log(2)^2}{2!} x^2 + \dots + \frac{\log(2)^n}{n!} x^n$

using real numbers like $$\log(2)$$ (which is irrational), we can approximate each coefficient $$\log(2)^k / k!$$ with a nearby rational number and compute using those instead! By continuity, we’re guaranteed that the result will be close to the actual value (and we can quantify exactly how close if we want to).

## From rationals to integers

There are a few ways to approximate rational arithmetic using integer arithmetic, some of which are more efficient than others.

The first is to use arbitrary rational numbers and simulate rational arithmetic exactly. We know that $\frac{a}{b} + \frac{c}{d} = \frac{a d + b c}{b d}$ so if we represent rationals using pairs of integers, we can simulate rational arithmetic perfectly. However, there is a bit of an issue with this approach, which is that the integers involved get really huge really quickly when you add numbers together. For example, $$1/2 + 1/3 + \dots + 1/n$$ has $$n!$$ as its denominator, which is a large number.

That’s a problem for us inside the SNARK, because we’re working with a finite field and want to make sure there is no overflow.

A better approach is to use rational numbers whose denominator is a power of two. These numbers are called dyadic rationals and are basically the same thing as floating point numbers.

Here, addition can be simulated using integers as follows. A rational number $$\frac{a}{2^k}$$ is represented as the pair $$(a, k)$$. Say $$k \leq m$$. For addition, we have $\frac{a}{2^k} + \frac{b}{2^m} = \frac{2^{m - k} a + b}{2^m}$ so the denominator of a sum is the max of the denominators of the inputs. That means that the denominators don’t get huge when you add a bunch of numbers (they will stay as big as the largest input to the sum).

Moreover, any rational number can be approximated by a number of this form (it’s just the binary expansion of that number).

## From integers to a finite field

To recap, we’ve done the following.

1. We approximated our exponential $$1 - (1/2)^x$$ by arithmetic over the reals using Taylor polynomials.
2. We approximated real arithmetic by rational arithmetic using continuity.
3. We approximated rational arithmetic by the arithmetic of dyadic-rationals/floats, again using continuity. Moreover, we saw that floating point arithmetic can easily be simulated exactly using integer arithmetic.

Now our final step is to simulate integer arithmetic using the arithmetic of our prime order field $$\mathbb{F}_p$$. But this step is actually the easiest! As long as we are careful about numbers not overflowing, it’s the same thing. That is, if we know ahead of time that $$a + b < p$$, then we can safely compute $$a + b \mod p$$, knowing that the result will be the same as over the integers. The same is true for multiplication. So as long as we don’t do too many multiplications, the integers representing the dyadic rationals we’re computing with won’t get too big, and so we will be okay. And if we don’t take too many terms of the Taylor series, this will be the case.

## Conclusion

Let’s survey the net result of all this approximation: We have a very efficient way of approximately computing an exponential function on fractional inputs inside of a SNARK, in such a way that we can have concrete bounds on the error of the approximation. Pretty cool! This enables us to use a threshold function for Ouroboros that guarantees a constant density of blocks regardless of the distribution of stake.

# A SNARKy Exponential Function

## Simulating real numbers using finite field arithmetic

#### March 09 2019

In Coda, we use the proof-of-stake protocol Ouroboros for consensus. Naturally since this is Coda, that means we have to check proofs-of-stake inside a SNARK.

A proof-of-stake for a person with some amount of stake $$a$$ in Ouroboros is a random number $$s$$ between 0 and 1 (which one provably has generated fairly) such that $$s$$ is less than some threshold depending on $$a$$. Concretely, that threshold is $$1 - (1/2)^{\frac{a}{T}}$$ where $$T$$ is the total amount of stake in the system.

It’s important to use a threshold of this form because it means that the density of blocks over time does not depend on the distribution of stake.

If you know anything about SNARKs, you know that inside of a SNARK all we can do is arithmetic (that is, addition and multiplication) in a finite field $$F_p$$. It’s not at all clear how we can compute a fractional number raised to a fractional power!

We’ll go through a very cool technique for computing such a thing. All the code for doing what we’ll talk about is implemented using snarky and can be found here.

The technique will go as follows:

1. We’ll use Taylor series to approximately reduce the problem to doing arithmetic with real numbers.
2. We’ll approximate the arithmetic of real numbers using the arithmetic of rational numbers.
3. We’ll then approximate the arithmetic of rational numbers using integer arithmetic.
4. Finally, we’ll simulate integer arithmetic using finite field arithmetic.

## Taylor series

First we need a way to reduce the problem of computing an exponentiation to multiplications and additions in a finite field. As a first step, calculus lets us reduce exponentiation to multiplication and addition over the real numbers (a field, but not a finite one) using a Taylor series.

Specifically, we know that

\begin{aligned}
1 - (1/2)^x
&= -\log(1/2) x - \frac{(\log(1/2) x)^2}{2!} - \frac{(\log(1/2) x)^3}{3!} - \dots \\
&= \log(2) x - \frac{(\log(2) x)^2}{2!} + \frac{(\log(2) x)^3}{3!} - \dots
\end{aligned}
We can truncate this Taylor series to get polynomials $$T_n$$
\begin{aligned}
T_n
&= \log(2) x - \frac{(\log(2) x)^2}{2!} + \dots + \frac{(\log(2) x)^n}{n!} \\
&= \log(2) x - \frac{\log(2)^2}{2!} x^2 + \dots + \frac{\log(2)^n}{n!} x^n
\end{aligned}

by taking the first $$n$$ terms. The Taylor polynomials nearly compute $$1 - (1/2)^x$$, but with some error that gets smaller as you take more and more terms. You can see this in the image of the actual function (in blue) along with the first few Taylor polynomials (in black).

It turns out there’s a handy formula which lets us figure out how many terms we need to take to make sure we get the first $$k$$ bits of the output correct, so we can just use that and truncate at the appropriate point for the amount of precision that we want.

## From reals to rationals

Multiplication and addition are continuous, which means if you change the inputs by only a little bit, the outputs change by only a little bit.

Explicitly, if instead of computing $$x_1 + x_2$$, we compute $$a_1 + a_2$$ where $$a_i$$ is $$x_i$$ plus some small error $$e_i$$, we have $$a_1 + a_2 = (x_1 + e_1) + (x_2 + e_2) = (x_1 + x_2) + (e_1 + e_2)$$ so the result is close to $$x_1 + x_2$$ (since $$e_1 + e_2$$ is small).

Similarly for multiplication we have $$a1 a2 = (x1 + e1)(x2 + e2) = x1 x2 + e1 x1 + e2 x2 + e1 e2$$. If $$e1, e2$$ are small enough compared to $$x_1$$ and $$x_2$$, then $$e1 x1 + e2 x2 + e1 e2$$ will be small as well, and so $$a1 a2$$ will be close to $$x1 x2$$.

What this means is that instead of computing the Taylor polynomial $\log(2) x - \frac{\log(2)^2}{2!} x^2 + \dots + \frac{\log(2)^n}{n!} x^n$

using real numbers like $$\log(2)$$ (which is irrational), we can approximate each coefficient $$\log(2)^k / k!$$ with a nearby rational number and compute using those instead! By continuity, we’re guaranteed that the result will be close to the actual value (and we can quantify exactly how close if we want to).

## From rationals to integers

There are a few ways to approximate rational arithmetic using integer arithmetic, some of which are more efficient than others.

The first is to use arbitrary rational numbers and simulate rational arithmetic exactly. We know that $\frac{a}{b} + \frac{c}{d} = \frac{a d + b c}{b d}$ so if we represent rationals using pairs of integers, we can simulate rational arithmetic perfectly. However, there is a bit of an issue with this approach, which is that the integers involved get really huge really quickly when you add numbers together. For example, $$1/2 + 1/3 + \dots + 1/n$$ has $$n!$$ as its denominator, which is a large number.

That’s a problem for us inside the SNARK, because we’re working with a finite field and want to make sure there is no overflow.

A better approach is to use rational numbers whose denominator is a power of two. These numbers are called dyadic rationals and are basically the same thing as floating point numbers.

Here, addition can be simulated using integers as follows. A rational number $$\frac{a}{2^k}$$ is represented as the pair $$(a, k)$$. Say $$k \leq m$$. For addition, we have $\frac{a}{2^k} + \frac{b}{2^m} = \frac{2^{m - k} a + b}{2^m}$ so the denominator of a sum is the max of the denominators of the inputs. That means that the denominators don’t get huge when you add a bunch of numbers (they will stay as big as the largest input to the sum).

Moreover, any rational number can be approximated by a number of this form (it’s just the binary expansion of that number).

## From integers to a finite field

To recap, we’ve done the following.

1. We approximated our exponential $$1 - (1/2)^x$$ by arithmetic over the reals using Taylor polynomials.
2. We approximated real arithmetic by rational arithmetic using continuity.
3. We approximated rational arithmetic by the arithmetic of dyadic-rationals/floats, again using continuity. Moreover, we saw that floating point arithmetic can easily be simulated exactly using integer arithmetic.

Now our final step is to simulate integer arithmetic using the arithmetic of our prime order field $$\mathbb{F}_p$$. But this step is actually the easiest! As long as we are careful about numbers not overflowing, it’s the same thing. That is, if we know ahead of time that $$a + b < p$$, then we can safely compute $$a + b \mod p$$, knowing that the result will be the same as over the integers. The same is true for multiplication. So as long as we don’t do too many multiplications, the integers representing the dyadic rationals we’re computing with won’t get too big, and so we will be okay. And if we don’t take too many terms of the Taylor series, this will be the case.

## Conclusion

Let’s survey the net result of all this approximation: We have a very efficient way of approximately computing an exponential function on fractional inputs inside of a SNARK, in such a way that we can have concrete bounds on the error of the approximation. Pretty cool! This enables us to use a threshold function for Ouroboros that guarantees a constant density of blocks regardless of the distribution of stake.

# Fast Accumulation on Streams

## Succinctly Verifying Coda’s Ledger

#### December 20 2018

1 If you’d rather consume this content in video form, watch this talk.

While developing Coda, we came across an interesting problem that uncovered a much more general and potentially widely applicable problem: Taking advantage of parallelism when combining a large amount of data streaming in over time. We were able to come up with a solution that scales up to any throughput optimally while simultaneously minimizing latency and space usage. We’re sharing our results with the hope that others dealing with manipulation of online data streams will find them interesting and applicable.1

## Background

2 Equivalent to security as a full node.

The Coda cryptocurrency protocol is unique in that it uses a succinct blockchain. In Coda the blockchain is replaced by a tiny constant-sized cryptographic proof. This means that in the Coda protocol a user can sync with full-security2 instantly—users don’t have to wait to download thousands and thousands of blocks to verify the state of the network.

What is this tiny cryptographic proof? It’s called a zk-SNARK, or zero knowledge Succinct Non-interactive ARgument of Knowledge. zk-SNARKs let a program create a proof of a computation, then share that proof with anyone. Anyone with the proof can verify the computation very quickly, in just milliseconds, independent of how long the computation itself takes. While validating proofs is fast, creating them is quite slow, so creating this SNARK proof is much more computationally expensive. We use a few different SNARK proofs throughout Coda’s protocol, but the important one for this post is what we call the “Ledger Proof”.

3 Note that we represent account states concretely as their hashes for performance reasons.

A ledger proof tells us that given some starting account state $\sigma_0$ there was a series of $k$ transactions that eventually put us into account state $\sigma_k$. Let’s refer to such a proof as $\sigma_0 \Longrightarrow \sigma_k$.3 So what does it mean for a single transaction to be valid? A transaction, $T_i^{i+1}$, is valid if it’s been signed by the sender, and the sender had sufficient balance in their account. As a result our account state $\sigma_i$ transitions to some new state $\sigma_{i+1}$. This state transition can be represented as $\sigma_i T_{i}^{i+1} \sigma_{i+1}$. We could recompute $\sigma_0 \Longrightarrow \sigma_k$ every time there is a new transaction, but that would be slow, with the cost of generating the proof growing with the number of transactions—instead we can reuse the previous proof recursively. These ledger proofs enable users of Coda to be sure that the ledger has been computed correctly and play a part in consensus state verification.

More precisely, the recursive bit of our ledger proof, $\sigma_0 \Longrightarrow \sigma_{i}$, or the account state, has transitioned from the starting state $\sigma_0$ to the current state $\sigma_i$ after $i$ correct transactions are applied, could naively be defined in the following way:

There exists a proof, $\sigma_0 \Longrightarrow \sigma_{i-1}$, and $\sigma_{i-1}T_{i-1}^{i}\sigma_i$ such that $\sigma_0 \Longrightarrow \sigma_{i-1}$ verifies and $\sigma_{i-1}T_{i-1}^{i}\sigma_i$ is valid.

Let’s examine what running this process over four steps would look like:

The functional programming enthusiast will notice that this operation is like a scan:

The ~init in OCaml refers to a named argument, and 'a and 'b are a type unification variables that work similarly to generics in Java.

(* scan [1;2;3] ~init:0
~f:(fun b a -> b + a)
=> [1,3,6] *)
val scan : 'a list
-> ~init:'b
-> ~f:('b -> 'a -> 'b)
-> 'b list
(* scan [1;2;3] ~init:0 ~f:(fun b a -> b + a)
=> [1,3,6] *)
val scan : 'a list -> ~init:'b
-> ~f:('b -> 'a -> 'b) -> 'b list

4

A scan combines elements of a collection together incrementally and returns all intermediate values. For example if our elements are numbers and our operation is plus, scan [1;2;3] ~init:0 ~f:(fun b a → b + a) has following evaluation trace:

:: means “cons” or prepend to the front of a linked list.

scan [1;2;3] ~init:0 ~f:add
(0+1)::(scan [2;3] ~init:(0+1) ~f:add)
1::(scan [2;3] ~init:1 ~f:add)
1::(1+2)::(scan [3] ~init:(1+2) ~f:add)
1::3::(scan [3] ~init:3 ~f:add)
1::3::(3+3)::(scan [] ~init:(3+3) ~f:add)
1::3::6::(scan [] ~init:6 ~f:add)
1::3::6::[]
[1;3;6]

5

However, what we really have is a scan operation over some sort of stream of incoming information, not a list. A signature in OCaml may look like this:

val scan : 'a Stream.t
-> ~init:'b
-> ~f:('b -> 'a -> 'b)
-> 'b Stream.t

6 We write streams as lists in the evaluation.

As new information flows into the stream we combine it with the last piece of computed information and emit that result onto a new stream. Here’s a trace with transactions and proofs6:

\begin{aligned}
scan &[\sigma_0T_0^{1}\sigma^{1}; \; \sigma_1T_1^{2}\sigma^{2}; \; \sigma_2T_2^{3}\sigma^{3}] \\
\sim &init:\sigma_0 \Longrightarrow \sigma_0 \\
\sim &f:combine \\
\\

combine&(\sigma_0 \Longrightarrow \sigma_0,\sigma_0T_0^{1}\sigma_1):: \\
(scan &[\sigma_1T_1^{2}\sigma^{2}; \; \sigma_2T_2^{3}\sigma^{3}] \\
\sim &init:\\
&combine(\sigma_0 \Longrightarrow \sigma_0,\sigma_0T_0^{1}\sigma_1)  \\
\sim &f:combine) \\
\\

\sigma_0 \Longrightarrow \sigma_1&:: \\
(scan &[\sigma_1T_1^{2}\sigma^{2}; \; \sigma_2T_2^{3}\sigma^{3}] \\
\sim &init:\sigma_0 \Longrightarrow \sigma_1 \\
\sim &f:combine) \\
\\

\sigma_0 \Longrightarrow \sigma_2&::\sigma_0 \Longrightarrow \sigma_1:: \\
(scan &[\sigma_2T_2^{3}\sigma_3] \\
\sim &init:\sigma_0 \Longrightarrow \sigma_2 \\
\sim &f:combine) \\
\\

\sigma_0 \Longrightarrow \sigma_3&::\sigma_0 \Longrightarrow \sigma_2::\sigma_0 \Longrightarrow \sigma_1:: \\
(scan &[] \\
\sim &init:\sigma_0 \Longrightarrow \sigma_3 \\
\sim &f:combine) \\
\\

\sigma_0 \Longrightarrow \sigma_3&::\sigma_0 \Longrightarrow \sigma_2::\sigma_0 \Longrightarrow \sigma_1::[] \\
\\

[\sigma_0 \Longrightarrow \sigma_3&; \; \sigma_0 \Longrightarrow \sigma_2; \; \sigma_0 \Longrightarrow \sigma_1]
\end{aligned}
\begin{aligned}
scan &[\sigma_0T_0^{1}\sigma^{1}; \; \sigma_1T_1^{2}\sigma^{2}; \; \sigma_2T_2^{3}\sigma^{3}] \\
\sim &init:\sigma_0 \Longrightarrow \sigma_0 \quad\sim f:combine \\
\\

combine&(\sigma_0 \Longrightarrow \sigma_0,\sigma_0T_0^{1}\sigma_1):: \\
(scan &[\sigma_1T_1^{2}\sigma^{2}; \; \sigma_2T_2^{3}\sigma^{3}] \\
\sim &init:combine(\sigma_0 \Longrightarrow \sigma_0,\sigma_0T_0^{1}\sigma_1)  \\
\sim &f:combine) \\
\\

\sigma_0 \Longrightarrow \sigma_1&:: \\
(scan &[\sigma_1T_1^{2}\sigma^{2}; \; \sigma_2T_2^{3}\sigma^{3}] \\
\sim &init:\sigma_0 \Longrightarrow \sigma_1 \quad\sim f:combine) \\
\\

\sigma_0 \Longrightarrow \sigma_2&::\sigma_0 \Longrightarrow \sigma_1:: \\
(scan &[\sigma_2T_2^{3}\sigma_3] \\
\sim &init:\sigma_0 \Longrightarrow \sigma_2 \quad\sim f:combine) \\
\\

\sigma_0 \Longrightarrow \sigma_3&::\sigma_0 \Longrightarrow \sigma_2::\sigma_0 \Longrightarrow \sigma_1:: \\
(scan &[] \quad\sim init:\sigma_0 \Longrightarrow \sigma_3 \quad\sim f:combine) \\
\\

\sigma_0 \Longrightarrow \sigma_3&::\sigma_0 \Longrightarrow \sigma_2::\sigma_0 \Longrightarrow \sigma_1::[] \\
\\

[\sigma_0 \Longrightarrow \sigma_3&; \; \sigma_0 \Longrightarrow \sigma_2; \; \sigma_0 \Longrightarrow \sigma_1]
\end{aligned}
\begin{aligned}
&scan [\sigma_0T_0^{1}\sigma^{1}; \; \sigma_1T_1^{2}\sigma^{2}; \; \sigma_2T_2^{3}\sigma^{3}] \quad\sim init:\sigma_0 \Longrightarrow \sigma_0 \quad\sim f:combine \\
\\

&combine(\sigma_0 \Longrightarrow \sigma_0,\sigma_0T_0^{1}\sigma_1):: \\
&\quad(scan [\sigma_1T_1^{2}\sigma^{2}; \; \sigma_2T_2^{3}\sigma^{3}] \quad\sim init:combine(\sigma_0 \Longrightarrow \sigma_0,\sigma_0T_0^{1}\sigma_1) \quad\sim f:combine) \\
\\

&\sigma_0 \Longrightarrow \sigma_1:: (scan [\sigma_1T_1^{2}\sigma^{2}; \; \sigma_2T_2^{3}\sigma^{3}] \quad\sim init:\sigma_0 \Longrightarrow \sigma_1 \quad\sim f:combine) \\
\\

&\sigma_0 \Longrightarrow \sigma_2::\sigma_0 \Longrightarrow \sigma_1:: (scan [\sigma_2T_2^{3}\sigma_3] \quad\sim init:\sigma_0 \Longrightarrow \sigma_2 \quad\sim f:combine) \\
\\

&\sigma_0 \Longrightarrow \sigma_3::\sigma_0 \Longrightarrow \sigma_2::\sigma_0 \Longrightarrow \sigma_1:: (scan [] \quad\sim init:\sigma_0 \Longrightarrow \sigma_3 \quad\sim f:combine) \\
\\

&\sigma_0 \Longrightarrow \sigma_3::\sigma_0 \Longrightarrow \sigma_2::\sigma_0 \Longrightarrow \sigma_1::[] \\
\\

&[\sigma_0 \Longrightarrow \sigma_3; \; \sigma_0 \Longrightarrow \sigma_2; \; \sigma_0 \Longrightarrow \sigma_1]
\end{aligned}

Unfortunately, we have a serial dependency of proof construction here: you must have $\sigma_0 \Longrightarrow \sigma_i$ before getting $\sigma_0 \Longrightarrow \sigma_{i+1}$. This is very slow. When using Libsnark it takes ~20 seconds to do one of these steps on an 8 core cloud instance, and that’s just for a single transaction. This translates to merely 3 transactions per minute globally on the network!

What we’ll do in this blog post is find a better scan. A scan that maximizes throughput, doesn’t incur too much latency, and doesn’t require too much intermediate state. A scan that takes advantage of properties of the zk-SNARK primitives we have. We’ll do this by iterating on our design until we get something that best meets our requirements. Finally, we’ll talk about a few other potential use cases for such a scan outside of cryptocurrency.

## Requirements

Now that we understand the root problem, let’s talk about requirements to help guide us toward the best solution for this problem. We want to optimize our scan for the following features:

1. Maximize transaction throughput

Transaction throughput here refers to the rate at which transactions can be processed and validated in the Coda protocol network. Coda strives to be able to support low transaction fees and more simultaneous users on the network, so this is our highest priority.

1. Minimize transaction latency

7 The more we sacrifice latency the longer proposer nodes have to keep around full copies of the state before just relying on the small SNARK itself.

It’s important to minimize transaction latency to enter our SNARK to keep the low RAM requirements on proposer nodes, nodes that propose new transitions during Proof of Stake.7 SNARKing a transaction is not the same as knowing a transaction has been processed, so this is certainly less important for us than throughput.

1. Minimize size of state

Again, to keep low RAM requirements on proposer nodes we want to minimize the amount of data we need to represent one state.

And moreover, this is the order of importance of these goals from most to least important: Maximize throughput, minimize latency, minimize size of state.

## Properties

8 This is possible because of a cryptographic notion known as “Signature of Knowledge” which lets us embed information about the creator and a fee into the proof in a way that is unforgeable. We will talk more about how we use this information in another blog post.

• All SNARK proofs take one unit of time to complete
• Transactions arrive into the system at a constant rate $R$ per unit time
• We effectively have any number of cores we need to process transactions because we can economically incentivize actors to perform SNARK proofs and use transaction fees to pay those actors.8
• Two proofs can be recursively merged:

This merge operation is associative:

So we can actually write transaction SNARKs that effectively prove the following statements:

Base ($\sigma_i \Longrightarrow \sigma_{i+1}$)

There exists $\sigma_iT_i^{i+1}\sigma_{i+1}$ such that the transaction is valid

Merge ($\sigma_i \Longrightarrow \sigma_k$)

There exists $\sigma_i \Longrightarrow \sigma_j$ and $\sigma_j \Longrightarrow \sigma_k$ such that both proofs verify

Before we go any further, though, let’s abstract away some details here.

## Abstractions

Data:

$D_i := \; \; \sigma_iT_i^{i+1}\sigma_{i+1}$

Base work:

$B_i := \; \; \sigma_i \Longrightarrow \sigma_{i+1}$

Merge work:

$M_{ij} := \; \; \sigma_i \Longrightarrow \sigma_j$

Accumulated value:

$A_k := \; \; \sigma_0 \Longrightarrow \sigma_k$

Let’s say that data effectively enqueues a “Base job” that can be completed to become “Base work”. Similarly, two “Base work”s (or two “Merge works”s) can be combined in a “Merge job” to create “Merge work”.

## Initial Analysis

### Upper Bound

Let’s set an upper bound efficiency target for any sort of scan. No matter what we do we can’t do better than the following:

• Throughput: $R$ per unit time

We said new data was entering the system at a rate of $R$ per unit time, so the best we can do is complete the work as soon as it’s added.

• Latency: $O(1)$

In the best case, we don’t have to wait to get the piece of data included as part of the scan result. Whatever time it takes to do one step is the time it takes before our data is included in the scan result.

• Space: $O(1)$

We don’t need to store any extra information besides the most recent result.

As a reminder, we decided that the naive approach is just a standard linear scan. This “dumb scan” can be a nice lower bound on throughput, we can also analyze the other attributes we care about here:

### Linear Scan

• Throughput: $1$ per unit time

Our linear scan operation emits a result at every step and so we need the prior result before we can perform the next step.

• Latency: $O(1)$

Every step emits a single result based on the data

• Space: $O(1)$

We only have to hold on to the most recently accumulated result to combine with the next value.

Since our primary goal is to maximize throughput, it’s clear a linear scan isn’t appropriate.

## Parallel Periodic Scan

Recall that the merge operation is associative. This means that we can choose to evaluate more than one merge at the same time, thus giving us parallelism! Even though data are coming in only $R$ at a time, we can choose to hold more back to unlock parallel merge work later. Because we effectively have infinite cores we can get a massive speedup by doing work in parallel.

This gives rise to the notion of a “periodic scan”:

(* periodicScan 1->2->3->4->5->6->7->8
~init:0
~lift:(fun a -> a)
~merge:(fun a b -> a + b) =>
10->36
*)
val periodicScan :
'a Stream.t ->
~init:'b ->
~lift:('a -> 'b) ->
~merge:('b -> 'b -> 'b) ->
'b Stream.t
(* periodicScan 1->2->3->4->5->6->7->8
~init:0 ~lift:(fun a -> a)
~merge:(fun a b -> a + b) => 10->36
*)
val periodicScan : 'a Stream.t -> ~init:'b ->
~lift:('a -> 'b) -> ~merge:('b -> 'b -> 'b) -> 'b Stream.t

A scan that periodically emits complete values, not every time an 'a datum appears on a stream, but maybe every few times. This therefore has slightly different semantics than a traditional scan operation.

Rather than returning a stream emitting 1→3→6→10→15→21→28→36, we buffer data elements 1 through 4 and compute with those in parallel, and only emit the resulting sum, 10, when we’re done. Likewise we buffer 5 through 8, and combine that with 10 and emit that 36 when we’re done. We periodically emit intermediate results instead of doing so every time.

## Naive Implementation of Periodic Scan

Let’s go over this tree construction step-by-step, considering what happens to our data over time as it’s coming through into the system. Let’s consider $R = 8$.

First we gather $R$ pieces of data and enqueue $R$ Base jobs for our network to complete. We use $R$ of our cores and can complete all jobs in one time step. We hold back the data on the pipe, and we are forced to buffer it because we haven’t finished handling the first $R$.

As we add Base work, we give way for a series of Merge jobs that can be completed in the next step:

Now we have $\frac{R}{2}$ pieces of merge work to complete and we use $\frac{R}{2}$ cores and complete them in one time step.

We repeat until we reach the top of the tree. The completed Merge work at the top can be consumed by the rest of the system.

## Analysis

• Throughput: $\frac{R}{log(R)}$

Every $log(R)$ steps, we have the opportunity to consume $R$ more pieces of data.

• Latency: $O(log(R))$

It takes $log(R)$ time steps before we emit our top-level merge work as we half the nodes in each layer of our tree at each step.

• Space: $O(R)$

We now have to keep parts of a tree around at each step. Since our trees have $R$ leaves, typical binary trees have $2R-1$ nodes when completed, and we have an extra layer, we actually use $3R-1$ nodes.

### Naive Periodic Scan

For the purposes of visualization, unit time is being replaced with 60 seconds. We assume the space of a single node in the tree is 2KB.

Throughput (in data per second) Latency (in seconds) Space (in bytes)
$R=4$ 0.0333 180 ~22KB
$R=16$ 0.0667 300 ~94KB
$R=1024$ 1.71 660 ~6MB
$R=16384$ 19.5 900 ~98MB
Throughput (in data per second) Latency (in seconds) Space (in bytes)
$R=4$ 0.0333 180 ~22KB
$R=16$ 0.0667 300 ~94KB
$R=1024$ 1.71 660 ~6MB
$R=16384$ 19.5 900 ~98MB

### Serial Scan

Throughput (in data per second) Latency (in seconds) Space (in bytes)
$R=4$ 0.05 20 ~2KB
$R=16$ 0.05 20 ~2KB
$R=1024$ 0.05 20 ~2KB
$R=16384$ 0.05 20 ~2KB
Throughput (in data per second) Latency (in seconds) Space (in bytes)
$R=4$ 0.05 20 ~2KB
$R=16$ 0.05 20 ~2KB
$R=1024$ 0.05 20 ~2KB
$R=16384$ 0.05 20 ~2KB

We have increased throughput at the cost of some latency and space when compared with the serial approach, so this is a little bit better!

However, this solution leaves something to be desired—why must we halve our parallelism as we walk up each layer of the tree? We have a stream feeding us $R$ data values every unit of time, so we should have enough work to do. Shouldn’t we use this somehow?

## Better Solution

Let’s take advantage of the fact that we get $R$ new data values each time we complete work—still preferring earlier queued data values to minimize latency once we’ve exhausted available parallelism.

With this in mind, let’s trace a run-through, this time always making sure we have $R$ pieces of work to do at every step—for illustration, let’s pick $R=2$:

We do as we did before, but this time we have $R$ jobs to complete and can dispatch to our $R$ cores every step. We have exactly $log(R)$ trees pending at a time. At every step, we complete the first tree (tree zero) and at tree $i$, we complete layer $i$.

## Analysis

• Throughput: $R$

Throughput of work completion matches our stream of data! It’s perfect, we’ve hit our upper-bound.

• Latency: $O(log(R))$

9 Here’s a short informal proof: Note that any sort of reduction operation on $N$ pieces of data can’t be done faster than $O(log(N))$ span. If we assume we could handle our $R$ units that we enqueue at a time in fewer than $O(log(N))$ steps then since we’re doing a reduction operation we would be doing it faster than $O(log(N))$ which is a contradiction.

Latency is still logarithmic, though now it’s $log(R)+1$ steps as our trees have $R$ leaves and we an extra layer on the bottom for base jobs. In fact, this is actually the lower bound.9

• Space: $O(R*log(R))$

We have multiple trees now. Interestingly, we have exactly $log(R)$ trees pending at a time. Again our longer trees take up an extra layer than traditional binary trees, so in this case $3R-1$ nodes since we have $R$ leaves, and we have $log(R)$ of these trees.10

Now that we have thoroughly optimized our throughput and latency, let’s optimize for space.

## Optimize size

10 In order to prevent latency and space from growing over time, we need to make sure we complete work as fast as we add it.

Do we really need to hold all $log(R)$ trees? We only ever care about the frontier of work. All the information we need to perform the next layer of jobs. We clearly don’t need to store anything above that or below it in the trees.

Notice that we only use some of each layer of trees even across the $log(R)$ trees. And so we can represent the frontier of the $log(R)$ trees with only a single tree representing the work pipeline moving from leaves to the root in the following manner:

## Analysis

• Throughput: $R$

Throughput is the same as before.

• Latency: $O(log(R))$

Latency is the same as above.

• Space: $O(R)$

We’ve reduced our space back down to a single tree with leaves $3R-1$.

## Space Optimization

Do we really need that extra layer? If we change how we think about the problem, we can use a perfect binary tree which we can manipulate to save even more space:

Now we’re down to $2R-1$ nodes—a standard binary tree with $R$ leaves.

How do we store the tree? Since we know the size a priori (a complete binary tree with $R$ leaves), we can use a succinct representation.

11 This is a very interesting area of computer science research, and I very much recommend the curious to read more: See Zhou, et. al 2013 and wavelet trees.

12 In our case, just the cursor.

A succinct data structure requires only $o(Z)$ extra space to manage the relationship between the elements if $Z$ is the optimal number of bits that we need to express the information in an unstructured manner. Note that this is little-$o$ not big-$O$—a much tighter bound.11

In fact our structure as described is actually an implicit one because of our scalar cursor. An implicit data structure is one that uses only $O(1)$ extra bits.12 In later refinements (in part 2), we’ll go back to a succinct representation because we need to relax one of the assumptions we made here. This is similar to the popular implicit heap that you may have learned about in a computer science class.

## Final Analysis

• Throughput: $R$

Throughput keeps up with production rate $R$, so we couldn’t do better.

• Latency: $O(log(R))$

Latency is proportional to $log(R)$ steps, as we described earlier, so we don’t get hurt too badly there.

• Space: $2R-1 + O(1)$

We have an implicit data structure representation for our complete binary tree with $2R$ leaves as described above.

### Fully Optimized Scan

Throughput (in data per second) Latency (in seconds) Space (in bytes)
$R=4$ 0.0667 180 ~22KB
$R=16$ 0.267 300 ~94KB
$R=1024$ 17.1 660 ~6MB
$R=16384$ 273 900 ~98MB
$R=65536$ 1092 1020 ~393MB
Throughput (in data per second) Latency (in seconds) Space (in bytes)
$R=4$ 0.0667 180 ~22KB
$R=16$ 0.267 300 ~94KB
$R=1024$ 17.1 660 ~6MB
$R=16384$ 273 900 ~98MB
$R=65536$ 1092 1020 ~393MB

We went from a sequential solution that at $R=16384$ only handled a throughput of 0.05 data per second to an initial parallel solution that handled 19.5 data per second to a fully optimized solution that handles 273 data per second. Our final solution even has optimal latency and space characteristics.

We did it! Coda can now be limited in its throughput by the speed at which information can flow across the network, and no longer by the time it takes to construct a SNARK. Moreover, we solved a more general problem: Efficiently computing an online periodic parallel scan over an infinite stream for some associative operation.

## Other Use Cases

Deep space telescopes produce an astronomical amount of data per second. For example, the Square Kilometre Array will process petabits of data per second. If data frames are coming in faster than we can process them which is certainly true for some types of workloads like non-parametric machine learning, we can use this data structure to handle these streams.

More generally, certain map-reduce type workloads that act in an online fashion (on an infinite stream of inputs instead of a finite collection) with expensive operators, could benefit from using our same data structure.

You can also go through literature and try to find prior art. We didn’t find much searching through map-reduce papers. The only thing that was a bit related is a paper from the GPU programming world, but doesn’t address the infinite streaming bit. Please leave a comment if you want to share any related work.

## Conclusion

We were able to take advantage of parallelism and other properties of our system to materialize this general “periodic scan” problem of combining data streaming in online fashion which as we described doesn’t limit throughput at all, has optimal latency characteristics, and is succinct. With this data structure, Coda is free to take advantage of succinctness to offer a high-throughput with no risk of centralization!

In a future blog post, we’ll talk about instantiating this parametric structure with concrete parameters and how we instantiate our infinite core machine model by farming work out to the network. We’ll also talk about the optimization problem we have for choosing how to fill out these trees with completed work.

If you like this sort of stuff, we’re looking for open source contributors and hiring.

## Future work

We’ll explore modifying this structure to optimize latency in the presence of variable throughput. You can imagine that if we detect input data throughput becomes sufficiently slow we can remove a layer from the next virtual tree, and if it’s too fast we can add one. We haven’t yet explored how this will affect the further refinements we made on top of the virtual trees.

Additionally, we will want to explore a more efficient mechanism to share account states that are part of the scan tree to nodes that don’t care about the in-progress proofs, so that bandwidth-constrained nodes can still look up their most recent account states without waiting for a ledger proof to pop out of the tree.

## Appendix

We can reify this model with the following signature in the Coda codebase:

'a is the type of the top value and there’s some notion of an associative merging operation on the 'a values. 'd is the type of the data at the leaves that comes in at rate $R$.

val start : parallelism_log_2:int
-> ('a, 'd) State.t
(** The initial state of the parallel
scan at some parallelism *)

val next_jobs : state:('a, 'd) State.t
-> ('a, 'd) Available_job.t list
(** Get all the available jobs *)

val enqueue_data : state:('a, 'd) State.t
-> data:'d list
-> unit Or_error.t
(** Add data to parallel scan state *)

val free_space : state:('a, 'd) State.t
-> int
(** Compute how much data ['d] elements we
are allowed to add to the state *)

val fill_in_completed_jobs :
state:('a, 'd) State.t
-> completed_jobs:
'a State.Completed_job.t list
-> 'a option Or_error.t
(** Complete jobs needed at this state --
optionally emits the ['a] at the top of
the tree *)
val start : parallelism_log_2:int -> ('a, 'd) State.t
(** The initial state of the parallel scan at some parallelism *)

val next_jobs : state:('a, 'd) State.t -> ('a, 'd) Available_job.t list
(** Get all the available jobs *)

val enqueue_data : state:('a, 'd) State.t -> data:'d list -> unit Or_error.t
(** Add data to parallel scan state *)

val free_space : state:('a, 'd) State.t -> int
(** Compute how much data ['d] elements we are allowed to add to the state *)

val fill_in_completed_jobs :
state:('a, 'd) State.t
-> completed_jobs:'a State.Completed_job.t list
-> 'a option Or_error.t
(** Complete jobs needed at this state -- optionally emits the ['a] at the top
of the tree *)

13

## Acknowledgements

Thanks to Evan Shapiro for working through these data structures with me when we were first figuring this stuff out. Thanks to Deepthi Kumar for collaborating with me on several optimizations. Thanks to Laxman Dhulipala for taking a video call early on and helping with an early core insight about the multiple trees. Finally, thanks to Omer Zach and Corey Richardson (and Evan and Deepthi) for their very thorough feedback on drafts of this post!

1. If you’d rather consume this content in video form, watch this talk.

2. Equivalent to security as a full node.

3. Note that we represent account states concretely as their hashes for performance reasons.

4. The ~init in OCaml refers to a named argument, and 'a and 'b are a type unification variables that work similarly to generics in Java.

5. :: means “cons” or prepend to the front of a linked list.

6. We write streams as lists in the evaluation.

7. The more we sacrifice latency the longer proposer nodes have to keep around full copies of the state before just relying on the small SNARK itself.

8. This is possible because of a cryptographic notion known as “Signature of Knowledge” which lets us embed information about the creator and a fee into the proof in a way that is unforgeable. We will talk more about how we use this information in another blog post.

9. Here’s a short informal proof: Note that any sort of reduction operation on $N$ pieces of data can’t be done faster than $O(log(N))$ span. If we assume we could handle our $R$ units that we enqueue at a time in fewer than $O(log(N))$ steps then since we’re doing a reduction operation we would be doing it faster than $O(log(N))$ which is a contradiction.

10. In order to prevent latency and space from growing over time, we need to make sure we complete work as fast as we add it.

11. This is a very interesting area of computer science research, and I very much recommend the curious to read more: See Zhou, et. al 2013 and wavelet trees.

12. In our case, just the cursor.

13. 'a is the type of the top value and there’s some notion of an associative merging operation on the 'a values. 'd is the type of the data at the leaves that comes in at rate $R$.

# Fast Accumulation on Streams

## Succinctly Verifying Coda’s Ledger

#### December 20 2018

1 If you’d rather consume this content in video form, watch this talk.

While developing Coda, we came across an interesting problem that uncovered a much more general and potentially widely applicable problem: Taking advantage of parallelism when combining a large amount of data streaming in over time. We were able to come up with a solution that scales up to any throughput optimally while simultaneously minimizing latency and space usage. We’re sharing our results with the hope that others dealing with manipulation of online data streams will find them interesting and applicable.1

## Background

2 Equivalent to security as a full node.

The Coda cryptocurrency protocol is unique in that it uses a succinct blockchain. In Coda the blockchain is replaced by a tiny constant-sized cryptographic proof. This means that in the Coda protocol a user can sync with full-security2 instantly—users don’t have to wait to download thousands and thousands of blocks to verify the state of the network.

What is this tiny cryptographic proof? It’s called a zk-SNARK, or zero knowledge Succinct Non-interactive ARgument of Knowledge. zk-SNARKs let a program create a proof of a computation, then share that proof with anyone. Anyone with the proof can verify the computation very quickly, in just milliseconds, independent of how long the computation itself takes. While validating proofs is fast, creating them is quite slow, so creating this SNARK proof is much more computationally expensive. We use a few different SNARK proofs throughout Coda’s protocol, but the important one for this post is what we call the “Ledger Proof”.

3 Note that we represent account states concretely as their hashes for performance reasons.

A ledger proof tells us that given some starting account state $\sigma_0$ there was a series of $k$ transactions that eventually put us into account state $\sigma_k$. Let’s refer to such a proof as $\sigma_0 \Longrightarrow \sigma_k$.3 So what does it mean for a single transaction to be valid? A transaction, $T_i^{i+1}$, is valid if it’s been signed by the sender, and the sender had sufficient balance in their account. As a result our account state $\sigma_i$ transitions to some new state $\sigma_{i+1}$. This state transition can be represented as $\sigma_i T_{i}^{i+1} \sigma_{i+1}$. We could recompute $\sigma_0 \Longrightarrow \sigma_k$ every time there is a new transaction, but that would be slow, with the cost of generating the proof growing with the number of transactions—instead we can reuse the previous proof recursively. These ledger proofs enable users of Coda to be sure that the ledger has been computed correctly and play a part in consensus state verification.

More precisely, the recursive bit of our ledger proof, $\sigma_0 \Longrightarrow \sigma_{i}$, or the account state, has transitioned from the starting state $\sigma_0$ to the current state $\sigma_i$ after $i$ correct transactions are applied, could naively be defined in the following way:

There exists a proof, $\sigma_0 \Longrightarrow \sigma_{i-1}$, and $\sigma_{i-1}T_{i-1}^{i}\sigma_i$ such that $\sigma_0 \Longrightarrow \sigma_{i-1}$ verifies and $\sigma_{i-1}T_{i-1}^{i}\sigma_i$ is valid.

Let’s examine what running this process over four steps would look like:

The functional programming enthusiast will notice that this operation is like a scan:

The ~init in OCaml refers to a named argument, and 'a and 'b are a type unification variables that work similarly to generics in Java.

(* scan [1;2;3] ~init:0
~f:(fun b a -> b + a)
=> [1,3,6] *)
val scan : 'a list
-> ~init:'b
-> ~f:('b -> 'a -> 'b)
-> 'b list
(* scan [1;2;3] ~init:0 ~f:(fun b a -> b + a)
=> [1,3,6] *)
val scan : 'a list -> ~init:'b
-> ~f:('b -> 'a -> 'b) -> 'b list

4

A scan combines elements of a collection together incrementally and returns all intermediate values. For example if our elements are numbers and our operation is plus, scan [1;2;3] ~init:0 ~f:(fun b a → b + a) has following evaluation trace:

:: means “cons” or prepend to the front of a linked list.

scan [1;2;3] ~init:0 ~f:add
(0+1)::(scan [2;3] ~init:(0+1) ~f:add)
1::(scan [2;3] ~init:1 ~f:add)
1::(1+2)::(scan [3] ~init:(1+2) ~f:add)
1::3::(scan [3] ~init:3 ~f:add)
1::3::(3+3)::(scan [] ~init:(3+3) ~f:add)
1::3::6::(scan [] ~init:6 ~f:add)
1::3::6::[]
[1;3;6]

5

However, what we really have is a scan operation over some sort of stream of incoming information, not a list. A signature in OCaml may look like this:

val scan : 'a Stream.t
-> ~init:'b
-> ~f:('b -> 'a -> 'b)
-> 'b Stream.t

6 We write streams as lists in the evaluation.

As new information flows into the stream we combine it with the last piece of computed information and emit that result onto a new stream. Here’s a trace with transactions and proofs6:

\begin{aligned}
scan &[\sigma_0T_0^{1}\sigma^{1}; \; \sigma_1T_1^{2}\sigma^{2}; \; \sigma_2T_2^{3}\sigma^{3}] \\
\sim &init:\sigma_0 \Longrightarrow \sigma_0 \\
\sim &f:combine \\
\\

combine&(\sigma_0 \Longrightarrow \sigma_0,\sigma_0T_0^{1}\sigma_1):: \\
(scan &[\sigma_1T_1^{2}\sigma^{2}; \; \sigma_2T_2^{3}\sigma^{3}] \\
\sim &init:\\
&combine(\sigma_0 \Longrightarrow \sigma_0,\sigma_0T_0^{1}\sigma_1)  \\
\sim &f:combine) \\
\\

\sigma_0 \Longrightarrow \sigma_1&:: \\
(scan &[\sigma_1T_1^{2}\sigma^{2}; \; \sigma_2T_2^{3}\sigma^{3}] \\
\sim &init:\sigma_0 \Longrightarrow \sigma_1 \\
\sim &f:combine) \\
\\

\sigma_0 \Longrightarrow \sigma_2&::\sigma_0 \Longrightarrow \sigma_1:: \\
(scan &[\sigma_2T_2^{3}\sigma_3] \\
\sim &init:\sigma_0 \Longrightarrow \sigma_2 \\
\sim &f:combine) \\
\\

\sigma_0 \Longrightarrow \sigma_3&::\sigma_0 \Longrightarrow \sigma_2::\sigma_0 \Longrightarrow \sigma_1:: \\
(scan &[] \\
\sim &init:\sigma_0 \Longrightarrow \sigma_3 \\
\sim &f:combine) \\
\\

\sigma_0 \Longrightarrow \sigma_3&::\sigma_0 \Longrightarrow \sigma_2::\sigma_0 \Longrightarrow \sigma_1::[] \\
\\

[\sigma_0 \Longrightarrow \sigma_3&; \; \sigma_0 \Longrightarrow \sigma_2; \; \sigma_0 \Longrightarrow \sigma_1]
\end{aligned}
\begin{aligned}
scan &[\sigma_0T_0^{1}\sigma^{1}; \; \sigma_1T_1^{2}\sigma^{2}; \; \sigma_2T_2^{3}\sigma^{3}] \\
\sim &init:\sigma_0 \Longrightarrow \sigma_0 \quad\sim f:combine \\
\\

combine&(\sigma_0 \Longrightarrow \sigma_0,\sigma_0T_0^{1}\sigma_1):: \\
(scan &[\sigma_1T_1^{2}\sigma^{2}; \; \sigma_2T_2^{3}\sigma^{3}] \\
\sim &init:combine(\sigma_0 \Longrightarrow \sigma_0,\sigma_0T_0^{1}\sigma_1)  \\
\sim &f:combine) \\
\\

\sigma_0 \Longrightarrow \sigma_1&:: \\
(scan &[\sigma_1T_1^{2}\sigma^{2}; \; \sigma_2T_2^{3}\sigma^{3}] \\
\sim &init:\sigma_0 \Longrightarrow \sigma_1 \quad\sim f:combine) \\
\\

\sigma_0 \Longrightarrow \sigma_2&::\sigma_0 \Longrightarrow \sigma_1:: \\
(scan &[\sigma_2T_2^{3}\sigma_3] \\
\sim &init:\sigma_0 \Longrightarrow \sigma_2 \quad\sim f:combine) \\
\\

\sigma_0 \Longrightarrow \sigma_3&::\sigma_0 \Longrightarrow \sigma_2::\sigma_0 \Longrightarrow \sigma_1:: \\
(scan &[] \quad\sim init:\sigma_0 \Longrightarrow \sigma_3 \quad\sim f:combine) \\
\\

\sigma_0 \Longrightarrow \sigma_3&::\sigma_0 \Longrightarrow \sigma_2::\sigma_0 \Longrightarrow \sigma_1::[] \\
\\

[\sigma_0 \Longrightarrow \sigma_3&; \; \sigma_0 \Longrightarrow \sigma_2; \; \sigma_0 \Longrightarrow \sigma_1]
\end{aligned}
\begin{aligned}
&scan [\sigma_0T_0^{1}\sigma^{1}; \; \sigma_1T_1^{2}\sigma^{2}; \; \sigma_2T_2^{3}\sigma^{3}] \quad\sim init:\sigma_0 \Longrightarrow \sigma_0 \quad\sim f:combine \\
\\

&combine(\sigma_0 \Longrightarrow \sigma_0,\sigma_0T_0^{1}\sigma_1):: \\
&\quad(scan [\sigma_1T_1^{2}\sigma^{2}; \; \sigma_2T_2^{3}\sigma^{3}] \quad\sim init:combine(\sigma_0 \Longrightarrow \sigma_0,\sigma_0T_0^{1}\sigma_1) \quad\sim f:combine) \\
\\

&\sigma_0 \Longrightarrow \sigma_1:: (scan [\sigma_1T_1^{2}\sigma^{2}; \; \sigma_2T_2^{3}\sigma^{3}] \quad\sim init:\sigma_0 \Longrightarrow \sigma_1 \quad\sim f:combine) \\
\\

&\sigma_0 \Longrightarrow \sigma_2::\sigma_0 \Longrightarrow \sigma_1:: (scan [\sigma_2T_2^{3}\sigma_3] \quad\sim init:\sigma_0 \Longrightarrow \sigma_2 \quad\sim f:combine) \\
\\

&\sigma_0 \Longrightarrow \sigma_3::\sigma_0 \Longrightarrow \sigma_2::\sigma_0 \Longrightarrow \sigma_1:: (scan [] \quad\sim init:\sigma_0 \Longrightarrow \sigma_3 \quad\sim f:combine) \\
\\

&\sigma_0 \Longrightarrow \sigma_3::\sigma_0 \Longrightarrow \sigma_2::\sigma_0 \Longrightarrow \sigma_1::[] \\
\\

&[\sigma_0 \Longrightarrow \sigma_3; \; \sigma_0 \Longrightarrow \sigma_2; \; \sigma_0 \Longrightarrow \sigma_1]
\end{aligned}

Unfortunately, we have a serial dependency of proof construction here: you must have $\sigma_0 \Longrightarrow \sigma_i$ before getting $\sigma_0 \Longrightarrow \sigma_{i+1}$. This is very slow. When using Libsnark it takes ~20 seconds to do one of these steps on an 8 core cloud instance, and that’s just for a single transaction. This translates to merely 3 transactions per minute globally on the network!

What we’ll do in this blog post is find a better scan. A scan that maximizes throughput, doesn’t incur too much latency, and doesn’t require too much intermediate state. A scan that takes advantage of properties of the zk-SNARK primitives we have. We’ll do this by iterating on our design until we get something that best meets our requirements. Finally, we’ll talk about a few other potential use cases for such a scan outside of cryptocurrency.

## Requirements

Now that we understand the root problem, let’s talk about requirements to help guide us toward the best solution for this problem. We want to optimize our scan for the following features:

1. Maximize transaction throughput

Transaction throughput here refers to the rate at which transactions can be processed and validated in the Coda protocol network. Coda strives to be able to support low transaction fees and more simultaneous users on the network, so this is our highest priority.

1. Minimize transaction latency

7 The more we sacrifice latency the longer proposer nodes have to keep around full copies of the state before just relying on the small SNARK itself.

It’s important to minimize transaction latency to enter our SNARK to keep the low RAM requirements on proposer nodes, nodes that propose new transitions during Proof of Stake.7 SNARKing a transaction is not the same as knowing a transaction has been processed, so this is certainly less important for us than throughput.

1. Minimize size of state

Again, to keep low RAM requirements on proposer nodes we want to minimize the amount of data we need to represent one state.

And moreover, this is the order of importance of these goals from most to least important: Maximize throughput, minimize latency, minimize size of state.

## Properties

8 This is possible because of a cryptographic notion known as “Signature of Knowledge” which lets us embed information about the creator and a fee into the proof in a way that is unforgeable. We will talk more about how we use this information in another blog post.

• All SNARK proofs take one unit of time to complete
• Transactions arrive into the system at a constant rate $R$ per unit time
• We effectively have any number of cores we need to process transactions because we can economically incentivize actors to perform SNARK proofs and use transaction fees to pay those actors.8
• Two proofs can be recursively merged:

This merge operation is associative:

So we can actually write transaction SNARKs that effectively prove the following statements:

Base ($\sigma_i \Longrightarrow \sigma_{i+1}$)

There exists $\sigma_iT_i^{i+1}\sigma_{i+1}$ such that the transaction is valid

Merge ($\sigma_i \Longrightarrow \sigma_k$)

There exists $\sigma_i \Longrightarrow \sigma_j$ and $\sigma_j \Longrightarrow \sigma_k$ such that both proofs verify

Before we go any further, though, let’s abstract away some details here.

## Abstractions

Data:

$D_i := \; \; \sigma_iT_i^{i+1}\sigma_{i+1}$

Base work:

$B_i := \; \; \sigma_i \Longrightarrow \sigma_{i+1}$

Merge work:

$M_{ij} := \; \; \sigma_i \Longrightarrow \sigma_j$

Accumulated value:

$A_k := \; \; \sigma_0 \Longrightarrow \sigma_k$

Let’s say that data effectively enqueues a “Base job” that can be completed to become “Base work”. Similarly, two “Base work”s (or two “Merge works”s) can be combined in a “Merge job” to create “Merge work”.

## Initial Analysis

### Upper Bound

Let’s set an upper bound efficiency target for any sort of scan. No matter what we do we can’t do better than the following:

• Throughput: $R$ per unit time

We said new data was entering the system at a rate of $R$ per unit time, so the best we can do is complete the work as soon as it’s added.

• Latency: $O(1)$

In the best case, we don’t have to wait to get the piece of data included as part of the scan result. Whatever time it takes to do one step is the time it takes before our data is included in the scan result.

• Space: $O(1)$

We don’t need to store any extra information besides the most recent result.

As a reminder, we decided that the naive approach is just a standard linear scan. This “dumb scan” can be a nice lower bound on throughput, we can also analyze the other attributes we care about here:

### Linear Scan

• Throughput: $1$ per unit time

Our linear scan operation emits a result at every step and so we need the prior result before we can perform the next step.

• Latency: $O(1)$

Every step emits a single result based on the data

• Space: $O(1)$

We only have to hold on to the most recently accumulated result to combine with the next value.

Since our primary goal is to maximize throughput, it’s clear a linear scan isn’t appropriate.

## Parallel Periodic Scan

Recall that the merge operation is associative. This means that we can choose to evaluate more than one merge at the same time, thus giving us parallelism! Even though data are coming in only $R$ at a time, we can choose to hold more back to unlock parallel merge work later. Because we effectively have infinite cores we can get a massive speedup by doing work in parallel.

This gives rise to the notion of a “periodic scan”:

(* periodicScan 1->2->3->4->5->6->7->8
~init:0
~lift:(fun a -> a)
~merge:(fun a b -> a + b) =>
10->36
*)
val periodicScan :
'a Stream.t ->
~init:'b ->
~lift:('a -> 'b) ->
~merge:('b -> 'b -> 'b) ->
'b Stream.t
(* periodicScan 1->2->3->4->5->6->7->8
~init:0 ~lift:(fun a -> a)
~merge:(fun a b -> a + b) => 10->36
*)
val periodicScan : 'a Stream.t -> ~init:'b ->
~lift:('a -> 'b) -> ~merge:('b -> 'b -> 'b) -> 'b Stream.t

A scan that periodically emits complete values, not every time an 'a datum appears on a stream, but maybe every few times. This therefore has slightly different semantics than a traditional scan operation.

Rather than returning a stream emitting 1→3→6→10→15→21→28→36, we buffer data elements 1 through 4 and compute with those in parallel, and only emit the resulting sum, 10, when we’re done. Likewise we buffer 5 through 8, and combine that with 10 and emit that 36 when we’re done. We periodically emit intermediate results instead of doing so every time.

## Naive Implementation of Periodic Scan

Let’s go over this tree construction step-by-step, considering what happens to our data over time as it’s coming through into the system. Let’s consider $R = 8$.

First we gather $R$ pieces of data and enqueue $R$ Base jobs for our network to complete. We use $R$ of our cores and can complete all jobs in one time step. We hold back the data on the pipe, and we are forced to buffer it because we haven’t finished handling the first $R$.

As we add Base work, we give way for a series of Merge jobs that can be completed in the next step:

Now we have $\frac{R}{2}$ pieces of merge work to complete and we use $\frac{R}{2}$ cores and complete them in one time step.

We repeat until we reach the top of the tree. The completed Merge work at the top can be consumed by the rest of the system.

## Analysis

• Throughput: $\frac{R}{log(R)}$

Every $log(R)$ steps, we have the opportunity to consume $R$ more pieces of data.

• Latency: $O(log(R))$

It takes $log(R)$ time steps before we emit our top-level merge work as we half the nodes in each layer of our tree at each step.

• Space: $O(R)$

We now have to keep parts of a tree around at each step. Since our trees have $R$ leaves, typical binary trees have $2R-1$ nodes when completed, and we have an extra layer, we actually use $3R-1$ nodes.

### Naive Periodic Scan

For the purposes of visualization, unit time is being replaced with 60 seconds. We assume the space of a single node in the tree is 2KB.

Throughput (in data per second) Latency (in seconds) Space (in bytes)
$R=4$ 0.0333 180 ~22KB
$R=16$ 0.0667 300 ~94KB
$R=1024$ 1.71 660 ~6MB
$R=16384$ 19.5 900 ~98MB
Throughput (in data per second) Latency (in seconds) Space (in bytes)
$R=4$ 0.0333 180 ~22KB
$R=16$ 0.0667 300 ~94KB
$R=1024$ 1.71 660 ~6MB
$R=16384$ 19.5 900 ~98MB

### Serial Scan

Throughput (in data per second) Latency (in seconds) Space (in bytes)
$R=4$ 0.05 20 ~2KB
$R=16$ 0.05 20 ~2KB
$R=1024$ 0.05 20 ~2KB
$R=16384$ 0.05 20 ~2KB
Throughput (in data per second) Latency (in seconds) Space (in bytes)
$R=4$ 0.05 20 ~2KB
$R=16$ 0.05 20 ~2KB
$R=1024$ 0.05 20 ~2KB
$R=16384$ 0.05 20 ~2KB

We have increased throughput at the cost of some latency and space when compared with the serial approach, so this is a little bit better!

However, this solution leaves something to be desired—why must we halve our parallelism as we walk up each layer of the tree? We have a stream feeding us $R$ data values every unit of time, so we should have enough work to do. Shouldn’t we use this somehow?

## Better Solution

Let’s take advantage of the fact that we get $R$ new data values each time we complete work—still preferring earlier queued data values to minimize latency once we’ve exhausted available parallelism.

With this in mind, let’s trace a run-through, this time always making sure we have $R$ pieces of work to do at every step—for illustration, let’s pick $R=2$:

We do as we did before, but this time we have $R$ jobs to complete and can dispatch to our $R$ cores every step. We have exactly $log(R)$ trees pending at a time. At every step, we complete the first tree (tree zero) and at tree $i$, we complete layer $i$.

## Analysis

• Throughput: $R$

Throughput of work completion matches our stream of data! It’s perfect, we’ve hit our upper-bound.

• Latency: $O(log(R))$

9 Here’s a short informal proof: Note that any sort of reduction operation on $N$ pieces of data can’t be done faster than $O(log(N))$ span. If we assume we could handle our $R$ units that we enqueue at a time in fewer than $O(log(N))$ steps then since we’re doing a reduction operation we would be doing it faster than $O(log(N))$ which is a contradiction.

Latency is still logarithmic, though now it’s $log(R)+1$ steps as our trees have $R$ leaves and we an extra layer on the bottom for base jobs. In fact, this is actually the lower bound.9

• Space: $O(R*log(R))$

We have multiple trees now. Interestingly, we have exactly $log(R)$ trees pending at a time. Again our longer trees take up an extra layer than traditional binary trees, so in this case $3R-1$ nodes since we have $R$ leaves, and we have $log(R)$ of these trees.10

Now that we have thoroughly optimized our throughput and latency, let’s optimize for space.

## Optimize size

10 In order to prevent latency and space from growing over time, we need to make sure we complete work as fast as we add it.

Do we really need to hold all $log(R)$ trees? We only ever care about the frontier of work. All the information we need to perform the next layer of jobs. We clearly don’t need to store anything above that or below it in the trees.

Notice that we only use some of each layer of trees even across the $log(R)$ trees. And so we can represent the frontier of the $log(R)$ trees with only a single tree representing the work pipeline moving from leaves to the root in the following manner:

## Analysis

• Throughput: $R$

Throughput is the same as before.

• Latency: $O(log(R))$

Latency is the same as above.

• Space: $O(R)$

We’ve reduced our space back down to a single tree with leaves $3R-1$.

## Space Optimization

Do we really need that extra layer? If we change how we think about the problem, we can use a perfect binary tree which we can manipulate to save even more space:

Now we’re down to $2R-1$ nodes—a standard binary tree with $R$ leaves.

How do we store the tree? Since we know the size a priori (a complete binary tree with $R$ leaves), we can use a succinct representation.

11 This is a very interesting area of computer science research, and I very much recommend the curious to read more: See Zhou, et. al 2013 and wavelet trees.

12 In our case, just the cursor.

A succinct data structure requires only $o(Z)$ extra space to manage the relationship between the elements if $Z$ is the optimal number of bits that we need to express the information in an unstructured manner. Note that this is little-$o$ not big-$O$—a much tighter bound.11

In fact our structure as described is actually an implicit one because of our scalar cursor. An implicit data structure is one that uses only $O(1)$ extra bits.12 In later refinements (in part 2), we’ll go back to a succinct representation because we need to relax one of the assumptions we made here. This is similar to the popular implicit heap that you may have learned about in a computer science class.

## Final Analysis

• Throughput: $R$

Throughput keeps up with production rate $R$, so we couldn’t do better.

• Latency: $O(log(R))$

Latency is proportional to $log(R)$ steps, as we described earlier, so we don’t get hurt too badly there.

• Space: $2R-1 + O(1)$

We have an implicit data structure representation for our complete binary tree with $2R$ leaves as described above.

### Fully Optimized Scan

Throughput (in data per second) Latency (in seconds) Space (in bytes)
$R=4$ 0.0667 180 ~22KB
$R=16$ 0.267 300 ~94KB
$R=1024$ 17.1 660 ~6MB
$R=16384$ 273 900 ~98MB
$R=65536$ 1092 1020 ~393MB
Throughput (in data per second) Latency (in seconds) Space (in bytes)
$R=4$ 0.0667 180 ~22KB
$R=16$ 0.267 300 ~94KB
$R=1024$ 17.1 660 ~6MB
$R=16384$ 273 900 ~98MB
$R=65536$ 1092 1020 ~393MB

We went from a sequential solution that at $R=16384$ only handled a throughput of 0.05 data per second to an initial parallel solution that handled 19.5 data per second to a fully optimized solution that handles 273 data per second. Our final solution even has optimal latency and space characteristics.

We did it! Coda can now be limited in its throughput by the speed at which information can flow across the network, and no longer by the time it takes to construct a SNARK. Moreover, we solved a more general problem: Efficiently computing an online periodic parallel scan over an infinite stream for some associative operation.

## Other Use Cases

Deep space telescopes produce an astronomical amount of data per second. For example, the Square Kilometre Array will process petabits of data per second. If data frames are coming in faster than we can process them which is certainly true for some types of workloads like non-parametric machine learning, we can use this data structure to handle these streams.

More generally, certain map-reduce type workloads that act in an online fashion (on an infinite stream of inputs instead of a finite collection) with expensive operators, could benefit from using our same data structure.

You can also go through literature and try to find prior art. We didn’t find much searching through map-reduce papers. The only thing that was a bit related is a paper from the GPU programming world, but doesn’t address the infinite streaming bit. Please leave a comment if you want to share any related work.

## Conclusion

We were able to take advantage of parallelism and other properties of our system to materialize this general “periodic scan” problem of combining data streaming in online fashion which as we described doesn’t limit throughput at all, has optimal latency characteristics, and is succinct. With this data structure, Coda is free to take advantage of succinctness to offer a high-throughput with no risk of centralization!

In a future blog post, we’ll talk about instantiating this parametric structure with concrete parameters and how we instantiate our infinite core machine model by farming work out to the network. We’ll also talk about the optimization problem we have for choosing how to fill out these trees with completed work.

If you like this sort of stuff, we’re looking for open source contributors and hiring.

## Future work

We’ll explore modifying this structure to optimize latency in the presence of variable throughput. You can imagine that if we detect input data throughput becomes sufficiently slow we can remove a layer from the next virtual tree, and if it’s too fast we can add one. We haven’t yet explored how this will affect the further refinements we made on top of the virtual trees.

Additionally, we will want to explore a more efficient mechanism to share account states that are part of the scan tree to nodes that don’t care about the in-progress proofs, so that bandwidth-constrained nodes can still look up their most recent account states without waiting for a ledger proof to pop out of the tree.

## Appendix

We can reify this model with the following signature in the Coda codebase:

'a is the type of the top value and there’s some notion of an associative merging operation on the 'a values. 'd is the type of the data at the leaves that comes in at rate $R$.

val start : parallelism_log_2:int
-> ('a, 'd) State.t
(** The initial state of the parallel
scan at some parallelism *)

val next_jobs : state:('a, 'd) State.t
-> ('a, 'd) Available_job.t list
(** Get all the available jobs *)

val enqueue_data : state:('a, 'd) State.t
-> data:'d list
-> unit Or_error.t
(** Add data to parallel scan state *)

val free_space : state:('a, 'd) State.t
-> int
(** Compute how much data ['d] elements we
are allowed to add to the state *)

val fill_in_completed_jobs :
state:('a, 'd) State.t
-> completed_jobs:
'a State.Completed_job.t list
-> 'a option Or_error.t
(** Complete jobs needed at this state --
optionally emits the ['a] at the top of
the tree *)
val start : parallelism_log_2:int -> ('a, 'd) State.t
(** The initial state of the parallel scan at some parallelism *)

val next_jobs : state:('a, 'd) State.t -> ('a, 'd) Available_job.t list
(** Get all the available jobs *)

val enqueue_data : state:('a, 'd) State.t -> data:'d list -> unit Or_error.t
(** Add data to parallel scan state *)

val free_space : state:('a, 'd) State.t -> int
(** Compute how much data ['d] elements we are allowed to add to the state *)

val fill_in_completed_jobs :
state:('a, 'd) State.t
-> completed_jobs:'a State.Completed_job.t list
-> 'a option Or_error.t
(** Complete jobs needed at this state -- optionally emits the ['a] at the top
of the tree *)

13

## Acknowledgements

Thanks to Evan Shapiro for working through these data structures with me when we were first figuring this stuff out. Thanks to Deepthi Kumar for collaborating with me on several optimizations. Thanks to Laxman Dhulipala for taking a video call early on and helping with an early core insight about the multiple trees. Finally, thanks to Omer Zach and Corey Richardson (and Evan and Deepthi) for their very thorough feedback on drafts of this post!

1. If you’d rather consume this content in video form, watch this talk.

2. Equivalent to security as a full node.

3. Note that we represent account states concretely as their hashes for performance reasons.

4. The ~init in OCaml refers to a named argument, and 'a and 'b are a type unification variables that work similarly to generics in Java.

5. :: means “cons” or prepend to the front of a linked list.

6. We write streams as lists in the evaluation.

7. The more we sacrifice latency the longer proposer nodes have to keep around full copies of the state before just relying on the small SNARK itself.

8. This is possible because of a cryptographic notion known as “Signature of Knowledge” which lets us embed information about the creator and a fee into the proof in a way that is unforgeable. We will talk more about how we use this information in another blog post.

9. Here’s a short informal proof: Note that any sort of reduction operation on $N$ pieces of data can’t be done faster than $O(log(N))$ span. If we assume we could handle our $R$ units that we enqueue at a time in fewer than $O(log(N))$ steps then since we’re doing a reduction operation we would be doing it faster than $O(log(N))$ which is a contradiction.

10. In order to prevent latency and space from growing over time, we need to make sure we complete work as fast as we add it.

11. This is a very interesting area of computer science research, and I very much recommend the curious to read more: See Zhou, et. al 2013 and wavelet trees.

12. In our case, just the cursor.

13. 'a is the type of the top value and there’s some notion of an associative merging operation on the 'a values. 'd is the type of the data at the leaves that comes in at rate $R$.


text:
# What determines the charge of an electron? [closed]

So I am thinking of making a machine that turns electrons into positrons. So you put as many electrons as you want in one side and positrons come out the other side. This will solve all out energy problems! But before I start my project I need to know what determines the change of an electron. Right now, the only way to make antimatter is particle accelerators but these are super uneconomical and inefficient so I want to make a machine that is economical and efficient but I don't know how... if my machine is physically impossible to make, theoretically, what machine will allow me to do this? Will it ever be invented or is it just too impossible to make?

-

## closed as off-topic by John Rennie, Dilaton, Chris White, Qmechanic♦Jul 18 '13 at 15:42

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "We deal with mainstream physics here. Questions about the general correctness of unpublished personal theories are off topic, although specific questions evaluating new theories in the context of established science are usually allowed. For more information, see Is non mainstream physics appropriate for this site?." – John Rennie, Chris White, Qmechanic
If this question can be reworded to fit the rules in the help center, please edit the question.

There are conserved quantities(preserved charge numbers) preventing you from doing this(at least due to the current physical knowledge). e.g. one of these quantities is the well known electric charge! which is conserved. – Ali Jul 18 '13 at 7:22
It took centuries, maybe millenia, to learn how to turn lead into gold. It was even thought impossible. Now we may barely know how to do it at great expense. So do not despair, keep working, and be patient. One point though: the people who succeeded were looking for something else. – babou Jul 18 '13 at 12:38

The charge of an electron is part of the definition of an electron. If you have a particle with a different charge than $-e$ then it is not an electron by definition. There is currently no deeper theory of why there should exist particles with the basic defining properties of an electron (charge $-e$, mass ~511 keV, spin 1/2, ...). These properties just go into the theory as a basic ingredient.
If you ask the question "is there any process which changes the net charge" then the answer is no. There are very strong theoretical reasons for believing that charge is exactly conserved in all reactions in nature. As far as direct experimental evidence goes, the Particle Data Group lists the limit on the rate of charge changing interactions as less than once per $6.4\times10^{24}\ \mathrm{yr}$ (possibly not available on the pdg website, but available here - thanks Ali. It is also available in the print version of the review.).
Particle accelerators do not produce antimatter by converting charged particles into their antiparticles like $e^- \to e^+$, rather they work by pair production processes where the net charge is conserved, for example $e^- \to e^- + e^- + e^+$.


text:
# Math Help - Technique for finding the correct factor

1. ## Technique for finding the correct factor

From teh answer in my textbook and the result given in wolframAlpha/Maple etc i know that this:

$\frac{16}{27}u^3 + \frac{4}{45}u^5$

Simplifies to this:

$\frac{4}{135}u^3(20 + 3u^2)$

But i don't see how they work out that $\frac{4}{135}$ is the factor to take out.

If there computer can work it out consistently im assuming theres a technique/method used to find it? Could anyone point me in the right direction?

Thank you

2. Originally Posted by aceband
From teh answer in my textbook and the result given in wolframAlpha/Maple etc i know that this:

$\frac{16}{27}u^3 + \frac{4}{45}u^5$

Simplifies to this:

$\frac{4}{135}u^3(20 + 3u^2)$

But i don't see how they work out that $\frac{4}{135}$ is the factor to take out.

If there computer can work it out consistently im assuming theres a technique/method used to find it? Could anyone point me in the right direction?

Thank you
You only have to factorize the summands and then take the graetest common factor in front of the bracket:

$\frac{4 \cdot 4}{3 \cdot 9}u^3 + \frac{4}{5 \cdot 9}u^3 \cdot u^2 = \frac{4}{3 \cdot 5 \cdot 9}u^3(20 + 3u^2)$

3. Originally Posted by earboth
You only have to factorize the summands and then take the graetest common factor in front of the bracket:

$\frac{4 \cdot 4}{3 \cdot 9}u^3 + \frac{4}{5 \cdot 9}u^3 \cdot u^2 = \frac{4}{3 \cdot 5 \cdot 9}u^3(20 + 3u^2)$
$\frac{4 \cdot 4}{3 \cdot 9}u^3 + \frac{4}{5 \cdot 9}u^3 \cdot u^2= \frac{4 \cdot 4\cdot 5}{3\cdot 5\cdot 9}u^3+ \frac{4\cdot 3}{3\cdot 5\cdot 9}u^3\cdot u^2 = \frac{4}{3 \cdot 5 \cdot 9}u^3(20 + 3u^2)$
is perhaps a little clearer. To get both "3" and "5" in both numerators I multiplied numerator and denominator of the first fraction by 5 and of the second fraction by 3.