path.gno

  1package zkgm
  2
  3import (
  4	"errors"
  5
  6	u256 "gno.land/p/onbloc/math/uint256"
  7)
  8
  9// ErrChannelPathFull is returned by UpdateChannelPath when the path can no
 10// longer hold another hop.
 11var ErrChannelPathFull = errors.New("zkgm: channel path is full")
 12
 13const (
 14	channelIDMask  = uint64(0xFFFFFFFF)
 15	channelSlotBit = uint(32)
 16	maxHopIndex    = 7
 17	// MaxHops is the largest number of channel hops a path can encode.
 18	// Mirrors the maxHopIndex+1 invariant enforced by UpdateChannelPath.
 19	MaxHops = maxHopIndex + 1
 20)
 21
 22func channelIDMaskU256() *u256.Uint { return u256.NewUint(channelIDMask) }
 23
 24// DequeueChannelFromPath pops the lowest 32-bit channel slot off the path and
 25// shifts the remainder right. Returns the truncated path and the popped
 26// channel ID. A channel ID of 0 means the path was empty.
 27//
 28// Based on Union's `dequeue_channel_from_path` path helper.
 29func DequeueChannelFromPath(path *u256.Uint) (*u256.Uint, uint32) {
 30	if path.IsZero() {
 31		return u256.Zero(), 0
 32	}
 33
 34	newPath := u256.Zero().Rsh(path, channelSlotBit)
 35	low := u256.Zero().And(path, channelIDMaskU256())
 36
 37	return newPath, uint32(low.Uint64())
 38}
 39
 40// PopChannelFromPath extracts the highest non-zero 32-bit channel slot from
 41// the path, returning the path with that slot cleared and the popped channel
 42// ID. A channel ID of 0 means the path was empty.
 43//
 44// Based on Union's `pop_channel_from_path` path helper.
 45func PopChannelFromPath(path *u256.Uint) (*u256.Uint, uint32) {
 46	if path.IsZero() {
 47		return u256.Zero(), 0
 48	}
 49
 50	highestIndex := uint(path.BitLen()-1) / channelSlotBit
 51	channelID := GetChannelFromPath(path, int(highestIndex))
 52
 53	slotMask := u256.Zero().Lsh(channelIDMaskU256(), highestIndex*channelSlotBit)
 54	basePath := u256.Zero().AndNot(path, slotMask)
 55
 56	return basePath, channelID
 57}
 58
 59// UpdateChannelPath appends nextChannelID to the path at the next free
 60// 32-bit slot. Returns ErrChannelPathFull when the path can no longer hold
 61// another hop.
 62//
 63// Uses the occupied slot count so full-width 32-bit channel IDs still append
 64// to the immediately next slot instead of skipping an aligned bit boundary.
 65func UpdateChannelPath(path *u256.Uint, nextChannelID uint32) (*u256.Uint, error) {
 66	if path.IsZero() {
 67		return u256.NewUint(uint64(nextChannelID)), nil
 68	}
 69
 70	nextHopIndex := HopCount(path)
 71	if nextHopIndex > maxHopIndex {
 72		return nil, ErrChannelPathFull
 73	}
 74
 75	slot := MakePathFromChannel(nextChannelID, nextHopIndex)
 76
 77	return u256.Zero().Or(slot, path), nil
 78}
 79
 80// GetChannelFromPath returns the channel ID stored at the given 32-bit slot
 81// (0-indexed from the LSB). Returns 0 if the slot is empty or out of range.
 82//
 83// Based on Union's `get_channel_from_path` path helper.
 84func GetChannelFromPath(path *u256.Uint, index int) uint32 {
 85	if index < 0 {
 86		return 0
 87	}
 88
 89	shifted := u256.Zero().Rsh(path, uint(index)*channelSlotBit)
 90	masked := u256.Zero().And(shifted, channelIDMaskU256())
 91
 92	return uint32(masked.Uint64())
 93}
 94
 95// HopCount returns the number of 32-bit channel slots occupied by path.
 96// A nil or zero path has zero hops.
 97func HopCount(path *u256.Uint) int {
 98	if path == nil || path.IsZero() {
 99		return 0
100	}
101
102	return (path.BitLen() + int(channelSlotBit) - 1) / int(channelSlotBit)
103}
104
105// MakePathFromChannel builds a path containing channelID at the given slot.
106//
107// Based on Union's `make_path_from_channel` path helper.
108func MakePathFromChannel(channelID uint32, index int) *u256.Uint {
109	if index < 0 {
110		return u256.Zero()
111	}
112
113	return u256.Zero().Lsh(u256.NewUint(uint64(channelID)), uint(index)*channelSlotBit)
114}
115
116// ReverseChannelPath returns a path with the same channel hops in reversed
117// order. Empty channel slots are skipped. Returns ErrChannelPathFull when the
118// reversed path would overflow.
119//
120// Based on Union's `reverse_channel_path` path helper.
121func ReverseChannelPath(path *u256.Uint) (*u256.Uint, error) {
122	reversed := u256.Zero()
123
124	cur := path
125	for hops := 0; hops < MaxHops; hops++ {
126		tail, head := PopChannelFromPath(cur)
127		if head != 0 {
128			updated, err := UpdateChannelPath(reversed, head)
129			if err != nil {
130				return nil, err
131			}
132
133			reversed = updated
134		}
135
136		if tail.IsZero() {
137			return reversed, nil
138		}
139
140		cur = tail
141	}
142	// A valid uint256 path has at most MaxHops 32-bit slots. Reaching this
143	// branch means the path invariant was violated before the tail was consumed.
144	return nil, ErrChannelPathFull
145}