Kimchi: The latest update to Mina’s proof system | Hacker News Reader

Kimchi: The latest update to Mina’s proof system

minaprotocol.com

81 pointsbaby31 comments

Congratulations to the cryptographers and engineers at Mina for shipping this. We are getting palpably close to efficiently provable general computation. (For others interested in the evolution, see TinyRAM and the various zkEVM efforts especially zkSync2. This is a fascinating development in CS with wide implications.)

My issue with Mina as a platform is the token distribution. It's over 50% allocated to insiders: https://minaprotocol.com/blog/mina-token-distribution-and-su...

(Note that of the 1m initial tokens, slightly over half is "backers", "core contributors", and the two foundations. Since Mina is proof-of-stake, all ongoing issurance goes to existing tokenholders, so we can expect that Mina will always be over 50% insider owned unless they sell.)

> all ongoing issurance goes to existing tokenholders

David Rosenthal also raised this issue in his recent blog entry [1]:

"It isn't just that the Gini coefficients of cryptocurrencies are extremely high[4], but that Proof-of-Stake makes this a self-reinforcing problem. Because the rewards for mining new blocks, and the fees for including transactions in blocks, flow to the HODL-ers in proportion to their HODL-ings, whatever Gini coefficient the systems starts out with will always increase. Proof-of-Stake isn't effective at decentralization."

[1] https://news.ycombinator.com/item?id=30310317

Is the Gini coefficient a valid measure here?

I haven't read the blog entry, but the logic here doesn't make sense to me. If everyone gets a 5% return on their stake, the gini coefficient doesn't change at all. Probably small holders never stak and so never get any return, but these people were never going to run nodes anyway so I don't know if it matters.

Furthermore, let's say it costs $1000 to set up a PoW mining rig, compared to $1000 to buying a stake big enough to let you validate. I'm not sure it makes such a big difference in either case.

> If everyone gets a 5% return on their stake,

Transaction fees slightly tip the balance from transactors to hodlers.

> let's say it costs $1000 to set up a PoW mining rig

Setting it up does nothing. You have to pay the ongoing electricity bill, which most miners do by selling a substantial fraction of their mined coins.

David's post seems pretty confused.

> Because the rewards for mining new blocks, and the fees for including transactions in blocks, [...] whatever Gini coefficient the systems starts out with will always increase

That doesn't follow at all. If everyone staked their coins and nobody ever bought or sold, the distribution would remain constant over time. In reality, coins do trade, and this causes diffusion. Coin ownership can decentralize over time.

In practice, proof-of-stake is better for distributing ownership than proof-of-work, because the block rewards (new issuance) go to a wider set of participants. Staking can be done by anyone, while mining profitably requires a specialized operation with large upfront capital costs.

Finally, be wary of anyone quoting Gini coefficients for blockchains. Gini only makes sense if calculated per person. If you calculate Gini from on-chain address balances, you get numbers that are wildly off. See https://vitalik.ca/general/2021/07/29/gini.html

Debates about cryptocurrencies aside, that website is beautiful. Colours are nice, aesthetics are great, without being too retro and the performance is good.

Can the provers in this blockchain also get away with not storing any of the underlying chain data?

Yes. The proof of block n's validity proves both that the state transition from block n-1 to block n is valid and that the previous block's proof was valid. The arithmetic circuit for a state transition proof actually encodes a program which verifies SNARK proofs (in addition to the less academically interesting "doesn't create $ out of thin air" sort of rules). The proof of the latest block at any height (which is all the state you need to know you're on at least a valid chain history) remains constant size because of the indirection of proving that a verifier accepts the last block's proof without actually including it (taking advantage of the fact that a zero-knowledge proof doesn't have to include or even reveal the data it's proving something about).

Thanks for this explanation.

Do you know anything of how Mina would handle things that need to exist in the public state of a blockchain, but which cannot be learned from the 22KB proof—for instance, DeFi smart contracts? For something like a DeFi DEX to be useful, it's not enough to know that specific operation succeeded. It has to be possible for anyone to invoke the operation themselves, and that means that the state of the smart contract, and the contract's executable code, need to be publicly known.

These are called snapps in Mina, basically the state of a smart contract is nothing more special than the balance of an account, so you can store it on the blockchain in the same way. Now Mina is a succinct blockchain and zkp allows most data to be stored off-chain so I think the idea will be to limit heavily the amount of on-chain data.

I just get the feeling that "on-chain data" doesn't mean the same thing in Mina as it does with other blockchain systems. The 22kb is a ZKP and would not contain any contract logic or contract data, I think, so any contract data and logic would have to come from another source.

The 22kb, which is more like 11kb I believe? is a proof of the state, you don’t get the balances of all accounts within the proof itself, that’s something you need to download separately.

Each block contains a commitment to the state of the chain in the form of a Merkle tree. In that regard it's not that different from Bitcoin's MAST or Ethereum's (WIP) stateless clients. To prove something (say, an account balance) is in the block, one would need to know the data you're trying to prove as well as its Merkle path in that block's tree.

> that means that the state of the smart contract, and the contract's executable code, need to be publicly known.

Yes, they would need to be separately distributed somehow. But I think this is similar to how Ethereum contracts typically have their source code (and by extension ABI) uploaded to Etherscan, without which they'd be difficult to interact with.

> Do you know anything of how Mina would handle things that need to exist in the public state of a blockchain, but which cannot be learned from the 22KB proof—for instance, DeFi smart contracts?

A good rule of thumb is that Mina full nodes behave like other blockchains' light clients that just happen to sync quickly & trustlessly. I am not an expert on smart contracts, but I think in practice, a Mina DEX would probably work something like this:

- You visit minaswap.io or whatever (or a copy on IPFS). The static page includes a copy of the contract's interface.

- The page tries to call a hypothetical Mina browser extension running a full node in the background. If it's installed, it uses it; otherwise, it downloads & runs a Mina full node compiled to WASM as a "polyfill".

- As the WASM node syncs & verifies the latest block's proof, it asks someone for the contract's current state and the Merkle path to it within the block.

- Once the node has synced, it verifies the contract's data is actually in the Merkle tree using the given path. Now we know the interface & state of the contract and that's all we have to keep locally.

Also: although block producers don't necessarily have to, provers always keep a copy of the current ledger state (see my above comment; sorry if my first comment was a bit misleading). This would include smart contracts' state (but not their code). If you run one of these nodes, it knows every contract's state, which should still be small compared to Ethereum as so much can be done off-chain.

I realized this is misleading as an answer to your question, but it's too late to edit. Block producers (i.e. miners) don't need to keep track of chain state, but provers need to know the state of block n-1 to generate a proof for block n. In practice, the current state is pretty small, but admittedly way more than 22KB: I just synced a node and its data directory is 235MB.

The zero-knowledge proofs still provide the advantage that historical state doesn't need to be kept by anybody: if news of a better chain tip comes along (including while bootstrapping), it'll come with a recursive proof of its validity, whereas with Bitcoin et al. it'd need to check if it's building on a valid block (and thus keep at least the hashes of previous blocks).

Very cool and unexpected to see something we worked on on HN!

If you’re a good hacker who wants to work on this stuff (Rust, C++, or OCaml especially) we’re hiring cryptography engineers[0] and offering training on all the relevant cryptography.

We’re also majority worker-owned and worker-governed which is a rare perk for VC funded startups :0

[0]: https://boards.greenhouse.io/o1labs/jobs/4023646004

does this version of SNARK require a trusted setup (a ceremony)?

plonk based proof system can take advantage of an existing universal setup (like Powers of Tau ceremony). I’d be curious to know more about how Mina approaches this though.

Hi - I work on proof systems for Mina. Our proof system does not require any trusted setup. It uses a polynomial commitment scheme based on the setupless scheme used in bulletproofs (the version we use is close to the one described in this paper https://eprint.iacr.org/2020/499.pdf), which is based on the hardness of discrete-log.

Some SNARKs use pairing-based polynomial commitment schemes, which require a trusted setup (and some require a trusted setup for other reasons.)

As someone not very knowledgeable with cryptography, what practical benefits would such a blockchain have? What benefits would we see with widespread adoption?

zk proofs could be used to add privacy features to a blockchain, but also verifiable computation. Ethereum smart contracts are bound by “gas” as they run on-chain (and so highly expensive computation is infeasible), in Mina the smart contract computation can execute on the user’s own machine; only the lightweight zk-SNARK proof is submitted to the network.

Zk proofs also enable some novel forms of verifiable attestations. For example proving that you have sufficient funds for a bid, or belong to a group of addresses, or know something private, without revealing any additional information about it.

I've never seen this before, but this is a bit odd:

> the entire Mina blockchain is about 22KB – the size of a couple of tweets

When did we get 11,000 character tweets?

Certainly looks very interesting otherwise, hopefully it'll be used for more than speculation and money laundering.

From a developers perspective the size of a tweet is typically greater than the character count of its text:

https://developer.twitter.com/en/docs/twitter-api/data-dicti...

Ah yeah, you're right, I forgot about wide modes etc.

22 tps? Is this still correct?

https://www.youtube.com/watch?v=Zj6rNewnbrw

See https://medium.com/minaprotocol/answering-community-question...

thanks

I never heard of this before, went to the site, saw it's some new blockchain rugpull with a new coat of paint, and closed the tab. I mean, they literally want me to be a "snark producer", so here we go.

I don't care to defend a blockchain company, however, Mina has been about for a while and is one of the groups actually investing in engineering + tech. Maybe worth another look? If you can persevere past the disgust indicing food names

Most people don't understand this stuff so they'll take it at face value even though it's likely a scam

Zero knowledge proof are larger than crypto-currency. I think snark is one of the algorithms that implements it ( again, nothing to do with cryptocurrency )

But correct, that’s a blockchain thingy.

Reply on news.ycombinator.com