feat(vsss): wide wire

[cyphersnake]

Wide Labels for VSSS Input Encoding

Prerequisites

• Issue feat(vsss): poly-driven input labels for garble mode #66

Goal

Reduce on-chain data by 8x when posting input labels to Bitcoin.

Current Problem

• Each input bit requires posting 1 label/signature on-chain
• For 1000 input bits: 1000 on-chain signatures
• Bitcoin transaction size becomes prohibitive

Wide Labels Solution

Instead of treating each bit separately, group 8 bits into bytes:

• Generate 256 different labels for each possible byte value (0x00-0xFF)
• When revealing inputs, reveal only the label for the actual byte value
• 8x reduction: 1 label per byte instead of 8 labels per 8 bits

How It Works with VSSS

Current (bit-level):

• Each bit has 2 polynomials (for values 0 and 1)
• Reveal the polynomial evaluation for the actual bit value
• 8 bits = 8 reveals

Wide labels (byte-level):

• Each byte has 256 polynomials (for values 0x00-0xFF)
• Reveal the polynomial evaluation for the actual byte value
• 8 bits = 1 reveal

The Trade-off

Win: 8x less data on Bitcoin blockchain

Cost: 32x more polynomial computations during setup

• Before: 16 polynomials for 8 bits (2 per bit)
• After: 256 polynomials for 8 bits (256 per byte)

Expected Performance Impact:

• Without wide labels: ~12s for full VSSS flow
• With wide labels: ~12min for full VSSS flow
• Full C&C protocol takes ~4h, so +12min is not critical

Integration Challenge

The garbled circuit still needs individual bit wires. So we need:

1. Packing: Convert 8 bit labels → 1 byte label
2. Unpacking: Convert 1 byte label → 8 bit labels for circuit

This unpacking must be deterministic and verifiable.

Why This Matters

For BitVM/Bitcoin integration:

• On-chain cost is high
• Computation is relatively cheap
• 32x more computation for 8x less on-chain data is a good trade

Open Questions

1. How exactly do we pack/unpack labels?
2. Can we use intermediate widths (2-bit, 4-bit) for better trade-offs?
3. How does this affect adaptor signature complexity?

Decision

Only implement if on-chain cost is the primary bottleneck. The 32x computational overhead is significant.

Note

https://hackmd.io/@alpen/B1QfSSO5gg

So far, we have generically discussed input wires and labels without directly examining how they correspond to input data required by the circuit.

We can group multiple input data bits into a bit string for more efficient on-chain operations. For example, let us consider 8-bit strings (bytes). In this model, each wire represents a byte with 256 possible values. Each value is encoded with a label, so there are 256 labels per wire. Each input wire has 256 polynomials that each produce a share from which a label is obtained.

Exactly one signature per input byte is posted on chain. Therefore, the on-chain footprint is reduced by a factor of 8 (8 signatures per byte → 1 signature per byte). The downside is that the total number of labels / shares / polynomials is increased by a factor of 32 (8 labels per byte → 256 labels per byte).

This label construction concerns only the input. The remaining circuit keeps using standard labels. Each input wire that carries a byte value needs to go into a translation gate that maps 8-bit labels into 8 1-bit labels.

This technique generalizes further to longer bit strings, flexibly decreasing on-chain size.

[cyphersnake]

I don't yet understand, apart from simply modifying GarbleMode to encode the input differently, what parts of the overall design will be affected.