Bitcoin Forum
August 09, 2022, 10:25:44 AM *
News: Latest Bitcoin Core release: 23.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: compact block relay: why not use Golomb Coded sets for encoding of shortids?  (Read 69 times)
martinus
Newbie
*
Offline Offline

Activity: 12
Merit: 1


View Profile
January 07, 2021, 02:04:29 PM
Merited by ETFbitcoin (1)
 #1

In bip 152 compact block relay is described, which consist of a list of 6-byte shortids: https://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki

In bip 158 Golomb-Coded Sets are described, which sounds to me like the ideal data structure for these IDs. I wonder if it would be beneficial to encode & transmit a golomb-coded sets for the shortids instead of the fixed 6-bytes? It should reduce the size of the transmitted data a bit, at the cost of a bit more processing power.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1660040744
Hero Member
*
Offline Offline

Posts: 1660040744

View Profile Personal Message (Offline)

Ignore
1660040744
Reply with quote  #2

1660040744
Report to moderator
1660040744
Hero Member
*
Offline Offline

Posts: 1660040744

View Profile Personal Message (Offline)

Ignore
1660040744
Reply with quote  #2

1660040744
Report to moderator
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 3696
Merit: 6435



View Profile
January 07, 2021, 02:29:16 PM
Merited by ETFbitcoin (2)
 #2

In bip 152 compact block relay is described, which consist of a list of 6-byte shortids: https://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki

In bip 158 Golomb-Coded Sets are described, which sounds to me like the ideal data structure for these IDs. I wonder if it would be beneficial to encode & transmit a golomb-coded sets for the shortids instead of the fixed 6-bytes? It should reduce the size of the transmitted data a bit, at the cost of a bit more processing power.

The data being sent isn't a set!  The order is needed.  The order could be guessed and a correction to the guess sent, but thats fairly complex.

GCS's savings come mostly from not encoding the permutation of elements. (Some savings comes from non-duplication, but when the 2^keybits is large compared to the number of entries, non-duplication saves very little.)

There are ways to make compact blocks smaller, much smaller in fact--  e.g. I had a prototype implementation that used minisketch which made typical compact blocks about 800 bytes.  But there seems to be littler reason to bother further reducing the size right now.

(This also required the above mentioned guess and correct ordering-- in my case I didn't implement correction and only supported it on blocks where the guess was 100% correct: ones where the miner didn't use prioritization, which is most of them)

Probably more important would be techniques from fibre that let blocks propagate unconditionally without round trips at all even when some txn are missing or some packets are lost.
martinus
Newbie
*
Offline Offline

Activity: 12
Merit: 1


View Profile
January 07, 2021, 05:51:14 PM
 #3

Quote
The data being sent isn't a set!  The order is needed

Ah, of course, I thought I was missing something! Thanks
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!