OS | ustas.eth (@ustas) • Hey
It's /ʲustɑs/ • rollups • zk-proofs • security research
Publications
- The most web3 tea I've ever tried
- Hey @yup_io.lens
- **Daily Glider, article 14: **Low-Level Data (part 2)
Continuing yesterday's article, today we'll talk about the** .instruction_data** property of an **Instruction**.
https://github.com/ustas-eth/daily-glider/blob/main/articles/low-level-data-2/README.md
- @lens/cryptothegame tried to login in FF and Brave, what's wrong?
- **Daily Glider, article 13:** Low-Level Data (part 1)
Your proficiency with **Instruction** and **Function** can be significantly increased if you know how to look into the deeper level of what they contain.
https://github.com/ustas-eth/daily-glider/blob/main/articles/low-level-data-1/README.md
- **Daily Glider, article 12:** Instruction
The last of the trio, Instruction, is another huge class with 44 methods in total + 5 from its child classes (there will be more!).
https://github.com/ustas-eth/daily-glider/blob/main/articles/instruction/README.md
- @lens/orb is growing 🪴
- 20 minutes to go!
https://twitter.com/xyz_remedy/status/1775175345974517760
- **Daily Glider, article 11:** Function
Good day to learn about the Function methods, isn't it? Function is the second of our fundamental trio.
https://github.com/ustas-eth/daily-glider/blob/main/articles/function/README.md
- $BONSAI 🍵
- **Daily Glider, article 10:** Contract
Now that we're done with the easy stuff, let's dive into complex arbitrary code. From top to bottom, we'll start with the Contract object.
https://github.com/ustas-eth/daily-glider/blob/main/articles/contract/README.md
- **Daily Glider, article 1 and a half (9):** Setup and Writing Style
Today, we will talk about the maintainability of your glides.
https://github.com/ustas-eth/daily-glider/blob/main/articles/setup-and-style/README.md
- **Daily Glider, article 8:** Contracts
We've covered the object a little in the previous articles, so you should already be quite familiar with it.
https://github.com/ustas-eth/daily-glider/blob/main/articles/contracts/README.md
- **Daily Glider, article 7:** Instructions
`Instructions` and its twin `Instruction` are perhaps the most complex objects in Glider, with the most methods.
https://github.com/ustas-eth/daily-glider/blob/main/articles/instructions/README.md
- **Daily Glider, article 6:** Functions
The second element in the declarative part's hierarchy, `Functions`.
https://github.com/ustas-eth/daily-glider/blob/main/articles/functions/README.md
- **Daily Glider, article 5:** Debug Technique
Errors are frustrating and can cause aggression and violence towards your computer. Today, we'll talk about a few methods of their location and correction.
https://github.com/ustas-eth/daily-glider/blob/main/articles/debug-technique/README.md
- **Daily Glider, article 4:** Boosting the declarative part
The declarative DB query is so much more than just the Contracts object!
https://github.com/ustas-eth/daily-glider/tree/main/articles/boosting-declarative-part
- Daily Glider, article 3: Arbitrary Logic
https://github.com/ustas-eth/daily-glider/blob/main/articles/arbitrary-logic/README.md
We're continuing to modify the glide
- **Daily Glider, article 2:** Limit and Offset
https://github.com/ustas-eth/daily-glider/blob/main/articles/limit-and-offset/README.md
- Just received this certificate for taking part in the zkEVM Bootcamp powered by Encode Club and zkSync
Thank you, guys!
- Text editors in Lens clients seriously lack some renewal 🫠
- Daily Glider, article 1: Get Started
Alright, straight to business?
https://github.com/ustas-eth/daily-glider/blob/main/articles/get-started/README.md
P.S. Sorry I can't put it together and post everything on Lens, I have troubles with code blocks 😭
- Have you seen the 1400 USD contest for a new security tool, Glider?
https://twitter.com/xyz_remedy/status/1770781557545980130
I’m here to help! I’m starting a new educational repo with Glider guides and tips for beginners and pros (complexity will grow gradually):
https://github.com/ustas-eth/daily-glider
- Gonna post a new educational project soon (these are in trend now)
- Ordered Gnosis Pay today. Hopefully I'll get the card soon because I really want to test it
The first **self-custodial** card 🤌
- Notification-as-a-Service
The link is legit
My allocation is not😂(😭)
How the hell did these chases find this email alias? I don't usually use it.
- The gods have finally heard our praises
🫴 EIP-6963
https://eips.ethereum.org/EIPS/eip-6963
I'm glad to see Frame on the list of early supporters. Good work, as always.
- FYI, the report for the @lens/zksync contest on @lens/code4rena (where I placed 11th) is finally done. Be sure to go through the findings, most of them are unique in the space and very interesting.
https://code4rena.com/reports/2023-10-zksync
Some of the findings are about underconstrained circuits, such as the H-01 "Missing range constraint on remainder check in div opcode implementation".
https://github.com/code-423n4/2023-10-zksync-findings/issues/1133
Many thanks to the team @lens/gluk64 and the organizers @lens/sockdrawer, it was the biggest contest I've ever seen at the time!
- I'm done
Hello @lens/orbapp 😮💨
- There will be a space tomorrow with the second public presentation of Glider (the first one ended in Discord a few minutes ago)
https://twitter.com/xyz_remedy/status/1762479681528287481
Don't miss it 🫵
- This is my usual UX, nothing to worry about 🙂
@lens/kaira
- 📈
- **Do you remember the Hexens x The Secureum Bootcamp?**
https://twitter.com/hexensio/status/1744373662533226797
It's time when I finally got permission to speak about the tool I was using, Glider (formerly Astrea).
It is essentially Dune but for smart contract code. You can query all the smart contracts on multiple blockchains with a desired specific behavior pattern (written in a DSL) at once. Glider provides both semantic/syntactic search and other cool features.
As a security researcher, you can use the tool to find systematic bugs like the recent ThirdWeb bug or the well-known ERC721 safeMint reentrancy in unknown contracts.
It opens up a new field of smart contract security, which concentrates on multiple protocols instead of only one (like bug bounties, public contests, and private audits do).
- Just had a great conversation about FHE logical operations in Fhenix and privacy. Very cool, I want to see it in the production.
- 🌿 Join the discussion of the Lens future, everyone is welcome!
https://github.com/lens-protocol/LIPs/pull/29
https://github.com/lens-protocol/LIPs/pull/30
Kudos to @lens/zkjew for opening the issues
- 🏆 **Top 12** in the zkSync 1.1M contest on @lens/code4rena with:
*-* QA report (grade A)
*-* Valid medium with two more dups
I recommend you to look at the discussions below some of my other invalidated findings when they're open.
The protocol had 9 previous audits (in different areas)
Thanks to the zkSync and Code4rena teams for the provided opportunity, I'm glad I've decided to participate!
- **Puzzle #1 from zkHack IV is successfully completed ✔️**
It took some time to sort the things out, so I had to take a nap over the night. To my surprise, the solution was very close to where I left off yesterday! I won't be getting a prize this time; just happy I've made it 🏋️♂️
Try to solve it yourself: https://github.com/ZK-Hack/puzzle-gamma-ray
- **Day 19 of zkEVM Bootcamp by Encode Club and zkSync**
**Plonk, part 2: Boojum**
**Customizable Constraint Systems**
An interesting and new concept of generalization of the usual constraint systems: https://github.com/ustas-eth/zkEVM-Bootcamp/blob/main/media/ccs.png (I still have trouble with uploading pictures on Hey).
**Plonky2 (**https://github.com/0xPolygonZero/plonky2**)**
It is a library by Polygon that allows us to create SNARKs with PLONK and FRI.
We've taken a quick example of how to make a circuit to prove a polynomial. Check out the corresponding homework; I'll make a Rust program with Plonky2 later.
**Presentation of Boojum by Oles Holembovskyy from zkSync**
The execution trace table has a size of ~$ 240$ columns with ~$ 2^{20}$ rows, which contain gates, lookup arguments, and copy-permutation arguments. Columns define how many variables a gate can have or how many gates can be placed in a row.
Check the repo: https://github.com/matter-labs/era-boojum
**Copy-permutation arguments**
They allow us to establish constant relations between cells and prove that these cells are equal.
**Gates**
Gates are polynomial equations over cells in one row. E.g., boolean check: x^2 - x = 0. Gate columns in the table can be of general purpose or specialized. The difference is in the performance and the use of available space. The specialized columns contain gates that apply to every row in the table (like a boolean check), while the general-purpose columns can contain different numbers of different gates.
Boojum has a list of available gates: boolean allocator, constant allocator, conditional select, reduction gate, U32 add, Poseidon, etc., similar to the instructions in a CPU.
**Lookup columns**
These columns are used to optimize the circuit. They also can be general or specialized, but in practice, they almost always are the latter. Boojum has a number of native lookup tables: binary operations, SHA256, range check, etc.
**Boojum Gadgets**
*-* Numeric types like Boolean, UInt8, UInt256. You can allocate new variables in the constraint system, put a value inside, and create a constraint. The types are optimized; e.g., they use lookup tables to check ranges of UInts.
*-* Poseidon hashes
*-* Keccak / SHA256
*-* Modulo arithmetic
*-* Elliptic curves
*-* Pairing
**Keep an eye on the repo where I post these notes:**
https://github.com/ustas-eth/zkEVM-Bootcamp
- **Day 18 of zkEVM Bootcamp by Encode Club and zkSync**
**Plonk, part 1: Linea**
Two days ago, we talked about the trace tables, as you probably remember. We can express our gates or steps in the form of a table, which gives us a nice visual of the data that we use to generate proof.
Today, we've taken an example with the Fibonacci numbers, which you can read in more detail here: https://medium.com/starkware/arithmetization-ii-403c3b3f4355.
**Presentation by Emily and Alexandre from Linea**
(see pictures in the Github repo below)
Linea is a zk-rollup; it uses validity proofs to create batches of transactions and post them on L1. This part is quite common now.
Emily is a DevRel; Alexandre is a developer (he's working in the Prover team) of Consensys.
More interestingly, Linea has a Lisp-based DSL named Corset. I didn't hear about it before. They compile the language into Go and then use the program as an input to Vortex, a gnark-based prover.
The zkEVM circuit is a composition of different smaller circuits similar to zkSync.
Linea is a type 2 rollup (from Buterin's graph) because they use different hash functions, MiMC7 (instead of Keccak) and Sparse Merkle Trees (instead of Patricia Merkle Tree), which allows not storing the full tree.
The Prover of Linea has two parts:
- Inner system, Arcane, where all the traces are being "compiled" into a homogeneous polynomial (https://en.wikipedia.org/wiki/Homogeneous_polynomial), and they use lattice-based hashes (cool!).
- The outer system, Vertex, compresses the output of the inner system and prepares it to be posted on the L1.
Lattice-based cryptography is a middle between SNARK-friendly hashes (MiMC, Poseidon) and traditional hashes (Keccak, SHA, Blake).
**Keep an eye on the repo where I post these notes:**
https://github.com/ustas-eth/zkEVM-Bootcamp
- **Day 17 of zkEVM Bootcamp by Encode Club and zkSync**
**STARK implementation**
STARKs, as was mentioned before, don't have toxic waste. This means we can make a transparent setup quick and easy. Also, they are quantum secure, but it is more like a nice topping. The fundamental security assumption of a STARK is a collision-resistant hash function, a well-known cryptographic primitive.
Cairo VM (Starknet) uses AIR (arithmetic intermediate representation) arithmetization, in opposite to the popular R1CS.
**Computation integrity**
It is one of the features of STARKs (and SNARKs). Computation integrity means we can prove that some algorithm/program/circuit/computation was executed correctly. In the context of Cairo and zkEVMs this property is more important than zero-knowledge, for example, because the data is public.
**Reed-Solomon error correction (**https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction**)**
Reed–Solomon codes are a world-used technique that allows us to find and correct broken/lost bits of data in all the mighty Internet and computer world (CD/DVDs, QR codes, broadcast systems, storage systems like data centers) by adding redundant information.
**FRI (Fast Reed-Solomon IOP of Proximity)**
This is what STARK uses as a polynomial commitment scheme. Check this video (https://www.youtube.com/watch?v=ySlibAm9IVM) by RISC Zero to learn more. FRI allows us to check if the commitment of a polynomial is of a low degree.
**Presentation by Henri Lieutaud from Starknet**
I knew some things about Cairo and Starknet already, but the presentation was pretty solid and covered some of my blind spots. Henri shared a little of the history of Starkware company, which is interesting.
What's even cooler is that Cairo VM is actually an idea of a broader caliber than sole blockchains. Starknet is a validity rollup on L1, which is only one of the things that can be built with Cairo. You can make a usual computer program with the provable execution property.
Compilation path: Cairo (higher language) -> Sierra (Safe Intermediate Representation) -> CASM (assembly) -> Validity Proofs
Starknet itself is not compatible with EVM. But there's another program in Cairo, Kakarot (https://www.kakarot.org/), which implements EVM.
There's also SHARP (Shared Prover), which can take a Cairo program and generate proofs. It is used for Starknet and Starex, for example.
They've recently disclosed the source code of Stone, which can be run on a local machine to prove and verify Cairo 0 (Python) programs.
**Keep an eye on the repo where I post these notes:**
https://github.com/ustas-eth/zkEVM-Bootcamp
- **I've just completed zkSync's zkEVM Bootcamp, powered by Encode Club! 🙌🥳**
Stay tuned for the rest of the notes:
https://github.com/ustas-eth/zkEVM-Bootcamp
Many thanks to Coogan, Laurence, Angela, and all the visitors for guiding us along the way! 🚀
- **Day 16 of zkEVM Bootcamp by Encode club and zkSync**
**SNARK implementation**
As mentioned on Day 13, SNARKs comprise a probabilistic proof and a commitment scheme. They usually require a setup where we establish a) the program that will be proved and b) some randomness.
The randomness is useful both in interactive and non-interactive proofs. We use it to keep the system sound because otherwise, the Prover can craft malicious proofs. The system won't be sound if the values we use to create randomness are known. That's why it's important to create ceremonies with many independent participants. If at least one of them is honest, the system is good to go. And this is the reason why we would want to use STARKs because they don't require such a ceremony.
STARKs also require randomness, but there's no toxic waste like in SNARKs; no secret values in the setup. This is why we call them transparent.
**Polynomial checking**
(see https://github.com/ustas-eth/zkEVM-Bootcamp for better visuals)
We can express the gate constraints as follows:
L := sum_{i=1}^{m} * ci * Li,
R := sum_{i=1}^{m} * ci * Ri,
O := sum_{i=1}^{m} * ci * Oi,
Where L is the left input of a gate, R is the right one, and O is the output. And the polynomial P that contains all the constraints will be:
P := L * R − O
In other words, all the lefts multiplied by all the rights minus all the outputs should be zero.
The Verifier will create a target polynomial from the roots, something like:
V(x) := (x − 1) * (x − 2)...
P is V multiplied by some number, and it also should be equal to zero if the constraints are met. In such a case, the Verifier can divide P by V, and there will be no remainder.
The above also means there's some polynomial P' such that P = P' * V, and the Verifier can pick random (remember about the trusted setup?) z values and ask the Prover or the oracle to check if the statement P(z) = P'(z) * V(z) still holds.
The degree of P is at most 2(d - 1); L, R, O at most d - 1; V at most d - 2.
**Trace tables**
Check out this great article by Scroll: https://scroll.io/blog/proofGeneration. You'll find examples of the trace tables and more math there.
**Fiat-Shamir heuristic (**https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic**)**
This is the final operation of any SNARK or STARK that makes them non-interactive. The basic principle is that instead of a random value from the Verifier (which is why the proofs are interactive), the Prover takes a hash of several parameters. It is similar to how we use keccak in Solidity sometimes when we want to verify some data or get pseudo-randomness.
I recommend you to check the Wiki because it has quite an illustrative example.
Similar to the keccak in smart contracts (permit signature), the Prover can manipulate parameters if they are not included in the hash.
**Keep an eye on the repo where I post these notes:**
https://github.com/ustas-eth/zkEVM-Bootcamp
- I'll be back tomorrow with new posts ✌
Took a little vacation due to New Year's celebrations. The Github repo is up to date, you can see the latest notes there!
https://github.com/ustas-eth/zkEVM-Bootcamp
- **Day 15 of zkEVM Bootcamp by Encode club and zkSync**
**Overview of Proving Systems**
In this lesson, we repeated some parts from the previous ones, like the history of ZKP, trusted setup, SNARK vs STARK, etc.
STARK uses FRI as a commitment scheme, which stands for Fast Reed-Solomon IOP of Proximity. They have a much larger proof size (like 100 kB), which is not feasible if we talk about L1 Ethereum, but a transparent setup due to the chosen commitment scheme, plus the post-quantum security.
During the lesson, I also discovered that Boojum is meant to be a fusion of STARK and SNARK. Specifically, big brains from zkSync want to make proofs of the EVM execution as STARKs and then prove these STARKs with SNARK to make the proofs more succinct. I have my doubts about the effectiveness of such an approach because I think we still have to make the trusted setup for the SNARK part, and it won't be post-quantum secure. But probably there's a good explanation.
If you want to read more, check the official announcement: https://zksync.mirror.xyz/HJ2Pj45EJkRdt5Pau-ZXwkV2ctPx8qFL19STM5jdYhc
UPD. I asked Porter about this, and he said that we indeed have to run the trusted setup. Also, he mentioned that there's no real point in post-quantum security for zk-rollups at the moment due to the fact that we use ECDSA anyway, and it is not secure in the post-quantum world.
**Halo 2**
It is a proving system that combines PLONK, recursion from Halo 1, and the Inner Product Argument commitments scheme.
You can find the documentation on the official site: https://halo2.dev
**Mina**
A pretty interesting blockchain that works entirely on ZKP without L1: https://minaprotocol.com/
**Keep an eye on the repo where I post these notes:**
https://github.com/ustas-eth/zkEVM-Bootcamp
- **Day 14** **of zkEVM Bootcamp by Encode club and zkSync**
**Presentation by Porter Adams**
Today (actually a week ago, why don't you follow my Github? 🤨) was a less formal lesson where I finally had an opportunity to flex some knowledge because I've spent two weeks trying to figure out how zkSync works in the recent C4 contest :D
We've talked briefly about things that we previously learned in the other lessons but from a different perspective.
More interestingly, we discussed the security aspects of zk rollups and many of the common concerns that developers in the space are trying to solve:
*-* Cryptography weakness
*-* Centralization issues
*-* Interoperation between layers
*-* Trusted execution
*-* Infrastructure (e.g., backdoor in a dependency)
Later in the lesson, Porter showed us some very cool examples of vulnerabilities that were found in implementations of SNARK constraint systems. Underconstrained code is probably one of the most common mistakes developers make during development.
**Keep an eye on the repo where I post these notes:**
https://github.com/ustas-eth/zkEVM-Bootcamp
- **Day 13 of zkEVM Bootcamp by Encode club and zkSync**
**What are ZK EVMs, part 3: Proving systems**
Week 4, more than half of the bootcamp.
**Polynomial Commitment Schemes**
A simple example of a commitment scheme in Solidity is:
*1.* You make a keccak hash of some secret string, e.g., "hello".
*2.* Then you save it in a smart contract storage.
*3.* Anybody can see the hash and make some operations, knowing you can't change the underlying string.
*4.* After the operations have been done, you reveal the string. You don't have much choice but to reveal "hello", because any other string would produce another hash.
A polynomial commitment is similar to the hash of a private string: it is a short representation of that polynomial. Given such a commitment, as a Verifier, you can run a number of experiments to see if the Prover is truthful in its statements.
This gives us three useful properties:
*-* Prover cannot change the polynomial after a commitment.
*-* Verifier cannot compute the polynomial from a commitment itself.
*-* Commitments are more succinct.
Common commitment schemes are:
*-* FRI
*-* KZG
*-* IPA
*-* DARK
Check this video (https://www.youtube.com/watch?v=bz16BURH_u8) to find out more.
Cool slide from the video: see Github repo.
**Interactive Oracle Proofs**
Check this (https://youtu.be/bGEXYpt3sj0?list=PLS01nW3Rtgor_yJmQsGBZAg5XM4TSGpPs&t=3920)
Different combinations of commitment schemes and interactive oracle proofs result in different proving systems with different characteristics: post-quantum security, transparency, good proof size, verification time, etc.
**Keep an eye on the repo where I post these notes:**
https://github.com/ustas-eth/zkEVM-Bootcamp
- Interesting discussion about the use of Celestia by Manta, fault proofs, and Blobstream from a security perspective.
https://twitter.com/donnoh_eth/status/1736792589741736290
*Spoiler:* Blobstream doesn't make sense if you don't use the proofs in the first place 🥲
- A brief description of inscriptions on Ethereum for the curious
https://docs.ethscriptions.com/overview/introducing-ethscriptions
- **Day 12 of zkEVM Bootcamp by Encode club and zkSync**
**What are ZK EVMs, part 2: Universal circuits/circuit compiler**
EVM is a stack-based virtual machine. For example, if we want to add two numbers, 3 and 9, we first need to push them onto the stack and then call `ADD` opcode:
PUSH1 3
PUSH1 9
ADD
The zkEVM Prover we want to build has to compute all these small operations (create traces), which lead to changes in the blockchain's global state.
**zkEVM Challenges:**
*-* Limited support of Elliptic Curves on EVM
*-* Mismatched fields (native 256-bit words on EVM vs prime fields on zkEVM)
*-* Special EVM opcodes like `CALL` and errors
*-* Stack-based model. In practice, zkEVM works better with registers rather than stack. This is the reason why, for example, zkSync zkEVM is based on registers.
*-* Storage overhead. Ethereum uses Keccak and MPT for storage computations; both are not zk-friendly.
*-* Machine-based proof overhead
**Significant advancements of the recent years in the field:**
*-* Polynomial Commitment Schemes allow us to use polynomials with higher degrees.
*-* Lookup tables turn zk-unfriendly operations into precomputed mappings that allow us to save computation time. The biggest limitation here is that we have to include these tables, and it seems like we have a solution. Check out this podcast (https://zeroknowledge.fm/274-2/) with Ariel Gabizon, especially the part about Cached Quotients (cq) (https://eprint.iacr.org/2022/1763).
*-* Customized gates.
*-* Recursive proofs. Recent techniques made them more feasible compared to the previous approaches.
*-* Hardware acceleration. Specifically, developed hardware for zk-proof generation purposes or at least GPUs instead of CPUs can hugely boost any computations.
**Gates**
We use addition and multiplication gates similar to electric circuits in order to express our programs one step closer to pure polynomials (check out the repo to see the visual representation).
Check out this playlist (https://www.youtube.com/watch?v=RUZcam_jrz0&list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC) by David Wong with more examples to see how these gates will become polynomials later.
**Lookup tables and Custom gates**
Instead of implementing some of the operations as general circuits (e.g., bitwise operations), we can add custom gates to our circuit with lookup tables. I think of them as mappings in Solidity where you can define which value => another value and use this operation instead of addition or multiplication.
**Underconstrained code**
When we write our circuits, we have to ensure that there are enough constraints because otherwise, it is possible to create proofs for erroneous inputs.
Check out this writeup (https://medium.com/chainlight/uncovering-a-zk-evm-soundness-bug-in-zksync-era-f3bc1b2a66d8) by zkSync of a disclosed bug.
**Keep an eye on the repo where I post these notes:**
https://github.com/ustas-eth/zkEVM-Bootcamp
- Gm everybody! I'm starting a new wonderful day that will most definitely bring me some new opportunities.