Connect with us

Blockchain

How Ethereum can scale with SNARKs 101

Published

on


The beginner guide I would have liked a few months ago before digging into this stuff

Marco De Rossi

What you’ll need:

  • a computer science background
  • the basics of Ethereum
  • the basics of calculus (constraints optimisation)

What you’ll get:

  • the basics of zero-knowledge SNARKs
  • the basics of Merkle trees
  • how Ethereum could scale to thousands of transactions per second thanks to SNARKs

SNARKs allow a Prover to prove to a Verifier that she/he has a solution W to the problem F with shared/known inputs X, without revealing W.

Finding the solution to the problem could require a huge amount of computational power and memory.

So the Verifier can basically be 100% sure that the Prover has worked properly (and found a solution), with neither re-doing the job by herself/himself to check the solution nor knowing the solution at all. It’s magic!

The process has 3 steps:

  • SETUP — The problem F (that need to be expressed as quadratic arithmetic program, see below) is prepared for SNARKs. This process is very high memory and computing intensive depending on the complexity of the problem (→ The number of inputs and constraints → The dimension of the matrix of the constraints satisfaction problem). The player who does the Setup (could be the Verifier itself) must be trusted by all parties, since the output of the Setup is used in the next phases. The setup is usually done using , a C++ library which is the most popular implementation for zkSNARKs.
  • PROVING — The Prover, who has a solution W for the problem F with shared inputs X (maybe she/he spent huge amounts of CPU and memory to find it!), uses libsnark and the output of the Setup phase to create a proof 𝚷. This process is definitely high memory and computing intensive (depending on the complexity of the problem, as above). The size of the output (i.e. proof 𝚷) is instead succinct and constant independently from the complexity of the problem. The Prover needs to trust who has done the Setup phase, since she/he uses its output…
  • VERIFYING — A Verifier — giving as input the output of the Setup phase, shared inputs X and proof 𝚷 – checks the proof. If the verification is successful, the Prover managed to prove to a Verifier that she/he has found the solution W to the problem F… without revealing W! The nice part is that not only the Proof is succinct and has always the same length.., the verification process is fast and not memory/computing intensive at all. Unlike the two previous phases… the verification can be easily done with a smartphone in milliseconds!

A good recap ():

How can this happen? Well, it’s Merlin magic! If you want to get the maths behind this, .

How can I transform my software to a quadratic arithmetic program?

As mentioned above, Setup phase’s problem F needs to be a quadratic arithmetic program. Rules of the game are tough:

  • Your software’s inputs should be numbers. Convert your stuff (arrays, strings, etc) to numbers. That’s trivial.
  • A “quadratically constrained system of equations” means:

where x is the n-dimensional vector of your inputs, m is the number of constraints (i.e. the number of equations of your system), C is the n-by-n coefficients Matrix and q is a n-dimensional coefficients vector. If you don’t like matrix and vectors, here is the n = 3 and m = 2 case (3 inputs, 2 constraints):

  • The implementation is an arithmetic circuit, which means that the outcome is Problem solved (the system is solved, i.e. all polynomials are equal to 0) or Problem not solved (all the other cases). In other words: “these inputs are/aren’t one of the solutions to this Problem”.
  • C₁, C₂, …, C𝚖, q₁, q₂, …, q𝚖 coefficients are the constraints of the system. This is basically what defines your software. Change them… and you’ll get another software! Getting back to how SNARKs work: C₁, C₂, …, C𝚖, q₁, q₂, …, q𝚖 are the input of the Setup phase. The output of the Setup phase (that you need for Proving and Verifying) is therefore strictly related to those C₁, C₂, …, C𝚖, q₁, q₂, …, q𝚖 and works only for that Problem. If you change them you’re defining another software/problem and you need to re-run the Setup phase! x₁, x₂, …, x𝗇 are the variables (i.e. what you have to guess to get a system’s solution). So when we say “Dear Prover, could you please find a secret solution W for problem F with shared/public inputs X” we mean for example “Dear Prover, can you find the x₁, x₂, …, x𝗇 values which solve the system with, for example, x₇ = 2393, x₅₂₆ = 5647?” You can do what you want with all x𝗇, except for x₇ and x₅₂₆, which are constrained to the shared/public inputs.

It’s a tough life but you can survive… If you need loops you can unfold them repeating the same operation many times. Or if you need for example x₁⁴ x₂⁵, you define a new input x₃ = x₁⁴ x₂⁵ and use x₃ in your constraints. It’s all about adding variables and constraints… Even for pretty simple softwares it’s easy to reach hundreds of millions or billions of inputs and constraints!

Want to know more? Read . And also check out this basic from ethereum/research.

What’s a Merkle tree?

An hash function is a rule that maps an input of arbitrary size to an output of fixed size. We could invent a pretty useless hash function “Concatenate the first two with the last two letters” which transforms “Woody Allen” to “Woen” and “Paul McCartney” to “Paey”.

A Merkle tree is a data structure where every parent is the hash of its two sons. At the top you find the Root, which is the hash of the two sons of level 1. At the bottom, every leaf is the hash of an external input.

Using our fictionary “Woody Allen”→”Woen” hash function:

When a leaf changes, the modification is propagated up to the Root. If ANTHONY changes, also ANNY (leaf), CENY and CECO (Root) change. Whichever leaf changes, the Root changes too.

You don’t need the entire tree to recalculate the Root. In our example, if ANTHONY changes and you know both JACO and CECILY, you can easily recalculate the Root even if you completely ignore JAMES, MARCO, JAES and MACO. For huge trees this saves a lot of time!

So what?

Merkle trees are great for data integrity checks. Usually: you know which is the valid Root, and you check that the received data matches that Root. For example: a trusted party who can’t give you the entire data set of the first names of people on Earth (no time, no bandwidth or maybe she/he hasn’t the data at all) gives you only the Root (e.g. “CECO”). Afterwords: you receive millions of first names, with reference to the leaf number, by thousands of untrusted parties. Well, since you have the correct Root you can check who you can rely on, who is giving you fake data…

Merkle trees are part of your life too! When you’re downloading a 3GB Torrent file, your file is divided in millions of little chunks. The hash of every chunk is stored in a leaf. Since you know which is the valid Root of the tree, every time you receive a chunk of the file by somebody, you can check if it’s correct. If it’s not, you can ask the same chunk to somebody else.

You can do that even if you haven’t download yet the entire tree/all the leaves: if you know that the Root is CECO and you trust JACO… when you receive the chunk ANTHONY you can verify it even if you haven’t downloaded yet the chunks MARCO and JAMES.

Why Merkle trees are useful in distributed ledger technology is straightforward: you use consensus protocols (slow, expensive) only for reaching consensus on the Root. Then the untrusted nodes of the network can efficiently and directly share data… and can sleep safe and sound thanks to integrity checks with the Root.

When God asked Ethereum to choose 2 superpowers among Security, Scalability and Decentralization… Ethereum sacrificed Scalability. Actually there is no strong cap on “transactions per second”: the cap concerns the amount of gas of each block — which is, simplifying, the amount of operations that I can do in each block. This limit is 8 million gas. That could mean many “tiny” transactions (no data attached to the transactions, no operations to be executed on that data) or few large transactions. It’s up to Ethereum’s nodes, which submit transactions, and to Ethereum’s miners, who include in the block the transactions which pay more.

A block is mined ~15 seconds. That means ~32 million gas per minute, which is definitely not enough if we want Ethereum’s dapps to go mainstream.

By the way: stop with those tedious comparisons between Ethereum and Visa. A centralized system will always be faster than Ethereum… by design! They do different stuff and you need them in different situations. If you don’t need decentralization and a trust-less environment… of course you should choose Visa. In short: the fact that your blender spins faster than your washing machine doesn’t mean you’ll clean your trousers in a blender!

Let’s put the puzzle together! Imagine you could “compress” many tiny transactions in one large transaction thanks to SNARKs. If the gas spent by this large transaction is less than the sum of the gas spent by the tiny transactions, that means you’re saving gas.

And saving gas means:

  • Users spending less for transactions overall → This would be a push for the entire ecosystem
  • Being able to put more stuff in a block → Ethereum spinning faster than your blender!

How does it work?

There are users, a relayer (or more relayers) who aggregates transactions and a smart contract.

  1. Users willing to play this game send their Ether (or tokens) to a publicly audited smart contract. For every new player a new leaf in a Merkle tree is created. The leaf includes information about the Ether’s owner (her/his address, which is also the public key), amount of Ether and nonce (the transactions’ counter of that account, which is 0 when the leaf is added)
  2. When A wants to send Ether to B (they both need to have a leaf/account in the smart contract), A packs a transaction, which includes the address of the fromaccount, the to account, the nonce of the from account, the amount of Ether to be transferred and the signature of the transaction (signed with the private key of the “from” account, obviously). She/he then sends the packed transaction to the relayer.
  3. The relayer aggregates all the transactions received in a given time window (e.g. one hour), updates the Merkle tree with the new balances’ amounts and creates a SNARK proof which proves that all signatures and the new Merkle tree’s root are valid. The relayer finally sends the new state and the proof to the smart contract.
  4. The smart contract validates the Proof on-chain. If it’s valid it saves the Merkle tree root of the New state in the internal memory of the contract.

Basically, the Merkle tree root depicts the entire state of all the accounts. And you can’t change it (= steal money) unless you can prove the validity of the signatures whose transactions lead to the New state summarized by the new root you’re submitting.

In a nutshell: users have super fast and almost free transactions, like on Coinbase, without needing to trust the relayer, who can’t do anything, unlike on Coinbase, without your signature.

It’s a non custodial side chain whose state is summarized by a Merkle tree root.

Let’s connect what we learnt above about SNARKs with what we just discussed about scaling. There are different ways to do that. I’ll compare 2 recipes: Vitalik’s and barryWhiteHat’s .

The SETUP is done by…

The guy who starts the project, who also creates the smart contract. The more auditable it is, the better.You should trust her/him… it’s a trusted setup!

The smart contract saves…

2 Merkle roots (bytes32 values): the first tree contains accounts’ addresses (public signatures), the second accounts’ balances and nonces

PROVING is done by…

The relayer

The relayer sends to the smart contract…

  • the 2 Merkle roots of the New state (addresses tree and balances+nonces tree)
  • the list of transactions, without signatures. “Each transaction costs 68 gas per byte. Hence, for a regular transfer, we can expect the marginal cost to be 68 * 3 (from) + 68 * 3 (to) + 68 * 1 (fee) + 68 * 4 + 4 * 2 (amount) + 68 * 2 (nonce), or 892 gas”

PROVING process’s known inputs are…

  • the 2 Old state Merkle roots
  • the 2 New state Merkle roots
  • transactions list

PROVING process proves that…

Given

  • the 2 Old state Merkle roots (already stored in the contract)
  • the 2 New state Merkle roots (sent in the aggr. transaction)
  • the transactions list (sent in the aggr. transaction)

… the relayer has valid signatures to move from state with 2 Old roots to state with 2 New roots with those transactions.

VERIFYING is done by…

The smart contract (coded in solidity, vyper, as you like!)

VERIFYING process’s known inputs are…

The same PROVING’s process known inputs, clearly…!

Limits to scalability

Every aggregated transaction uses 650k gas for SNARK verification (fixed cost) plus ~900 gas of marginal cost per transaction (It costs to send data!). So using the entire block the relayer can aggregate at most:

which means ~544 tx per second

barryWhiteHat’s

The SETUP is done by…

The guy who starts the project.

The smart contract saves…

1 Merkle root with the current State. Every leaf is the hashed state of an account.

Want to an account?

state = AccountState(pubkey, balance, nonce)
state.index = self._tree.append(state.hash())

PROVING is done by…

The relayer

The relayer sends to the smart contract…

  • proof 𝚷
  • the New state Merkle root
  • proof 𝚷

PROVING process’s known inputs are…

  • the Old state Merkle root
  • the New state Merkle root

PROVING process proves that…

Given

  • the Old Merkle root (already stored in the contract)
  • the New Merkle root (senti in the aggr. transaction)

… the relayer has a list of transactions with valid signatures to move from state with Old root to state with New root

VERIFYING is done by…

The smart contract (coded in solidity, vyper, as you like!)

VERIFYING process’s known inputs are…

The same PROVING’s process known inputs, clearly…!

Limits to scalability

The relayer is not sending transactions’ data to the smart contract (which is costly), so the limit is actually the amount of gas to verify the SNARK proof.

Mentioning Howard Wu’s about running SNARK’s PROVING phase on distributed systems, barryWhiteHat optimistically states that is possible to confirm 16666 transactions in a huge SNARK (1 billion constraints!).

barryWhiteHat also it’s possible to verify proof 𝚷 on-chain with 500k gas, which means that you can put 16 SNARKs (8 million/500k) per block, which is ~1.07 SNARKs per seconds… which means ~17,832 tx per second (16,666 * 1.07).

To infinity and beyond

  • All that glitters is not gold / 1. The amount of computing power and memory that you need in the Proving phase can be literally shocking. Especially in barryWhiteHat’s version, where part of the complexity is moved off-chain. barry writes “On a laptop with 7 GB of ram and 20 GB of swap space it struggles to aggregate 20 transactions per second”. Well, if the goal is 17,832 tx per second… LOL. This introduces non trivial parallel computation challenges. But if the average $ cost per transaction is far cheaper than the ordinary no-SNARKs option… the game is worth the candle.
  • All that glitters is not gold / 2. There is a relevant data availability issue! Since only the tree’s root is saved in the contract, you must be sure that an entire version of the tree (or, it’s the same, the entire transactions history) is always available. If data is not available the relayer, even with valid signed transactions, can’t do anything because she/he can’t prove Old State → Transactions → New State.
  • In order the relayer to be trustless and Ethers in the contract to have the same value of Ethers outside (liquidity problem)… users should be able to withdraw money from the smart contract when they want, without relying on a (specific) relayer. How? This is not in the scope of this 101 post, but you can read about this in the enclosed links.
  • Want to understand more about how the current State (addresses, balances and nonces) can be handled with a Merkle tree? Adding a leaf, updating a leaf, etc? Check out (test file ) which uses this underlying . Thanks HarryR!
  • Want to setup your personal Ethereum-SNARKs environment? Let’s start off-chain with C++ (Setup, Proving, Verifying) . Then you can move to Ethereum (don’t forget, only the Verification is done on-chain!) with Zokrates (, the ).
  • How about using RSA accumulators instead of Merkle trees? Google “rsa accumulators ethereum” to start…

Enjoy!

Twitter

Source: https://tokeneconomy.co/how-ethereum-can-scale-with-snarks-101-5b06ff048bb7?source=rss—-fbbd350c08fc—4

Blockchain

Just One Client Dominates Ethereum 2.0 Testnet

Prysm ethereum 2.0 testnet, Oct 2020The ethereum 2.0 Medalla testnet has five node clients, but just one of them is being used by the vast majority of nodes. Despite a week long network crash in…

Published

on

The ethereum 2.0 Medalla testnet has five node clients, but just one of them is being used by the vast majority of nodes.

Despite a week long network crash in August due to a small bug in Prysm, that client is still being used by some 60% of the network.

That’s way more than enough to take the whole thing down as knocking off only 33% of the nodes is sufficient to prevent ethereum 2.0 from finalizing.

Once the network can not finalize, it effectively stops working, something that would cause chaos in a live ethereum network that holds some $11 billion in defi.

The second most popular client is Lighthouse with just 36 nodes out of 155, making it 23% according to our own research based on eth2stats.

If this client goes down there could be problems, but not fully critical problems like were anything to be exploited in Prysm.

Teku has 15 nodes out of 155, less than 10%, with Nimbus at 9 and Lodestar at just 2.

It’s not clear why Teku and Nimbus are not finding much use, but in this testnet we have a Pareto distribution between dominating Prysm and way behind Lighthouse, with then the rest even more behind in network share.

It’s not clear whether there’s anything that can be done about this as if it replicates in the live network, then there would be significant problems temporarily if Prysm nodes are DDoS-ed for example.

These open networks are somewhat easy to DDoS and there’s so many ways to do it, you can’t fully protect from it but you can minimize or even avoid it in bitcoin by not having open connections on your node.

In ethereum 2.0 there’s probably minimization strategies as well, but Prysm nodes are currently nearly twice the amount required to take down the network. Just half of them would be close to enough.

Prysm is working on a method to quickly export your validation to another client, but it’s not too clear whether that is something that can easily be done.

Nor is it too clear whether node operators can effectively be persuaded to maintain a less than 30% share per client.

Continue Reading

Blockchain

Market Analysis Report (01 Oct 2020)

Twitter’s Jack Dorsey Calls Out Coinbase For its Apolitical Stance | MakerDAO Adds Chainklink, Compound, and Loopring as DAI Collateral Options | IRS Paying up to $1.25 Million for Data Firms to Break Privacy-Centric Coin Monero

Published

on

Wolf.bet is a licensed cryptocurrency gambling casino known for its mobile-first approach and low house edge (1%). Their VIP program incentivizes players to wager by giving them up to 30% rakeback on every bet they place.

Another known feature is the daily $1000 wagering contest, rewarding 50 winners per day, totalling $30,000 in prizes and 1500 winners monthly.

Wolf.bet has an affiliate program that gives you 5% from the house edge collected on every bet your referrals place on the casino.

Gaming Experience

Thanks to their advanced Dice and Limbo features you have infinite possibilities when creating strategies and tremendous speed of 2.000 bets per second thanks to their Flashbet feature.

With two modes (easy and expert) you are able to diversify your gameplay on Dice and Limbo games.

Bonus and Promotions

Wolf.bet offers a 7-Day Streak bonus, a bonus you can claim by logging in daily and that gets increased as the days go by, resetting on the 8th day. They also host promos and giveaways across the web and chat games and rains every 20 minutes

Provably Fair

The casino is 100% provably fair, owning an RNG certification. Players can also change their server and client seeds anytime.

Customer Support

Wolf.bet live support is active 24/7 on the site or via [email protected]

Security and Payment Methods

Wolf.bet detains a certificate of RNG validity issued by iTech labs and an Antillephone License Validation, authorized and regulated by the Government of Curacao.

The platform currently supports several cryptocurrencies like Bitcoin (BTC), Ethereum (ETH), Bitcoin Cash (BCH), Tron (TRX), Doge, Litecoin (LTC) and Ripple (XRP) being the latest one introduced.

Key Features

• Mobile Focused Experience
• Fast and smooth dice gaming
• Daily $1000 Wagering contest (TOP 30 Winners)
• Up to 30% Rakeback
• Active 24/7 Multilingual Customer Support
• Licensed Cryptocurrency Casino
• Multiple Chat Rooms
• 7 Cryptocurrencies
• Affiliate System
• Anonymous

Continue Reading

Blockchain

New in Chainlink: More DeFi Price Feeds, Gitcoin Support, Novel Integrations, & More

Published

on

Follow decentralized oracle project Chainlink even casually? Then you know its builders and community move fast and stay busy, so keeping up with all the happenings around the Chainlink ecosystem is no small feat.

No worries, though: in today’s post we’ll catch you right up by breaking down Chainlink’s biggest highlights from the past two weeks. First up, let’s talk the project’s bread and butter, i.e. price feeds.

New Price Feeds

Chainlink’s oracles help smarten up on-chain smart contracts by serving as reliable bridges by which they can access off-chain data. The most dominant of Chainlink’s “bridges” today are its price feeds, which serve decentralized finance (DeFi) apps with accurate, real-time price info.

Accordingly, Chainlink’s growing ranks of price feeds have already proven extremely useful around DeFi, and the project’s adding more feeds all the while. Recent significant additions include:

Aave’s LEND, yEarn’s YFI, and Ethereum’s rising tokenized bitcoin projects are some of the most popular tokens in Ethereum’s DeFi sector, so these new Chainlink price feeds will surely see no shortage of use in the months ahead and beyond.

New L1 & L2 Integrations

Ultimately, Chainlink is blockchain agnostic. It’s rise has largely been built atop Ethereum, but it’s capable of providing decentralized oracle networks for layer-one smart contract platforms in general. Chainlink’s recent advances in L1 integrations include work with projects like Blockstack and Reef.

Indeed, on Wednesday, September 30th, decentralized apps network project Blockstack announced it was working with the Chainlink team to “integrate Chainlink as the preferred oracle solution” for Blockstack’s Clarity smart contract language.

“Given our familiarity with and knowledge of Chainlink’s impressive team and technology, we are confident that this partnership and resulting Chainlink oracles will advance our shared ecosystem,” Blockstack co-founder Muneeb Ali said on the news.

Moreover, Reef, a cross-chain smart asset management platform built on Polkadot, also just revealed it was integrating Chainlink’s price feeds to access DeFi pricings “denominated in both ETH and DOT.”

The decentralized oracle project has also been involved with notable layer-two scaling forays lately. For example, synthetic assets protocol Synthetix, which relies on Chainlink’s oracles, is now live on the L2 Optimistic Ethereum Testnet. Additionally, L2 scaling platform Matic Network is presently working on integrating Chainlink’s tech into its mainnet.

More Gaming Integrations

Beyond Chainlink’s flagship oracle tech, the Chainlink VRF solution — which helps products generate verifiably random results on-chain — has become a hit in the blossoming blockchain gaming arena.

Just this week, Aave’s up-and-coming Aavegotchi NFT game project announced its mechanics would “make full use of Chainlink VRF,” adding:

“Each Aavegotchi summoned needs to be randomly generated with a massive variety of intrinsic qualities, including visual traits, wearables, and collaterals. These unique Aavegotchi are then able to again engage Chainlink VRF for many of our mini-games and AavegotchiDAO experiences.”

Another NFT gaming project that’s going all-in on Chainlink is Planetarium, which revealed on Tuesday, September 29th, that it was integrating Chainlink’s tech to “power cross-game Metaverse communication, in-game commodity pricing, and secure trading of in-game items.”

Chainlink Makes Grant Moves

Gitcoin Grants is a respected ecosystem project that provides matching funds (therefore boosting grassroots donations) to open-source projects building around Ethereum. And now Chainlink’s pitching in to help the funding.

That’s per an announcement last week that the project would be providing an influx of funding to help support the ongoing Gitcoin Grants 7 campaign.

Earlier this month, Chainlink also revealed it was giving a grant to blockchain infrastructure project SimplyVC. The purpose of the funding is to help the firm “build its PANIC monitoring and alerting system for the Chainlink Network so it can be leveraged by Chainlink Nodes.”

991

Source: https://blockonomi.com/chainlink-defi-price-feeds-gitcoin-more/

Continue Reading

Trending