New paper: Accelerating Bitcoin's Trasaction Processing

[jtimon]

Nobody said that propagation delays are the *only* obstacle. We said they are currently the *primary* obstacle, because currently you will run into the trouble at much lower tps.

That's what I understood here:

Surely you must agree that if there were no block propagation delays, there would be no centralization associated with scaling up. Blocks go instantly to everyone, and there are no problems with miners getting more than their share of the blocks.

I agree with you that it is quite likely that BTC is less scalable than the dollar and other centralized systems, but it is worth it to try and get as close as possible. Plus, you still can't completely rule out the chance that someone will find a way to distribute the workload and not just distribute trust among the many nodes.

That's were we disagree, I think. As close as possible may be sacrificing too much decentralization.
As said, this doesn't mean that the proposal isn't interesting for increasing scalability to a "decentralized-enough level", whatever that is.

Plus, you still can't completely rule out the chance that someone will find a way to distribute the workload and not just distribute trust among the many nodes.

Distributing the validation workload would be ideal. But I think that such a system (if possible) would be very different from bitcoin in several ways.
You would need some zero knowledge proof (ZKP) system so that the rest of the nodes could trust a single validator. I'm also very interested in that kind of proposals.

[1714118837]

1714118837

[1714118837]

1714118837

[1714118837]

1714118837

[1714118837]

1714118837

[iddo]

jtimon, why zero-knowledge? And relying on a single validator is bad, because that validator could deny txns.

[jtimon]

jtimon, why zero-knowledge? And relying on a single validator is bad, because that validator could deny txns.

I don't mean a single validator. But if validator A validates tx1 and you don't want all the other validators to also validate tx1, they could use a ZKP provided by validator A.
If validator A doesn't want to validate tx 1, validator B can do it, no problem.

Maybe there's other ways to distribute the validation workload, but that's what initially comes to mind.
Another approach could be to don't validate anything but timestamp everything and leave the validation to non-miner nodes using the sequence of transactions, but that looks less SPV-friendly.
I was just thinking out loud, but this is kind of off-topic.

[TierNolan]

Maybe there's other ways to distribute the validation workload, but that's what initially comes to mind.

Is it not the case that checking zero-knowledge proofs is more complex than actually doing the calculations directly? 

For example, would checking a zero knowledge proof that a signature is valid be faster than just checking if the signature was valid?

Anyway, why not just have different nodes validate a sub-set of the transactions. 

Each node picks a random byte and only validates transaction inputs that start with that byte.

This could be combined with a system where a broadcast can be made if a block contains an invalid transaction.

Nodes could still check the entire block, as now, except that only 1/256 of the signatures would be checked.

In addition, node would only need to store 1/256 of the transactions in each block.  That reduces disk usage and CPU load.

Checking that minting/tx fees are correct doesn't use much CPU.  The main cost is bandwidth.

Maybe the Blook filter system could be used rather than a prefix.  A node specifies a Bloom filter and only ever receives those transactions.  A reduced size block packet could be sent which just has the hashes of the transactions.

Transaction inputs that point to non-existent transactions are a problem though.  There would need to be some DOS protection for messages that transaction inputs are invalid since they don't point to an actual transaction output.  You can't prove non-existence.

[iddo]

Guys, what you're talking about doesn't benefit from zero-knowledge, please google "succinct non-interactive argument of knowledge" or "probabilistically checkable proof", i.e. you'd like to have SNARK and not necessarily zk-SNARK here.

[jtimon]

Guys, what you're talking about doesn't benefit from zero-knowledge, please google "succinct non-interactive argument of knowledge" or "probabilistically checkable proof", i.e. you'd like to have SNARK and not necessarily zk-SNARK here.

Sorry, iddo but I'm just starting to learn about zkp/snark/scip.
I thought snark was just a technique to generalize ZKP, I didn't knew about snark vs zk-snark.
What I mean you need this kind of cryptography if you want all nodes to trust a node's validation without repeating it themselves.

Is it not the case that checking zero-knowledge proofs is more complex than actually doing the calculations directly?  

For example, would checking a zero knowledge proof that a signature is valid be faster than just checking if the signature was valid?

If that was the case for both zkp and snark, then they are useless for distributing the validation workload.
But I think it's not the case. Maybe someone who knows more about this can answer you better.

Anyway, why not just have different nodes validate a sub-set of the transactions.  
...

Yes, that's what "distributing the validation workload" is about.
I'm not sure I understand your proposal or why some nodes can trust others, but this is definitely getting off-topic.

[maaku]

I think the point of being zero knowledge is that you don't have to download the blockchain, no?

[iddo]

I think the point of being zero knowledge is that you don't have to download the blockchain, no?

Maybe you're confusing zero-trust with zero-knowledge?

[maaku]

Maybe. The proof needs to be verifiable without any blockchain data. Regular SNARKS can do this?

[MatthewLM]

I was thinking about this myself. Could you use a zero-knowledge proof to validate the block-chain without needing the actual block-chain? I don't know very much about it at all.

[MatthewLM]

I read part of the paper. In layman's terms, the "GHOST" parent selection of blocks takes into account the work of all the blocks that are children of a block which is a candidate to be made parent. Therefore it takes into full account the hash distribution of the network. In the current system, if the time between blocks was reduced significantly, then blocks which are propagated slowly will be placed on a side-chain as they will lose out in the propagation race, therefore, unlike the "GHOST" system, the current system cannot take the full hash-distribution into account.

Now if only that was explained in the abstract, it would have saved me so much time!

[iddo]

Maybe. The proof needs to be verifiable without any blockchain data. Regular SNARKS can do this?

I was thinking about this myself. Could you use a zero-knowledge proof to validate the block-chain without needing the actual block-chain? I don't know very much about it at all.

The answer is yes, but why do you guys keep resurrecting zero-knowledge back into this discussion?

Here's a talk from the 2013 Bitcoin conference by my PhD supervisor about it: http://www.youtube.com/watch?v=YRcPReUpkcU

You can think of it as some specified C or assembler source code having a similar role to that of ECDSA pubkey, and a succinct form of an execution of this source code as having a similar role to that of ECDSA signature. Given this "pubkey", everyone can verify that the "signature" indeed corresponds to a valid execution of that C/assembler program and that this execution terminated with the required output. The probability that an invalid "signature" will pass this verification algorithm is negligible. So in order to "compress" the blockchain, we specify the C/assembler code that checks the blocks from genesis until a certain checkpoint block, and compute a "signature" for an execution this computation, so that nodes can verify with zero-trust that this checkpoint is valid without downloading all the blocks since genesis, and without the need to fetch any blockchain data (to answer maaku's question). Saying that this "signature"/proof is zero-knowledge just means that it doesn't reveal any additional information besides the single bit that says whether in this execution all the blockchain blocks indeed passed validation (an example of additional info is, say, that this "signature"/proof leaks that Alice sent Bob 5 coins at some block). Why do you guys care about zero-knowledge in this regard?

[jtimon]

Why do you guys care about zero-knowledge in this regard?

I think we just tend to confuse snark/scip with zero knowledge.

[ShadowOfHarbringer]

* ShadowOfHarbringer is watching this.

[MatthewLM]

Why do you guys care about zero-knowledge in this regard?

Because nodes wouldn't need to store and validate the block-chain. It only needs to be validated once. The output of the validation could be the unspent outputs, so that all miners need is the last block alongside the unspent outputs. Then they can build upon that. Non-miners would simply verify the proofs in the blocks and take the unspent outputs relevant to them. Why is this not a good idea?

How would anyone actually start developing a crypto-currency that worked in such a way? It all seems very theoretical to me.

[iddo]

The output of the validation could be the unspent outputs

Long output will blowup the complexity, the output can be boolean, where the hash the UTXO set is an input.

Why is this not a good idea?

It's a great idea, but what does it got to do with zero-knowledge?

How would anyone actually start developing a crypto-currency that worked in such a way? It all seems very theoretical to me.

When an efficient SNARK implementation is available, there's a good chance that the Bitcoin devs will integrate this option.

[MatthewLM]

It's a great idea, but what does it got to do with zero-knowledge?

I suppose it's partially zero-knowledge as you wouldn't need all of the inputs to the program. I did read somewhere that the SNARK programs can have public inputs as well as arbitrary inputs which are unknown to verifiers. Is that right? Some details would be hidden to the verifier, such as the transactions.

[jtimon]

The output of the validation could be the unspent outputs

Long output will blowup the complexity, the output can be boolean, where the hash the UTXO set is an input.

I thought it would be something like

inputs: prev_utxo_tree_hash, transaction set for current block
output: utxo_tree_hash

or

F(prev_utxo_tree_hash, transaction set for current block) = utxo_tree_hash

I did read somewhere that the SNARK programs can have public inputs as well as arbitrary inputs which are unknown to verifiers. Is that right? Some details would be hidden to the verifier, such as the transactions.

If this is correct then another node would just need prev_utxo_tree_hash, utxo_tree_hash and the signature of the execution of F to validate that the block was correctly processed. Doesn't even need the transactions.

Sorry again if I'm saying something stupid about snark, this is still like magic to me so it's hard to retain what can and cannot be done.

[Cryddit]

As I understand it, you generate a verifiable 'trace signature' of a program run which bears a distinctive cryptographic relationship with the code itself; it can be considered to be 'signed' by the code used to create it.

But GIGO still applies.  Given the same starting point, the same code could run with different input, then you can give 'trace signatures' to two different people to verify, and have two people verify that the code ran correctly and those two people will still have different results. 

However, for some data structures, if you are given the starting point, the 'trace signature' AND the results, you can verify that the starting point was transformed into the results via the 'signed' run of the code, even if that valid run had unknown inputs.  This is possible with some structures and not others, but because of the cryptographic chain-of-evidence qualities, the Bitcoin Blockchain is one of the finest examples of a structure that it *DOES* work with.

But I think this is going rather far afield from the original intent of this thread, which was to make Bitcoin able to handle more transactions per second.

[halvoraarud]

You guys have made the biggest contribution to the biggest problem with cryptocurrencies, transaction times.
Now we just need to implement it + zerocoin support. Ahh how i love open source.

I would also like to see some kind of community interest rate in the currency, similar to what was outlined here: https://docs.google.com/document/d/1302Fb5BpgTRS2P-snN4ys5JR3l8QU2QhpncldAYaXfM/edit?usp=sharing

No currency can have limited supply and stable prices.

Besides that, I think we are on to a winning formula, yes.

HA