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.

Link: hackmd.io/@liamzebedee/H…
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)

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

Keep Current with Liam (📍Paris)

Liam (📍Paris) Profile picture

Stay in touch and get notified when new unrolls are available from this author!

Read all threads

This Thread may be Removed Anytime!


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

Try unrolling a thread yourself!

how to unroll video
  1. Follow @ThreadReaderApp to mention us!

  2. From a Twitter thread mention us with a keyword "unroll"
@threadreaderapp unroll

Practice here first or read more on our help page!

More from @liamzebedee

Oct 6
Has OFAC violated your rights?
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
Read 29 tweets
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.
Read 29 tweets
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.

Read 6 tweets
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 :)
Read 101 tweets
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
Read 13 tweets
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.
Read 62 tweets

Did Thread Reader help you today?

Support us! We are indie developers!

This site is made by just two indie developers on a laptop doing marketing, support and development! Read more about the story.

Become a Premium Member ($3/month or $30/year) and get exclusive features!

Become Premium

Don't want to be a Premium member but still want to support us?

Make a small donation by buying us coffee ($5) or help with server cost ($10)

Donate via Paypal

Or Donate anonymously using crypto!


0xfe58350B80634f60Fa6Dc149a72b4DFbc17D341E copy


3ATGMxNzCUFzxpMCHL5sWSt4DVtS8UqXpi copy

Thank you for your support!

Follow Us on Twitter!