More on Web3 & Crypto
Vitalik
4 years ago
An approximate introduction to how zk-SNARKs are possible (part 2)
If tasked with the problem of coming up with a zk-SNARK protocol, many people would make their way to this point and then get stuck and give up. How can a verifier possibly check every single piece of the computation, without looking at each piece of the computation individually? But it turns out that there is a clever solution.
Polynomials
Polynomials are a special class of algebraic expressions of the form:
- x+5
- x^4
- x^3+3x^2+3x+1
- 628x^{271}+318x^{270}+530x^{269}+…+69x+381
i.e. they are a sum of any (finite!) number of terms of the form cx^k
There are many things that are fascinating about polynomials. But here we are going to zoom in on a particular one: polynomials are a single mathematical object that can contain an unbounded amount of information (think of them as a list of integers and this is obvious). The fourth example above contained 816 digits of tau, and one can easily imagine a polynomial that contains far more.
Furthermore, a single equation between polynomials can represent an unbounded number of equations between numbers. For example, consider the equation A(x)+ B(x) = C(x). If this equation is true, then it's also true that:
- A(0)+B(0)=C(0)
- A(1)+B(1)=C(1)
- A(2)+B(2)=C(2)
- A(3)+B(3)=C(3)
And so on for every possible coordinate. You can even construct polynomials to deliberately represent sets of numbers so you can check many equations all at once. For example, suppose that you wanted to check:
- 12+1=13
- 10+8=18
- 15+8=23
- 15+13=28
You can use a procedure called Lagrange interpolation to construct polynomials A(x) that give (12,10,15,15) as outputs at some specific set of coordinates (eg. (0,1,2,3)), B(x) the outputs (1,8,8,13) on thos same coordinates, and so forth. In fact, here are the polynomials:
- A(x)=-2x^3+\frac{19}{2}x^2-\frac{19}{2}x+12
- B(x)=2x^3-\frac{19}{2}x^2+\frac{29}{2}x+1
- C(x)=5x+13
Checking the equation A(x)+B(x)=C(x) with these polynomials checks all four above equations at the same time.
Comparing a polynomial to itself
You can even check relationships between a large number of adjacent evaluations of the same polynomial using a simple polynomial equation. This is slightly more advanced. Suppose that you want to check that, for a given polynomial F, F(x+2)=F(x)+F(x+1) with the integer range {0,1…89} (so if you also check F(0)=F(1)=1, then F(100) would be the 100th Fibonacci number)
As polynomials, F(x+2)-F(x+1)-F(x) would not be exactly zero, as it could give arbitrary answers outside the range x={0,1…98}. But we can do something clever. In general, there is a rule that if a polynomial P is zero across some set S=\{x_1,x_2…x_n\} then it can be expressed as P(x)=Z(x)*H(x), where Z(x)=(x-x_1)*(x-x_2)*…*(x-x_n) and H(x) is also a polynomial. In other words, any polynomial that equals zero across some set is a (polynomial) multiple of the simplest (lowest-degree) polynomial that equals zero across that same set.
Why is this the case? It is a nice corollary of polynomial long division: the factor theorem. We know that, when dividing P(x) by Z(x), we will get a quotient Q(x) and a remainder R(x) is strictly less than that of Z(x). Since we know that P is zero on all of S, it means that R has to be zero on all of S as well. So we can simply compute R(x) via polynomial interpolation, since it's a polynomial of degree at most n-1 and we know n values (the zeros at S). Interpolating a polynomial with all zeroes gives the zero polynomial, thus R(x)=0 and H(x)=Q(x).
Going back to our example, if we have a polynomial F that encodes Fibonacci numbers (so F(x+2)=F(x)+F(x+1) across x=\{0,1…98\}), then I can convince you that F actually satisfies this condition by proving that the polynomial P(x)=F(x+2)-F(x+1)-F(x) is zero over that range, by giving you the quotient:
H(x)=\frac{F(x+2)-F(x+1)-F(x)}{Z(x)}
Where Z(x) = (x-0)*(x-1)*…*(x-98).
You can calculate Z(x) yourself (ideally you would have it precomputed), check the equation, and if the check passes then F(x) satisfies the condition!
Now, step back and notice what we did here. We converted a 100-step-long computation into a single equation with polynomials. Of course, proving the N'th Fibonacci number is not an especially useful task, especially since Fibonacci numbers have a closed form. But you can use exactly the same basic technique, just with some extra polynomials and some more complicated equations, to encode arbitrary computations with an arbitrarily large number of steps.
see part 3
Percy Bolmér
3 years ago
Ethereum No Longer Consumes A Medium-Sized Country's Electricity To Run
The Merge cut Ethereum's energy use by 99.5%.
The Crypto community celebrated on September 15, 2022. This day, Ethereum Merged. The entire blockchain successfully merged with the Beacon chain, and it was so smooth you barely noticed.
Many have waited, dreaded, and longed for this day.
Some investors feared the network would break down, while others envisioned a seamless merging.
Speculators predict a successful Merge will lead investors to Ethereum. This could boost Ethereum's popularity.
What Has Changed Since The Merge
The merging transitions Ethereum mainnet from PoW to PoS.
PoW sends a mathematical riddle to computers worldwide (miners). First miner to solve puzzle updates blockchain and is rewarded.
The puzzles sent are power-intensive to solve, so mining requires a lot of electricity. It's sent to every miner competing to solve it, requiring duplicate computation.
PoS allows investors to stake their coins to validate a new transaction. Instead of validating a whole block, you validate a transaction and get the fees.
You can validate instead of mine. A validator stakes 32 Ethereum. After staking, the validator can validate future blocks.
Once a validator validates a block, it's sent to a randomly selected group of other validators. This group verifies that a validator is not malicious and doesn't validate fake blocks.
This way, only one computer needs to solve or validate the transaction, instead of all miners. The validated block must be approved by a small group of validators, causing duplicate computation.
PoS is more secure because validating fake blocks results in slashing. You lose your bet tokens. If a validator signs a bad block or double-signs conflicting blocks, their ETH is burned.
Theoretically, Ethereum has one block every 12 seconds, so a validator forging a block risks burning 1 Ethereum for 12 seconds of transactions. This makes mistakes expensive and risky.
What Impact Does This Have On Energy Use?
Cryptocurrency is a natural calamity, sucking electricity and eating away at the earth one transaction at a time.
Many don't know the environmental impact of cryptocurrencies, yet it's tremendous.
A single Ethereum transaction used to use 200 kWh and leave a large carbon imprint. This update reduces global energy use by 0.2%.
Ethereum will submit a challenge to one validator, and that validator will forward it to randomly selected other validators who accept it.
This reduces the needed computing power.
They expect a 99.5% reduction, therefore a single transaction should cost 1 kWh.
Carbon footprint is 0.58 kgCO2, or 1,235 VISA transactions.
This is a big Ethereum blockchain update.
I love cryptocurrency and Mother Earth.
Vitalik
4 years ago
An approximate introduction to how zk-SNARKs are possible (part 1)
You can make a proof for the statement "I know a secret number such that if you take the word ‘cow', add the number to the end, and SHA256 hash it 100 million times, the output starts with 0x57d00485aa". The verifier can verify the proof far more quickly than it would take for them to run 100 million hashes themselves, and the proof would also not reveal what the secret number is.
In the context of blockchains, this has 2 very powerful applications: Perhaps the most powerful cryptographic technology to come out of the last decade is general-purpose succinct zero knowledge proofs, usually called zk-SNARKs ("zero knowledge succinct arguments of knowledge"). A zk-SNARK allows you to generate a proof that some computation has some particular output, in such a way that the proof can be verified extremely quickly even if the underlying computation takes a very long time to run. The "ZK" part adds an additional feature: the proof can keep some of the inputs to the computation hidden.
You can make a proof for the statement "I know a secret number such that if you take the word ‘cow', add the number to the end, and SHA256 hash it 100 million times, the output starts with 0x57d00485aa". The verifier can verify the proof far more quickly than it would take for them to run 100 million hashes themselves, and the proof would also not reveal what the secret number is.
In the context of blockchains, this has two very powerful applications:
- Scalability: if a block takes a long time to verify, one person can verify it and generate a proof, and everyone else can just quickly verify the proof instead
- Privacy: you can prove that you have the right to transfer some asset (you received it, and you didn't already transfer it) without revealing the link to which asset you received. This ensures security without unduly leaking information about who is transacting with whom to the public.
But zk-SNARKs are quite complex; indeed, as recently as in 2014-17 they were still frequently called "moon math". The good news is that since then, the protocols have become simpler and our understanding of them has become much better. This post will try to explain how ZK-SNARKs work, in a way that should be understandable to someone with a medium level of understanding of mathematics.
Why ZK-SNARKs "should" be hard
Let us take the example that we started with: we have a number (we can encode "cow" followed by the secret input as an integer), we take the SHA256 hash of that number, then we do that again another 99,999,999 times, we get the output, and we check what its starting digits are. This is a huge computation.
A "succinct" proof is one where both the size of the proof and the time required to verify it grow much more slowly than the computation to be verified. If we want a "succinct" proof, we cannot require the verifier to do some work per round of hashing (because then the verification time would be proportional to the computation). Instead, the verifier must somehow check the whole computation without peeking into each individual piece of the computation.
One natural technique is random sampling: how about we just have the verifier peek into the computation in 500 different places, check that those parts are correct, and if all 500 checks pass then assume that the rest of the computation must with high probability be fine, too?
Such a procedure could even be turned into a non-interactive proof using the Fiat-Shamir heuristic: the prover computes a Merkle root of the computation, uses the Merkle root to pseudorandomly choose 500 indices, and provides the 500 corresponding Merkle branches of the data. The key idea is that the prover does not know which branches they will need to reveal until they have already "committed to" the data. If a malicious prover tries to fudge the data after learning which indices are going to be checked, that would change the Merkle root, which would result in a new set of random indices, which would require fudging the data again... trapping the malicious prover in an endless cycle.
But unfortunately there is a fatal flaw in naively applying random sampling to spot-check a computation in this way: computation is inherently fragile. If a malicious prover flips one bit somewhere in the middle of a computation, they can make it give a completely different result, and a random sampling verifier would almost never find out.
It only takes one deliberately inserted error, that a random check would almost never catch, to make a computation give a completely incorrect result.
If tasked with the problem of coming up with a zk-SNARK protocol, many people would make their way to this point and then get stuck and give up. How can a verifier possibly check every single piece of the computation, without looking at each piece of the computation individually? There is a clever solution.
see part 2
You might also like
Ivona Hirschi
3 years ago
7 LinkedIn Tips That Will Help in Audience Growth
In 8 months, I doubled my audience with them.
LinkedIn's buzz isn't over.
People dream of social proof every day. They want clients, interesting jobs, and field recognition.
LinkedIn coaches will benefit greatly. Sell learning? Probably. Can you use it?
Consistency has been key in my eight-month study of LinkedIn. However, I'll share seven of my tips. 700 to 4500 people followed me.
1. Communication, communication, communication
LinkedIn is a social network. I like to think of it as a cafe. Here, you can share your thoughts, meet friends, and discuss life and work.
Do not treat LinkedIn as if it were a board for your post-its.
More socializing improves relationships. It's about people, like any network.
Consider interactions. Three main areas:
Respond to criticism left on your posts.
Comment on other people's posts
Start and maintain conversations through direct messages.
Engage people. You spend too much time on Facebook if you only read your wall. Keeping in touch and having meaningful conversations helps build your network.
Every day, start a new conversation to make new friends.
2. Stick with those you admire
Interact thoughtfully.
Choose your contacts. Build your tribe is a term. Respectful networking.
I only had past colleagues, family, and friends in my network at the start of this year. Not business-friendly. Since then, I've sought out people I admire or can learn from.
Finding a few will help you. As they connect you to their networks. Friendships can lead to clients.
Don't underestimate network power. Cafe-style. Meet people at each table. But avoid people who sell SEO, web redesign, VAs, mysterious job opportunities, etc.
3. Share eye-catching infographics
Daily infographics flood LinkedIn. Visuals are popular. Use Canva's free templates if you can't draw them.
Last week's:
It's a fun way to visualize your topic.
You can repost and comment on infographics. Involve your network. I prefer making my own because I build my brand around certain designs.
My friend posted infographics consistently for four months and grew his network to 30,000.
If you start, credit the authors. As you steal someone's work.
4. Invite some friends over.
LinkedIn alone can be lonely. Having a few friends who support your work daily will boost your growth.
I was lucky to be invited to a group of networkers. We share knowledge and advice.
Having a few regulars who can discuss your posts is helpful. It's artificial, but it works and engages others.
Consider who you'd support if they were in your shoes.
You can pay for an engagement group, but you risk supporting unrelated people with rubbish posts.
Help each other out.
5. Don't let your feed or algorithm divert you.
LinkedIn's algorithm is magical.
Which time is best? How fast do you need to comment? Which days are best?
Overemphasize algorithms. Consider the user. No need to worry about the best time.
Remember to spend time on LinkedIn actively. Not passively. That is what Facebook is for.
Surely someone would find a LinkedIn recipe. Don't beat the algorithm yet. Consider your audience.
6. The more personal, the better
Personalization isn't limited to selfies. Share your successes and failures.
The more personality you show, the better.
People relate to others, not theories or quotes. Why should they follow you? Everyone posts the same content?
Consider your friends. What's their appeal?
Because they show their work and identity. It's simple. Medium and Linkedin are your platforms. Find out what works.
You can copy others' hooks and structures. You decide how simple to make it, though.
7. Have fun with those who have various post structures.
I like writing, infographics, videos, and carousels. Because you can:
Repurpose your content!
Out of one blog post I make:
Newsletter
Infographics (positive and negative points of view)
Carousel
Personal stories
Listicle
Create less but more variety. Since LinkedIn posts last 24 hours, you can rotate the same topics for weeks without anyone noticing.
Effective!
The final LI snippet to think about
LinkedIn is about consistency. Some say 15 minutes. If you're serious about networking, spend more time there.
The good news is that it is worth it. The bad news is that it takes time.
Maddie Wang
3 years ago
Easiest and fastest way to test your startup idea!
Here's the fastest way to validate company concepts.
I squandered a year after dropping out of Stanford designing a product nobody wanted.
But today, I’m at 100k!
Differences:
I was designing a consumer product when I dropped out.
I coded MVP, got 1k users, and got YC interview.
Nice, huh?
WRONG!
Still coding and getting users 12 months later
WOULD PEOPLE PAY FOR IT? was the riskiest assumption I hadn't tested.
When asked why I didn't verify payment, I said,
Not-ready products. Now, nobody cares. The website needs work. Include this. Increase usage…
I feared people would say no.
After 1 year of pushing it off, my team told me they were really worried about the Business Model. Then I asked my audience if they'd buy my product.
So?
No, overwhelmingly.
I felt like I wasted a year building a product no one would buy.
Founders Cafe was the opposite.
Before building anything, I requested payment.
40 founders were interviewed.
Then we emailed Stanford, YC, and other top founders, asking them to join our community.
BOOM! 10/12 paid!
Without building anything, in 1 day I validated my startup's riskiest assumption. NOT 1 year.
Asking people to pay is one of the scariest things.
I understand.
I asked Stanford queer women to pay before joining my gay sorority.
I was afraid I'd turn them off or no one would pay.
Gay women, like those founders, were in such excruciating pain that they were willing to pay me upfront to help.
You can ask for payment (before you build) to see if people have the burning pain. Then they'll pay!
Examples from Founders Cafe members:
😮 Using a fake landing page, a college dropout tested a product. Paying! He built it and made $3m!
😮 YC solo founder faked a Powerpoint demo. 5 Enterprise paid LOIs. $1.5m raised, built, and in YC!
😮 A Harvard founder can convert Figma to React. 1 day, 10 customers. Built a tool to automate Figma -> React after manually fulfilling requests. 1m+
Bad example:
😭 Stanford Dropout Spends 1 Year Building Product Without Payment Validation
Some people build for a year and then get paying customers.
What I'm sharing is my experience and what Founders Cafe members have told me about validating startup ideas.
Don't waste a year like I did.
After my first startup failed, I planned to re-enroll at Stanford/work at Facebook.
After people paid, I quit for good.
I've hit $100k!
Hope this inspires you to request upfront payment! It'll change your life
Hudson Rennie
3 years ago
My Work at a $1.2 Billion Startup That Failed
Sometimes doing everything correctly isn't enough.
In 2020, I could fix my life.
After failing to start a business, I owed $40,000 and had no work.
A $1.2 billion startup on the cusp of going public pulled me up.
Ironically, it was getting ready for an epic fall — with the world watching.
Life sometimes helps. Without a base, even the strongest fall. A corporation that did everything right failed 3 months after going public.
First-row view.
Apple is the creator of Adore.
Out of respect, I've altered the company and employees' names in this account, despite their failure.
Although being a publicly traded company, it may become obvious.
We’ll call it “Adore” — a revolutionary concept in retail shopping.
Two Apple execs established Adore in 2014 with a focus on people-first purchasing.
Jon and Tim:
The concept for the stylish Apple retail locations you see today was developed by retail expert Jon Swanson, who collaborated closely with Steve Jobs.
Tim Cruiter is a graphic designer who produced the recognizable bouncing lamp video that appears at the start of every Pixar film.
The dynamic duo realized their vision.
“What if you could combine the convenience of online shopping with the confidence of the conventional brick-and-mortar store experience.”
Adore's mobile store concept combined traditional retail with online shopping.
Adore brought joy to 70+ cities and 4 countries over 7 years, including the US, Canada, and the UK.
Being employed on the ground floor, with world dominance and IPO on the horizon, was exciting.
I started as an Adore Expert.
I delivered cell phones, helped consumers set them up, and sold add-ons.
As the company grew, I became a Virtual Learning Facilitator and trained new employees across North America using Zoom.
In this capacity, I gained corporate insider knowledge. I worked with the creative team and Jon and Tim.
It's where I saw company foundation fissures. Despite appearances, investors were concerned.
The business strategy was ground-breaking.
Even after seeing my employee stocks fall from a home down payment to $0 (when Adore filed for bankruptcy), it's hard to pinpoint what went wrong.
Solid business model, well-executed.
Jon and Tim's chase for public funding ended in glory.
Here’s the business model in a nutshell:
Buying cell phones is cumbersome. You have two choices:
Online purchase: not knowing what plan you require or how to operate your device.
Enter a store, which can be troublesome and stressful.
Apple, AT&T, and Rogers offered Adore as a free delivery add-on. Customers could:
Have their phone delivered by UPS or Canada Post in 1-2 weeks.
Alternately, arrange for a person to visit them the same day (or sometimes even the same hour) to assist them set up their phone and demonstrate how to use it (transferring contacts, switching the SIM card, etc.).
Each Adore Expert brought a van with extra devices and accessories to customers.
Happy customers.
Here’s how Adore and its partners made money:
Adores partners appreciated sending Experts to consumers' homes since they improved customer satisfaction, average sale, and gadget returns.
**Telecom enterprises have low customer satisfaction. The average NPS is 30/100. Adore's global NPS was 80.
Adore made money by:
a set cost for each delivery
commission on sold warranties and extras
Consumer product applications seemed infinite.
A proprietary scheduling system (“The Adore App”), allowed for same-day, even same-hour deliveries.
It differentiates Adore.
They treated staff generously by:
Options on stock
health advantages
sales enticements
high rates per hour
Four-day workweeks were set by experts.
Being hired early felt like joining Uber, Netflix, or Tesla. We hoped the company's stocks would rise.
Exciting times.
I smiled as I greeted more than 1,000 new staff.
I spent a decade in retail before joining Adore. I needed a change.
After a leap of faith, I needed a lifeline. So, I applied for retail sales jobs in the spring of 2019.
The universe typically offers you what you want after you accept what you need. I needed a job to settle my debt and reach $0 again.
And the universe listened.
After being hired as an Adore Expert, I became a Virtual Learning Facilitator. Enough said.
After weeks of economic damage from the pandemic.
This employment let me work from home during the pandemic. It taught me excellent business skills.
I was active in brainstorming, onboarding new personnel, and expanding communication as we grew.
This job gave me vital skills and a regular paycheck during the pandemic.
It wasn’t until January of 2022 that I left on my own accord to try to work for myself again — this time, it’s going much better.
Adore was perfect. We valued:
Connection
Discovery
Empathy
Everything we did centered on compassion, and we held frequent Justice Calls to discuss diversity and work culture.
The last day of onboarding typically ended in tears as employees felt like they'd found a home, as I had.
Like all nice things, the wonderful vibes ended.
First indication of distress
My first day at the workplace was great.
Fun, intuitive, and they wanted creative individuals, not salesman.
While sales were important, the company's vision was more important.
“To deliver joy through life-changing mobile retail experiences.”
Thorough, forward-thinking training. We had a module on intuition. It gave us role ownership.
We were flown cross-country for training, gave feedback, and felt like we made a difference. Multiple contacts responded immediately and enthusiastically.
The atmosphere was genuine.
Making money was secondary, though. Incredible service was a priority.
Jon and Tim answered new hires' questions during Zoom calls during onboarding. CEOs seldom meet new hires this way, but they seemed to enjoy it.
All appeared well.
But in late 2021, things started changing.
Adore's leadership changed after its IPO. From basic values to sales maximization. We lost communication and were forced to fend for ourselves.
Removed the training wheels.
It got tougher to gain instructions from those above me, and new employees told me their roles weren't as advertised.
External money-focused managers were hired.
Instead of creative types, we hired salespeople.
With a new focus on numbers, Adore's uniqueness began to crumble.
Via Zoom, hundreds of workers were let go.
So.
Early in 2022, mass Zoom firings were trending. A CEO firing 900 workers over Zoom went viral.
Adore was special to me, but it became a headline.
30 June 2022, Vice Motherboard published Watch as Adore's CEO Fires Hundreds.
It described a leaked video of Jon Swanson laying off all staff in Canada and the UK.
They called it a “notice of redundancy”.
The corporation couldn't pay its employees.
I loved Adore's underlying ideals, among other things. We called clients Adorers and sold solutions, not add-ons.
But, like anything, a company is only as strong as its weakest link. And obviously, the people-first focus wasn’t making enough money.
There were signs. The expansion was presumably a race against time and money.
Adore finally declared bankruptcy.
Adore declared bankruptcy 3 months after going public. It happened in waves, like any large-scale fall.
Initial key players to leave were
Then, communication deteriorated.
Lastly, the corporate culture disintegrated.
6 months after leaving Adore, I received a letter in the mail from a Law firm — it was about my stocks.
Adore filed Chapter 11. I had to sue to collect my worthless investments.
I hoped those stocks will be valuable someday. Nope. Nope.
Sad, I sighed.
$1.2 billion firm gone.
I left the workplace 3 months before starting a writing business. Despite being mediocre, I'm doing fine.
I got up as Adore fell.
Finally, can we scale kindness?
I trust my gut. Changes at Adore made me leave before it sank.
Adores' unceremonious slide from a top startup to bankruptcy is astonishing to me.
The company did everything perfectly, in my opinion.
first to market,
provided excellent service
paid their staff handsomely.
was responsible and attentive to criticism
The company wasn't led by an egotistical eccentric. The crew had centuries of cumulative space experience.
I'm optimistic about the future of work culture, but is compassion scalable?