Bitcoin Forum
March 19, 2024, 08:37:21 AM *
News: Latest Bitcoin Core release: 26.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Non-Interactive Proofs of Proofs of Work  (Read 114 times)
thefreshprinceofbell (OP)
Newbie
*
Offline Offline

Activity: 20
Merit: 2


View Profile
February 03, 2021, 10:57:49 PM
Merited by ABCbits (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.
1710837441
Hero Member
*
Offline Offline

Posts: 1710837441

View Profile Personal Message (Offline)

Ignore
1710837441
Reply with quote  #2

1710837441
Report to moderator
1710837441
Hero Member
*
Offline Offline

Posts: 1710837441

View Profile Personal Message (Offline)

Ignore
1710837441
Reply with quote  #2

1710837441
Report to moderator
The trust scores you see are subjective; they will change depending on who you have in your trust list.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1710837441
Hero Member
*
Offline Offline

Posts: 1710837441

View Profile Personal Message (Offline)

Ignore
1710837441
Reply with quote  #2

1710837441
Report to moderator
NotATether
Legendary
*
Offline Offline

Activity: 1540
Merit: 6495


bitcoincleanup.com / bitmixlist.org


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.

  BTC
.
BTC
.
 BTC
.
BTC
..JAMBLER.io..
██
██
██
██
██
██
██

██

██

██

██
YOUR OPPORTUNITY TO
HAVE BITCOIN BUSINESS

██
██
██
██
██
██
██

██

██

██

██
.
  BTC
. BTC
.
.
 
BTC
  BTC
tromp
Legendary
*
Online Online

Activity: 967
Merit: 1075


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
Legendary
*
Offline Offline

Activity: 1540
Merit: 6495


bitcoincleanup.com / bitmixlist.org


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.

  BTC
.
BTC
.
 BTC
.
BTC
..JAMBLER.io..
██
██
██
██
██
██
██

██

██

██

██
YOUR OPPORTUNITY TO
HAVE BITCOIN BUSINESS

██
██
██
██
██
██
██

██

██

██

██
.
  BTC
. BTC
.
.
 
BTC
  BTC
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!