Bitcoin Forum
October 01, 2023, 12:50:46 PM
 News: Latest Bitcoin Core release: 25.0 [Torrent]
 Home Help Search Login Register More
 Pages: [1]
 Author Topic: Defining algorithmic complexity of a blockchain protocol  (Read 171 times)
tromp (OP)
Legendary

Offline

Activity: 921
Merit: 1024

 February 21, 2021, 10:25:00 AMMerited by ETFbitcoin (1), zeuner (1)

In Algorithmic Information Theory [1] one studies the minimal number of bits needed to describe objects.
Normally the objects studied are just binary strings. For instance, the first million bits of pi in binary.
Random as they may look, the fact that they can be generated by a small program shows that they are anything but.
A truly random string of n bits would take a program of length at least n bits to describe it. With only 1+2+...2^{n-1}
= 2^n - 1 possible descriptions/programs shorter than n bits, it's clear that such a random bitstring must exist.
What if we want to extend this notion of descriptional complexity to blockchain protocols?
This would allow us to quantitatively compare the complexity of different coins.

It remains to answer two questions.
1) What programming language do we use to encode the protocol?
2) What is it that the program would do?

For 1) we could pick a common popular language like C99.
For 2) we could have a program that will interact with the network and a payer to receive 1 coin and see it confirmed.

Does this seem like a reasonable definition? Does it capture all the complexity of a blockchain protocol? Could it be further simplified?

[1] https://en.wikipedia.org/wiki/Algorithmic_information_theory
1696164646
Hero Member

Offline

Posts: 1696164646

Ignore
 1696164646

1696164646
 Report to moderator
1696164646
Hero Member

Offline

Posts: 1696164646

Ignore
 1696164646

1696164646
 Report to moderator
1696164646
Hero Member

Offline

Posts: 1696164646

Ignore
 1696164646

1696164646
 Report to moderator
Each block is stacked on top of the previous one. Adding another block to the top makes all lower blocks more difficult to remove: there is more "weight" above each block. A transaction in a block 6 blocks deep (6 confirmations) will be very difficult to remove.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
odolvlobo
Legendary

Offline

Activity: 4088
Merit: 3033

 February 22, 2021, 10:28:51 PM

I'm not an expert in Algorithmic Information Theory, but I understand the premise.

First I want to point out a misconception. The term "random" describes a process and not the individual values generated by that process. The fact that the first million digits of pi can be compressed does not make the digits of pi not random. The value 2256-1 might not seem random, but if it is generated by SHA-256, then it is because SHA-256 is random.

Anyway, ...

1. I wouldn't pick a general purpose programming language. These languages would come with a lot of baggage making actual measurement infeasible if not impossible.
2. What do you mean by the complexity of a block chain protocol? I would measure the validation rules, since those are what ultimately determine the output.

Join an anti-signature campaign: Click ignore on the members of signature campaigns.
PGP Fingerprint: 6B6BC26599EC24EF7E29A405EAF050539D0B2925 Signing address: 13GAVJo8YaAuenj6keiEykwxWUZ7jMoSLt
NotATether
Legendary

Offline

Activity: 1372
Merit: 5822

 February 23, 2021, 04:21:54 AM

1. I wouldn't pick a general purpose programming language. These languages would come with a lot of baggage making actual measurement infeasible if not impossible.
2. What do you mean by the complexity of a block chain protocol? I would measure the validation rules, since those are what ultimately determine the output.

It's better to avoid any Turing complete language to represent state, so you don't have to deal with invalid states which are inventible in languages that let you use unlimited loops.

Amazon States Language looks like a good way to represent protocol intrinsics and consensus rules (maybe the number of these is what OP means by 2.)

There is also ASML by Microsoft but I couldn't find any specification for it.

 ...M. MixTum.io ▀▄ Premium Bitcoin Mixer ▄▀ ████████████████████████████████ ███████████████████████████████████████████████████████████████.MIX FREEUp to 1mBTC.███████████████████████████████████████████████████████████████ ████████████████████████████████ █████████████████████████████████████▀▄▀████████████████████▀█▄███████████████████▀▌█▄████████████████████▌▄█████████████████████▀▄███▀███████████████▀▄▄███████▀████████████▀▄█▀▄███████████████████████▀▄█▌▐████▐███████████▌▐██▀▌▐█████▐██████████████████████▄█████████████▄▄██████▄████████████████████████████████
zeuner
Member

Offline

Activity: 185
Merit: 15

 February 26, 2021, 10:24:39 PM

In Algorithmic Information Theory [1] one studies the minimal number of bits needed to describe objects.
Normally the objects studied are just binary strings. For instance, the first million bits of pi in binary.

For a static binary string, you are looking at programs that compute something with no input involved.

For a blockchain protocol, it seems unlikely that a static binary string would be representative for what constitutes the protocol. Most likely, you'll want to look at at least one protocol operation that involves an input (say, from another node).

After deciding what exactly to study here, it may be easier to determine a good definition for the complexity measure.

For 2) we could have a program that will interact with the network and a payer to receive 1 coin and see it confirmed.
What if there is a program that can do the operation with less complexity using a SPV-based protocol? We will probably agree that this cannot cover all the complexity of the blockchain protocol since the protocol could not work with only SPV nodes being present. If so, the definition should be designed in a way so that this is not considered as valid.
aliashraf
Legendary

Offline

Activity: 1456
Merit: 1170

Always remember the cause!

 February 26, 2021, 11:10:01 PM

OP,
Besides that I'm suspicious about the original problem you put forward here as being a fruitful one because I tried but didn't find any application, I oppose the strategy you suggest.

As @zeuner correctly reminded above, a blockchain is not just an algorithm or a protocol, you can't represent it by any form of abstraction because it holds and preserves events from the real world. To represent Bitcoin blockchain for instance, the most efficient way would be expressing the state of the system which could be efficiently summarized in a canonical form of the UTXO, period.

On the other hand, if supposedly you are concerned about formalizing the protocol, I don't think programming language and code base would yield anything significant. Protocols are efficiently representable as finite state machines, this technique is applicable both for the p2p network and the consensus protocols while we have the notorious relational theory that gives an excellent notation of FSM.

I may have missed something here, otherwise I think what you are looking for should be viewed from such perspectives.
tromp (OP)
Legendary

Offline

Activity: 921
Merit: 1024

 February 27, 2021, 08:03:25 AM

For 2) we could have a program that will interact with the network and a payer to receive 1 coin and see it confirmed.
What if there is a program that can do the operation with less complexity using a SPV-based protocol?

SPV should be excluded, of course. We want the program to fully verify that it has been paid 1 coin,
even in the presence malicious miners with a majority of hashpower, that can make incorrect history
appear to be the most worked on branch.
tromp (OP)
Legendary

Offline

Activity: 921
Merit: 1024

 February 27, 2021, 08:06:59 AM

To represent Bitcoin blockchain for instance

As I explained already, I'm not interested in describing the blockchain data.

I'm only interested in describing the rules for recognizing the longest (highest cumulative difficulty) valid chain,
and whether that includes a payment to me.
aliashraf
Legendary

Offline

Activity: 1456
Merit: 1170

Always remember the cause!

 February 27, 2021, 12:52:50 PM

To represent Bitcoin blockchain for instance

As I explained already, I'm not interested in describing the blockchain data.

I'm only interested in describing the rules for recognizing the longest (highest cumulative difficulty) valid chain,
and whether that includes a payment to me.

Firstly, the MLC problem is a trivial one as far as it is seen from an SPV perspective (which it should  be, by the way) and I don't think it yields meaningfully different results for different protocols because they could simply adopt the best scheme without going through major changes.

As of the inclusion problem, I suppose it has also something to do with light clients/wallets (not necessarily SPVs) because we are now in the territory of state commitment, i.e. continuously committing to the total state of the blockchain in each block.
Again any blockchain protocol is capable of supporting state commitment almost trivially and seamlessly, so we are ending in the same situation as with the MLC problem.

odolvlobo
Legendary

Offline

Activity: 4088
Merit: 3033

 February 27, 2021, 09:49:15 PMMerited by ETFbitcoin (1)

Here's an interesting idea:

Write the rules in Solidity and run them on Ethereum. The gas cost will tell you the complexity.

And a side benefit is that you now have a node running on Ethereum.

Join an anti-signature campaign: Click ignore on the members of signature campaigns.
PGP Fingerprint: 6B6BC26599EC24EF7E29A405EAF050539D0B2925 Signing address: 13GAVJo8YaAuenj6keiEykwxWUZ7jMoSLt
tromp (OP)
Legendary

Offline

Activity: 921
Merit: 1024

 February 28, 2021, 07:18:31 AM

Write the rules in Solidity and run them on Ethereum. The gas cost will tell you the complexity.

It would the contract size that defines the complexity.
ETFbitcoin
Legendary

Offline

Activity: 2646
Merit: 6706

Mixero: Privacy by XMR (Monero) bridge

 February 28, 2021, 09:50:21 AM

Write the rules in Solidity and run them on Ethereum. The gas cost will tell you the complexity.

It would the contract size that defines the complexity.

I think you're referring when smart contract is created. Ethereum also have gas cost when the contract is executed (either when receive transaction or executed by another smart contract).

 █████████████   ██████        █████████████   ██████        █████████████   ██████        █████████████                 █████████████      █████████  █████████████      █████████      █████████      █████████    █████████                   █████████ ████        ██    █████████ ████              █████████ ███████████████████████████████████████▀▀███▀▀  ▀▀▀████████████████▀  █▀    ▄▄▄▄▄▄▄█████████████   ██  ▄█▀▀     ▀▀███████████    █  ███████▄▄▄   ▀███████ ██   █▄████████▄ ▀█▄   ██████  ██   ███████████  ▀█▄ ███████  ▀██▄▄████████ ██   █▄████████     ▀▀▀▀▀▀██  ██   ████████████▄▄▄▄▄▄▄█▀   ▄█   ██████████████▀▀▀▀      ██  ▄█████████████████▄▄▄▄▄████▄████████████████████████████████████████ ● BTC ● ●● ● ● BTCBTC ● ● ●● ● BTC ● ...ADVANCED MIXING METHOD...►  BTC     ►  XMR     ►  BTC ● ● BTC ●BTC ● ● ●● ● ● BTC● BTC ● ● █████████████████████████████████████▀▀██ ▀█████████████████████████  █ █▀▀ ██████████████████████  ▀   ▄█████████████████████▀         ▀██████ ▀█████████▀             ██▀▀█▄  ████████           ▄████▄ ▀██  ███████         ▄██▀ ▄██  ██  ████████      ▄██▀████▀  ██  ███████████▄▄▄████▄    ▄██▀  ████████████████  ▀▀▀██▀▀▀  ▄████████████████████▄▄▄▄▄▄████████████████████████████████████████ ● ● ● BTCBTC ● ● ●● ● BTC ●● BTC ● ● ██████████████████████████         ███████████████████    ██   ███████████████████         ████████████████████████████████  █████████               █████████               █████████  █████████    █████████  █████████  █████████   ██          ████  █████████               ████
oryhp
Jr. Member

Offline

Activity: 54
Merit: 83

 February 28, 2021, 11:27:21 AM

I think you're referring when smart contract is created. Ethereum also have gas cost when the contract is executed (either when receive transaction or executed by another smart contract).

I think this assumes that the gas prices measure complexity, but they likely don't.
tromp (OP)
Legendary

Offline

Activity: 921
Merit: 1024

 February 28, 2021, 12:30:44 PM

I think you're referring when smart contract is created. Ethereum also have gas cost when the contract is executed (either when receive transaction or executed by another smart contract).

I think this assumes that the gas prices measure complexity, but they likely don't.

According to e.g. https://ethereum.stackexchange.com/questions/35539/what-is-the-real-price-of-deploying-a-contract-on-the-mainnet, contract creation gas cost is roughly affine in contract size.
zeuner
Member

Offline

Activity: 185
Merit: 15

 March 01, 2021, 02:19:18 AM

For 2) we could have a program that will interact with the network and a payer to receive 1 coin and see it confirmed.
What if there is a program that can do the operation with less complexity using a SPV-based protocol?

SPV should be excluded, of course. We want the program to fully verify that it has been paid 1 coin,
even in the presence malicious miners with a majority of hashpower, that can make incorrect history
appear to be the most worked on branch.

You will need a formal definition of the payment being verified. It remains to be proven that there is a definition that is both sound and capable of distinguishing an SPV-based verification from a full verification.
 Pages: [1]