Bitcoin Forum
October 16, 2021, 03:22:48 AM *
News: Latest Bitcoin Core release: 22.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Non-Interactive Proofs of Proofs of Work  (Read 89 times)
thefreshprinceofbell
Newbie
*
Offline Offline

Activity: 19
Merit: 2


View Profile
February 03, 2021, 10:57:49 PM
Merited by ETFbitcoin (1)
 #1

I just read up about Non-Interactive Proofs of Proofs of Work from this white paper: https://eprint.iacr.org/2019/226.pdf .

Just wondering what the current thoughts them is and if they are likely to be implemented into Bitcoin at any point in the future.
1634354568
Hero Member
*
Offline Offline

Posts: 1634354568

View Profile Personal Message (Offline)

Ignore
1634354568
Reply with quote  #2

1634354568
Report to moderator
1634354568
Hero Member
*
Offline Offline

Posts: 1634354568

View Profile Personal Message (Offline)

Ignore
1634354568
Reply with quote  #2

1634354568
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1634354568
Hero Member
*
Offline Offline

Posts: 1634354568

View Profile Personal Message (Offline)

Ignore
1634354568
Reply with quote  #2

1634354568
Report to moderator
NotATether
Hero Member
*****
Offline Offline

Activity: 672
Merit: 2132


Cryptographic Crawler


View Profile WWW
February 04, 2021, 04:57:50 AM
 #2

I see one big problem with implementing this super-light client verifier and it's that since this algorithm only requires O(log(n)) block headers to be downloaded (to the base e I assume) applying it to Bitcoin's block height of around 650K will result in FlyClient retrieving only 13 or 14 blocks. It's far too little to assume the validity of a chain with them, especially if the blocks are spaced in equal intervals. There's going to be just one block header downloaded for every 50,000 blocks.

tromp
Hero Member
*****
Offline Offline

Activity: 756
Merit: 619


View Profile
February 04, 2021, 08:08:29 AM
 #3

only requires O(log(n)) block headers
only 13 or 14 blocks.

O(log n) can be anything of the form a + b * log n.
In the case of flyclient a could be over 1000, and b over 10.
It also requires a bitcoin header to commit to a merkle tree of all previous headers,
and perhaps the cumulative difficulty.
NotATether
Hero Member
*****
Offline Offline

Activity: 672
Merit: 2132


Cryptographic Crawler


View Profile WWW
February 04, 2021, 10:02:58 AM
 #4

only requires O(log(n)) block headers
only 13 or 14 blocks.

O(log n) can be anything of the form a + b * log n.
In the case of flyclient a could be over 1000, and b over 10.
It also requires a bitcoin header to commit to a merkle tree of all previous headers,
and perhaps the cumulative difficulty.

This makes me feel relieved, as I had applied the run-time function literally.

Still there's another hurdle, maybe even two, to overcome. It uses a probability distribution with the difficulty as input and returns the chance that it's block will be used in the proof. First off the difficulty of bitcoin mining is ever-increasing and this distribution takes difficulties on a scale from 0 to 1. It means every time the mining difficulty breaks a high, each and every full node has to compute the new difficulty "percentage" (a terrible name but let's just call it that) for all of the blocks, and I imagine this is not going to take as much time as transaction verification but you are still processing 650K+ blocks so... that's going to take a few hours on average.

If the difficulty breaks a new high during that period this reassignment has to be aborted and it has to start all over again.

The second hurdle is choosing a probability distribution for choosing the blocks. Even if there are no major hot spots in the blockchain that may need more verification (because of user-developer drama so theoretically are the first targets by rouges) such as the blocks around the segwit and taproot activation blocks, as I mentioned above the difficulty is ever changing so choosing a new probability distribution that mostly corresponds to the blocks it previously selected will be challenging because you keep having to compute it again.

This also assumes that there's a 1-to-1 mapping between the difficulties and blocks, which shouldn't be a problem except maybe for the earliest blocks with near-zero difficulty.

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!