Nov 13 13 tweets 4 min read
Haha so I've actually written another note on STARK's (for mere mortals).

Basically I wanted to figure out - how hard is it to implement this fantasy alien technology, recursive proofing?

To do this, I had to understand a couple of areas.

What does the data structure of a STARK proof actually look like?

I went and reverse-engineered/read the code of a Circom verifier and Starkware's codebase.
From this, I was able to tell I had no idea what was going on. Why is there a separate trace and constraint merkle tree, AND the FRI? So I tried to research how STARK's are actually generated, to understand the domain.

How are STARK proofs actually generated?
There's this amazing guide here which this is directly lifted from (I mention this clearly in the notes)
aszepieniec.github.io/stark-anatomy/…

Super great read, especially around the "interpolation" step.
So now I understood the context of some additional concepts - the trace polynomial, the AIR constraints - I began to write them out.

The trace -> arithmetic equations -> interpolated into some polynomials -> combined into a single compositional polynomial
Still I didn't understand why trace/constraints/FRI were all separate data fields - I thought using a STARK was just validating one equation?

So the next logical place to look - ZK-STARK’s - how are they _actually_ verified?
This made a lot more sense - the computation is expressed as both the trace (registers) and the constraints (program counter++). Both are polynomials which we read from, and combine into a single poly, which we verify the low-degreeness of.
A good lot of this knowledge is directly picked from the Winterfell verifier documentation (incode), which I knew was good from working on Giza with Max. The rest came from the original ethSTARK spec for the EF.
It's awesome to finally understand how the verification works, because it's really quite simple in the end (7 steps, mostly computation).

There were a couple new concepts I had to learn - the composition polynomial, the random linear combination

Still no idea what LDE was!
I shot this doc to a mate, who I was already asking how hard it would be to implement verification. He comes back with a question I hadn't even thought of --

"the most difficult thing for me to understand about STARKS is why the FRI protocol converging implies the initial claim"
Basically - how can proving low-degreeness be related to proving the satisfiability of the polynomial?
Well that, we worked out today ;)

Basically - it's a mix of a foundational theorem in polynomial interpolation, which relates degree/roots, and a method to blow up the computational space to make it secure for some n. bits parameter (which is LDE!)

Experimenting with different ways of sharing + communicating. Last thread on STARK's was an actual realtime thread as I drank 50 coffees and just dived-deep into the whitepaper. This one was more post-hoc. Probably not as riveting to write the story retroactively, but hey! lfg

• • •

Missing some Tweet in this thread? You can try to force a refresh

This Thread may be Removed Anytime!

Twitter may remove this content at anytime! Save it as PDF for later use!

# More from @liamzebedee

Oct 6
You may be entitled to decentralization

..............

Introducing Dappnet 🍸
Dappnet resists capture
It's a permissionless application network
built on @ipfs and @ensdomains
The problem - we access dapps right now through DNS and servers, but they can be taken down, censored, captured, and seized from us at any time
Jun 7
The Ethereum database is such a beautiful monolithic bundling of so many things.

Indexes (logs), execution (EVM), sequencing (mempool), consensus (PoW + GHOST), data availability (coinbase)

Literally every aspect of this stack is being torn out and spun into its own protocol.
This may be my bias, but out of all the ecosystems I've played around in (eth, sol, cosmos, polka), Eth has the easiest model for composability - e.g. ERC20(0x123).transferFrom

It's like the Go of smart contracts. Really easy to understand and learn.
In terms of the UX of writing smart contracts, Cairo *currently* falls a bit short bc of some low-level frictions imo.

e.g. more complex mental model of variables (alloc_locals, let, tempvar), lack of string type

This should get better in the next 6mo though.
May 5
Bizarre question. Is bitcoin a horizontally or vertically scaled database?
Here's my take - it's vertically scaled.

When you look at distributed systems, the replicated state machine method is one way of achieving a fault-tolerant design.

Bitcoin fits that definition of a BFT replicated state machine.
The inputs are transactions, the state is the ledger, and the ordering method is a distributed clock mechanism called proof-of-work.

en.wikipedia.org/wiki/State_mac…
Apr 18
Deployed my first starknet contract tonight goerli.voyager.online/contract/0x064…
cairo doesn't have strings jfc it's early
I've recently gotten a grant from @StarkWareLtd to do some R&D into building a system on Cairo. Going to be using this thread to document my learnings :)
Feb 15
problem I have - there's so many smart people writing amazing longform content on blogs. but the modern internet makes it nigh-impossible to find it
a lot of this content is from the pre-social media era.

e.g. I learnt so much from @gafferongames series on building a game networking protocol:
- UDP, TCP, packets, reliability, sequencing

which later led me to read about how source engine (cs;go, tf2) syncs world state
this content doesn't fit perfectly on wikipedia. The 1st person voice of bloggers/random stackoverflow answers has some massive educational role that wikis don't fill, for one reason or another
Jul 13, 2020
This is my artificial pancreas. Changed the cron job last night so it would only run between 9pm and 7am (~ while I'm asleep).
Built a tool 🙆‍♂️ this weekend to annotate the glucose data from @NightscoutProj, so I could build a better view of different things like exercise, alcohol, etc.
Now the graphs have a date attached to them, and the visual design has a bit more breathing space.