Bitcoin Forum
May 20, 2022, 11:52:14 AM *
News: Latest Bitcoin Core release: 23.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Defining algorithmic complexity of a blockchain protocol  (Read 157 times)
tromp
Hero Member
*****
Offline Offline

Activity: 785
Merit: 663


View Profile
February 21, 2021, 10:25:00 AM
Merited by ETFbitcoin (1), zeuner (1)
 #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
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1653047534
Hero Member
*
Offline Offline

Posts: 1653047534

View Profile Personal Message (Offline)

Ignore
1653047534
Reply with quote  #2

1653047534
Report to moderator
1653047534
Hero Member
*
Offline Offline

Posts: 1653047534

View Profile Personal Message (Offline)

Ignore
1653047534
Reply with quote  #2

1653047534
Report to moderator
odolvlobo
Legendary
*
Offline Offline

Activity: 3584
Merit: 2402



View Profile
February 22, 2021, 10:28:51 PM
 #2

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.

Buy stuff on Amazon with BTC or convert Amazon points to BTC here: Purse.io
Join an anti-signature campaign: Click ignore on the members of signature campaigns.
PGP Fingerprint: 6B6BC26599EC24EF7E29A405EAF050539D0B2925 Signing address: 13GAVJo8YaAuenj6keiEykwxWUZ7jMoSLt
NotATether
Legendary
*
Online Online

Activity: 882
Merit: 2900


Resist all tyrants!


View Profile WWW
February 23, 2021, 04:21:54 AM
 #3

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.

zeuner
Member
**
Offline Offline

Activity: 134
Merit: 11


View Profile
February 26, 2021, 10:24:39 PM
 #4

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 Offline

Activity: 1400
Merit: 1074

Always remember the cause!


View Profile WWW
February 26, 2021, 11:10:01 PM
 #5

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
Hero Member
*****
Offline Offline

Activity: 785
Merit: 663


View Profile
February 27, 2021, 08:03:25 AM
 #6

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
Hero Member
*****
Offline Offline

Activity: 785
Merit: 663


View Profile
February 27, 2021, 08:06:59 AM
 #7

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 Offline

Activity: 1400
Merit: 1074

Always remember the cause!


View Profile WWW
February 27, 2021, 12:52:50 PM
 #8

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.

It was not how I read your op, but OK.

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 Offline

Activity: 3584
Merit: 2402



View Profile
February 27, 2021, 09:49:15 PM
Merited by ETFbitcoin (1)
 #9

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.

Buy stuff on Amazon with BTC or convert Amazon points to BTC here: Purse.io
Join an anti-signature campaign: Click ignore on the members of signature campaigns.
PGP Fingerprint: 6B6BC26599EC24EF7E29A405EAF050539D0B2925 Signing address: 13GAVJo8YaAuenj6keiEykwxWUZ7jMoSLt
tromp
Hero Member
*****
Offline Offline

Activity: 785
Merit: 663


View Profile
February 28, 2021, 07:18:31 AM
 #10

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 Offline

Activity: 2240
Merit: 4341


NotYourKeys.org - Not Your Keys, Not Your Bitcoin


View Profile
February 28, 2021, 09:50:21 AM
 #11

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).

oryhp
Jr. Member
*
Offline Offline

Activity: 34
Merit: 57


View Profile
February 28, 2021, 11:27:21 AM
 #12

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
Hero Member
*****
Offline Offline

Activity: 785
Merit: 663


View Profile
February 28, 2021, 12:30:44 PM
 #13

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 Offline

Activity: 134
Merit: 11


View Profile
March 01, 2021, 02:19:18 AM
 #14

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]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!